微尘--KeepMoving

为了忘却的记忆
posts - 3, comments - 2, trackbacks - 0, articles - 13
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

（转）在例3这个问题上栽了一回!关于multimap的删除问题

Posted on 2008-02-26 20:35 微尘 阅读(940) 评论(1)  编辑 收藏 引用
作者：未知[获得此文档时候没有作者记录，深感抱歉，本文档全为转载]  


在STL（标准模板库）中经常会碰到要删除容器中部分元素的情况，本人在编程中就经常编写这方面的代码，在编码和测试过程中发现在STL中删除容器有很多陷阱，网上也有不少网友提到如何在STL中安全删除元素这些问题。

上一篇文章主要讨论序列式容器vector、list中安全删除元素的方法和可能会遇到的陷阱，这一次讨论在map（multimap）容器中如何安全的删除和插入元素。

map（multimap）容器为关联式容器，是编程中经常使用的容器，有键值（key）和实值（value），又称字典、映射表。

你能看出以下代码有什么问题？

例1：

#pragma warning (disable : 4786)

#include

#include

using namespace std;

void main() {

      map< int, int* > mapInt;

      for ( int i = 0; i < 5; i++ ) {

             mapInt[ i ] = new int( i );

      }

      //     再插入键值为2的元素

      mapInt[ 2  ] = new int( 2 );

     

      //     做一些操作

      //     删除内存。

      map< int, int* >::iterator itMap = mapInt.begin();

      for ( ; itMap != mapInt.end();  ++itMap ) {

             delete itMap->second;

      }

}



例2：

void main() {



      map< int, int* > mapInt;

      for ( int i = 0; i < 5; i++ ) {

             mapInt.insert( make_pair( i, new int( i ) ) );

      }

      //     再插入键值为2的元素

      mapInt.insert( make_pair( 2, new int( 2 ) ) );

     

      //     做一些操作

      //     删除内存。

      map< int, int* >::iterator itMap = mapInt.begin();

      for ( ; itMap != mapInt.end();  ++itMap ) {

             delete itMap->second;

      }

}



例3：

void main() {

      map< int, int > mapInt;

      for ( int i = 0; i < 5; i++ ) {

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

      }

     

      mapInt.insert( make_pair( 5,  2 ) );

     

      //     删除所有实值为2的元素

      map< int, int >::iterator itMap = mapInt.begin();

      for ( ; itMap != mapInt.end();  ++itMap ) {

             if (  itMap->second == 2 ) {

                    mapInt.erase( itMap );

             }

      }

}



分析：

      例1将导致内存泄露，因为mapInt[ 2  ] = new int( 2 );这条语句把原来键值为2的元素的实值指针覆盖了，原来的指针就成为野指针，导致内存泄露。

例2也将导致内存泄露，因为mapInt.insert( make_pair( 2, new int( 2 ) ) );这条语句因为键值为2的元素已经存在，导致插入元素失败，所以指向刚分配的内存的指针成为野指针，导致内存泄露。

map容器插入元素的方法。可以调用map容器的insert成员函数插入元素，或者直接用map容器的下标运算式赋值，但这里有一个地方要注意，如果实值为指针的话，插入重复键值的元素时，会导致内存泄露。所以对于插入元素时，必须检查是否插入成功。



正确的方法：

void main() {

      map< int, int* > mapInt;

      bool bRet;

      for ( int i = 0; i < 5; i++ ) {

             int* pI = new int( i );

             bRet = mapInt.insert( make_pair( i, pI ) ).second;

             if ( !bRet ) {

                    //       插入元素不成功。

                    delete pI;

             }

      }

      //     再插入键值为2的元素

      int* pI = new int( 2 );

      bRet = mapInt.insert( make_pair( 2, pI ) ).second;

      if ( !bRet ) {

             //       插入元素不成功。

             delete pI;

      }

     

      //     做一些操作

      //     删除内存。

      map< int, int* >::iterator itMap = mapInt.begin();

      for ( ; itMap != mapInt.end();  ++itMap ) {

             delete itMap->second;

      }

}



例3将导致程序未定义的错误，在windows中即是访问非法内存，程序当掉。因为mapInt.erase( itMap );调用后itMap迭代器已无效了，所以当执行++itMap时，访问非法内存，导致程序当掉。

如果erase（）总是返回下一元素的位置，那就可以像在vector容器中删除元素一样，如：

//     删除所有实值为2的元素

      map< int, int >::iterator itMap = mapInt.begin();

      for ( ; itMap != mapInt.end();   ) {

             if (  itMap->second == 2 ) {

                    itMap = mapInt.erase( itMap );

             }

             else {

                    ++itMap;

             }



      }

但是，注意，以上的方式只在vc使用P.J.STL中才能编译通过，而使用SGI STL库则编译不过，因为SGISTL库在设计中考虑到如果用户不需要这一特性，就会损失性能，因此否决了这种想法。所以要保证可移植性，最好采用下面的方法：



//       删除所有实值为2的元素

        map< int, int >::iterator itMap = mapInt.begin();

        for ( ; itMap != mapInt.end();  ) {

                  if (  itMap->second == 2 ) {

                           //         itMap++将使itMap指向下一个元素，但返回原迭代器的副本，所以

                           //         erase（）被调用时，itMap不指向将要被删除的元素

                           mapInt.erase( itMap++ );

                  }

                  else {

                           ++itMap;

                  }

        }

Feedback

# re: （转）在例3这个问题上栽了一回!关于multimap的删除问题   回复  更多评论   

2008-02-26 21:00 by 微尘
看了这篇文章，一定要搞懂map的operator[]和insert不同啊～ HOHO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理