先来看一下 c++标准模板库中,容器类vector、list 、deque都属于顺行性容器(所谓顺序性容器是一种各元素之间有顺序关系的线性表,是一种线性结构的可序群集,每个元素都有固定的位置,这个位置与元素无关,只与插入删除的先后顺序有关);都可以用来存储一组类型相同的对象;不同于内置数据类型数组的是,vector、list、deque的大小不是固定的,他们支持动态增长。
之所以设计 vector、list、deque不同的容器类,是因为它们适用于不同的情况。 (详细可参考http://www.360doc.com/content/11/0330/22/4390689_106013089.shtml#)
vector
|
从后面快速的插入与删除,直接访问任何元素
|
deque
|
从前面或后面快速的插入与删除,直接访问任何元素
|
list
|
双链表,从任何地方快速插入与删除
|
单从上面适用情况来看,似乎deque完全可以代替vector和list的,后者没有存在的必要,但是,情况并不是这样的,还要看一下他们的性能。有人曾专门对各种情况性能做过对比,里面有些数值似乎不准确,但能说明一定的问题 (http://www.cnblogs.com/kingcat/archive/2012/04/13/2446186.html)
比赛项目/参赛选手
|
Vector
|
Deque
|
List
|
内存管理
|
Poor
|
Good
|
perfect
|
使用[ ]和at() 操作访问数据
|
Very good
|
Normal
|
N/A
|
Iterator的访问速度
|
Good
|
Very good
|
Good
|
Push_back操作(后插入)
|
Good
|
Good
|
Good
|
Push_front操作(前插入)
|
N/A
|
Very good
|
Good
|
Insert(中间插入)
|
Poor
|
Perfect
|
Perfect
|
Erase(中间删除)
|
Poor
|
Perfect
|
Perfect
|
Pop_back(后部删除)
|
Perfect
|
Perfect
|
Normal
|
Swap(交换数据)
|
Perfect
|
Very good
|
Good
|
遍历
|
Perfect
|
Good
|
Normal
|
从表中可以总结出一下几点:
(1)vector适用于随机存取,支持[],随机存取时间为常数;但是在非末尾删除插入数据时,效率极低。
(2)list适用于数组中间频繁插入删除数据,其插入删除开销低,但是不支持随机存取。
(3)deque界于vector和list两者之间,支持随机存取,队首队尾插入删除操作开销极小。随机存取效率接近于vector,队首队尾插入删除接近于list。
接下来,从它们的内部机制来分析原因:
vector事实上表示的是一块连续的内存,当数据超过数组大小,需要申请新的内存,这时,vector会申请一块足够大的连续内存,把原来数据复制到新的内存,并释放原来vector占用的内存。所谓随机存取,就是可以通过公式直接计算出元素地址的方式,而不需要挨个查找。vector的计算公式类似于 a0+(i-1)*d (a0为vector地址,i为第i个元素,d为每个元素占用的地址个数。
list是双向链式表,在内存中不一定连续。如果要实现随机访问,需要遍历整个数组,在c++标准库模版索性没有提供随机存储([]操作)。但是链式存储有一个好处,就是在表中间插入和删除元素特别方便。
deque事实上是有多个连续块组成,是c++中的双向队列,因此在两端插入删除元素特别方便,(其内存结构如下:
http://blog.csdn.net/yfkiss/article/details/6559149)
对于deque的工作机制,有几点没得到确认的猜测:
(1)因为可以再队列两头快速的插入元素,则说明,元素的第一个位置并不在申请内存的第一个位置,其前面应该还有连续的空间待用
(2)因为deque的随机访问时间为常数,所以可推测其其随机访问公式为 一分段函数
if(i<s0)
addr=a0+d*(i-1)
else if(i>s0&&i<s1)
addr=a1+d*(i-s0)
else if(i>s1 && i<s2)
addr=a2+d*(i-s0-s1)
else
....
(3)因为中间插入删除元素逊于list,优于vector,可推测:对于中间插入删除时这样的,给待插入(删除)元素所在的连续块重新分配内存,插入(删除)新元素,其他连续快不动。
下图为vector、list、deque的无理存储结构。(http://www.360doc.com/content/11/0330/22/4390689_106013089.shtml#)
待继续完善.......
分享到:
相关推荐
STL中vector、list、deque和map的区别
vector和deque使用方法
presentation about vector and deque
自己动手实现vector,deque,包含各种测试用例,面向对象程序设计要求写的
案例-评委打分 ...遍历vector容器,取出来每一个选手,执行for循环,可以把10个评分打分存到deque容器中 sort算法对deque容器中分数排序,去除最高和最低分 deque容器遍历一遍,累加总分 获取平均分
壬寅朔月的背包和指针-KHIN的讲义(指针,vector,deque部分)
非常实用的STL容器讲解学习,内容全,讲解详细 包括Vector、Vector、String、Deque、sort、set、map,绝对有用!!
python--双端队列deque(csdn)————程序
双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列双队列
本文深入地研究了std::deque 容器...读完这篇文章后读者应该能够理解在容量增长的过程中deque 与vector在内存分配和性能的不同表现。由于deque> 和vector的用法很相似,读者可以参考vector 文档中介绍如何使用STL容器。
-> JDK(Java集合)-> Guava(谷歌)-> Commons-collections(Apache) 主要抽象数据结构——ADS列表(ArrayList、LinkedList、Vector)栈(FIFO)队列(LIFO、Deque——双端队列) interface Map<Key> TreeMap<K> ...
list 和 deque郭 炜 刘家瑛北京大学程序设计实习双向链表 #include <list>在任何位置插入/删除都是常数时间不支持根据下标随机存取元素具有
deque结构可以看作是内置的list结构的加强版,且比队列提供了更强大的方法,下面就通过几个小例子来详解Python的collections模块中的deque双端队列结构:
本例程提供了C++的STL常用数据结构及其算法的使用范例,比如vector、string、list、forward_list、deque、queue、stack、map、set、multimap、multiset、tuple、bitset的使用范例,以及algorithm常….zip
STL的容器deque的详细使用方法和文档 6.0代码
Vector、Deque、List、Set等等,快速学习STL实例 ,迄今为止较好的实例,包括类、结构等作为stl元素
STL中的deque模板包括迭代器等接口
本篇文章介绍了,深入分析C++中deque的使用。需要的朋友参考下
容器的各种用法,包括list,deque,vector的用法
PTA 6-3 Deque for DS lesson