C++ Idioms: Erase-Remove

STL标准库中remove算法是比较容易被人误用的算法。std::remove的行为并不像的它名字的字面意思一样,删除容器中的某些元素,而是将容器中不被删除的元素依次向前移动。或许只有中国的程序员会对这个算法有误解,毕竟英语中remove还有”移动”的含义,只是中文经常翻译成删除。

C++11中std::remove等价于如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class ForwardIterator, class T>
ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val)
{
ForwardIterator result = first;
while (first!=last) {
if (!(*first == val)) {
*result = move(*first);
++result;
}
++first;
}
return result;
}

Erase-Remove惯用法是在《Effective STL》中提出的, 书中第32条款对remove的工作原理和设计初衷解释的很清楚。remove被设计用来操作不同的容器,并不知道如何具体删除容器的一个元素,如果要真的删除某些元素,需要和erase一起用。

Erase-Remove的基本形式:

1
2
3
4
std::vector<int> v;
// fill it up somehow
v.erase(std::remove(v.begin(), v.end(), 99), v.end());
// really remove all elements with value 99