关于C++中STL的erase用法

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

STL中的容器主要分两类，一是顺序存储的，如vector；一是以红黑树形式存储的，如map。下面分别以vector和map为例，说明怎样利用迭代器在遍历的同时删除容器内元素。

下面示例程序首先往容器中添加一定元素，然后循环删除其中连续或不连续的元素。程序在VS2003以及g++3.4下调试，不同编译器下可能结果不同。

// vector sample for Windows and Linux

int main()

{

 vector vec;

 vector::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

代码1

//////////////////////////////////////////////////////////////////////////////////////

int main()

{

 map tree;

 map::iterator iter; 

 for ( int i = 9; i > 0; i-- )

 {

  tree.insert(make_pair(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

inline void

rb_tree::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

代码2

////////////////////////////////////////////////////////////////////////////

int main()

{

 map tree;  

 for ( int i = 9; i > 0; i-- )

 {

  tree.insert(make_pair(i,i));

 } 

 map::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;

}

////////////////////////////////////////////////////////////////////////////////

以MAP实现为例简单说明一下问题：

代码1中采用没有erase时执行迭代器++的方式，

由于

if ( iter->first == 3 )

  {   

   iter = tree.erase( iter ); cout << iter->second;

  }

中  iter = tree.erase( iter );将erase之后的返回值记到iter中所以再次进入循环体时iter仍为有效，但在一般情况下iter = tree.erase( iter );这样编译并不能通过，如果只是tree.erase( iter );则到一次再进入循环体时由于iter已成为无效迭代器，这时程序会出现异常。

代码2中采用erase时--的方式，tree.erase( iter-- )没有记录返回值，看似没有问题，但如果第一次循环体执行时执行的不是

  if ( iter->first == 3 )

  {   

   tree.erase( iter-- );  cout << iter->second;

  }

而是第一个迭代器

  if ( iter->first == 1 )

  {   

   tree.erase( iter-- );  cout << iter->second;

  }

则这时，iter—之后越界，迭代器这时无效。

////////////////////////////////////////////////////////////////////////////////////////

再来看一下

http://www.cppblog.com/sandy/archive/2006/12/27/16913.html

和

中的相关介绍，这才明白过来。http://www.cppblog.com/sandy/archive/2006/12/27/16913.html中的方法才是正确的。。。。。

VECTOR操作的正确方法：

void erase(vector &v)

{

    for(vector::iterator vi=v.begin();vi!=v.end();)

    {

        if(*vi % 2 == 0)

        {

            cout << "Erasing " << *vi << endl;

            vi = v.erase(vi);//区别在这里，没有++

        }

        else ++vi;

    }

}

MAP操作的正确方法其实应该是：

void erase(map &m)

{

    for(map::iterator mi=m.begin();mi!=m.end();)

    {

        if(mi->second % 2 == 0)

        {

            cout << "Erasing " << mi->second << endl;

            m.erase(mi++);//区别在这，有++

        }

        else ++mi;

    }

}

另外又提到了逆向删除，一种新的提高效率的做法，推荐！

 

void erase2(vector &v)

{

    for(vector::reverse_iterator ri=v.rbegin();ri!=v.rend();)

    {

        if(*ri % 2 == 0)

        {

            cout << "Erasing " << *ri << endl;

            v.erase((++ri).base());

        }

        else ++ri;

    }

}