顺序容器
可顺序访问的数据结构。
| 容器 | 数据结构 |
|---|---|
| vector | 数组 |
| deque | 数个缓冲区相接，由一个中央控制器管理 |
| list | 双向链表 |
比较
- 随机访问
- vector：支持快速随机访问，一次指针解引用
- deque：支持随机访问，两次指针解引用（中央控制器和缓冲区两次）
- list：不支持随机访问
- 内存管理：
- vector：扩充时须将所有的元素拷贝到新位置
- deque：按需扩充一个缓冲区大小，无需拷贝
- list：为各节点单独分配内存
- 增删元素：
- vector：在尾部可快速增删，中间插入会导致之后的元素拷贝
- deque：在头尾可快速增删，中间插入会导致元素拷贝
- list：在任意位置都可快速增删
关联容器
可快速查找（ \(O(logN)\) ）的容器，且可按键排序。
| 容器 | 数据结构 | 集合内容 | 键是否唯一 |
|---|---|---|---|
| set | 红黑树 | 键 | 是 |
| map | 红黑树 | 键值对 | 是 |
| multiset | 红黑树 | 键 | 否 |
| multimap | 红黑树 | 键值对 | 否 |
关联容器底层数据结构均为红黑树，因为红黑树性能平均下来最好，也因此这四个容器行为类似，一般操作时间复杂度一般均为 \(O(logN)\)，差别仅在于是键集合还是键值对集合，以及键是否可重复。
无序关联容器
从 C++11 开始提供的可快速查找（均摊 \(O(1)\)，最坏 \(O(n)\) ）的无序容器。
| 容器 | 数据结构 | 集合内容 | 键是否唯一 |
|---|---|---|---|
| unordered_set | 哈希表 | 键 | 是 |
| unordered_map | 哈希表 | 键值对 | 是 |
| unordered_multiset | 哈希表 | 键 | 否 |
| unordered_multimap | 哈希表 | 键值对 | 否 |
相对于关联容器，上层行为表现一致，底层数据结构更换为了哈希表获得了更好的均摊性能，但同时付出了不可按序访问的代价。
容器适配器
在其他容器的接口上进行封装和改写实现。
| 容器 | 默认底层容器 | 描述 |
|---|---|---|
| stack | deque | 堆栈，后进先出（LIFO） |
| queue | deque | 队列，先进先出（FIFO） |
| priority_queue | vector | 优先队列 |
stack 和 queue 默认用 deque 实现为了让当数据量很大时，不会因元素移动导致过多的时间消耗。而 priority_queue 利用 vector 则是因为为了实现优先队列用到了 heap 相关的函数，其中用到了大量的随机访问。