第十四章 标准模板库(STL)

STL 是“Standard Template Library”的缩写，中文译为“标准模板库”。STL 是 C++ 标准库的一部分，不用单独安装。

STL是一套功能强大的 C++ 模板类，提供了通用的模板类和函数，借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。例如，vector 的底层为顺序表（数组），list 的底层为双向链表，deque 的底层为循环队列，set 的底层为红黑树，hash_set 的底层为哈希表。

C++ 标准模板库的核心包括以下三个组件(component)：

组件	描述
容器（Containers）	容器可以看成是数组的拓展，是用来管理某一类对象的集合。C++ 提供了各种不同类型的容器，比如 栈(stack)、队列(queque)、链表(list)、向量(vector)、映射(map) 等。
算法（Algorithms）	算法作用于容器。它们提供了执行各种操作的方式，包括对容器内容执行初始化、排序、搜索和转换等操作。
迭代器（iterators）	迭代器可以认为是容器的”专用指针”，来表示数据位置，用于存取数据，遍历对象集合的元素。这些集合可能是容器，也可能是容器的子集。

STL（Standard Template Library）中的容器主要分为两大类：顺序容器和关联容器。

1. 顺序容器（Sequence Containers）

顺序容器用于按顺序存储数据，支持通过索引或迭代器访问元素，通常元素在内存中是连续存储的。常用的顺序容器包括：

C++ 序列式容器详细对比表

特性 / 容器	vector	deque	list	forward_list	array
是否动态大小	✅ 是	✅ 是	✅ 是	✅ 是	❌ 固定
底层结构	连续内存	分段连续内存	双向链表	单向链表	静态数组封装
随机访问	✅ 支持	✅ 支持	❌ 不支持	❌ 不支持	✅ 支持
尾部插入/删除	✅ 高效	✅ 高效	✅ 高效	✅ 高效	❌ 不支持
头部插入/删除	❌ 慢	✅ 高效	✅ 高效	✅ 高效	❌ 不支持
中间插入/删除	❌ 慢	❌ 慢	✅ 高效	✅ 高效	❌ 不支持
迭代器类型	随机访问	随机访问	双向	单向	随机访问
大小可变性	✅ 动态	✅ 动态	✅ 动态	✅ 动态	❌ 固定
安全访问 .at()	✅ 支持	✅ 支持	❌ 不支持	❌ 不支持	✅ 支持
STL 算法兼容	✅ 完全	✅ 完全	✅ 完全	✅ 完全	✅ 完全
使用建议	大量数据，需随机访问	首尾频繁插入删除	中间频繁插入删除	节省空间，单向遍历	固定小数组
C++ 引入版本	C++98	C++98	C++98	C++11	C++11

顺序容器的特点是元素的存储位置与插入顺序有关，适合需要按照顺序访问元素的场景。

2. 关联容器（Associative Containers）

关联容器用于通过键来存储数据，通常是通过树或哈希表实现的。这类容器自动根据键的顺序（有序）或哈希值（无序）来管理数据。常用的关联容器包括：

C++ 所有关联式容器对比表（有序 vs 无序）

容器	是否有序	键是否唯一	键值结构	底层结构	查找效率	插入效率	删除效率	迭代器类型	典型用途
set	✅ 有序	✅ 是	仅键	红黑树	O(log n)	O(log n)	O(log n)	双向迭代器	唯一集合
multiset	✅ 有序	❌ 否	仅键	红黑树	O(log n)	O(log n)	O(log n)	双向迭代器	统计频次
map	✅ 有序	✅ 是	Key → Value	红黑树	O(log n)	O(log n)	O(log n)	双向迭代器	键值映射
multimap	✅ 有序	❌ 否	Key → Value	红黑树	O(log n)	O(log n)	O(log n)	双向迭代器	一键多值
unordered_set	❌ 无序	✅ 是	仅键	哈希表	O(1)*	O(1)*	O(1)*	前向迭代器	快速去重
unordered_multiset	❌ 无序	❌ 否	仅键	哈希表	O(1)*	O(1)*	O(1)*	前向迭代器	无序多重集合
unordered_map	❌ 无序	✅ 是	Key → Value	哈希表	O(1)*	O(1)*	O(1)*	前向迭代器	高性能映射
unordered_multimap	❌ 无序	❌ 否	Key → Value	哈希表	O(1)*	O(1)*	O(1)*	前向迭代器	多值哈希表

