STL之容器初探

说是stl的容器,其实这里主要就是比较vector、list和deque了。都能动态增加容量、以拷贝的方式存储对象的三者,各自的擅长领域是什么呢?

先试着对三位进行介绍,再进行基于超级不正规测试的能力大比拼!

说来STL想学好,还是必须要看书呀。学期初借的那本《泛型编程与STL》没看完,《STL源码剖析》没得借又觉得可能会有点难,真是微妙的心情

 

介绍先行

1.vector

擅长随机访问、尾部插入/删除操作;不擅长尾部以外位置的插入/删除操作;有点畏惧海量数据

 

实现原理:类似原生数组一样的连续空间用来存放数据,所以具备原生数组的特点:随机访问,在插入/删除操作时会涉及大规模的数据移动

当容量不够时,会重新分配一个较大的容量(比如说大小为之前容量*2),然后进行内存拷贝、释放旧容量。因此在面对海量数据时,不仅要关注是否有如此大的连续空间,还要考虑在数据增长时重分配空间带来的额外大量拷贝、释放操作。有reserve()方法预分配一定大小的内存,可缓解一些额外操作。

 

2.list

基本不支持随机访问;擅长对各个位置的插入/删除操作;遍历时取址操作多;数据量不管怎么增长,效率都不会有太大起伏

 

实现原理:本质是双向链表,所以对各个位置的插入/删除操作游刃有余,也不用担心连续空间的分配问题;但是遍历时有额外取址操作,存储时每个对象也要额外存两个指针

 

3.deque(double-ended queue)

支持随机访问;擅长头部和尾部的插入/删除操作;

 

实现原理:可视为是vector与list的中间态,是STL里stack和queue的默认容器。在STL中一般的实现方式是:以一小段连续内存作为整体单位的双向链表,即用一小段连续内存代替了链表中的节点。当遇到连续增长的数据时,也可以用小段连续内存为单位进行分配,比起vector来说平缓温和得多,限制也少。

 

 

能力大比拼

(">"表示优于,测试平台为vs2008 release模式,电脑配置为cpu T4300,内存2G)

1.内存管理

测试方式:插入1000个对象,查看构造函数调用次数:

结果数据:vector 2024  |   list 1001  |  deque 1008

测试结果:list>deque>>vector

 

2.随机访问速度

测试方式:插入1000个int,分别用[]和::at()随机访问一亿次的毫秒数(使用::at()会额外检查下标越界、异常处理)

结果数据(每次都使用rand()):vector[]  2750  |  vector::at() 3438  |  deque[] 3390  |  deque::at() 3547  ;

结果数据(预先生成随机数表):vector[] 141   |   vector::at() 1062  |  deque[]1047   |  deque::at() 1047 ;

测试结果:vector>deque>>list

 

3.头部插入速度

测试方式:push_front 一百万个int的毫秒数

结果数据:list 1594  |  deque 438

测试结果:deque>list>>vector

 

4.中间插入/删除速度

测试方式:在已有1000个int数据的情况下,从第500个位置开始插入十万个int、再删除十万个int的毫秒数

结果数据:list插入 157   |  deque插入 1218  |   list删除 1532  |  deque删除 1172

测试结果:list>deque>>vector

(为啥deque的删除会比list快呢,有疑问)

 

5.iterator遍历操作

测试方式:在已有十万个int数据的情况下,使用iterator顺序遍历1000遍的毫秒数

结果数据:vector 1016  |   list 1437  |  deque 1203

测试结果:vector>deque>list

===================================================================

测试的时候再一次发现了stl在debug和release下的速度巨大差异,说来当初就是这个使自己对stl产生兴趣的

现在想想,大概主要是debug下没有inline吧!毕竟stl基本操作都是函数

但是vs的参数让人感觉还是不够自由,还是要换平台试试sgi stl为好

一条评论

  1. hongbai 说道:

    一天不学习。。又被教主落下了十万八千里。。怎么办T T

发表评论

电子邮件地址不会被公开。

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>