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

Question

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

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

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

谢谢

Answer 1

我提供了几种方法:

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

将 vector 的当前最后一个元素赋值给要删除的元素，然后删除最后一个元素。这将避免大 Action ，并且除最后一个之外的所有索引都将保持不变。如果从后面开始删除，所有预计算的索引都是正确的。

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

我认为这基本上是 Klaim 指出的删除删除成语的手工编码版本......

<强>2。保留元素原始顺序的较慢方法:

第 1 步:标记所有要删除的 vector 元素，即使用特殊值。这有 O(|要删除的索引|)。

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

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

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

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