sailing

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  1 Posts :: 4 Stories :: 0 Comments :: 0 Trackbacks

常用链接

留言簿

我参与的团队

搜索

  •  

最新评论

转载: http://ikaruga.name/Technology/ccplusplus/stlCollection.html

STL容器类vector,list,deque的比较
作者:斑鸠
更新时间:2009/01/04
编译器版本:Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 15.00.21022.08 for 80x86

C++的STL模板库中提供了3种容器类:vector,list,deque
对于这三种容器,在觉得好用的同时,经常会让我们困惑应该选择哪一种来实现我们的逻辑。
在少量数据操作的程序中随便哪一种用起来感觉差别并不是很大,
但是当数据达到一定数量后,会明显感觉性能上有很大差异。

本文就试图从介绍,以及性能比较两个方面来讨论这个问题。

  1. vector - 会自动增长的数组

  2. list - 擅长插入删除的链表

  3. deque - 拥有vector和list两者优点的双端队列

  4. 性能竞技场

  5. 性能总结与使用建议

  6. 测试程序清单

vector - 会自动增长的数组

vector又称为向量数组,他是为了解决程序中定义的数组是
不能动态改变大小这个缺点而出现的。
一般程序实现是在类创建的时候同时创建一个定长数组,
随着数据不断被写入,一旦数组被填满,则重新开辟一块更大的内存区,
把原有的数据复制到新的内存区,抛弃原有的内存,如此反复。

由于程序自动管理数组的增长,对于我们程序员来说确实轻松了不少,
只管把数据往里面插就行了,当然把物理内存和虚拟内存插爆掉了
就是操作系统来找你麻烦了:-)

vector由于数组的增长只能向前,所以也只提供了后端插入和后端删除,
也就是push_back和pop_back。当然在前端和中间要操作数据也是可以的,
用insert和erase,但是前端和中间对数据进行操作必然会引起数据块的移动,
这对性能影响是非常大的。

对于所有数组来说,最大的优势就是随机访问的能力。
在vector中,提供了at和[]运算符这两个方法来进行随机访问。
由于每个数据大小相同,并且无间隔地排列在内存中,
所以要对某一个数据操作,只需要用一个表达式就能直接计算出地址:
address = base + index * datasize

同样,对vector进行内存开辟,初始化,清除都是不需要花大力气的,
从头到尾都只有一块内存。

list - 擅长插入删除的链表

有黑必有白,世界万物都是成对出现的。
链表对于数组来说就是相反的存在。
数组本身是没有动态增长能力的(程序中也必须重新开辟内存来实现),
而链表强悍的就是动态增长和删除的能力。
但对于数组强悍的随机访问能力来说的话,链表却很弱。

list是一个双向链表的实现。
为了提供双向遍历的能力,list要比一般的数据单元多出两个指向前后的指针。
这也是没办法的,毕竟现在的PC内存结构就是一个大数组,
链表要在不同的环境中实现自己的功能就需要花更多空间。

list提供了push_back,push_front,pop_back,pop_front四个方法
来方便操作list的两端数据的增加和删除,不过少了vector的at和[]运算符的
随机访问数据的方法。并不是不能实现,而是list的设计者
并不想让list去做那些事情,因为他们会做得非常差劲。

对于list来说,清除容器内所有的元素是一件苦力活,
因为所有数据单元的内存都不连续,list只有一个一个遍历来删除。

deque - 拥有vector和list两者优点的双端队列

黑与白,处于这两个极端之间的就是令人愉悦的彩色了。
deque作为vector和list的结合体,确实有着不凡的实力。

STL的deque的实现没有怎么去看过,不过根据我自己的猜测,
应该是把数组分段化,在分段的数组上添加指针来把所有段连在一起,
最终成为一个大的数组。

deque和list一样,提供了push_back,push_front,
pop_back,pop_front四个方法。可以想象,如果要对deque的两端进行操作,
也就是要对第一段和最后一段的定长数组进行重新分配内存区,
由于分过段的数组很小,重新分配的开销也就不会很大。

deque也和vector一样,提供了at和[]运算符的方法。
要计算出某个数据的地址的话,虽然要比vector麻烦一点,
但效率要比list高多了。
首先和list一样进行遍历,每次遍历的时候累积每段数组的大小,
当遍历到某个段,而且baseN <= index < baseN + baseN_length的时候,
通过address = baseN + baseN_index就能计算出地址
由于分过段的后链表的长度也不是很长,所以遍历对于
整体性能的影响就微乎其微了。

看起来deque很无敌吧,不过deque和希腊神话的阿吉里斯一样,
再怎么强大也是有自己的弱点的,之后的测试数据中就能看到了。

