STL标准库中一共有 7 种序列容器， 4 种关联容器， 4 种无序关联容器(C++11新增)
首先明确定义：什么是容器？
- 容器是存储其他对象的对象
- 容器贯彻了C++泛型编程的思想，结合OOP理念
- 底层实现：类与模板
- 忘记了可以来开天辟地（bushi）C++笔记
- 注意，在不加其他限制措施的情况下，任何STL容器都不提供任何强度的线程安全保证
序列容器
序列的基本方法：
| 方法 | 含义 | 备注 |
|---|---|---|
| insert() | 插入一个对象 | |
| erase() | 删除一个对象 | 需要传入迭代器 |
| clear() | 清空序列内容 |
- 元素按照线性顺序排列
- vector
动态数组
- 支持随机访问且速度较快
- 可以根据数组长度动态申请内存大小
- 在尾部添加和删除元素的时候是固定时间复杂度
- 在头部添加和删除元素的时候是线性时间复杂度
- 可反转
- deque
双端队列
- 支持随机访问
- 在首位添加或删除元素的时候是固定时间复杂度（效率低于vector）
- 可反转
- list
双向链表
- 不支持随机访问
- 任意插入或删除都是线性时间复杂度
- 存在sort成员函数
- forward
单向链表
- 不支持随机访问
- 不可反转
- 在C++11后提供
- queue
队列
- 性质如其名
- 为deque的封装
- priority_queue
pq(greater ) 优先队列
- 底层使用堆实现
- 队列内数据有序
- 性质如其名
- stack
栈
- 性质如其名
- 为deque的封装
关联容器
- 保存k-v数据
- 元素保存有序
- 查询性能和插入性能较稳定，一般为log级
- 一般底层使用树存储
- set
集合容器
- 没有kv，k就是v
- 可反转
- 可排序，默认升序
- 键唯一，不可重复
- 提供交并差运算(略复杂)
- multiset
多重集合
- 在set的基础上允许重复
- map 映射
- k-v结构，键不可重复
- 查询和插入都是稳定的log(n)
- 可反转，有排序
- multimap 多重映射
- 在map的基础上允许重复
无序关联容器（哈希容器）
- 保存k-v数据
- 元素保存无序
- 查询与插入性能优异，一般为O(1)
- 遍历性能较差
- 底层使用哈希存储
- unordered_map 哈希组织的map
- unordered_map是如何解决哈希冲突的？
首先明确 unordered_map底层采用的是开链法，即，如果发生哈希冲突，会在当前节点初始化一链表，并将当前数据插在链表的头部，因此每一次插入的时间复杂度仍然为O(1)。
在极限情况下，哈希表会退化为链表，此时引入概念：
负载因子(load_factor)：
hashtable的元素个数和hashtable的桶数间的比值
即load_factor=(float)map.size()/map.buck_count();
最大负载因子(max_load_factor):负载因子的上限
当load_factor>=max_load_factor(调用max_load_factor方法可以得最大负载因子默认为1)时，发生rehash
unordered_set 哈希组织的set
unordered_multimap 哈希组织的mulitmap，key可重复出现
unordered_multiset 哈希组织的multiset，key可重复出现