List：双向链表

list就是双向链表,元素也是在堆中存放,每个元素都是放在一块内存中,它的内存空间可以是不连续的，通过指针来进行数据的访问，这个特点使得它的随机存取变的非常没有效率，因此它没有提供[]操作符的重载。但由于链表的特点，它可以以很好的效率支持任意地方的删除和插入。

list没有空间预留习惯,所以每分配一个元素都会从内存中分配,每删除一个元素都会释放它占用的内存.

list在哪里添加删除元素性能都很高,不需要移动内存,当然也不需要对每个元素都进行构造与析构了,所以常用来做随机操作容器.
但是访问list里面的元素时就开始和最后访问最快
访问其它元素都是O(n) ,所以如果需要经常随机访问的话,还是使用其它的好

总结
如果你喜欢经常添加删除大对象的话,那么请使用list
要保存的对象不大,构造与析构操作不复杂,那么可以使用vector代替
list<指针>完全是性能最低的做法,这种情况下还是使用vector<指针>好,因为指针没有构造与析构,也不占用很大内存.

1.vector 底层数据结构为数组，支持快速随机访问

2.list 底层数据结构为双向链表，支持快速增删

3.deque 底层数据结构为一个中央控制器和多个缓冲区，详细见STL源码剖析P146，支持首尾（中间不能）快速增删，也支持随机访问
deque是一个双端队列(double-ended queue)，也是在堆中保存内容的.它的保存形式如下:
[堆1] —> [堆2] —>[堆3] —> …
每个堆保存好几个元素,然后堆和堆之间有指针指向,看起来像是list和vector的结合品.

4.stack 底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时

5.queue 底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时

（stack和queue其实是适配器,而不叫容器，因为是对容器的再封装）

6.priority_queue 的底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现

7.set 底层数据结构为红黑树，有序，不重复

8.multiset 底层数据结构为红黑树，有序，可重复

9.map 底层数据结构为红黑树，有序，不重复

10.multimap 底层数据结构为红黑树，有序，可重复

11.hash_set 底层数据结构为hash表，无序，不重复

12.hash_multiset 底层数据结构为hash表，无序，可重复

13.hash_map 底层数据结构为hash表，无序，不重复

14.hash_multimap 底层数据结构为hash表，无序，可重复

迭代器模式的定义是：设计一种方法，使得依据某种顺序遍历容器时，容器内部的具体结构是不可见的。C++ STL中，迭代器的本质就是指针，但是这个指针在不同场合是有区别的：

对vector::iterator而言，迭代器是指向vector某元素的指针，和T a*差不多；对于list和slist而言，迭代器指向链表节点；对map和set等基于二叉搜索树的容器而言，迭代器可以看成是指向treenode的指针。因此STL迭代器大致可分为两种，一种是连续地址空间的，一种是非连续地址空间的。然而不管是哪一种，在遍历过程中修改容器的内容绝对是大忌中的大忌！
对vector而言，插入删除操作往往包含着malloc、realloc操作，一旦空间重塑了，原来的迭代器也将失效，如再理所应当地it++，你的it就不知道跑哪里去了。
对list而言，虽然it++仅仅意味着p=p->next，但如果list的内容改变，此next还是不是彼next可就说不好了。
对于map和set，it的遍历是遵循二叉搜索树中序遍历顺序的（即有序遍历），it++找的是右子树的最左边，reverse_it++找的是左子树的最右边，随随便便插入删除，既有可能影响迭代器的遍历。