获取随机元素并将其删除

Question

问题:我需要为容器获取一个随机元素,并将其从该容器中删除.容器不需要排序.我不在乎订单.

• 矢量可以让我随机元素,O(1)但只删除它O(N)
• List删除元素O(1)但只能获取随机元素O(N)

所以我提出了一个创建自定义向量的想法,允许您通过O(1)+复杂的索引删除任何元素.我们的想法是交换最后一个元素和你想要删除的元素pop_back().如果你需要删除最后一个元素 - 只是pop_back().向量的顺序不一样,但是你得到一个快速删除方法.

我可以理解deque的索引访问速度较慢,删除复杂性较差,然后我的解决方案,但我不是100%肯定.

我很好奇有没有随机访问和元素删除的数据结构O(1)或O(logN)索引或mb值？

Answer 1

你有解决方案,看起来很好.在C++中编写它的惯用方法不是创建另一个类(并且请 不要继承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;
}

实际上,如果在移动操作期间抛出异常,则不希望向量处于无效状态.