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

Question

我有一个std::vector<int>和第二个容器持有迭代器或索引(没有键,我希望不断访问元素)到这个向量用于删除目的.让我们假设我有一个1000个元素的向量,并想要删除其中的200个元素.在删除操作之后,未删除元素的顺序应该与之前相同.

我在问题的第一个版本中错过了另一件事:价值观是独一无二的.他们是身份.

你如何在安全(关于stl规则)和有效方式(传统的决定是最终的)中做到这一点？

我想到的可能性或方法:

• 所述擦除remove惯用法(http://en.wikipedia.org/wiki/Erase-remove_idiom):最初为其中满足条件(包括直链的搜索)的元素的删除,但我认为有尺寸1这种方法可能是范围习惯于已经给定的迭代器和虚拟条件.问题:保留的元素的原始顺序是否比最后一种方法更高效？
• 循环遍历索引并使用vector.erase(vector.begin()+index+offset)同时删除元素,同时保持在容器中删除索引以计算偏移量.可以使用std::lower_bound已经移除的元素的容器来确定每次移除迭代的该偏移.问题:由于随机位置删除,很多binary_searches用于获取偏移量和大量移动操作.
• 目前我正在做以下事情:获取要删除的元素的所有迭代器.根据向量中的位置按降序对它们进行排序,并在它们上面循环以进行最终删除vector.erase.现在我没有使任何迭代器失效,除了删除本身之外没有向量重新排列操作.问题:很多排序

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

感谢您的输入.

萨沙

编辑/更新/拥有结果:我实现了擦除 - 删除习惯用法,这也是KennyTM提到的,带有一个基于boost :: dynamic_bitset中的查找的谓词,并且它的速度非常快.此外,我尝试了PigBen的move-and-truncate方法(也由Steve Jessop提到),它也在它的while循环中访问bitset.对我的数据来说,两者似乎同样快.我试图删除100个1000个元素(无符号整数)中的100个,这100个删除了1M次并且没有显着差异.因为我认为基于stl的擦除删除成语更"天生",我选择了这种方法(KennyTM也提到了参数).

Answer 1

在<algorithm>有一个remove_if功能,它将所有未被删除的值压缩到维持订单的前面.如果这200个元素可以纯粹由值而不是索引确定,则此方法有效.

这基本上就是你链接到的Erase-remove习惯用法.remove_if保证执行O(N)比较(并且最多是O(N)复制),这比排序(O(N log N))更有效,尽管如果索引是最后一个选项实际上不需要排序根据值确定(只需在复制时按相反方向扫描).

然而,使用remove_if(如果可以的话)比其他2个选项更好,因为已经为您编写了实现,因此逻辑错误的可能性更小,并且更好地传达了(不是如何)执行的操作.

Answer 2

如何循环遍历向量,并且对于需要删除的每个元素,将不需要删除的下一个元素复制到该位置.然后,当你到达最后,截断它.

int last = 0;
for(int i=0; i<vec.size(); ++i, ++last)
{
   while(needs_to_be_removed(i))
      ++i;
   if(i >= vec.size()) break;

   vec[last] = vec[i];   
}

vec.resize(last);