c++ 中的 remove-erase 俗语

Erase–remove_idiom 和 Scott Mayer 的 effective stl 都提到过这个俗语。

类似下面的代码，删除所有偶数。

// remove_erase.cpp
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char *argv[])
{
    vector<int> avec={1,2,3,4,6,7,8};
    avec.erase(remove_if(avec.begin(), avec.end(), [](int a) { return a %2 == 0; }), avec.end());

    for(auto i : avec){
        cout << "i= " << i << endl;
    }
    return 0;
}

我们深入研究一下，remove 之后，vector 里面变成了什么。

// remove_erase_2.cpp
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char *argv[])
{
    vector<int> avec={1,2,3,4,6,7,8};
    auto it = remove_if(avec.begin(), avec.end(), [](int a) { return a %2 == 0; });
    cout << "before erase " << endl;
    for(auto i : avec){
        cout << "i= " << i << endl;
    }

    avec.erase(it, avec.end());

    cout << "after erase " << endl;
    for(auto i : avec){
        cout << "i= " << i << endl;
    }
    return 0;
}

before erase
i= 1
i= 3
i= 7
i= 4
i= 6
i= 7
i= 8
after erase
i= 1
i= 3
i= 7

可以看到， remove 重新排列了 vector 中的元素。

但是后面的元素有些奇怪，2 不见了，出现两个 7 。无论如何，根据手册，后面的元素已经是无效了。我们只是好奇，后面的元素是什么。

我们看看 remove 的实现，gcc 中的 stl 的实现。

template <class _ForwardIterator, class _Predicate>
_ForwardIterator
remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
{
    __first = std::__1::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type>
                           (__first, __last, __pred);
    if (__first != __last)
    {
        _ForwardIterator __i = __first;
        while (++__i != __last)
        {
            if (!__pred(*__i))
            {
                *__first = std::__1::move(*__i);
                ++__first;
            }
        }
    }
    return __first;
}

可以看到，标准库里面用 std::move 函数重新排列了顺序。

这里可以看到，代码移动了 3 和 7 元素，但是不保证 2 元素继续有效，因为他的位置已经无效了，在移动过程中，2 把位置让给了 3 。3 的位置让给了 7。

我们验证一下移动的次数。

// remove_erase_3.cpp
#include <iostream>
using namespace std;
#include <vector>

class Foo {
  public:
    Foo(int v): value(v) {
        cout <<  __FILE__ << ":" << __LINE__ << ": [" << __FUNCTION__<< "] "
             << "v "  << v << " "
             << endl;
    }
    Foo(const Foo& other): value(other.value) {
        cout <<  __FILE__ << ":" << __LINE__ << ": [" << __FUNCTION__<< "] "
             << "other.value "  << other.value << " "
             << "value "  << value << " "
             << endl;
    }
    Foo& operator =(Foo&& other) {
        cout <<  __FILE__ << ":" << __LINE__ << ": [" << __FUNCTION__<< "] "
             << "other.value "  << other.value << " "
             << "value "  << value << " "
             << endl;
        value = other.value;
        other.value = 0;
        return *this;
    }
    ~Foo() {
            cout <<  __FILE__ << ":" << __LINE__ << ": [" << __FUNCTION__<< "] "
                 << "value "  << value << " "
                 << endl;
    }
  public:
    int value;
};

using namespace std;
int main(int argc, char *argv[])
{
    vector<Foo> avec={1,2,3,4,6,7,8};
    auto it = remove_if(avec.begin(), avec.end(), [](Foo& a) { return a.value %2 == 0; });
    cout << "before erase " << endl;
    for(auto i : avec){
        cout << "i= " << i.value << endl;
    }

    avec.erase(it, avec.end());

    cout << "after erase " << endl;
    for(auto i : avec){
        cout << "i= " << i.value << endl;
    }
    return 0;
}

我们观察一下输出

