从 std::vector 中删除多个对象？

Question

这是我的问题，假设我有一个带有整数的 std::vector。

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

我知道我需要删除第二个、第五个和第三个元素。我不一定总是知道要删除的元素的顺序，也不知道有多少。问题是通过擦除一个元素，这会改变其他元素的索引。因此，我怎样才能擦除这些并补偿索引变化。 （排序然后用偏移量线性擦除不是一种选择）

谢谢

原文由 jmasterx 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

我提供了几种方法：

1.一种不保留元素原有顺序的快速方法：

将向量的当前最后一个元素分配给要擦除的元素，然后擦除最后一个元素。这将避免大动作，并且除最后一个之外的所有索引都将保持不变。如果从后面开始擦除，所有预先计算的索引都是正确的。

 void quickDelete( int idx )
{
  vec[idx] = vec.back();
  vec.pop_back();
}

我看到这基本上是克莱姆指出的擦除删除成语的手工编码版本……

2.保持元素原始顺序的较慢方法：

步骤1：标记所有要删除的向量元素，即用一个特殊的值。这有 O(|要删除的索引|)。

第 2 步：使用 v.erase( remove (v.begin(), v.end(), special_value), v.end() ); 擦除所有标记的元素。这有 O(|vector v|)。

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

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

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

原文由 Peter G. 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

如果您想保留索引，这是一个优雅的解决方案，其想法是将您要删除的值替换为保证不会在任何地方使用的特殊值，然后在最后执行擦除本身：

 std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};

// marking 3 elements to be deleted
vec[2] = std::numeric_limits<int>::lowest();
vec[5] = std::numeric_limits<int>::lowest();
vec[3] = std::numeric_limits<int>::lowest();

// erase
vec.erase(std::remove(vec.begin(), vec.end(), std::numeric_limits<int>::lowest()), vec.end());

// print values => 1 2 5 7 8 9
for (const auto& value : vec) std::cout << ' ' << value;
std::cout << std::endl;

如果您删除很多元素，它会非常快，因为删除本身只发生一次。项目也可以以任何顺序删除。

如果您使用 aa 结构而不是 int，那么您仍然可以标记该结构的元素，例如 dead=true 然后使用 remove_if 而不是 remove >

 struct MyObj
{
    int  x;
    bool dead = false;
};

std::vector<MyObj> objs = {{1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}};
objs[2].dead = true;
objs[5].dead = true;
objs[3].dead = true;
objs.erase(std::remove_if(objs.begin(), objs.end(), [](const MyObj& obj) { return obj.dead; }), objs.end());

// print values => 1 2 5 7 8 9
for (const auto& obj : objs) std::cout << ' ' << obj.x;
std::cout << std::endl;

这个有点慢，大约是 remove 速度的 80%。

原文由 Octo Poulos 发布，翻译遵循 CC BY-SA 4.0 许可协议