我需要从向量中删除满足特定条件的所有元素。
我的第一种方法是循环遍历向量并对满足条件的所有元素调用 vector::erase 。
据我所理解，vector::erase对于这个用例来说，性能很差，因为它从底层数组中删除了该项目，并将向量的其余部分向前移动一个元素（如果删除一系列元素，则移动更多元素）。
当您移除多个元素时，后面的元素将在每次移除时移动。
The remove算法获取所有要删除的元素，并将它们移动到向量的末尾，因此您只需删除向量的后部部分，这不涉及移位。
但为什么这比擦除更快呢？（是不是更快了？）
将元素移动到末尾并不意味着将所有以下元素向前移动，如vector::erase?
为什么删除的复杂度只有 O(n)？
这里的性能问题不是擦除要删除的元素，或者将它们移动到末尾（这实际上不会发生），而是关于移动要保留的元素.
如果你使用erase在要删除的每个元素上，您需要移动这些元素之后的所有元素...对于每次调用erase。通常，如果您想删除k元素，您将移动最新元素之后的元素（在向量中）k多次而不是一次。
但如果你打电话remove，您只能移动这些一次（参见下面的示例）。
一个小例子可以更好地理解这两种方法的工作原理：
假设您有一个大小为 1000 的向量，并且要删除的元素位于位置 17 和 37。
With erase作用于要删除的两个元素：
- 你打电话时
erase()对于第 17 个元素，您需要将元素 18 移动到 999、982 个元素。
- 你打电话时
erase()对于第 36 个元素（现在是第 36 个！），您需要将元素 37 移动到 998、962 个元素。
总共，您移动了 962 + 982 = 1944 个元素，其中 962 个元素被无故移动了两次。
With 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 个，则效果更好。
你可以看看可能的实施 http://en.cppreference.com/w/cpp/algorithm/remove访问 en.cppreference.com 以更好地了解如何std::remove works.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
