顺序容器vector,deque,list

vector的特点：

(1)指定一块如同数组一样的连续存储，但空间可以动态扩展。即它可以像数组一样操作，并且可以进行动态操作。通常体现在push_back() pop_back()。

(2)随机访问方便，它像数组一样被访问，即支持[ ]操作符和vector.at()

(3)节省空间，因为它是连续存储，在存储数据的区域都是没有被浪费的，但是要明确一点vector大多情况下并不是满存的，在未存储的区域实际是浪费的。

(4)在内部进行插入、删除操作效率非常低，这样的操作基本上是被禁止的。Vector被设计成只能在后端进行追加和删除操作，其原因是vector内部的实现是按照顺序表的原理。

(5)只能在vector的最后进行push和pop，不能在vector的头进行push和pop。

(6)当动态添加的数据超过vector默认分配的大小时要进行内存的重新分配、拷贝与释放，这个操作非常消耗性能。所以要vector达到最优的性能，最好在创建vector时就指定其空间大小。

双向链表list

是一个线性链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。

由于其结构的原因，list随机检索的性能非常的不好，因为它不像vector那样直接找到元素的地址，而是要从头一个一个的顺序查找，这样目标元素越靠后，它的检索时间就越长。检索时间与目标元素的位置成正比。

虽然随机检索的速度不够快，但是它可以迅速地在任何节点进行插入和删除操作。因为list的每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响，不像vector会对操作点之后的所有元素的存储地址都有所影响，这一点是vector不可比拟的。

list的特点：

(1)不使用连续的内存空间这样可以随意地进行动态操作；

(2)可以在内部任何位置快速地插入或删除，当然也可以在两端进行push和pop。

(3)不能进行内部的随机访问，即不支持[ ]操作符和vector.at()；

(4)相对于verctor占用更多的内存。

双端队列deque

是一种优化了的、对序列两端元素进行添加和删除操作的基本序列容器。它允许较为快速地随机访问，但它不像vector把所有的对象保存在一块连续的内存块，而是采用多个连续的存储块，并且在一个映射结构中保存对这些块及其顺序的跟踪。向deque两端添加或删除元素的开销很小。它不需要重新分配空间，所以向末端增加元素比vector更有效。

实际上，deque是对vector和list优缺点的结合，它是处于两者之间的一种容器。

deque的特点：

(1)随机访问方便，即支持[ ]操作符和vector.at()，但性能没有vector好；

(2)可以在内部进行插入和删除操作，但性能不及list；

(3)可以在两端进行push、pop；

顺序容器vector,deque,list

vector是一段连续的内存块，而deque是多个连续的内存块，list是所有数据元素分开保存，可以是任何两个元素没有连续。

vector的查询性能最好，并且在末端增加数据也很好，除非它重新申请内存段；适合高效地随机存储。

list是一个链表，任何一个元素都可以是不连续的，但它都有两个指向上一元素和下一元素的指针。所以它对插入、删除元素性能是最好的，而查询性能非常差；适合大量地插入和删除操作而不关心随机存取的需求。

deque是介于两者之间，它兼顾了数组和链表的优点，它是分块的链表和多个数组的联合。所以它有被list好的查询性能，有被vector好的插入、删除性能。如果你需要随即存取又关心数据的插入和删除，那么deque是最佳之选。