c++ - 保持具有频繁插入和删除的小对象的无序列表

Question

假设我有一个小对象列表，我通过频繁的插入和删除来迭代（例如，在循环中）。但是，我遍历列表的顺序并不重要。我没有使用 std::list 来存储元素，而是考虑以下列方式使用 std::vector （用于恒定时间删除）：

插入：使用 push_back 在数组末尾插入。

删除：假设我想从大小为 n 的向量中删除位置 k 处的元素。然后，我将第 n 个（或 (n-1)st，取决于您如何看待）元素的内容复制到第 k 个元素并使用 pop_back。鉴于元素很小，复制操作不应该是昂贵的。

这是为了利用连续内存，而不必为每次插入动态分配内存。这种方法有缺点吗？我还注意到 C++11 有 unordered_set，但我认为这对于我正在尝试做的事情来说可能是矫枉过正。

如果这个想法听起来很明显，我深表歉意。

Answer 1

您的想法是保持阵列高效的基本方法。如果订单对您来说真的不重要，我认为这是理想的方法。您可能希望将它封装在一个类中（一个包装器std::vector），这样您就可以在多个地方使用它而无需重复代码，单独测试它并且通常遵循“单一责任”原则。

如果您可以访问 C++11 功能，您甚至不必复制第 n 个元素 - 您可以移动它，即使对于较重的对象也可以这样做。

Answer 2

鉴于您的要求相当宽松，我看不出这种方法有什么缺点。

另一个要考虑的选择是，如果您的项目交换比复制便宜，您可以将最后一个项目与要删除的项目交换，然后将您现在交换的项目从末尾弹出。

它确实听起来unordered_set对您的需求来说太重了，因为它有恒定的时间find，您不需要满足您的需求。