擦除删除成语的性能增益来自何处

Question

我需要从满足某个标准的向量中擦除所有元素.

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

据我所知,vector::erase这个用例的性能不好,因为它从底层数组中删除了项目,并将向量的其余部分向前移动了一个元素(如果擦除了一系列元素,则移动更多).当您移除多个元素时,后部元素将在每次移除时移动.

该remove算法将所有元素移除,并将它们移动到向量的末尾,因此您只需要移除向量的后部,这不涉及移位.

但为什么这比擦除更快？(它更快吗？)

不将元素移动到最后是否意味着将所有后续元素向前移动vector::erase？

怎么来,删除只有O(n)的复杂性？

Answer 1

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

如果你使用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工作原理.