Get a random item and delete it

Question

Problem: I need to get a random item for a container, and also remove it from this container. The container does not need to be sorted. I do not care about the order.

• A vector can get a random element in O(1), but delete it only inO(N)
• The list removes the item in O(1), but can only get a random item inO(N)

So, I came up with the idea of ​​creating a custom vector that will allow you to remove any element by its index using complexity O(1)+. The idea is to swap the last item and the item you want to delete, then pop_back(). If you need to remove the last item - simply pop_back(). The order of the vector will not be the same, but you get a quick delete method.

As I can understand, deque has slower index access and worse delete complexity, then my solution, but I'm not 100% sure.

I am curious if there are data structures that have random access and deletion of elements in O(1)either O(logN)index or mb by value?

Answer 1

You have a solution and it looks great. The idiomatic way to write it in C ++ is not to create another class (and please do not inherit fromstd::vector ), but simply 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();
}

Using:

remove_at(v, 42);

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

, , ++ 11, . :

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;
}

, , , .

Answer 2

O (n)

vec.erase(vec.begin() + randomIdx); randomIdx 0 vec.size() - 1

O (1), , , , . ( )

Answer 3

, , .

node . , O (log N) n- .

Removing the nth element is also equal to O (log N), since you need to go back to the tree to fix all the counts. Any rebalancing will be equal to O (log N).

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

It would be nice if the standard library “discovered” the use of trees used for std :: set and std :: map as an open interface for use in custom trees.