Get random element and remove it

Question

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 ?

Answer 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.