Appearance
第1章 STL 标准模板库总览
在 C++ 编程中，STL（Standard Template Library，标准模板库）是不可或缺的工具集，它封装了大量通用的数据结构和算法，遵循"泛型编程"思想，具有跨平台、高效、可复用的特点，旨在帮助开发者减少重复编码，专注于核心业务逻辑。
🎯 本章学习目标
学完本章，你将能够：
- 说出 STL 的三大核心组成（容器、算法、迭代器）及其作用
- 区分序列式容器、关联式容器、容器适配器三大类
- 掌握 vector、list、deque 三种序列式容器的特点与区别
- 掌握 set、map 系列关联式容器的四种变体及选型方法
- 掌握 stack、queue、priority_queue 三种容器适配器的适用场景
- 理解 pair 的基本用法及其与 map/set 的关系
- 根据实际需求选择最合适的容器进行编程
- 熟练使用各容器的增删改查、遍历等基本操作
- 了解各容器的底层实现原理与性能特点
- 在算法竞赛和日常开发中灵活运用 STL 解决问题
🗺️ 本章知识图谱
STL 标准模板库
├── 三大核心组件
│ ├── 容器（Containers）—— 数据存储的载体
│ ├── 算法（Algorithms）—— 操作数据的方法
│ └── 迭代器（Iterators）—— 容器与算法的桥梁
├── 序列式容器
│ ├── vector（动态数组）
│ ├── list（双向链表）
│ └── deque（双端队列）
├── 关联式容器
│ ├── set 系列
│ │ ├── set（有序、去重）
│ │ ├── unordered_set（无序、去重）
│ │ ├── multiset（有序、可重复）
│ │ └── unordered_multiset（无序、可重复）
│ └── map 系列
│ ├── map（有序、key唯一）
│ ├── unordered_map（无序、key唯一）
│ ├── multimap（有序、key可重复）
│ └── unordered_multimap（无序、key可重复）
├── 容器适配器
│ ├── stack（栈，LIFO）
│ ├── queue（队列，FIFO）
│ └── priority_queue（优先队列）
└── 基础工具
└── pair（键值对基础）一、STL 核心组成
STL 的核心由三大组件构成，三者相互配合，形成完整的开发体系：
- 容器（Containers）：存储数据的载体，决定数据的存储方式和组织形式，是 STL 最常用的部分；
- 算法（Algorithms）：操作容器中数据的方法（如排序、查找、插入、删除），与容器解耦，可灵活适配；
- 迭代器（Iterators）：容器与算法的桥梁，提供统一的元素访问接口，让算法无需关心容器类型。
二、核心容器分类与导航
STL 容器按存储方式和功能，主要分为三大类。
1. 序列式容器
按插入顺序存储，元素位置由插入顺序决定，不依赖元素值：
| 章节 | 容器 | 特点 | 适用场景 | 学习难度 |
|---|---|---|---|---|
| 第2章 | vector（动态数组） | 连续内存，随机访问 O(1)，尾插 O(1)，中间插入 O(n) | 频繁访问、尾部插入删除、需要排序 | ⭐ 入门 |
| 第3章 | list（双向链表） | 非连续内存，任意位置插入删除 O(1)，不支持随机访问 | 频繁修改、无需随机访问 | ⭐⭐ 基础 |
| 第4章 | deque（双端队列） | 分段连续内存，双端操作 O(1)，随机访问 O(1) | 头尾都需要高效操作 | ⭐⭐ 基础 |
2. 关联式容器
按关键字（key）存储，支持快速查找，核心用于去重、映射：
| 章节 | 容器 | 特点 | 适用场景 | 学习难度 |
|---|---|---|---|---|
| 第5章 | set 系列 | 以元素值为关键字，支持去重（部分类型允许重复） | 去重、有序查找、集合操作 | ⭐⭐ 基础 |
| 第6章 | map 系列 | 以键值对（key-value）存储，实现关键字到值的映射 | 关键字映射、通过 key 查找 value | ⭐⭐⭐ 进阶 |
3. 容器适配器
基于其他容器封装，提供特定操作接口，屏蔽多余功能：
| 章节 | 容器 | 特点 | 适用场景 | 学习难度 |
|---|---|---|---|---|
| 第7章 | stack（栈） | 先进后出（LIFO），仅支持栈顶操作 | 括号匹配、递归模拟、逆序输出 | ⭐ 入门 |
| 第8章 | queue（队列） | 先进先出（FIFO），仅支持队尾插入、队头删除 | BFS、任务排队、消息队列 | ⭐ 入门 |
| 第9章 | priority_queue（优先队列） | 按优先级排序，每次取出优先级最高的元素 | TopK 问题、任务调度 | ⭐⭐⭐ 进阶 |
4. 基础工具
| 章节 | 工具 | 特点 | 适用场景 | 学习难度 |
|---|---|---|---|---|
| 第10章 | pair（键值对） | 两个值的组合，支持字典序比较 | 存坐标、存名次+名字、map元素类型 | ⭐ 入门 |
三、🚀 学习路径建议
📌 章序 ≠ 学序：本书章序按容器分类编排（序列式 → 关联式 → 容器适配器 → 基础工具）， 便于同类对比与查阅；下面给出的是按难度由浅入深排列的学习顺序。建议先按学序通读一遍， 之后再按章序查阅、横向对比。
第一阶段：基础入门（建议 2-3 天）
目标：掌握最常用的容器，能解决基础问题
- pair（第10章）—— 最基础的工具，先理解"键值对"概念
- vector（第2章）—— 最常用的序列式容器，掌握连续内存的特点
- stack（第7章）—— 最简单的容器适配器，理解 LIFO 思想
第二阶段：进阶提升（建议 3-4 天）
目标：掌握主要容器类型，能应对大多数算法题
- queue（第8章）—— 理解 FIFO 思想，学习 BFS 应用
- list（第3章）—— 理解链表结构，对比 vector 的差异
- deque（第4章）—— 理解分段连续内存，掌握双端操作
- set 系列（第5章）—— 掌握四种 set 的区别与选型
- map 系列（第6章）—— 掌握键值对映射的用法
第三阶段：深入精通（建议 2-3 天）
目标：掌握高级容器，理解底层原理
- priority_queue（第9章）—— 理解堆结构，掌握 TopK 等经典问题
- 综合练习 —— 多种容器配合使用的复杂场景（第1章实战练习 + 附录 D 综合自测）
四、📊 各容器难度分级与出题频率
| 章节 | 容器 | 难度 | 出题频率 | 常见题型 |
|---|---|---|---|---|
| 第10章 | pair | ⭐ | ★★★☆☆ | 选择题、填空题 |
| 第2章 | vector | ⭐ | ★★★★★ | 选择题、编程题、阅读题 |
| 第7章 | stack | ⭐ | ★★★★☆ | 选择题、编程题（括号匹配） |
| 第8章 | queue | ⭐ | ★★★☆☆ | 选择题、编程题（BFS） |
| 第3章 | list | ⭐⭐ | ★★★☆☆ | 选择题、判断题 |
| 第4章 | deque | ⭐⭐ | ★★☆☆☆ | 选择题、判断题 |
| 第5章 | set | ⭐⭐ | ★★★★☆ | 选择题、编程题、阅读题 |
| 第6章 | map | ⭐⭐⭐ | ★★★★☆ | 选择题、编程题、阅读题 |
| 第9章 | priority_queue | ⭐⭐⭐ | ★★★☆☆ | 选择题、编程题（TopK） |
五、📝 实战练习
本章的 8 道练习题覆盖全书九种容器，题型包括选择题、判断题、程序阅读题与编程题，用于检验"看到问题能否选对容器"这一核心能力。所有题目均配有答案与解析，折叠在题目下方，建议先独立完成再对照。
练习题 1（多选题）
题目： 下列容器中，哪些不支持用下标 [] 随机访问元素？（多选）
A. vector B. deque C. list D. stack
🔑 点击查看答案与解析
答案： C、D
解析： vector 与 deque 都支持随机访问（O(1)），提供 operator[]；list 是双向链表，只能沿指针逐个移动，访问第 k 个元素是 O(n)，不提供 []；stack 是容器适配器，本身就不提供任何随机访问接口（连遍历都不支持）。因此 C、D 两项在事实上均满足"不支持用下标 [] 访问"。若题目限定单选，通常取 list 为标准答案，但严格来说 stack 同样不支持。
练习题 2（选择题）
题目： 需要按 key 快速查找 value，数据量很大（10⁶ 级），且不要求按 key 有序，应优先选择哪个容器？
A. map B. unordered_map C. multimap D. set
🔑 点击查看答案与解析
答案： B
解析： map / set 底层是红黑树，查找 O(log n) 且自动有序；unordered_map 底层是哈希表，平均查找 O(1)，在"不要求有序 + 数据量大"的场景下最快。注意 unordered_* 的最坏情况会退化到 O(n)，但平均表现最好。
练习题 3（选择题）
题目： 关于 priority_queue<int> 的默认行为，下列说法正确的是？
A. 底层容器默认是 vector，默认是大顶堆 B. 底层容器默认是 deque，默认是大顶堆 C. 底层容器默认是 vector，默认是小顶堆 D. 底层容器默认是 list，默认是小顶堆
🔑 点击查看答案与解析
答案： A
解析： priority_queue 的默认声明是 priority_queue<T, vector<T>, less<T>>，底层容器为 vector，比较方式为 less，即大顶堆（堆顶是最大元素）。若要小顶堆需写成 priority_queue<int, vector<int>, greater<int>>。注意 list 不能作底层容器（堆需要随机访问）。
练习题 4（判断题）
题目： stack 和 queue 都提供迭代器，可以用范围 for 遍历所有元素（ ）
🔑 点击查看答案与解析
答案： 错误
解析： stack、queue、priority_queue 均为容器适配器，刻意屏蔽了迭代器，只能访问栈顶 / 队头（priority_queue 只能访问堆顶），不支持遍历。若需要遍历，应直接用底层容器（vector、deque、list 等）。
练习题 5（判断题）
题目： 对于 vector，size() 的返回值一定小于或等于 capacity() 的返回值（ ）
🔑 点击查看答案与解析
答案： 正确
解析： size() 是当前元素个数，capacity() 是当前已分配内存能容纳的元素个数。vector 会预留额外空间以减少扩容次数，因此恒有 size() <= capacity()。reserve(n) 只改 capacity 不改 size，resize(n) 会同时改变 size（必要时也改 capacity）。
练习题 6（判断题）
题目： map 容器中存储的每一个元素，其类型都是 pair<const Key, T>（ ）
🔑 点击查看答案与解析
答案： 正确
解析： map 的元素就是 pair：用 p->first 取 key、p->second 取 value。其中 key 带 const 修饰——不可通过迭代器修改 key，否则会破坏红黑树的有序性；value 可以修改。
练习题 7（程序阅读题）
题目： 阅读以下代码，写出输出结果。
cpp
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main() {
vector<int> v = {3, 1, 2, 1};
set<int> s(v.begin(), v.end());
cout << s.size() << " " << *s.begin() << endl;
return 0;
}🔑 点击查看答案与解析
答案： 3 1
解析： set 由迭代器区间构造时会自动去重 + 升序排序，v 中的 {3,1,2,1} 变为 {1,2,3}，故 s.size() 为 3；s.begin() 指向最小元素，解引用得 1。输出为 3 1。
练习题 8（编程题）
题目： 输入 n 个整数，统计每个整数出现的次数，并按数字从小到大的顺序输出"数字 次数"。请选用最合适的 STL 容器完成。
**输入格式：**两行。第一行一个整数 n，第二行 n 个整数。 **输出格式：**若干行，每行一个整数及其出现次数，用空格隔开，按整数从小到大排列。
样例输入：
7
3 1 4 1 5 9 2样例输出：
1 2
2 1
3 1
4 1
5 1
9 1🔑 点击查看答案与解析
参考代码：
cpp
#include <iostream>
#include <map>
using namespace std;
int main() {
int n;
cin >> n;
map<int, int> mp;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
mp[x]++; // 不存在的 key 会自动插入，value 默认 0
}
for (auto& p : mp) { // map 按 key 升序遍历
cout << p.first << " " << p.second << endl;
}
return 0;
}解析： 本题同时需要"计数"和"按 key 有序输出"，用 map 一步到位——mp[x]++ 自动完成插入与累加，遍历时天然升序，无需再排序。若只计数不要求有序，可改用 unordered_map（平均 O(1)）；若数值范围很小且连续，也可用 vector 计数。
六、📊 考点总结表
| 知识点 | 重要程度 | 出题形式 | 易错点 |
|---|---|---|---|
| STL 三大组件（容器 / 算法 / 迭代器） | ⭐⭐⭐ | 选择题、判断题 | 把迭代器误当作容器的一部分 |
| 序列式 / 关联式 / 容器适配器分类 | ⭐⭐⭐⭐⭐ | 选择题 | 把 stack、queue 误归为序列式容器 |
| 支持随机访问的容器（vector、deque） | ⭐⭐⭐⭐ | 选择题 | 以为 list 也能 [] |
| 有序容器（set/map）vs 无序容器（unordered_*） | ⭐⭐⭐⭐⭐ | 选择题、判断题 | 混淆 O(log n) 与平均 O(1) |
| 去重能力（set/map 系；multiset/multimap 不去重） | ⭐⭐⭐⭐ | 选择题 | 以为 multiset 去重 |
| 适配器屏蔽迭代器，不可遍历 | ⭐⭐⭐⭐ | 判断题 | 试图遍历 stack |
| 容器选型：按需求反推容器 | ⭐⭐⭐⭐⭐ | 选择题、编程题 | 一律用 vector，忽略复杂度 |
| 常见复杂度对照（O(1) / O(log n) / O(n)） | ⭐⭐⭐⭐ | 选择题 | 把 unordered_* 的最坏 O(n) 当成常态 |
┌──────────────────────────────────────────┐ │ STL 容器选型速记卡 │ ├──────────────────────────────────────────┤ │ 要随机访问 + 尾插 → vector │ │ 要头尾都快 → deque │ │ 要中间频繁插删 → list │ │ 要排序 + 去重 → set │ │ 要排序 + 允许重复 → multiset │ │ 要 key→value 映射 → map │ │ 要极致查找、不计顺序 → unordered_map │ │ 要后进先出 → stack │ │ 要先进先出（BFS） → queue │ │ 要每次取最大 / 最小 → priority_queue │ │ 要两个值绑成一组 → pair │ ├──────────────────────────────────────────┤ │ 口诀：查得快用哈希，要有序用红黑树； │ │ 头尾动用 deque，中间动用 list； │ │ 只取一头用适配器，要遍历就别用栈。 │ └──────────────────────────────────────────┘
---
## 七、💡 学习建议
1. **动手写代码**：STL 是工具，光看不练等于没学。每个容器都要亲手写一遍增删改查。
2. **对比学习**：学习新容器时，主动和已学容器对比，找出异同点。
3. **理解底层**：不仅要会用，还要理解底层实现（如 vector 扩容、红黑树、哈希表），这样才能写出高效代码。
4. **刷题巩固**：在洛谷、LeetCode 等平台找对应标签的题目练习，学以致用。
5. **选型思维**：拿到一个问题，先思考"用什么容器最合适"，而不是上来就用 vector。
---
## 八、🍎 生活比喻
如果把 STL 容器比作**交通工具**：
- **vector** 就像**公交车**——容量大、按顺序坐、中途上下车麻烦（中间插入慢）
- **list** 就像**出租车**——随时可以上下车（任意位置插入快），但不能随便跳着坐（无随机访问）
- **deque** 就像**地铁**——两头都有门（双端操作快），车厢是连起来的（支持随机访问）
- **set** 就像**自动排序的书架**——书放进去自动按编号排好，找起来很快
- **map** 就像**字典**——按拼音（key）找字（value）
- **stack** 就像**摞盘子**——最后放上去的最先拿走
- **queue** 就像**排队买票**——先来的先买
- **priority_queue** 就像**VIP 通道**——优先级高的先服务
- **pair** 就像**一双筷子**——两个配成一对使用
掌握了这些"交通工具"，你就能根据不同的"出行需求"（编程需求），选择最合适的工具，写出高效、优雅的代码！
---
## ⭐ 必背速记卡