如何使用迭代器iterator循环删除容器中的元素?

王朝other·作者佚名  2007-01-22
窄屏简体版  字體: |||超大  

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 于北京

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有  導航