3.STL (标准库)容器大盘点

明月清风(互关)

2026-10-08 20:45:23

发布于：浙江

25阅读

0回复

0点赞

导言：

C++ 标准模板库（Standard Template Library，简称：STL）自 1994 年被纳入 C++ 标准以来，已成为现代 C++ 编程的基石。它用泛型编程的思想，把"数据结构"与"算法"从具体类型中解放出来，然而，STL 的容器繁多、版本迭代频繁.面对如此庞大的体系，初学者容易"记了 vector 忘了 deque为此我以底层逻辑分成 $5$ 大板块，供大家记忆参考。

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