remove_if and then erase 在向量上是否有效？

Question

虽然有几十个关于remove_if + erase for vector的问题。我找不到这种动作的表现。当我写：

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

remove if 将 return 迭代器指向最后一个相关项 + 1（我们称之为 X）。我相信这会在 O(n) 中发生。

但是擦除将如何工作？

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

谢谢。

Answer 1

vector::erase的复杂度是well-defined:

Linear: the number of calls to the destructor of T is the same as the number of elements erased, the assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements

它在内部的工作方式（即它究竟如何删除你的元素）有点无关紧要。

remove_if 的复杂度也是 defined 并且是

Exactly std::distance(first, last) applications of the predicate.

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

Answer 2

为什么不使用 swap 'n pop 方法？我们通过优化向量中的擦除进行了很多愚弄，发现这是最快的，因为它具有 O(1) 复杂性。唯一的缺点是它不保持秩序。很多情况下都很好。这是此类操作的模板方法：

template<typename T>
inline typename std::vector<T>::iterator unorderedErase(std::vector<T>& p_container,
                                                        typename std::vector<T>::iterator p_it)
{
    if (p_it != p_container.end() - 1)
    {
        std::swap(*p_it, p_container.back());
        p_container.pop_back();
        return p_it;
    }
    // else
    p_container.pop_back();
    return p_container.end();
}

Answer 3

考虑这个向量：

|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 遍历向量，直到找到谓词 return 为真的元素：

|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 的谓词（再次为假），然后进行另一个赋值：

|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:

的 "output" 位置

|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 是 past-the-end 所以我们 return X（指向输出序列的 past-the-end，即我们要保留的元素）。

在 remove_if returns 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 因为最后两个元素使用的内存仍然存在，但未被使用。

remove_if and then erase 在向量上是否有效？

Is remove_if and then erase efficient on vector?

c++

performance

vector

std

erase