c++的STL模板库中3种容器类:vector,list,deque的比较

时间:2022-11-20 14:10:51

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

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

 

  1. vector - 会自动增长的数组
  2. list - 擅长插入删除的链表
  3. deque - 拥有vector和list两者优点的双端队列
  4. 性能竞技场
  5. 性能总结与使用建议

 

vector - 会自动增长的数组

vector又称为向量数组,他是为了解决程序中定义的数组是
不能动态改变大小这个缺点而出现的。

一般程序实现是在类创建的时候同时创建一个定长数组,
随着数据不断被写入,一旦数组被填满,则重新开辟一块更大的内存区,
把原有的数据复制到新的内存区,抛弃原有的内存,如此反复。

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

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


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

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


注意:许多初学者认为vector调用clear能够释放其内存,而实际上STL设计上为了高效,并没有真正释放,所以正确的释放方式是——

构建一个空的vector,和需要释放的v进行swap

vector<Type>().swap(v);


 

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和希腊神话的阿吉里斯一样,
再怎么强大也是有自己的弱点的,之后的测试数据中就能看到了。

 

 

性能竞技场

为了能更好地进行比较,我们让静态数组(程序中写死的)和
动态数组(程序中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内存

c++的STL模板库中3种容器类:vector,list,deque的比较

 

 

性能总结与使用建议

c++的STL模板库中3种容器类:vector,list,deque的比较

 

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


延伸阅读:

http://blog.csdn.net/xiajun07061225/article/details/7438361

http://blog.csdn.net/xiajun07061225/article/details/7438782

http://blog.csdn.net/xiajun07061225/article/details/7459129

http://blog.csdn.net/xiajun07061225/article/details/7442816