c – 擦除删除习语的性能增益来自何处

发布时间：2020-12-16 10:14:15 所属栏目：百科来源：网络整理

导读：我需要从满足某个标准的向量中擦除所有元素. 我的第一种方法是遍历向量并在符合条件的所有元素上调用vector :: erase. 据我所知,vector :: erase对于这个用例有一个糟糕的性能,因为它从底层数组中删除了项目,并将向量的其余部分向前移动了一个元素(如果删除

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

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

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

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

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

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

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

解决方法

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

如果对要删除的每个元素使用擦除,则需要在这些元素之后移动所有元素…对于每个要擦除的调用.通常,如果要删除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.

擦除作用于要移除的两个元素：

>当你为第17个元素调用erase()时,你需要移动元素18到999,982个元素.
>当你为第36个元素调用erase()时(现在是第36个元素！),你需要将元素37移动到998,962个元素.

总的来说,你已经移动了962 982 = 1944个元素,其中962个被移动了两次,没有任何东西.

删除后,会发生以下情况：

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的工作原理.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!