1

我有一个向量 V，我想存储这个向量的哪些元素我以后必须删除。

为此，我使用了另一个向量 Y 来存储要删除的 V 元素的迭代器。所以我遍历 Y 以访问我需要在 V 中删除的元素的迭代器。

问题是当你从 V 中删除元素时，Y 中的所有迭代器（指向 V 的元素）都变得无效。

我找不到任何答案，但它似乎如此微不足道，必须有一个简单的解决方法，不是吗？

4

4 回答 4

5

利用V.erase(std::remove_if(V.begin(), V.end(), MyPredicate()), V.end())

于 2013-07-03T12:16:02.803 回答
3

您可以使用std::vector<unsigned> indices来存储每个元素的索引值。

于 2013-07-03T12:16:40.843 回答
2

指向位置（或第一个）及之后的迭代器、指针和引用无效，所有迭​​代器、指针和对位置（或第一个）之前元素的引用都保证继续引用它们在调用之前引用的相同元素。

http://www.cplusplus.com/reference/vector/vector/erase/

因此，如果 Y 的元素（迭代器）已排序，您可以向后迭代 Y 并删除 V 中的相应元素。这是有效的，因为当您擦除 V 中的元素时，只有 V 中后面元素的迭代器才会失效。

于 2013-07-03T12:18:24.507 回答
0

这是关于复杂性的。

您可以将元素从较高的索引擦除到较低的索引，在这种情况下，您的方法将起作用，但是每次您擦除向量的元素时，它后面的元素都会被重新定位。这在被擦除元素之后的元素数量中具有线性复杂性，因此我期望某种二次复杂性，或O(number_of_elements * number_of_elements_to_be_erased).

如果删除的数量很高，并且要擦除的元素的索引在整个范围内或多或少均匀分布，则从复杂性的角度来看，更好的解决方案是处理“要擦除的元素”的补码。相反，它将是“要保留的元素”，您可以将应该保留的元素复制到新数组并将其分配给旧数组。这与向量中的元素数量呈线性O(number_of_elements)关系， 。

更好的是，如果您可以完全控制实现并且可以将 std::vector 更改为 std::list，那么您可以完全按照您的描述继续进行其余操作，而不会产生不良副作用。在这种情况下，擦除也是高效的，在恒定时间内完成，所以整个操作是O(number_of_elements_to_be_erased).

于 2013-07-03T12:34:25.317 回答