获取随机元素并将其删除

问题：我需要获取容器的随机元素并将其从该容器中删除。容器不需要排序。我不在乎订单。

• 向量可以得到我的随机元素O(1)但仅删除它O(N)
• 列表删除元素O(1)但只能获取随机元素O(N)

所以我想出了一个想法，制作一个自定义向量，允许您通过索引删除任何元素O(1)+复杂。 这个想法是交换最后一个元素和要删除的元素，然后pop_back()。 如果您需要删除最后一个元素 - 只需pop_back()。 向量的顺序不会相同，但您可以获得快速删除方法。

据我了解，与我的解决方案相比，双端队列的索引访问速度更慢，删除复杂度更差，但我不能 100% 确定。

我很好奇是否存在具有随机访问和元素删除功能的数据结构O(1) or O(logN)按索引还是按值 mb ？

您已经找到了解决方案，而且看起来非常好。用 C++ 编写它的惯用方法不是创建另一个类（并且please 不继承自std::vector https://stackoverflow.com/questions/6806173/why-should-not-i-subclass-inherit-standard-containers），但只是写一个函数：

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

这提供了与以下相同的异常保证std::swap<T>.

现在，如果您想返回该对象，并且您可以访问 C++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;
}

事实上，如果在移动操作期间引发异常，您不希望向量处于无效状态。