| 顺序容器 | 有序关联容器 | 无序关联容器 | 容器适配器 | |
|---|---|---|---|---|
| 特点 | 1、只有实值 | |||
| 2、不涉及排序 | ||||
| 3、通过元素在容器的位置顺序存储和访问元素 | 1、键值对（key，val） | |||
| 2、内部自动排序 | ||||
| 3、通过键存储和读取 | ||||
| 4、 | 1、键值对（key，val） | |||
| 2、内部自动排序 | ||||
| 3、通过键存储和读取 | ||||
| 容器 | 1、array | |||
| 2、vector | ||||
| 3、deque | ||||
| 4、list | ||||
| 5、forward_list | 1、map(元素唯一) | |||
| 2、set(元素唯一) | ||||
| 3、multimap(元素可重复) | ||||
| 4、multiset(元素可重复) | 1、unordered_map | |||
| 2、unordered_set | ||||
| 1、stack | ||||
| 2、queue | ||||
| 3、priority_queue | ||||
| 底层 | 红黑树 | 散列表 |
有Multi和没Multi的区别：元素是否可以重复
set类型和map类型的区别：
| 类型 | 名称和迭代器 | 数据结构 | 特点 | 迭代器失效 | 插入 | 删除 | 查找 | 场景 | |
|---|---|---|---|---|---|---|---|---|---|
| 顺序 | array | 数组、顺序 | 固定长度 | 无 | 无 | O（1） | 类似vector，比数组更安全（不担心越界），但是内容在栈上，且属于定长容器。 | ||
| 顺序 | string | 字符串、顺序、随机访问 | 插入失效，删除不会 | 尾端O（1） | |||||
| 非尾端P：O（N-P） | 尾端O（1） | ||||||||
| 非尾端P：O（N-P） | O（1） | 类似vector，但是string删除元素不会释放空间（为了下次操作方便） | |||||||
| 顺序 | vector | 向量、顺序、随机访问 | 连续存储的数组形式（一端开口的组） | 获取元素效率很高，插入和删除的效率很低 | 插入和删除都会失效 | 尾端O（1） | |||
| 非尾端P：O（N-P） | 尾端O（1） | ||||||||
| 非尾端P：O（N-P） | O（1） | 需要快速查找，不需要频繁插入/删除 | |||||||
| stack | 栈（容器适配器） | 不支持迭代器 | 只能尾端入：O（1） | 只能尾端删除：O（1） | 不支持 | FILO（先进后出）底层容器可以是list或vector或deque。 | |||
| map | 映射/多重映射(有序关联）双向 | 红黑树 | 1.键和值分开（模版有两个参数，前面是键后面是值）2.键唯一3.元素默认按键的升序排列 | 插入不失效。删除时只是被删除节点的迭代器失效，但迭代器返回void，所以需要保存删除前迭代器位置。 | O(logN) | O(logN) | O(logN) | 需要key有序将值关联到key，查找/删除/插入性能一样 | |
| multimap | 映射/多重映射(有序关联）双向 | 红黑树 | 1.键和值分开2.键可以不唯一3.元素默认按键的升序排列 | 插入不失效。删除时只是被删除节点的迭代器失效，但迭代器返回void，所以需要保存删除前迭代器位置。 | O(logN) | O(logN) | O(logN) | 需要key有序将值关联到key，查找/删除/插入性能一样 | |
| set | 集合/多重集合（有序关联）双向 | 红黑树（平衡检索二叉树） | 1.键（关键字）和值（数据）相等（就是模版只有一个参数，键和值合起来）2.键唯一3.元素默认按升序排列 | 插入不失效。删除时只是被删除节点的迭代器失效，但迭代器返回void，所以需要保存删除前迭代器位置。 | O(logN) | O(logN) | O(logN) | 需要key有序将值关联到key，查找/删除/插入性能一样 | |
| multiset | 集合/多重集合（有序关联）双向 | 红黑树 | 1.键和值相等2.键可以不唯一3.元素默认按升序排列 | 插入不失效。删除时只是被删除节点的迭代器失效，但迭代器返回void，所以需要保存删除前迭代器位置。 | O(logN) | O(logN) | O(logN) | 需要key有序将值关联到key，查找/删除/插入性能一样 | |
| unordered_map | 无序集合（无序关联/哈希表）单向 | 插入删除失效 | 平均情况：O（1） | ||||||
| 最差情况：O（N） | 平均情况：O（1） | ||||||||
| 最差情况：O（N） | 平均情况：O（1）最差情况：O（N） | 内存使用比有序的高一下，但是查找速度更快。只有哈希函数太差或者发生哈希重建才会退化为O（N）。但是一般很少发生，均摊还是O（1）。 | |||||||
| unordered_set | 无序映射（无序关联/哈希表）单向 | 插入删除失效 | 平均情况：O（1） | ||||||
| 最差情况：O（N） | 平均情况：O（1） | ||||||||
| 最差情况：O（N） | 平均情况：O（1）最差情况：O（N） | 内存使用比有序的高一下，但是查找速度更快。只有哈希函数太差或者发生哈希重建才会退化为O（N）。但是一般很少发生，均摊还是O（1）。 | |||||||
| 顺序 | deque | 双向队列、顺序、随机访问 | 连续或分段连续存储数组（两端开口的数组） | 获取元素效率较高，插入和删除的效率较高 | 插入失效。删除头和尾元素，指向被删除节点迭代器失效，而删除中间元素会使所有迭代器失效 | 首尾端：O（1） | |||
| 非首尾P：O（min（p， N-P）） | 首尾端：O（1） | ||||||||
| 非首尾P：O（min（p， N-P）） | O（1） | 头尾增删元素很快，随机访问比vector慢一点，因为内部处理堆跳转。中间插入和删除效率交较高。因为他是list和vector综合的样子。使用较少 | |||||||
| 顺序 | list | 列表容器、顺序、双向 | 双向环状链表 | 获取元素效率很低，插入和删除的效率很高 | 插入不失效，被删除节点自身失效。 | O（1） | O（1） | O（N） | 需要频繁插入/删除，不需要快速查找 |
| 顺序 | forward_list | 前向列表、顺序、单向 | 插入不失效，被删除节点自身失效。 | O（1） | O（1） | O（N） | 需要list的优势，但只要向前迭代 | ||
| queue | 队列（容器适配器） | 不支持迭代器 | 只能尾端入：O（1） | 只能首端删除：O（1） | 不支持 | FIFO（先进先出）。底层容器可以是list或deque。 | |||
| priority_queue | 优先、队列（容器适配器） | 不支持迭代器 | 只能尾端入：O（1） | 只能首端删除：O（1） | 不支持 | FIFO（先进先出）。底层容器可以是vector或deque。 |