C++ STL容器中erase的使用-蒲公英云

C++ STL容器中erase的使用

erase()函数的功能是用来删除容器中的元素

函数原型:
iterator erase(iterator where);
iterator erase(iterator first,iterator last);
basic_string& erase(size_type p0=0,size_type n=np);

删除某个容器里的某个元素：c.erase(T);
看似一个简单的动作，然而对不同类型的容器，内部却做了截然不同的事情，后面介绍。

假设有这样一个题目，将某个容器中所有满足条件N == X的元素删除，按照常规的思路应该有类似这样的代码：

// 假设Container和container分别表示一种容器和对应的一个对象
Container::iterator it;
for (it = container.begin(); it != container.end(); ++it) {
if (N == X)
container.erase(it);
}

然而这样的代码对于任一种容器都是错误的
容器按内存分配方式可以分为链表容器和数组容器。
所谓的链表容器指的是一种表现方式，包括list、slist等这样基于节点的容器（动态分配内存块）和set、map、multiset、multimap等关联容器（平衡树实现），而数组容器指的是在一块连续的内存上保存元素的连续内存容器，比如vector、deque、string等。

OK，现在说说erase对他们的操作，链表容器以list为例，当执行container.erase(it)时，确实第一个满足条件的元素删除了，但这时it指针已经被删除了，它也不指向任何元素了，所以也只能到此为止了，也就是说上面的代码对于链表容器来说只能正确删除第一个满足条件的元素，针对这个问题我们首先想到的就是在删除指针之前，给其做个备份，很好，不错的主意，我们一般采用的方法是建立个临时变量，这个临时变量可以在程序循环中适当的位置使用，看下列代码实现，是将这个临时变量直接建立在erase实现里，这样做更简洁，也显得专业些（以删除int型链表中所有偶数为例，也是大家都喜欢的一个例子）：

list::iterator it;
for (it = lt.begin(); it != lt.end(); ) {
if (*it % 2 == 0)
lt.erase(it++);
else
++it;
}

链表容器使用erase删除节点还有一个特点，就是会将下一个元素的地址返回，所以也可以这样实现：

list::iterator it;
for (it = lt.begin(); it != lt.end(); ) {
if (*it % 2 == 0)
it = lt.erase(it);
else
++it;
}

当然用list容器本身提供的算法也是个不错的主意（挂回调）：

bool evenNumber(int n)
{
return (n % 2 == 0);
}

lt.remove_if(evenNumber);

数组容器以vector为例，当执行container.erase(it)时，和上面提到的一样，第一个满足条件的元素删除了，但这时数组容器不允许中间有“空隙”，所以会做个大动作，就是将被删元素后面所有的元素前移（参考STL源码），而数组容器记录的是下标，所以删除元素后，当前下标定位的元素也就顺理成章的变成了原有队列中的下一个元素，同样以删除偶数为例，代码如下：

vector::iterator it = v.begin();
for (it = v.begin(); it != v.end(); ) {
if (*it % 2 == 0)
v.erase(it);
else
++it;
}

也可以使用reverse_iterator迭代器，并且在某些删除操作中会有更好的效率（因为它会使上面提到的“大动作”变小一些）：

vector::reverse_iterator ri = v.rbegin();
for ( ; ri != v.rend(); ) {
if (*ri % 2 == 0)
v.erase((++ri).base());
else
++ri;
}