07.27 C++中vector list dequeue set map

在c++中，如果要存储的数据大小在编译期间就能确定，则使用数组即可，否则就要使用c++的容器类。容器类分为顺序存储结构（vector list deque）和关联存储结构（set map）

<vector>

连续的存储结构，连续的特性导致随机访问效率高（例如用[]下表访问元素），但插入和删除效率低（因为插入一个元素就要以块的形式挪动内存），当vector容量满了再插入元素时，系统会重新寻找一块比现在大的内存（不同编译器大小不一样，VS2005是1.5倍）将当前数组放入，这样做很耗时，所以最好提前定义好vector的容量不要超。

可允许重复对象

可插入null元素

有序容器

<list>

非连续双链表存储结构，这种特性导致随机访问效率低（不支持[]），但插入删除操作效率高。占用内存大。

可允许重复对象

可插入null元素

有序容器，插入顺序就是输出顺序

<deque>

deque是vector和list的折中，即支持随机存取，插入删除操作的效率也介于两者之间，但是占用内存比前二者都多

可允许重复对象

可插入null元素

有序容器，插入顺序就是输出顺序

vector or deque or list?

经常随机访问选vector，经过插入删除选list，都需要选deque，deque性能处于折中

capacity reverse size resize?

capacity是当前vector最大能容纳的元素数，size是当前vector存入的元素数，reverse(n)改变的是capacity值，resize改变的是size值，如果resize没有指定赋什么值给vector则按vector元素类型默认的构造函数塞数据进去，resize后vector的size就改变了

不允许重复对象

无序容器

只能插入一个null元素

不可重复键值对

set和map底层都是通过红黑树实现（具有较高的查找性能）