*注：哈希表的操作效率为平均 O(1)，最坏情况可能退化为 O(n)。

关联容器适合需要快速查找、插入、删除特定键的场景。

这两类容器的主要区别在于存储和访问元素的方式：顺序容器强调顺序性，关联容器则侧重通过键进行高效查找和管理。

3、容器适配器（Container Adapters）

对现有容器（如 deque、vector、list）的封装，提供特定用途的接口：

C++ 容器适配器详细对比表

容器适配器 / 特性	stack	queue	priority_queue
底层容器（默认）	deque	deque	vector
数据结构类型	栈（后进先出 LIFO）	队列（先进先出 FIFO）	优先队列（堆结构，最大/最小堆）
主要操作	push, pop, top	push, pop, front, back	push, pop, top
支持随机访问迭代器	❌ 不支持	❌ 不支持	❌ 不支持
元素访问顺序	后进先出	先进先出	优先级顺序（最大元素先出）
是否允许遍历迭代器	❌ 不支持	❌ 不支持	❌ 不支持
时间复杂度（push/pop）	O(1)	O(1)	O(log n)
是否支持自定义底层容器	✅ 支持（默认 deque，也可用 vector/list）	✅ 支持（默认 deque，也可用 list）	✅ 支持（默认 vector）
典型用途	函数调用栈、撤销操作	任务调度、消息队列	事件驱动、优先级任务管理
C++ 引入版本	C++98	C++98	C++98

4：常用容器函数

C++ 常用容器函数使用对照表

函数名	示例代码	功能说明	适用容器	备注
push_back()	v.push_back(10);	在尾部插入元素	vector, deque, list	常用插入操作
push_front()	dq.push_front(5);	在头部插入元素	deque, list, forward_list	vector 不支持
pop_back()	v.pop_back();	删除尾部元素	vector, deque, list	无返回值
pop_front()	dq.pop_front();	删除头部元素	deque, list, forward_list	vector 不支持
insert()	v.insert(v.begin()+2, 99);	在指定位置插入	vector, deque, list, set, map	set/map 的 insert 是按键插入
erase()	v.erase(v.begin()+1);	删除指定位置/键	所有容器（forward_list 除外）	list/set/map 用迭代器
at()	v.at(3);	安全访问元素（带边界检查）	vector, deque, array	抛出 out_of_range 异常
operator[]	v[2] = 8;	访问或赋值元素	vector, deque, array, map	map 自动插入键
find()	s.find(42)	查找元素是否存在	set, map, unordered_*	返回迭代器
count()	s.count(42)	统计元素出现次数	set, map, unordered_*	map最多为1，multimap可大于1
emplace()	v.emplace_back(10);	原地构造并插入	几乎所有容器	C++11 引入，优于 push_back
front()	v.front();	访问首元素	vector, deque, list	不能用于空容器
back()	v.back();	访问尾元素	vector, deque, list	不能用于空容器
sort()	sort(v.begin(), v.end());	对容器排序	vector, deque, array	需 `` 头文件
size()	v.size();	返回元素个数	所有容器（forward_list 除外）	forward_list 无 size()
empty()	v.empty();	判断容器是否为空	所有容器	返回布尔值
clear()	v.clear();	清空容器内容	所有容器	不释放内存
resize()	v.resize(10);	改变容器大小	vector, deque, string	多用于补零或截断
begin()/end()	for(auto it = v.begin(); it != v.end(); ++it)	获取迭代器范围	所有容器	适配 STL 算法