深入理解vector list deque——存储结构机理

先来看一下 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#）

待继续完善.......