remove_if然后在向量上擦除效率？

Question

虽然有关于vector的remove_if + erase有几十个问题.我找不到这种行为的表现.我写的时候:

    myVector.erase(remove_if(myVector.begin(),
                         myVector.end(),
                         some_predicate), myVector.end());

remove if会将迭代器返回到最后一个相关项+ 1(让我们称之为X).我相信这会发生在O(n)中.

但擦除将如何工作？

• 如果擦除将尝试从X删除到myVector.end(),它将是O(n ^ 2),因为它将导致将向量复制到新位置,并且将有来自堆的O(n)个新分配.
• 但如果它将从myVector.end()删除到X,它可以在O(n)中执行,更重要的是不会分配新的内存(我试图避免的事情).

谢谢.

Answer 1

考虑这个向量:

|0|1|2|3|4|5|6|7|8|9|

我们使用remove_if删除所有4的倍数的元素:

std::remove_if(v.begin(), v.end(), [](auto i){ return i != 0 && !(i%4); });

这开始使用迭代器X迭代向量,直到找到谓词返回true的元素:

|0|1|2|3|4|5|6|7|8|9|
         X

这是我们要删除的第一个元素.

接下来,它创建另一个指向下一个元素的迭代器,Y = X + 1,并检查谓词*Y:

|0|1|2|3|4|5|6|7|8|9|
         X Y

谓词是假的,所以我们想要保留该元素,因此它通过执行*X = std::move(*Y)以下操作将下一个元素分配给我们要删除的元素:

|0|1|2|3|5|5|6|7|8|9|
         X Y            *X = std::move(*Y)

所以我们有两个迭代器,X和Y,其中X指向"output"中的下一个元素(即我们没有删除的元素),Y是下一个要考虑删除的元素.

我们将两个迭代器移动到下一个位置,检查Y的谓词(再次为false),然后执行另一个赋值:

|0|1|2|3|5|6|6|7|8|9|
           X Y          *X = std::move(*Y)

然后它在下一个位置再次执行相同的操作:

|0|1|2|3|5|6|7|7|8|9|
             X Y       *X = std::move(*Y)

然后它继续前进,但发现Y的谓词是正确的

|0|1|2|3|5|6|7|7|8|9|
               X Y

所以它只增加Y,跳过该元素,因此不会将其复制到X的"输出"位置:

|0|1|2|3|5|6|7|7|8|9|
               X   Y 

Y的谓词不正确,所以它将它赋给X:

|0|1|2|3|5|6|7|9|8|9|
               X   Y     *X = std::move(*Y)

然后它再次增加X和Y.

|0|1|2|3|5|6|7|9|8|9|
                 X   Y

现在Y是过去的结果,所以我们返回X(它指向输出序列的末尾,即我们想要保留的元素).

在remove_if我们调用返回X 之后v.erase(X, v.end()),向量调用从X到结尾的每个元素的析构函数:

|0|1|2|3|5|6|7|9|~|~|
                 X   end

然后设置大小,使向量在X结束:

|0|1|2|3|5|6|7|9|
                 end

在此之后,v.capacity() >= v.size()+2因为两个最终元素使用的内存仍然存在,但未使用.

Answer 2

在复杂vector::erase是明确的:

线性:对T的析构函数的调用数与擦除的元素数相同,T的赋值运算符被称为等于擦除元素后向量中元素数的次数

它内部工作的方式(即如何删除你的元素)是无关紧要的.

复杂性remove_if也被定义并且是

完全是std :: distance(first,last)谓词的应用程序.

所以你的代码具有线性复杂性.