c++ - erase-remove 习语的性能增益来自哪里

Question

我需要从满足特定条件的 vector 中删除所有元素。

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

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

remove 算法获取所有要删除的元素，并将它们移动到 vector 的末尾，因此您只需删除 vector 的后部，这不涉及移位。

但为什么这比删除更快？(甚至更快吗？)

将元素移动到末尾是否意味着像 vector::erase 中那样向前移动所有后续元素？

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

Answer 1

这里的性能问题不是关于删除要删除的元素，或者将它们移动到末尾(实际上并没有发生)，而是关于移动要保留的元素 .

如果您对要删除的每个元素使用erase，则需要移动这些元素之后的所有元素...对于每次调用erase。通常，如果您要删除 k 元素，您会将这些元素移动到最后一个元素之后(在 vector 中)k 次，而不是只移动一次。

但是如果你调用remove，你只会移动一次(见下面的例子)。

一个小例子可以更好地理解这两种方法的工作原理:

Let's say you have a vector of size 1000 and the elements you want to remove are at position 17 and 37.

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

• 当您为第 17 个元素调用 erase() 时，您需要将第 18 个元素移动到第 999 个，即第 982 个元素。
• 当您为第 36 个元素(现在是第 36 个!)调用 erase() 时，您需要将第 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 个，这会更好。

你可以看看possible implementation在 en.cppreference.com 上更好地理解 std::remove 的工作原理。