erase-remove 习语的性能增益来自哪里
Where is the performance gain of the erase-remove idiom coming from
我需要从满足特定条件的向量中删除所有元素。
我的第一个方法是遍历向量并在所有满足条件的元素上调用 vector::erase。
据我了解，vector::erase 在此用例中的性能很差，因为它从底层数组中删除了项目，并将向量的其余部分向前移动一个元素（如果您删除了一系列元素）。
当您移除多个元素时，后面的元素将在每次移除时移动。
remove算法将所有要删除的元素移到向量的末尾，因此您只需删除向量的后部，不涉及移位。
但为什么这比擦除更快？（甚至更快吗？）
是否将一个元素移动到末尾意味着像 vector::erase 那样向前移动所有后续元素？
怎么会，那个remove的复杂度只有O(n)？
优点在于 std::remove 不只是一次删除一个元素。例如，如果调用 std::remove 导致删除向量的前 10 个元素，它将第 11 个元素直接移动到第 1 个位置，第 12 个元素直接移动到第 2 个位置等......然而，如果你一次擦除前 10 个元素，它会将你擦除的元素后移 1。然后你将擦除下一个元素，每个元素都必须再次移动。对于每个被擦除的元素，这都会重复。
此外，删除的元素不必按顺序排列即可实现此优势。例如，如果对 remove 的调用导致从第一个开始的所有其他元素被删除。首先，第二个元素将移动到第一个位置，这将留下两个元素的间隙，直到下一个可保留元素。然后第4个元素会直接移动到第2个位置，空出3个元素以此类推
另外，稍作更正：
The remove algorithm takes all the elements to be removed, and moves them to the end of the vector
删除算法不会那样做。它不关心要删除的元素会发生什么。它们只是被要保留的元素所取代。未指定调用 remove 后末尾元素的值。您描述的算法是分区（具有反向比较功能）。
这里的性能问题不是关于擦除要删除的元素，或者将它们移动到末尾（实际上并没有发生），而是关于移动要保留的元素.
如果您在每个要删除的元素上使用 erase，则需要移动这些元素之后的所有元素...每次调用 erase。通常，如果你想删除 k 个元素，你将在最后一个元素（在向量中）之后移动元素 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个元素调用
erase()时（现在是第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 上的 possible implementation 以更好地了解 std::remove 的工作原理。
我需要从满足特定条件的向量中删除所有元素。
我的第一个方法是遍历向量并在所有满足条件的元素上调用 vector::erase。
据我了解，vector::erase 在此用例中的性能很差，因为它从底层数组中删除了项目，并将向量的其余部分向前移动一个元素（如果您删除了一系列元素）。
当您移除多个元素时，后面的元素将在每次移除时移动。
remove算法将所有要删除的元素移到向量的末尾，因此您只需删除向量的后部，不涉及移位。
但为什么这比擦除更快？（甚至更快吗？）
是否将一个元素移动到末尾意味着像 vector::erase 那样向前移动所有后续元素？
怎么会，那个remove的复杂度只有O(n)？
优点在于 std::remove 不只是一次删除一个元素。例如，如果调用 std::remove 导致删除向量的前 10 个元素，它将第 11 个元素直接移动到第 1 个位置，第 12 个元素直接移动到第 2 个位置等......然而，如果你一次擦除前 10 个元素，它会将你擦除的元素后移 1。然后你将擦除下一个元素，每个元素都必须再次移动。对于每个被擦除的元素，这都会重复。
此外，删除的元素不必按顺序排列即可实现此优势。例如，如果对 remove 的调用导致从第一个开始的所有其他元素被删除。首先，第二个元素将移动到第一个位置，这将留下两个元素的间隙，直到下一个可保留元素。然后第4个元素会直接移动到第2个位置，空出3个元素以此类推
另外，稍作更正：
The remove algorithm takes all the elements to be removed, and moves them to the end of the vector
删除算法不会那样做。它不关心要删除的元素会发生什么。它们只是被要保留的元素所取代。未指定调用 remove 后末尾元素的值。您描述的算法是分区（具有反向比较功能）。
这里的性能问题不是关于擦除要删除的元素，或者将它们移动到末尾（实际上并没有发生），而是关于移动要保留的元素.
如果您在每个要删除的元素上使用 erase，则需要移动这些元素之后的所有元素...每次调用 erase。通常，如果你想删除 k 个元素，你将在最后一个元素（在向量中）之后移动元素 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个元素调用
erase()时（现在是第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 上的 possible implementation 以更好地了解 std::remove 的工作原理。