4

我需要从满足特定标准的向量中删除所有元素。

我的第一种方法是遍历向量并在所有满足条件的元素上调用 vector::erase。

据我了解，vector::erase此用例的性能很差，因为它会从底层数组中删除该项目，并将向量的其余部分向前移动一个元素（如果删除一系列元素，则向前移动更多）。当您删除多个元素时，后面的元素将在每次删除时移动。

该remove算法将所有要删除的元素移到向量的末尾，因此您只需删除向量的后部，这不涉及移位。

但是为什么这比擦除更快呢？（是不是更快？）

将一个元素移动到最后是否意味着将所有以下元素向前移动vector::erase？

怎么会，那个 remove 的复杂度只有 O(n)？

4

2 回答 2

10

这里的性能问题不是关于删除要删除的元素，或者将它们移动到最后（这实际上不会发生），而是关于移动要保留的元素。

如果您erase在要删除的每个元素上使用，则需要在这些元素之后移动所有元素...对于每次调用erase. 通常，如果要删除k元素，您将在最近一次（在向量中）之后移动元素，k而不是仅移动一次。

但是如果你打电话remove，你只会移动一次（见下面的例子）。

一个小例子可以更好地理解这两种方法是如何工作的：

假设您有一个大小为 1000 的向量，并且您要删除的元素位于位置 17 和 37。

作用于erase要删除的两个元素：

  • 当您调用erase()第 17 个元素时，您需要将第 18 个元素移动到 999、982 个元素。
  • 当您调用erase()第 36 个元素时（现在是第 36 个！），您需要将元素 37 移动到 998、962 个元素。

总共移动了 962 + 982 = 1944 个元素，其中 962 个元素被移动了两次。

随着remove，发生的情况如下：

element 0 does not change;
element 1 does not change;
...
element 17 is "discarded";
element 18 is moved at position 17;
element 19 is moved at position 18;
...
element 36 is moved at position 35;
element 37 is "discarded";
element 38 is moved at position 36;
...
element 999 is moved at position 997.

您总共移动了 998 个元素（1000 减去您删除的两个元素），这比之前方法的 1943 个元素要好得多。如果您有超过 2 个要删除的元素，这会更好。

您可以在 en.cppreference.com 上查看可能的实现，以更好地了解其std::remove工作原理。

于 2017-08-07T16:28:39.710 回答
4

优点在于std::remove一次不只是删除一个元素。例如，如果调用std::remove导致删除向量的前 10 个元素，它会将第 11 个元素直接移动到第 1 个位置，第 12 个元素直接移动到第 2 个位置等......然而，如果你删除了前 10 个元素一次一个，它会将您擦除的元素之后的每个元素移回 1。然后您将擦除下一个元素，每个元素都必须再次移动。对于每个被删除的元素，这将重复。

此外，删除的元素不必是连续的，这种优势就会发生。例如，如果调用 remove 导致从第一个开始的所有其他元素都被删除。首先，第二个元素将被移动到第一个位置，这将留下两个元素的间隙，直到下一个可保留元素。然后第4个元素将直接移动到第2个位置，留下3个元素的间隙，依此类推。

另外，稍微修正一下：

移除算法将所有要移除的元素，并将它们移动到向量的末尾

删除算法不这样做。它不关心要删除的元素会发生什么。它们只是被要保留的元素替换。在调用 remove 之后，最后元素的值是未指定的。您描述的算法是分区（具有反向比较功能）。

于 2017-08-07T16:10:01.450 回答