c++ - 在保留原始顺序的同时删除/删除多个 std::vector 元素的最有效方法？

Question

我有一个 std::vector<int>和第二个容器保存迭代器或索引(没有键，我想要不断访问元素)到这个 vector 用于删除目的。假设我有一个包含 1000 个元素的 vector ，并且想要删除其中的 200 个。在删除操作之后，未删除元素的顺序应该和之前一样。

在我的问题的第一个版本中我错过了另一件事:值是唯一的。它们是身份。

您将如何以安全(关于 STL 规则)和有效的方式( vector 的决定应为最终决定)来做到这一点？

可能性或方法我想过:

• erase-remove idiom(http://en.wikipedia.org/wiki/Erase-remove_idiom):最初用于删除满足条件的元素(包括线性搜索)，但我考虑大小为 1 的范围，此方法可用于已经给定的迭代器和虚拟条件。 问题:是否保留了元素的原始顺序，是否比上一种方法更高效？
• 使用 vector.erase(vector.begin()+index+offset) 遍历索引并删除元素同时将删除的索引保留在容器中以计算偏移量。可以使用 std::lower_bound 为每次删除迭代确定此偏移量。 n 已移除元素的容器。 问题:由于随机位置删除，大量二进制搜索用于获取偏移量和大量移动操作。
• 目前我正在执行以下操作:获取要删除的元素的所有迭代器。根据 vector 中的位置以降序对它们进行排序，并循环它们以使用 vector.erase 进行最终删除.现在我没有使任何迭代器失效，并且除了删除本身之外没有 vector 重新排列操作。 问题:很多排序

那么，你将如何解决这个问题？有什么新想法吗？有什么建议吗？

感谢您的意见。

萨沙

编辑/更新/自己的结果:我实现了erase-remove idiom，这也是KennyTM提到的，带有一个谓词基于在一个 boost::dynamic_bitset 并且它非常快。此外，我尝试了 PigBen 的移动和截断方法(Steve Jessop 也提到过)，它也在其 while 循环中访问位集。对于我的数据，两者似乎都同样快。我尝试删除 1000 个元素中的 100 个(无符号整数)，这 100 个删除了 1M 次，没有显着差异。因为我认为基于 STL 的删除删除习语有点“自然”，所以我选择了这种方法(KennyTM 也提到了这个论点)。

Answer 1

在 <algorithm>有一个 remove_if function它将所有未删除的值挤压到前面以保持顺序。如果这 200 个元素可以完全由值而不是索引确定，则此方法有效。

这本质上是您链接到的删除删除习语。 remove_if保证执行 O(N) 比较(最多 O(N) 次复制)，这将比排序 (O(N log N)) 更有效，尽管如果索引是，您的最后一个选项实际上不需要排序根据值确定(复印时只需反向扫描)。

尽管如此，使用 remove_if (如果可以的话)比其他 2 个选项更好，因为已经为您编写了实现，因此逻辑错误的可能性较小并且传达了更好的 what(而不是 how ) 去做。