STL中的容器主要分两类，一是顺序存储的，如vector；一是以红黑树形式存储的，如map。下面分别以vector和map为例，说明怎样利用迭代器在遍历的同时删除容器内元素。
下面示例程序首先往容器中添加一定元素，然后循环删除其中连续或不连续的元素。程序在VS2003以及g++3.4下调试，不同编译器下可能结果不同。
// vector sample for Windows and Linux
int main()
{
vector<int> vec;
vector<int>::iterator iter;
vec.reserve(10);
for ( int i = 0; i < 10; i++ )
{
vec.push_back( i );
}
// delete the elements from 3 to 5 and 9.
for ( iter = vec.begin(); iter != vec.end(); )
{
cout << "Position " << *iter << ": ";
if ( *iter == 3 )
{
vec.erase( iter ); cout << *iter;
}
else if ( *iter == 4 )
{
vec.erase( iter ); cout << *iter;
}
else if ( *iter == 5 )
{
vec.erase( iter ); cout << *iter;
}
else if ( *iter == 9 )
{
vec.erase( iter ); cout << *iter;
}
else
{
cout << *iter;
++iter;
}
cout << endl;
}
cout << "The left elements:" << endl;
for ( iter = vec.begin(); iter != vec.end(); ++iter )
{
cout << *iter << " ";
}
cout << endl;
return 0;
}
如果上面程序中要在for循环中使用++iter的话，就需要在删除元素后做一次--iter操作，但这样的效率显然没有上面代码效率高。注意到vector的erase方法在执行后，当前迭代器自动指向了下一个元素位置，这也是为什么不要在删除元素后再++iter的原因。至于为啥当前迭代器会自动指向下一个位置呢，看gcc下vector的源码就知道了：
iterator erase(iterator position)
{
if (position + 1 != end())
copy(position + 1, finish, position); // 后续元素往前移动
--finish;
destroy(finish); // 一个释放资源的全局函数
return position;
}
从上面代码可以看出，vector中删除一个元素后，此位置以后的元素都需要往前移动一个位置，虽然当前迭代器位置没有自动加1，但是由于后续元素的顺次前移，也就相当于迭代器的自动指向下一个位置一样。
// map sample for Windows
int main()
{
map<int,int> tree;
map<int,int>::iterator iter;
for ( int i = 9; i > 0; i-- )
{
tree.insert(make_pair<int ,int>(i,i));
}
// delete the elements from 3 to 5 and 9.
for ( iter = tree.begin(); iter != tree.end(); )
{
cout << "Position " << iter->first << ": ";
if ( iter->first == 3 )
{
iter = tree.erase( iter ); cout << iter->second;
}
else if ( iter->first == 4 )
{
iter = tree.erase( iter ); cout << iter->second;
}
else if ( iter->first == 5 )
{
iter = tree.erase( iter ); cout << iter->second;
}
else if ( iter->first == 9 )
{
iter = tree.erase( iter ); cout << iter->second;
}
else
{
cout << iter->second;
++iter;
}
cout << endl;
}
cout << "The left elements:" << endl;
for ( iter = tree.begin(); iter != tree.end(); ++iter )
{
cout << iter->first << " ";
}
cout << endl;
return 0;
}
值得注意的是，由于map 的内部存储机制与vector不一样，所以map的erase方法执行后并没有把当前迭代器自动置为下一个元素位置，而是需要从erase的返回值获取下一个迭代器位置。当然vector的erase方法也同样可以返回下一个位置的指针。map的内部数据结构是红黑树，也就是二叉平衡树，使用erase删除一个元素后，树需要进行重新调整，因为不同于vector的顺序存储，所以map中erase方法中当前迭代器没有自动指向下一个节点位置，而是指向被删除的节点，而此节点已经被释放，如下面从gcc的红黑树实现中摘录的代码：
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
inline void
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(iterator position)
{
// 下面函数在从树中删除当前节点链接，并对树进行旋转，以维护平衡
link_type y = (link_type) __rb_tree_rebalance_for_erase(position.node,
header->parent,
header->left,
header->right);
destroy_node(y); // 释放被删除节点
--node_count;
}
从上述STL源码可以看出，由于Linux下STL库中map类的erase方法实现不一样， erase没有返回值，所以只能采用如下代码进行循环erase操作：
// map sample for Windows and Linux
int main()
{
map<int,int> tree;
for ( int i = 9; i > 0; i-- )
{
tree.insert(make_pair<int ,int>(i,i));
}
map<int,int>::iterator iter;
// delete the elements from 3 to 5 and 9.
for ( iter = tree.begin(); iter != tree.end(); ++iter )
{
cout << "Position " << iter->first << ": ";
if ( iter->first == 3 )
{
tree.erase( iter-- ); cout << iter->second;
}
else if ( iter->first == 4 )
{
tree.erase( iter-- ); cout << iter->second;
}
else if ( iter->first == 5 )
{
tree.erase( iter-- ); cout << iter->second;
}
else if ( iter->first == 9 )
{
tree.erase( iter-- ); cout << iter->second;
}
/*else
{
cout << iter->second;
}*/
cout << endl;
}
cout << "The left elements:" << endl;
for ( iter = tree.begin(); iter != tree.end(); ++iter )
{
cout << iter->first << " ";
}
cout << endl;
return 0;
}
Copyright@戴维 2006.4 于北京
