删除/删除多个的std ::向量元素，同时保留原有订单的最有效的方法是什么？ [英] Most efficient way of erasing/deleting multiple std::vector elements while retaining original order?

问题描述

我有一个的std ::矢量＆lt; INT＆GT; 和第二容器保持迭代器或索引（无钥匙，我要不断的访问元素）这个载体为删除的目的。 让我们假设我有1000个元素的向量和要删除​​其中的200。非移除元素的顺序应该是删除操作后的同一像以前一样。

i have a std::vector<int> and a second container holding iterators or indexes (no keys, i want constant access to the element) to this vector for deletion purposes. Let's assume i have a vector of 1000 elements and want to erase 200 of them. The order of the non-removed elements should be the same after the deletion operations like before.

还有一件事我错过了我的问题的第一个版本：在值是唯一的。他们的身份。

One more thing i missed in the first version of my question: the values are unique. They are identities.

你会怎么做，在一个安全的（关于STL规则）和有效的方式（为载体的决定是最终决定）？的

可能性或方法我想到了：

• 在擦除remove惯用法（http://en.wikipedia.org/wiki/Erase-remove_idiom）：最初是为删除其满足条件（包括线性搜索）的元素，但我认为大小为1这种方法的范围，可以用来与已给定的迭代器和一个虚拟的状态。 问：是保持元素的原始顺序，它比过去的方法更好的性能
？
• 遍历所有的指标和擦除配合使用 vector.erase的元素（vector.begin（）+指数+偏移量），同时保持在一个容器中删除索引用于计算偏移。该偏移可确定为每删除重复的使用了的std :: LOWER_BOUND n个已经删除的元素容器。 的问题：很多binary_searches的获取偏移和很多因为随机位置缺失移动操作中
• 在那一刻我做了以下内容：获得所有的迭代器的元素删除。他们根据载体和循环在他们的最后删除的位置与 vector.erase 降序排列。现在我没有任何无效迭代器，也没有矢量重新排列，操作除删除自身。 的问题：大量的排序

• the erase-remove idiom (http://en.wikipedia.org/wiki/Erase-remove_idiom): originally for the deletion of elements which fulfill a condition (including linear search) but i think with ranges of size 1 this method could be used to with already given iterators and a dummy condition. Question: is the original order of elements kept and is it more performant than the last method?
• loop over the indexes and erase the elements with the use of vector.erase(vector.begin()+index+offset) while keeping the indexes removed in a container for calculating the offset. This offset could be determined for every remove iteration with the use of a std::lower_bound n the container of already removed elements. The problem: A lot of binary_searches for getting the offset and a lot of move operations because of random-location-deletion.
• At the moment I'm doing the following: get all the iterators for the elements to remove. Sort them in descending order according to the location in the vector and loop over them for the final deletion with vector.erase. Now I'm not invalidating any iterator and there are no vector rearrange-operations except for the deletion itself. The problem: a lot of sorting

那么，你会如何解决呢？任何新的想法？任何建议？

So, how would you tackle this? Any new ideas? Any recommendations?

感谢您的输入。

萨沙

修改/更新/自己的结果：我实现了擦除remove惯用法，这也是由KennyTM提到，有一个 predicate根据在升压查找::来，dynamic_bitset ，它的出奇的快。此外，我试过 PigBen的举动 - 和 - 截断法（也由史蒂夫·杰索普提到），这也是访问位集合在它的while循环。这两个似乎是同样快跟我类型的数据。我想1000元（无符号整数）的删除100，这样做100删除100万次，也没有显著差异。因为我觉得STL-基于擦除remove惯用法是有点更自然，我选择这种方法（参数也是由KennyTM提到的）。

Edit / Update / Own results: I implemented the erase-remove idiom, which was also mentioned by KennyTM, with a predicate based on the lookup in a boost::dynamic_bitset and it's insanely fast. Furthermore i tried PigBen's move-and-truncate method (also mentioned by Steve Jessop) which is also accessing the bitset in it's while-loop. Both seem to be equally fast with my kind of data. I tried to delete 100 of 1000 Elements (unsigned ints), did this 100 deletes 1M times and there was no significant difference. Because i think the stl-based erase-remove idiom is kinda more "natural, i'm choosing this method (argument was also mentioned by KennyTM).

推荐答案

在＆LT;算法＆GT; 有一个的 的remove_if 函数其中挤压所有值不拆下来的前维护命令。这工作，如果这些元素200可以通过数值是纯粹的决定，而不是指数。

In <algorithm> there is a remove_if function which squeezes all values not removed to the front maintaining the order. This works if those 200 elements can be purely determined by the values, not index.

这基本上是你连接到擦除remove惯用法。 的remove_if 是保证执行O（N）的比较（至多O（N）copyings），这将是更有效率比排序（O（N日志N）），虽然你最后的选择实际上并不需要，如果指数从值来确定排序（只是在扭转方向的扫描复制时）。

This is essentially the Erase-remove idiom you have linked to. remove_if is guaranteed to perform O(N) comparisons (and at most O(N) copyings), which would be more efficient than sorting (O(N log N)), although your last option doesn't actually require sorting if the indices are determined from values (just scan in the reversed direction while copying).

然而，使用的remove_if （如果你能）比其他2个选择，因为实施已为你写好好，所以有逻辑错误的机会少，传达更好的什么的（不是的如何的）做。

Nevertheless, using remove_if (if you can) is better than the other 2 options because the implementation has already been written for you, so there's less chance of logical error and conveys better what (not how) to do.

这篇关于删除/删除多个的std ::向量元素，同时保留原有订单的最有效的方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！