3.STL (标准库)容器盘点
2026-10-06 22:02:52
发布于:浙江
导言:
C++ 标准模板库(Standard Template Library,简称:STL)自 1994 年被纳入 C++ 标准以来,已成为现代 C++ 编程的基石。它用泛型编程的思想,把"数据结构"与"算法"从具体类型中解放出来,然而,STL 的容器繁多、版本迭代频繁.面对如此庞大的体系,初学者容易"记了 vector 忘了 deque为此我以底层逻辑分成大板块,供大家参考。
1.序列容器(Sequence Containers)
按线性顺序存储,元素位置由插入顺序决定。
| 容器 | 底层结构 | 内存连续 | 随机访问 | 头插 | 尾插 | 中间插删 | 查找 | C++版本 |
|---|---|---|---|---|---|---|---|---|
| array | 固定数组 | ✅ | O(1) | ❌ | ❌ | ❌ | O(n) | C++11 |
| vector | 动态数组 | ✅ | O(1) | O (n) | 均摊O(1) | O(n) | O (n) | C++98 |
| deque | 分段连续数组 | 分段 | O(1) | O(1) | O(1) | O(n) | O(n) | C++98 |
| list | 双向链表 | ❌ | ❌ | O(1) | O(1) | O(1) | O(n) | C++98 |
| forward_list | 单向链表 | ❌ | ❌ | O(1) | ❌ | O(1) | O(n) | C++11 |
头文件: <array> <vector> <deque> <list> <forward_list>
2.有序关联容器(Ordered Associative Containers)
基于红黑树,元素自动排序,查找O(log n)。
| 容器 | 键唯一 | 键值对 | 自动排序 | 查找 | 插入 | 删除 | C++版本 |
|---|---|---|---|---|---|---|---|
| set | ✅ | ❌ | ✅ | O(log n) | O(log n) | O(log n) | C++98 |
| multiset | ❌ | ❌ | ✅ | O(log n) | O(log n) | O(log n) | C++98 |
| map | ✅ | ✅ | ✅ | O(log n) | O(log n) | O(log n) | C++98 |
| multimap | ❌ | ✅ | ✅ | O(log n) | O(log n) | O(log n) | C++98 |
头文件: <set> <map>
特点: 支持范围查询(lower_bound / upper_bound / equal_range),迭代器稳定。
3.无序关联容器(Unordered Associative Containers)
基于哈希表,元素不排序,平均查找O(1)。
| 容器 | 键唯一 | 键值对 | 自动排序 | 平均查找 | 最坏查找 | C+ +版本 |
|---|---|---|---|---|---|---|
| unordered_set | ✅ | ❌ | ❌ | O(1) | O(n) | C++11 |
| unordered_multiset | ❌ | ❌ | ❌ | O(1) | O(n) | C++11 |
| unordered_map | ✅ | ✅ | ❌ | O(1) | O(n) | C++11 |
| unordered_multimap | ❌ | ✅ | ❌ | O(1) | O(n) | C++11 |
头文件: <unordered_set> <unordered_map>
特点 : 需要自定义 hash 和 equal_to;支持 bucket_count / load_factor / rehash。
4.容器适配器(Container Adaptors)
对底层容器封装,提供受限接口。
| 适配器 | 默认底层 | 可替换底层 | 访问模式 | 主要操作 | C++版本 |
|---|---|---|---|---|---|
| stack | deque | vector / list / deque | 后进先出LIFO | push / pop / top | C++98 |
| queue | deque | list / deque | 先进先出 FIFO | push / pop / front / back | C++98 |
| priority_queue | vector | vector / deque | 堆序(默认大顶堆) | push / pop / top | C++98 |
头文件: <stack> <queue>
注意: priority_queue 底层用 vector + make_heap / push_heap / pop_heap 实现。
5.C++23 新增 & 特殊容器(Modern / Special Containers)
| 容器 | 底层结构 | 分类 | 内存连续 | 查找 | 特点 | C++版本 |
|---|---|---|---|---|---|---|
| flat_set | 有序数组 | 关联(扁平) | ✅ | O(log n) | 缓存友好,读多写少 | C++23 |
| flat_multiset | 有序数组 | 关联(扁平) | ✅ | O(log n) | 键可重复 | C++23 |
| flat_map | 有序数组 | 关联(扁平) | ✅ | O(log n) | 键值对,缓存友好 | C++23 |
| flat_multimap | 有序数组 | 关联(扁平) | ✅ | O(log n) | 键可重复 | C++23 |
| bitset | 位数组 | 特殊 | ✅ | O(1) | 固定长度位集合 | C++98 |
| string | 动态字符数组 | 特殊 | ✅ | O(n) | 字符序列 | C++98 |
| span | 非拥有视图 | 视图 | --- | O(1) | 数组/容器视图 | C++20 |
| mdspan | 非拥有视图 | 视图 | --- | O(1) | 多维数组视图 | C++23 |
头文件: <flat_set> <flat_map> <bitset> <string> <span> <mdspan>
上一期:

这里空空如也



















有帮助,赞一个