remove_erase_3.cpp:9: [Foo] v 1 
remove_erase_3.cpp:9: [Foo] v 2 
remove_erase_3.cpp:9: [Foo] v 3 
remove_erase_3.cpp:9: [Foo] v 4 
remove_erase_3.cpp:9: [Foo] v 6 
remove_erase_3.cpp:9: [Foo] v 7 
remove_erase_3.cpp:9: [Foo] v 8 
remove_erase_3.cpp:14: [Foo] other.value 1 value 1 
remove_erase_3.cpp:14: [Foo] other.value 2 value 2 
remove_erase_3.cpp:14: [Foo] other.value 3 value 3 
remove_erase_3.cpp:14: [Foo] other.value 4 value 4 
remove_erase_3.cpp:14: [Foo] other.value 6 value 6 
remove_erase_3.cpp:14: [Foo] other.value 7 value 7 
remove_erase_3.cpp:14: [Foo] other.value 8 value 8 
remove_erase_3.cpp:29: [~Foo] value 8 
remove_erase_3.cpp:29: [~Foo] value 7 
remove_erase_3.cpp:29: [~Foo] value 6 
remove_erase_3.cpp:29: [~Foo] value 4 
remove_erase_3.cpp:29: [~Foo] value 3 
remove_erase_3.cpp:29: [~Foo] value 2 
remove_erase_3.cpp:29: [~Foo] value 1 
remove_erase_3.cpp:20: [operator=] other.value 3 value 2 
remove_erase_3.cpp:20: [operator=] other.value 7 value 0 
before erase 
remove_erase_3.cpp:14: [Foo] other.value 1 value 1 
i= 1
remove_erase_3.cpp:29: [~Foo] value 1 
remove_erase_3.cpp:14: [Foo] other.value 3 value 3 
i= 3
remove_erase_3.cpp:29: [~Foo] value 3 
remove_erase_3.cpp:14: [Foo] other.value 7 value 7 
i= 7
remove_erase_3.cpp:29: [~Foo] value 7 
remove_erase_3.cpp:14: [Foo] other.value 4 value 4 
i= 4
remove_erase_3.cpp:29: [~Foo] value 4 
remove_erase_3.cpp:14: [Foo] other.value 6 value 6 
i= 6
remove_erase_3.cpp:29: [~Foo] value 6 
remove_erase_3.cpp:14: [Foo] other.value 0 value 0 
i= 0
remove_erase_3.cpp:29: [~Foo] value 0 
remove_erase_3.cpp:14: [Foo] other.value 8 value 8 
i= 8
remove_erase_3.cpp:29: [~Foo] value 8 
remove_erase_3.cpp:29: [~Foo] value 8 
remove_erase_3.cpp:29: [~Foo] value 0 
remove_erase_3.cpp:29: [~Foo] value 6 
remove_erase_3.cpp:29: [~Foo] value 4 
after erase 
remove_erase_3.cpp:14: [Foo] other.value 1 value 1 
i= 1
remove_erase_3.cpp:29: [~Foo] value 1 
remove_erase_3.cpp:14: [Foo] other.value 3 value 3 
i= 3
remove_erase_3.cpp:29: [~Foo] value 3 
remove_erase_3.cpp:14: [Foo] other.value 7 value 7 
i= 7
remove_erase_3.cpp:29: [~Foo] value 7 
remove_erase_3.cpp:29: [~Foo] value 7 
remove_erase_3.cpp:29: [~Foo] value 3 
remove_erase_3.cpp:29: [~Foo] value 1

我试着解释一下输出结果。

{1,2,3...} 调用 Foo(int) 构造了 7 个 Foo 对象
vector 通过 Foo(const Foo& x) ，把 initialize_list 中的对象拷贝到 vector 中。
原来的 7 initialize_list 中的对象被析构掉了。
remove 移动对象，调用了 operator=(Foo&&) ，后面具体解释。
在打印过程中，因为 for(auto i: 中，没有使用 auto& ，于是拷贝构造了临时对象 1, 3, 7, 4, 6, 0, 8 ，然后打印，然后析构这些临时对象
调用 vector.erase 的时候，会调用 ~Foo 析构掉 8,0,6,4 。可以看到，vector 是倒着析构这些对象的。不过这个无关紧要，标准没有强调析构顺序。
然后类似步骤 5 打印过程中，构造，析构临时对象。 1,3,7
main 函数结束，析构 vector 对象，vector 对象倒着析构了 7,3,1 三个对象。

上面的代码，第4步中，在移动的过程中，打印调试信息，显式 2 的位置让给了 3 。然后 3 的位置设置为无效值 value = 0 。 3 位置上已经是带有了无效值，这个位置让给了 7 ，同时 7 的位置被设置成为了无效值。

Wang Chunye

c++ 中的 remove-erase 俗语