c++ - 获取随机元素并将其删除

Question

问题:我需要为一个容器获取一个随机元素，并将其从该容器中删除。容器不需要分类。 我不关心顺序。

• Vector 可以在 O(1) 中获取随机元素，但仅在 O(N) 中删除它
• List删除元素O(1)但只能随机取元素O(N)

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

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

我很好奇是否存在按索引或按值在 O(1) 或 O(logN) 中随机访问和删除元素的数据结构？

Answer 1

您有解决方案，而且看起来非常好。用 C++ 编写它的惯用方法不是创建另一个类(请 don't inherit from std::vector )，而是编写一个函数:

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

用法:

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

事实上，如果在移动操作期间抛出异常，您不希望 vector 处于无效状态。