P.S.请搜索「阿吉里斯的脚后跟」来获取详细内容

性能竞技场

为了能更好地进行比较,我们让静态数组(程序中写死的)和
动态数组(程序中new出来的)也参加了部分竞技。

竞技项目:
  •  初始化:对于静态和动态数组,逐一赋值,对于容器,push_back插入
  • 前向遍历:从0到n-1,每个数据自加1
  • 后向遍历:从n-1到0,每个数据自减1
  • 随机访问:在0到n-1中,随机抽取一定数量的数据进行读取
  • 后端插入:用push_back在后端插入一定数量的数据
  • 后端移除:用pop_back在后端移除一定数量的数据
  • 前端插入:用push_front在前端插入一定数量的数据
  • 前端移除:用pop_front在前端移除一定数量的数据
  • 中间插入:用insert在中间插入一定数量的数据
  • 中间移除:用erase在中间移除一定数量的数据
  • 反初始化:对于静态和动态数组,ZeroMemory删除所有数据,对于容器,调用clear方法
规则:
  • vector,list,deque都调用默认的构造函数来创建
  • 数组和容器的数据项都是1,000,000个
  • 前端和后端插入的数据项是10,000个
  • 前端和后端删除的数据项是10,000个
  • 随机访问的数据项是10,000个
  • 数据类型采用int型
  • 计时采用RDTSC高精度计时器来计时
  • 随机访问的数据的位置序列在测试前随机生成,所有数组和容器都采用这个序列
  • 测试采用Debug版(Release版会对代码进行优化,可能会对测试产生一定的影响)
  • 测试3次,取平均值
测试机配置:
Intel(R) Core(TM)2 CPU T7400 2.16GHz 2.16GHz
2.00GB内存

测试结果:(单位 秒)
测试项目静态数组动态数组vectorlistdeque备注
 初始化0.005510.004610.2071.300.352list每个数据项都有附加数据,速度稍慢了一些
前向遍历0.003810.005490.07960.07560.0713 
后向遍历0.004220.004780.8850.8790.690 
随机访问0.0003340.0003420.001191480.0115list把时间都耗在了找寻相应数据上
后端插入N/AN/A0.001920.01280.00260 
后端移除N/AN/A0.001310.02930.00194 
前端插入N/AN/A10.20.01280.00547vector对前端操作很苦手啊
前端移除N/AN/A10.30.02970.00135同上
中间插入N/AN/A195187764看似万能的deque的最大弱点,因为复杂的结构导致中间数据操作带来的复杂性大大增加,体现在操作时间是其他两个的几倍
中间移除N/AN/A195209753同上
反初始化0.001390.002900.00001060.6930.305vector貌似是直接抛弃内存的,其他两个就没那么简单了

性能总结与使用建议

测试项目静态数组动态数组vectorlistdeque
 初始化★★★★★★★★★★★★★★☆★★★☆☆★★★★☆
前向遍历★★★★★★★★★★★★★★☆★★★★☆★★★★☆
后向遍历★★★★★★★★★★★★★★☆★★★★☆★★★★☆
随机访问★★★★★★★★★★★★★★☆★☆☆☆☆★★★☆☆
后端插入N/AN/A★★★★★★★★★☆★★★★★
后端移除N/AN/A★★★★★★★★★☆★★★★★
前端插入N/AN/A★★☆☆☆★★★★☆★★★★★
前端移除N/AN/A★★☆☆☆★★★★☆★★★★★
中间插入N/AN/A★★☆☆☆★★☆☆☆★☆☆☆☆
中间移除N/AN/A★★☆☆☆★★☆☆☆★☆☆☆☆
反初始化★★★★★★★★★★★★★★★★★★★☆★★★★☆

一些使用上的建议:
Level 1 - 仅仅作为Map使用:采用静态数组
Level 2 - 保存定长数据,使用时也是全部遍历:采用动态数组(长度一开始就固定的话静态数组也行)
Level 3 - 保存不定长数组,需要动态增加的能力,侧重于寻找数据的速度:采用vector
Level 3 - 保存不定长数组,需要动态增加的能力,侧重于增加删除数据的速度:采用list
Level 4 - 对数据有复杂操作,即需要前后增删数据的能力,又要良好的数据访问速度:采用deque
Level 5 - 对数据中间的增删操作比较多:采用list,建议在排序的基础上,批量进行增删可以对运行效率提供最大的保证
Level 6 - 上述中找不到适合的:组合STL容器或者自己建立特殊的数据结构来实现

测试程序清单

>>>main.cpp<<<
posted on 2011-12-07 12:57 sailing 阅读(12493) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理