Get random element and remove it

问题:

Problem: I need to get a random element for a container and also delete it from that container. Container does not need to be sorted. I dont care about the order.

• Vector can get me random element in O(1) but delete it only in O(N)
• List deletes element in O(1) but can only get random element in O(N)

So I came up with an idea of making a custom vector that allow you to remove any element by its index with O(1)+ complexity. The idea is to swap the last element and an element you want to remove and then pop_back(). If you need to remove the last elemtent - just pop_back(). The order of the vector will not be the same but you get a fast remove method.

As i can understand deque have slower access by index and worse removal complexity then my solution but im not 100% sure.

I'm curious are there data structures that have random access and element removal in O(1) or O(logN) by index or mb by value ?

回答1:

You have the solution, and it seems perfectly fine. The idiomatic way to write it in C++ is not to create another class (and please don't inherit from std::vector), but just to write a function:

template <typename T>
void remove_at(std::vector<T>& v, typename std::vector<T>::size_type n)
{
    std::swap(v[n], v.back());
    v.pop_back();
}

Usage:

remove_at(v, 42);

This offers the same exception guarantee as std::swap<T>.

Now if you want to return the object, and you have access to a C++11 compiler, you can do it the following way. The difficult part is to provide the basic exception guarantee in all cases:

template <typename T>
T remove_at(std::vector<T>&v, typename std::vector<T>::size_type n)
{
    T ans = std::move_if_noexcept(v[n]);
    v[n] = std::move_if_noexcept(v.back());
    v.pop_back();
    return ans;
}

Indeed, you don't want the vector to be left in an invalid state if an exception is thrown during a move operation.

回答2:

With O(n) complexity

vec.erase(vec.begin() + randomIdx); randomIdx would be between 0 and vec.size()-1

If you want O(1) complexity you could either use the list container for example or swap the element with the last one and delete this instead. ( As mentioned by the others )

回答3:

Yes, there is a solution, a well-balanced binary tree.

One each node you would need to store the number of nodes on each side. From this it is O(log N) to find the nth element.

Removing the nth element is also O(log N) as you have to traverse back up to tree to correct all the counts. Any rebalancing would be O(log N) too at most.

A tree is considered well balanced if no leaf node is 2 nodes deeper than another. Look up AVL trees to get a rabalancing algorithm.

It would actually be good if the standard library "opened" the use of the trees used for std::set and std::map as a public interface for use in custom trees.