从std :: vector删除多个对象? [英] Erasing multiple objects from a std::vector?

问题描述

这是我的问题，可以说我有一个带有int的std :: vector.

Here is my issue, lets say I have a std::vector with ints in it.

假设它有50,90,40,90,80,60,80.

let's say it has 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)

谢谢

推荐答案

我提供了几种方法:

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();
}

我看到这实质上是Klaim指出的擦除-删除"惯用语的手工编码版本...

I see this essentially is a hand-coded version of the erase-remove idiom pointed out by Klaim ...

2.保留元素原始顺序的较慢方法:

步骤1:标记所有要删除的向量元素，即使用特殊值.它具有O(|要删除的索引|).

Step 1: Mark all vector elements to be deleted, i.e. with a special value. This has O(|indexes to delete|).

第2步:使用 v.erase(删除(v.begin()，v.end()，special_value)，v.end())擦除所有标记的元素..它具有O(| vector v |).

Step 2: Erase all marked elements using v.erase( remove (v.begin(), v.end(), special_value), v.end() );. This has O(|vector v|).

因此，假设索引列表短于向量，则总运行时间为O(| vector v |).

The total run time is thus O(|vector v|), assuming the index list is shorter than the vector.

3.保留元素原始顺序的另一种较慢的方法:

使用谓词并删除 https://stackoverflow.com/a/3487742/280314 中所述的谓词.为了提高效率并遵守以下要求不是排序然后使用偏移量线性擦除"，我的想法是使用哈希表实现谓词，并在删除返回"true"时调整哈希表中存储的索引，如Klaim建议的那样.

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.

这篇关于从std :: vector删除多个对象?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！