C++ 从 std::vector 中擦除多个对象？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3487717/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Erasing multiple objects from a std::vector?
提问by jmasterx
Here is my issue, lets say I have a std::vector with ints in it.
这是我的问题，假设我有一个带有整数的 std::vector 。
let's say it has 50,90,40,90,80,60,80.
假设它有 50,90,40,90,80,60,80。
I know I need to remove the second, fifth and third elements. I don't necessarily always know the order of elements to remove, nor how many. The issue is by erasing an element, this changes the index of the other elements. Therefore, how could I erase these and compensate for the index change. (sorting then linearly erasing with an offset is not an option)
我知道我需要删除第二个、第五个和第三个元素。我不一定总是知道要删除的元素的顺序，也不知道有多少。问题是通过擦除一个元素，这会改变其他元素的索引。因此，我如何擦除这些并补偿索引更改。（排序然后用偏移量线性擦除不是一种选择）
Thanks
谢谢
回答by Peter G.
I am offering several methods:
我提供了几种方法：
1. A fast method that does not retain the original order of the elements:
1.一种不保留元素原始顺序的快速方法：
Assign the current last element of the vector to the element to erase, then erase the last element. This will avoid big moves and all indexes except the last will remain constant. If you start erasing from the back, all precomputed indexes will be correct.
将向量的当前最后一个元素分配给要擦除的元素，然后擦除最后一个元素。这将避免大的变动，除最后一个以外的所有索引都将保持不变。如果从后面开始擦除，则所有预先计算的索引都是正确的。
void quickDelete( int idx )
{
vec[idx] = vec.back();
vec.pop_back();
}
I see this essentially is a hand-coded version of the erase-remove idiom pointed out by Klaim ...
我认为这本质上是 Klaim 指出的擦除-删除习语的手工编码版本......
2. A slower method that retains the original order of the elements:
2. 保留元素原始顺序的较慢方法：
Step 1: Mark all vector elements to be deleted, i.e. with a special value. This has O(|indexes to delete|).
步骤1：标记所有要删除的向量元素，即用一个特殊值。这有 O(|要删除的索引|)。
Step 2: Erase all marked elements using v.erase( remove (v.begin(), v.end(), special_value), v.end() );. This has O(|vector v|).
第 2 步：使用 擦除所有标记的元素v.erase( remove (v.begin(), v.end(), special_value), v.end() );。这有 O(|vector v|)。
The total run time is thus O(|vector v|), assuming the index list is shorter than the vector.
总运行时间因此是 O(|vector v|)，假设索引列表比向量短。
3. Another slower method that retains the original order of the elements:
3.另一种保留元素原始顺序的较慢方法：
Use a predicate and remove if as described in https://stackoverflow.com/a/3487742/280314. To make this efficient and respecting the requirement of not "sorting then linearly erasing with an offset", my idea is to implement the predicate using a hash table and adjust the indexes stored in the hash table as the deletion proceeds on returning true, as Klaim suggested.
如https://stackoverflow.com/a/3487742/280314 中所述，使用谓词并删除 if 。为了提高效率并尊重不“排序然后用偏移量线性擦除”的要求，我的想法是使用哈希表来实现谓词，并在删除返回真值时调整存储在哈希表中的索引，正如 Klaim建议。
回答by Klaim
Using a predicate and the algorithm remove_if you can achieve what you want : see http://www.cplusplus.com/reference/algorithm/remove_if/
使用谓词和算法 remove_if 你可以实现你想要的：见http://www.cplusplus.com/reference/algorithm/remove_if/
Don't forget to erase the item (see remove-erase idiom).
不要忘记擦除该项目（请参阅remove-erase idiom）。
Your predicate will simply hold the idx of each value to remove and decrease all indexes it keeps each time it returns true.
您的谓词将简单地保存每个值的 idx 以删除和减少它每次返回 true 时保留的所有索引。
That said if you can afford just removing each object using the remove-erase idiom, just make your life simple by doing it.
也就是说，如果您能负担得起使用 remove-erase 习惯用法删除每个对象，那么只需通过这样做让您的生活变得简单。
回答by Mark B
Erase the items backwards. In other words erase the highest index first, then next highest etc. You won't invalidate any previous iterators or indexes so you can just use the obvious approach of multiple erase calls.
向后擦除项目。换句话说，首先擦除最高的索引，然后是次高的等等。您不会使任何先前的迭代器或索引无效，因此您可以使用多次擦除调用的明显方法。
回答by Andreas Brinck
I would move the elements which you don'twant to erase to a temporary vector and then replace the original vector with this.
我会提出你的元素并不想删除的临时载体，然后用此代替原来的载体。
回答by Niki
Would this work:
这是否有效：
void DeleteAll(vector<int>& data, const vector<int>& deleteIndices)
{
vector<bool> markedElements(data.size(), false);
vector<int> tempBuffer;
tempBuffer.reserve(data.size()-deleteIndices.size());
for (vector<int>::const_iterator itDel = deleteIndices.begin(); itDel != deleteIndices.end(); itDel++)
markedElements[*itDel] = true;
for (size_t i=0; i<data.size(); i++)
{
if (!markedElements[i])
tempBuffer.push_back(data[i]);
}
data = tempBuffer;
}
It's an O(n) operation, no matter how many elements you delete. You could gain some efficiency by reordering the vector inline (but I think this way it's more readable).
无论您删除多少个元素，它都是 O(n) 操作。您可以通过重新排列内联向量来提高效率（但我认为这种方式更具可读性）。
