博文

STL中用erase()方法遍历删除元素(2010-09-02 15:17:00)

摘要:STL中的容器按存储方式分为两类,一类是按以数组形式存储的容器(如:vector 、deque);另一类是以不连续的节点形式存储的容器(如:list、set、map)。在使用erase方法来删除元素时,需要注意一些问题。
      在使用 list、set 或 map遍历删除某些元素时可以这样使用:

正确使用方法1         std::list< int> List;
      std::list< int>::iterator itList;
      for( itList = List.begin(); itList != List.end(); )
      {
            if( WillDelete( *itList) )
            {
               itList = List.erase( itList);
            }
            else......

阅读全文(2763) | 评论:3

去除VC map warning C4786(2010-05-12 18:43:00)

摘要:在vc6.0 下面使用stl中的map的时候,会发现报n个warning。看的都觉得烦,虽然不会有大影响。
这是vc的一个bug,就不说原因了,这里只给出具体解决方案: 如果有stdafx.h文件,则在其文件头加入: #pragma warning(disable: 4786) ............. #include <afxwin.h>         // MFC core and standard components
#include <afxext.h>         // MFC extensions   有其他用到map的头文件或者源文件处,也要加入 #pragma warning(disable: 4786)  ......

阅读全文(3991) | 评论:1

使用map和hash_map的效率问题(转)(2010-04-18 10:28:00)

摘要: 这篇文章来自我今天碰到的一个问题,一个朋友问我使用map和hash_map的效率问题,虽然我也了解一些,但是我不敢直接告诉朋友,因为我怕我说错了,通过我查询一些帖子,我这里做一个总结!内容分别来自
alvin_lee ,codeproject,codeguru.baidu等等! 先看看alvin_lee 朋友做的解析,我觉得还是很正确的,从算法角度阐述了他们之间的问题!
实际上这个问题不光C++会遇到,其他所有语言的标准容器的实现及选择上都是要考虑的。做应用程序你可能觉得影响不大,但是写算法或者核心代码就要小心了。今天改进代码,顺便又来温习基础功课了。   还记得Herb Sutter那极有味道的《C++对话系列》么,在其中《产生真正的hash对象》这个故事里就讲了map的选择。顺便回顾一下,也讲一下我在实用中的理解。   选择map容器,是为了更快的从关键字查找到相关的对象。与使用list这样的线性表容器相比,一可以简化查找的算法,二可以使任意的关键字做索引,并与目标对象配对,优化查找算法。在C++的STL中map是使用树来做查找算法,这种算法差不多相当与list线性容器的折半查找的效率一样,都是O(log2N),而list就没有map这样易定制和操作了。   相比hash_map,hash_map使用hash表来排列配对,hash表是使用关键字来计算表位置。当这个表的大小合适,并且计算算法合适的情况下,hash表的算法复杂度为O(1)的,但是这是理想的情况下的,如果hash表的关键字计算与表位置存在冲突,那么最坏的复杂度为O(n)。   那么有了这样的认识,我们应该怎么样选用算法呢?前两天看Python文章的时候,不知道哪个小子说Python的map比c++的map快,如何如何的。但是他并不知道Python是默认使用的hash_map,而且这些语言特征本质上是使用c/c++写出来的,问题在与算法和手段,而不是在于语言本身的优劣,你熟悉了各种算法,各种语言的细节、设计思想,还能在这偏激的嚷嚷孰好孰坏(片面与偏激的看待事物只能表明愚昧与无知,任何事物都有存在的价值,包括技术)。显然C++的STL默认使用树结构来实现map,是有考究的。   树查找,在总查找效率上比不上hash表,但是它很稳定,它的算法复杂度不会出现......

阅读全文(3464) | 评论:1