STL的对比
| 容器类型 | 底层数据结构 | 元素存储特点 | 访问方式 | 是否支持随机访问 | 动态大小调整 | 典型应用场景 |
|---|---|---|---|---|---|---|
vector |
动态数组 (连续内存) | 按加入顺序连续存储 | 下标访问 ([]) |
是 | 是 | 动态数组的替代，快速随机访问，大量数据按顺序存取。 |
deque |
分段连续内存 | 按加入顺序存储（分段实现） | 双向访问（头尾操作快） | 是 | 是 | 需要快速在首尾插入与删除，而仍然支持随机访问的场景。 |
list |
双向链表 | 不连续，每个元素存储指针 | 双向遍历 | 否 | 是 | 频繁插入/删除操作的场景，尤其在需要中间修改的情况下。 |
forward_list |
单向链表 | 不连续，只有前向指针 | 单向遍历 | 否 | 是 | 内存占用较小的场景，在对链表操作需求简单时用作优化。 |
array |
静态数组 (固定大小) | 按加入顺序连续存储 | 下标访问 ([]) |
是 | 否 | 小容量、固定大小、性能关键的场景，避免动态分配。 |
set |
平衡二叉搜索树（通常是 Red-Black 树） | 按键值自动排序 | 基于 key 查找和遍历 | 否 | 是 | 唯一值的集合，不允许重复值，支持快速有序的查找和插入。 |
multiset |
平衡二叉搜索树 | 按键值自动排序 | 基于 key 查找和遍历 | 否 | 是 | 允许重复值的集合，多次插入同一值场景（按顺序存储）。 |
map |
平衡二叉搜索树 | 按键值自动排序 | 基于 key 查找 | 否 | 是 | 有序的键值对储存，适合频繁按 key 查找具体值的场景。 |
multimap |
平衡二叉搜索树 | 按键值自动排序 | 基于 key 查找 | 否 | 是 | 允许同一键值存在多个映射值的场景。 |
unordered_set |
哈希表 | 无序存储 | 常数时间 key 查找 | 否 | 是 | 唯一值的集合，但无需排序，适合大量 key 快速判断是否存在的场景。 |
unordered_multiset |
哈希表 | 无序存储 | 常数时间 key 查找 | 否 | 是 | 允许重复值的集合，但无序存储，适合大数据去重分析场景。 |
unordered_map |
哈希表 | 无序存储 | 常数时间 key-value 查找 | 否 | 是 | 可快速通过 key 查找 value 的场景（无需排序）。 |
unordered_multimap |
哈希表 | 无序存储 | 常数时间 key 查找 | 否 | 是 | 允许同一个 key 存储多个值（无需排序）的场景。 |
stack |
基于 deque 实现 |
后进先出 (LIFO) | 只访问顶端 (top) |
否 | 是 | 后进先出的场景，比如函数调用栈、括号匹配等。 |
queue |
基于 deque 实现 |
先进先出 (FIFO) | 只访问头部和尾部 | 否 | 是 | 先进先出的场景，比如任务排队、消息队列等。 |
priority_queue |
基于堆实现 | 按优先级排序 | 访问最大（默认情况）值 | 否 | 是 | 按优先级任务调度、动态获取最大/最小值的场景。 |
bitset |
定长的位数组 | 每个位存储 true/false | 位访问 ([]) |
是 | 否 | 高效存储和操作布尔值，适合空间和位运算优化场景。 |
1. 底层数据结构
- 动态数组：元素连续存放且可动态扩展的数组。
- 链表：使用指针将元素链接而成的结构，可分为单向链表与双向链表。
- 平衡二叉树：自平衡的二叉搜索树，常用的是红黑树（Red-Black Tree）。
- 哈希表：以哈希函数作为索引，通过哈希冲突解决机制（如拉链法）高效存储数据。
- 堆：通常是二叉堆，支持动态调整以保证堆顶始终是最大值或最小值。
2. 元素存储特点
- 连续存储：
vector和array采用连续存储，内存紧凑，随机访问快。 - 分段连续存储：
deque分段实现，以保证在头尾添加数据的高效性。 - 不连续存储：
list、forward_list、set等采用链表或树结构，插入/删除效率高，但随机访问速度较慢。
3. 访问方式
- 下标访问 (
[])：vector、array支持随机访问，可迅速获取指定位置的元素。 - 头尾访问：
stack和queue限制为某些特定操作。 - 优先访问：
priority_queue只能访问堆顶元素（最大值/最小值）。 - 基于 key 访问：
map、unordered_map以键值对方式支持查找。
4. 是否支持随机访问
- 支持随机访问的容器（如
vector、array、deque等）提供 O(1) 复杂度的下标访问，操作简单。 - 不支持随机访问的容器（如
list、set等）需要遍历或依赖搜索结构，访问效率较低。
5. 动态大小调整
- 动态容器（如
vector、deque、list）可以根据元素数目动态分配或收缩内存。 - 静态容器（如
array）在定义时需指定固定大小。
6. 应用场景
每种容器都有其典型应用场景，选择合适的容器取决于业务需求（如性能、顺序性、查找效率）。
根据需求选择不同容器：
- 需要快速随机访问：使用
vector、array。 - 需要频繁插入和删除：使用
list、deque（插入和删除表现良好）。 - 需要数据自动排序：使用
set、multiset（有序集合）或map、multimap（有序键值对）。 - 需要快速查找，不关心顺序：优先选择哈希容器，比如
unordered_set和unordered_map。 - 使用栈或队列模型：考虑
stack、queue或priority_queue。