STL顺序容器类——vector、list、deque详解

1、分类
顺序容器：vector、deque、list
关联容器：set、multiset、map、multimap

2、顺序容器：

2.1 vector
（1）简介
    线性顺序结构，和数组类似，但是大小可以不预先设定，并且自动扩展。它可以像数组一样被操作，由于它的特性我们完全可以将vector 看作动态数组。
    在创建一个vector 后，它会自动在内存中分配一块连续的内存空间进行数据存储，初始的空间大小可以预先指定也可以由vector 默认指定，这个大小即capacity （）函数的返回值。当存储的数据超过分配的空间时vector 会重新分配一块内存块，但这样的分配很耗时，在重新分配空间时它会做这样的动作：  首先，vector 会申请一块更大的内存块；  然后，将原来的数据拷贝到新的内存块中；  其次，销毁掉原内存块中的对象（调用对象的析构函数）；  最后，将原来的内存空间释放掉。  
如果vector 保存的数据量很大时，这样的操作一定会导致糟糕的性能（这也是vector 被设计成比较容易拷贝的值类型的原因）。所以说vector 不是在什么情况下性能都好，只有在预先知道它大小的情况下vector 的性能才是最优的。

（2）特点  
1) 指定一块如同数组一样的连续存储，但空间可以动态扩展。即它可以像数组一样操作，并且可以进行动态操作。通常体现在push_back() pop_back() 。 
2) 随机访问方便，它像数组一样被访问，即支持[ ] 操作符和vector.at() 
3) 节省空间，因为它是连续存储，在存储数据的区域都是没有被浪费的，但是要明确一点vector 大多情况下并不是满存的，在未存储的区域实际是浪费的。  
4) 在内部进行插入、删除操作效率非常低，这样的操作基本上是被禁止的。Vector 被设计成只能在后端进行追加和删除操作，其原因是vector 内部的实现是按照顺序表的原理。 
5) 只能在vector 的最后进行push 和pop ，不能在vector 的头进行push 和pop 。 
6) 当动态添加的数据超过vector 默认分配的大小时要进行内存的重新分配、拷贝与释放，这个操作非常消耗性能。 所以要vector 达到最优的性能，最好在创建vector 时就指定其空间大小。

（3）使用方法  
包含头文件   #include
1)创建 
vector vt;//创建空的vector
vector vt(n); //创建包含3个默认为0的元素
vector vt(m,n);//创建m个n的元素的vector
vector vt(vt2);//vt2拷贝到vt
vector vt(vt2.begin(),vt2.end());//将vt2指定范围内元素拷贝到vt

vt2.assign(vt.begin(),vt.end());//vt拷贝到vt2
vt2.assign(int num,value);vt2初始化为num个value

2）增
vt.push_back(n);//尾部添加n

iterator vt.insert(iterator location, value);location前插入value，返回该元素迭代器
vt.insert(iterator location, int num,value);;location前插入num个value
vt.insert(iterator location,iterator start,iterator end);location前插入start到end之间的内容

3）删
vt.clear()；//删除所有

vt.erase(iterator location);删除location处的元素
vt.erase(iterator start,iterator end)；删除从start到end之间的元素

vt.pop_back()；删除最后一个元素

4）改
vt.at[n] = value;
vt.resize(); 重置容器大小
vt[] = value

vt.swap(vector vt2); vt2和vt互相交换

5） 查
vt.begin() vt.end();首尾迭代器
vt.rbegin() vt.rend();反向首尾迭代器
vt.front() vt.back(); 首尾元素

vt[];
vt.at(n);类似数组下标操作

vt.size()；查容器大小，如果没初始化为0，所以没有制定vector大小的，不要使用vt[i],而是用push_back（）
vt.capacity()；容器容量
bool vt.empty();是否为空，返回true为空

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

（2）特点 
1) 不使用连续的内存空间这样可以随意地进行动态操作； 
2) 可以在内部任何位置快速地插入或删除，当然也可以在两端进行push和pop  。  
3) 不能进行内部的随机访问，即不支持[ ] 操作符和vector.at()  ； 
    Lists将元素按顺序储存在链表中，与向量(vectors)相比，它允许快速的插入和删除，但是随机访问却比较慢.   

（3）使用方法 
增加 的方法：
list.push_front(n);前面添加n
list.opo_front();删除前面的一个元素

两链表合并：
list_one.merge(list_two);//将两有序链表合并为有序链表，放到list_one ,释放list_two，，必须是有序，且如有重复也会排序成重复
c1.merge(c2,comp)      合并2个有序的链表并使之按照自定义规则排序之后从新放到c1中,释放c2。comp必须和c1、c2排序一致。
c1.splice(c1.beg,c2)      将c2连接在c1的beg位置,释放c2
c1.splice(c1.begin(),c2,c2.begin())      将c2的begin位置的元素连接到c1的begin位置，并且在c2释放掉begin位置的元素
c1.splice(c1.beg,c2,c2.beg,c2.end)      将c2的[beg,end)位置的元素连接到c1的beg位置并且释放c2的[beg,end)位置的元素

删除：
remove(num)             删除链表中匹配num的元素。
remove_if(comp)       删除条件comp为真的元素,参数为自定义的回调函数。
list.reverse()       反转链表
list.unique()       删除相邻相同的的元素仅保留一个

排序：
c.sort()       将链表排序，默认升序
c.sort(comp)       自定义回调函数实现自定义排序
降序排序的cmp函数如下所示：
bool cmp(int x, int y)
{
return x>y;
}

减少的：不能随机访问[] .at()

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

（2）特点 
1) 随机访问方便，即支持[ ]  操作符和vector.at()  ，但性能没有vector 好； 
2)  可以在内部进行插入和删除操作，但性能不及list  ； 
3)  可以在两端进行push  、pop  ； 
4)  相对于verctor 占用更多的内存。 
双向队列和向量很相似，但是它允许在容器头部快速插入和删

（3）使用方法 
较vector增加push_front() pop_front()方法

2、4 总结 
    vector 是一段连续的内存块，而deque 是多个连续的内存块，  list  是所有数据元素分开保存，可以是任何两个元素没有连续。   
vector 的查询性能最好，并且在末端增加数据也很好，除非它重新申请内存段；适合高效地随机存储。   
list  是一个链表，任何一个元素都可以是不连续的，但它都有两个指向上一元素和下一元素的指针。所以它对插入、删除元素性能是最好的，而查询性能非常差；适合大量地插入和删除操作而不关心随机存取的需求。   
deque  介于两者之间，兼顾数组和链表的优点，它是分块的链表和多个数组的联合。所以它有被list好的查询性能，有比vector好的插入、删除性能。 
如果你需要随机存取又关心两端数据的插入和删除，那么deque是最佳之选。