C++——STL容器 1.序列式容器 1.2 list 1.3 deque 2.容器适配器 2.1 stack（栈，垛）先进，后出 2.2 queue（队列） 2.3 deque 3.关联性容器 4.hashtable
序列式容器：vector，list，deque；stack，queue；heap，priority_queue，slist
关联式容器：（底层都是红黑树）set，map，multiset，multimap
（底层都是哈希表）hashtable，hash_set，hash_map，hash_multiset，hash_multimap
综合对比：
| array | vector | list | deque | |
| 存储空间 | 静态 | 动态 | 动态 |
动态分段连续空间 （没用容量的概念） |
| 迭代器 | 普通指针+,-,++,--,+=,-=,->,* | 节点（向前指针，向后指针，数据） |
非普通指针，非常复杂 故非必要不要用deque |
|
| 数据结构 |
单向开口的线性连续空间（头部也可以插入，但操作效率低，无法接受） 可变大小数组 |
非连续空间，靠每个元素点的前后指针来串联起来——双向链表，甚至是双向环形链表 |
双向开口的线性连续空间（头尾均可插入、删除元素） star,finish两个迭代器， map指针， map大小 |
|
| 空间增加 |
1.原大小的2倍增加空间； 2.拷贝原空间内容并构造新元素 3.释放原空间 4.指向原vector的迭代器失效，要小心 |
插入一个元素，配置一个空间； 删除一个元素，释放一个空间 |
随时增加新的分段空间并连接起来 没有空间保留 |
|
| 任意位置插入数据 | 见下图1 | 插入，贴合，删除任意元素不会对其他元素/迭代器造成任何影响 | 操作复杂 |
选择原则：
1、如果你需要高效的随机存取，而不在乎插入和删除的效率，使用vector
2、如果你需要大量的插入和删除，而不关心随机存取，则应使用list
3、如果你需要随机存取，而且关心两端数据的插入和删除，则应使用deque。
4、如果你要存储一个数据字典，并要求方便地根据key找value，那么map是较好的选择
5、如果你要查找一个元素是否在某集合内存中，则使用set存储这个集合比较好
6、除非有更好的理由，否则用vector
7、很多很小的元素，额外开销——不要用list/forward_list
8、随机访问，vector/deque
9、只有头尾插入/删除，没有中间，用deque
10、输入时需要插入中间，随后访问随机
- 确定是否需要中间插入（可以先vector，后sort）
- 确实需要，输入阶段使用list，完成后将list拷贝到vector
一、vector：简单，允许随机存储，数据的存取十分灵活，在缺省情况下应该使用。
二、deque：经常在头部和尾部安插和移除元素，并且存储的容量也比vector大得多。
三、list：如果经常在容器的中段执行安插，移除和移动元素。但是不支持随机存储。 list容器中尽量不要使用删除操作，比插入操作多消耗近百倍
四、set和multiset：经常以某个准则寻找元素，可以使用“以这个准则为排序准则”的set和multiset，在大量的数据情况下，对数复杂度比线性复杂度的效果要好的多。
五、map和multimap：使用（key、value）的pair，使用字典，使用关联式数组 e.g“map[key] = value”。
迭代器：类别、前进、后退、成员访问、取值dereference(*操作符）
1.1 vector
插入数据操作：
图1 Vector任意位置插入数据
①vector不适合push_front(效率很低)
②vector不适合中间插入删除操作。中间插入删除操作会引起内存拷贝。
3.vector.capacity(); vector.reserve(n);vector.shrink_to_fit();
1.2 list
list采用非线性的空间存储数据。
①list适合插入删除频繁的场所。不管插入还是删除，时间基本上都是常数。
②list不适合随机线性访问。
1.3 deque
deque采用类似文件系统的方式存储数据。其中有数个连续空间的缓冲区存储数据。这些缓冲区连接起来，给上层用户一个假象就是，存储的数据空间是连续的。
deque是list和vector的折中方案。兼有list的优点，也有vector随机线性访问效率高的优点。
①deque仍旧不适合中间插入删除操作。
②deque适合线性随机访问数据。
2.容器适配器
2.1 stack（栈，垛）先进，后出
1 继承自deque（封闭头部开口）——更像一个adapter而不是container
2 新增、移除、获得顶端数据，除此之外，无法获得其他数据。
3 没有迭代器
4 deque、list都可以作为底层容器
stack是deque的一种变种，优缺点不变。
2.2 queue（队列）
1 新增、移除，从尾端加入元素，从首端取出数据，此外，无法获得其他数据。不允许遍历
2 SGI STL 以deque为底部容器，封闭其前端入口和后端出口，前端只允许出，后端只允许入，即为queue
3 没有迭代器
4.queue是deque的一种变种，优缺点不变。
2.3 deque
3.关联性容器
底层：红黑树
map:有序的key-word对
set:有序的key=word
multimap,multiset：有序的可重复出现的map/set
底层：哈希表
unordered_map:无序的key-word对
unordered_set:无序的key=word
unordered_multimap,unordered_multiset：无序的可重复出现的map/set
3.0 迭代器
单旋转和双旋转操作：
对1和4用单旋转操作，2和3用双旋转操作
单旋转：
双旋转：
3.1 红黑树
规则：
1. 节点：颜色，父节点指针，左右节点指针，值
2. 迭代器：基本迭代器和继承的迭代器两层组成
3. 插入操作：1. 插入值：——对比节点键值（遇大往左，遇小往右）——得到新值的插入点、父节点——插入值（维护leftmost和rightmost，设定父节点、左右子节点）
2. 更新树：更改颜色，旋转树使其平衡
3.2 Set
1.元素的键值就是实值，不需要构造键值对，迭代器只读
2.值自动排序，默认按照小于来比较
3.不允许相同的值
4.底层是红黑树
5.元素不可以重复(因此可以使用set进行去重)
3.3 map
1.所有的元素都是键值和实值的pair，迭代器可读写word，但key只读且唯一
2.不允许相同键值
3.键值自动排序，默认按照小于的方式对key进行比较
4.底层是红黑树
5.支持[]操作符，operator[]中实际进行插入查找。
3.3 multiset
set（insert_unique)+允许键值重复:insert_equal
3.4 multimap
map（insert_unique)+允许键值重复:insert_equal
4.hashtable
参考：
原文：https://blog.csdn.net/u013299585/article/details/78323973
https://blog.csdn.net/caojunhao123/article/details/11907857