C++ 标准容器 STL
C++ 标准容器 STL
STL 清单
1. 序列式容器
| 容器 | 头文件 | 逻辑结构 | 默认底层容器 | 特点 | operator[] | 常用频率 |
|---|---|---|---|---|---|---|
std::vector | <vector> | 动态数组 | 连续内存块 | 随机访问 O(1)，尾部增删 O(1)，中间插入删除 O(n)，内存连续缓存友好 | ✅ 支持（随机访问 O(1)） | ⭐⭐⭐⭐⭐ (极高) |
std::deque | <deque> | 双端队列 | 分段连续数组 | 首尾增删 O(1)，支持随机访问 O(1)，中间插入删除 O(n)，内存非完全连续 | ✅ 支持（随机访问 O(1)） | ⭐⭐⭐ (中等) |
std::list | <list> | 双向链表 | 离散节点+双向指针 | 任意位置插入删除O(1)，不支持随机访问，遍历较慢，内存开销大 | ❌ 不支持（非随机访问迭代器） | ⭐⭐ (较低) |
std::forward_list | <forward_list> | 单向链表 | 离散节点+单向指针 | 仅支持前向遍历，头部插入O(1)，比list更省内存，无size()方法 | ❌ 不支持（非随机访问迭代器） | ⭐ (极低) |
std::array | <array> | 固定大小数组 | 栈上连续内存 | 编译期确定大小，零开销抽象，支持STL接口和边界检查(at)，不可动态扩容 | ✅ 支持（随机访问 O(1)） | ⭐⭐⭐⭐ (高) |
2. 有序关联式容器
| 容器 | 头文件 | 逻辑结构 | 默认底层容器 | 特点 | operator[] | 常用频率 |
|---|---|---|---|---|---|---|
std::set | <set> | 有序唯一集合 | 红黑树 | 元素自动排序且唯一，查找/插入/删除 O(log n)，支持范围查询 | ❌ 不支持（无 Key-Value 结构） | ⭐⭐⭐⭐ (高) |
std::multiset | <set> | 有序可重复集合 | 红黑树 | 允许重复元素，其余同 set，count() 返回重复次数 | ❌ 不支持（无 Key-Value 结构） | ⭐⭐ (较低) |
std::map | <map> | 有序键值对映射 | 红黑树 | Key 唯一且自动排序，Value 通过 Key 访问，查找/插入 O(log n) | ✅ 支持（按 Key 访问，不存在则插入，O(log n)） | ⭐⭐⭐⭐⭐ (极高) |
std::multimap | <map> | 有序可重复键映射 | 红黑树 | 允许重复 Key，需用 equal_range() 获取所有匹配项 | ❌ 不支持（Key 不唯一，语义不明确） | ⭐ (极低) |
3. 无序关联式容器
| 容器 | 头文件 | 逻辑结构 | 默认底层容器 | 特点 | operator[] | 常用频率 |
|---|---|---|---|---|---|---|
std::unordered_set | <unordered_set> | 无序唯一集合 | 哈希表 | 平均查找/插入 O(1)，最坏 O(n)，元素无序，需自定义哈希函数 | ❌ 不支持（无 Key-Value 结构） | ⭐⭐⭐⭐ (高) |
std::unordered_multiset | <unordered_set> | 无序可重复集合 | 哈希表 | 允许重复元素，平均 O(1) 操作，无序 | ❌ 不支持（无 Key-Value 结构） | ⭐ (极低) |
std::unordered_map | <unordered_map> | 无序键值对映射 | 哈希表 | Key 唯一，平均查找 O(1)，高频查找场景首选，无序 | ✅ 支持（按 Key 访问，不存在则插入，平均 O(1)） | ⭐⭐⭐⭐⭐ (极高) |
std::unordered_multimap | <unordered_map> | 无序可重复键映射 | 哈希表 | 允许重复 Key，平均 O(1) | ❌ 不支持（Key 不唯一，语义不明确） | ⭐ (极低) |
4. 容器适配器
| 容器 | 头文件 | 逻辑结构 | 默认底层容器 | 特点 | operator[] | 常用频率 |
|---|---|---|---|---|---|---|
std::stack | <stack> | 栈(LIFO) | std::deque | 后进先出，仅暴露 push/pop/top，无迭代器，不可遍历 | ❌ 不支持（仅顶部访问，无随机访问语义） | ⭐⭐⭐⭐ (高) |
std::queue | <queue> | 队列(FIFO) | std::deque | 先进先出，仅暴露 push/pop/front/back，无迭代器 | ❌ 不支持（仅首尾访问，无随机访问语义） | ⭐⭐⭐⭐ (高) |
std::priority_queue | <queue> | 优先队列(堆) | std::vector | 出队始终为最大/最小元素，基于二叉堆实现，无迭代器 | ❌ 不支持（仅顶部访问，堆结构不允许随机下标访问） | ⭐⭐⭐ (中等) |
5. C++ 23 扁平关联容器
| 容器 | 头文件 | 逻辑结构 | 默认底层容器 | 特点 | operator[] | 常用频率 |
|---|---|---|---|---|---|---|
std::flat_set | <flat_set> | 排序唯一集合 | std::vector | 连续内存+二分查找，缓存友好，中小数据量优于红黑树 set | ❌ 不支持（无 Key-Value 结构） | ⭐⭐ (新特性) |
std::flat_multiset | <flat_set> | 排序可重复集合 | std::vector | 同上，允许重复元素 | ❌ 不支持（无 Key-Value 结构） | ⭐ (新特性) |
std::flat_map | <flat_map> | 排序键值对映射 | std::vector<pair> | Key-Value 分离存储或配对存储，缓存命中率远高于 std::map | ✅ 支持（按 Key 访问，不存在则插入，O(log n)） | ⭐⭐ (新特性) |
std::flat_multimap | <flat_map> | 排序可重复键映射 | std::vector<pair> | 同上，允许重复 Key | ❌ 不支持（Key 不唯一，语义不明确） | ⭐ (新特性) |