第十四章 标准模板库（STL）
1. STL 概述
1.1 六大部件
STL 是 Standard Template Library 的缩写。名字里带模板两个字，第十三章那张图纸就是它的地基，容器和算法全靠模板撑起来。第一章提过，C++98 这一版把 STL 迎进门，从此写 C++ 不用什么都自己造。
STL 里有六种部件，一间屋子六件家具。
┌─────────────────────────────────────────┐ │ 六大部件 │ ├─────────────────────────────────────────┤ │ 一间屋子，六件家具 │ │ │ │ 容器 数据放哪，vector list map │ │ 迭代器 怎么挨个走一遍 │ │ 算法 排序查找累加，认迭代器 │ │ 函数对象 行为像函数的东西 │ │ 适配器 换接口用，stack queue │ │ 分配器 内存谁管，默认那套够用 │ │ │ │ 挑大梁的：容器、迭代器、算法 │ └─────────────────────────────────────────┘容器管放数据，迭代器管挨个走，算法管排序查找这些套路。这三样挑大梁，本章的主角。函数对象是行为像函数的东西，算法排序时候能指定谁大谁小，知道有它就行。适配器换接口用，stack 和 queue 就是拿 deque 改的。分配器管内存从哪来，默认那套够用一辈子，日常提都不用提。
1.2 头文件和命名空间
用 STL 先得请头文件。老写法是 iostream.h 那样带 .h 的，九十年代的老貌，现在的编译器不认。新规矩一律不带 .h，vector 住 ，list 住 ，map 住，排序查找住 。
┌────────────────────────────────────────────┐ │ 头文件和大院 │ ├────────────────────────────────────────────┤ │ 两种老写法，一条新规矩 │ │ │ │ #include <iostream.h> 九十年代的老貌 │ │ #include <vector> 现在的写法 │ │ │ │ 头文件一律不带 .h │ │ using namespace std; 全院名字直接写 │ │ std::vector<int> v; 写全名也成 │ │ │ │ vector 住 std 大院，第一章那句话没变 │ └────────────────────────────────────────────┘第一章说过，std 是标准库住的大院，不声明的话写 cout 要写全名 std::cout。这条对 STL 原样管用。using namespace std;写上，全院名字直接写，vector、sort 都能省掉前缀。代码有规模了，或者多人合作，再老老实实写 std:: 前缀。本书图省事，都写上 using。
2. 容器
2.1 vector 动态数组
vector 是最常用的容器，没有之一。它是个会长个的数组，不用提前说好放几个，尾部加数据这事它包了。
#include <iostream> #include <vector> using namespace std; int main() { vector<int> scores; scores.push_back(78); scores.push_back(92); scores.push_back(55); scores.push_back(100); scores.push_back(88); cout << "size = " << scores.size() << endl; cout << "第一个 " << scores[0] << endl; cout << "最后一个 " << scores[scores.size() - 1] << endl; for (int s : scores) { cout << s << " "; } cout << endl; return 0; }输出长这样。
size = 5 第一个 78 最后一个 88 78 92 55 100 88vector 意思是装 int 的 vector，第十三章的图纸在这里第一次派上正经用场。scores[0] 和数组一样下标取值，size() 问个数，push_back 往尾部加。最后那个 for 是范围 for，冒号左边写元素类型，右边写容器，从头到尾走一遍，不用数下标。第五章手写循环数成绩的日子，到这里可以翻篇了。
vector 有个隐藏技能，它会趁你不备偷偷扩容。实测九次 push_back，size 和 capacity 的变化是这样。
#include <iostream> #include <vector> using namespace std; int main() { vector<int> v; for (int i = 0; i < 9; i++) { v.push_back(i); cout << "push " << i << " size " << v.size() << " capacity " << v.capacity() << endl; } return 0; }push 0 size 1 capacity 1 push 1 size 2 capacity 2 push 2 size 3 capacity 4 push 3 size 4 capacity 4 push 4 size 5 capacity 8 push 5 size 6 capacity 8 push 6 size 7 capacity 8 push 7 size 8 capacity 8 push 8 size 9 capacity 16capacity 是院子大小，size 是住了几口人。放不下了就换个大院子，整体搬家，搬完旧地址全部作废。这条规矩记住，3.3 节要吃它一次亏。
┌────────────────────────────────────────┐ │ vector 会长个 │ ├────────────────────────────────────────┤ │ push_back 一节，size 长一节 │ │ │ │ 装了 3 个 size 3 capacity 4 │ │ 装到第 5 个 size 5 capacity 8 │ │ │ │ 院子不够就换大的，连人带家当搬一次 │ │ 搬完家，旧地址全部作废 │ └────────────────────────────────────────┘要是能提前估摸个数，reserve 函数先把院子圈下来，少搬几回家。提一句，知道有它就行。
2.2 其余序列容器
vector 不是一个人在战斗。序列容器一家四口，元素排成一条线，区别在两头和中间的脾气。
┌───────────────────────────────────────────────┐ │ 容器家谱 │ ├───────────────────────────────────────────────┤ │ 四大门户 │ │ │ │ 序列容器 vector deque list array │ │ 关联容器 set map，按键排好 │ │ 无序关联 unordered_set map，点名 │ │ 适配器 stack queue priority_queue │ │ │ │ 家谱底下全是第十三章的图纸 │ └───────────────────────────────────────────────┘deque 两头都能插都能删，vector 只擅长一头。array 是定长数组，大小写死在类型里，为的是跑起来更快，日常用得少。list 是双向链表，第九章那套 Node 加 next 的现代化版本，中间插删是它的看家本领。
list 插删有多爽，第九章的痛苦就有多深。头插三个数，手写链表要两步加一句注释提醒自己别把旧头弄丢，list 一个函数的事。
#include <iostream> #include <list> using namespace std; int main() { list<int> lst; for (int i = 1; i <= 3; i++) { lst.push_front(i); } cout << "头插结果："; for (list<int>::iterator it = lst.begin(); it != lst.end(); ++it) { cout << *it << " "; } cout << endl; lst.push_back(99); cout << "尾接 99 之后："; for (int x : lst) cout << x << " "; cout << endl; return 0; }头插结果：3 2 1 尾接 99 之后：3 2 1 99输出和第九章一字不差，3 2 1，后来的站前面。区别在代码量，第九章那版洋洋洒洒一大段，这版二十行不到，还没有 new 没有 delete。链表那章要是当时有 list，我能少熬一个下午。
2.3 关联容器
序列容器管排成一条线的，关联容器管按键找值的。set 是一列不重复的钥匙，自动排好。map 是钥匙对值，也按钥匙排好。
┌─────────────────────────────────────────┐ │ 一对集装箱 │ ├─────────────────────────────────────────┤ │ 一个管去重，一个管查值 │ │ │ │ set 就一列钥匙，不重复，自动排好 │ │ map 钥匙对值，按钥匙排好 │ │ │ │ scores["李四"] = 92; │ │ 一句入库，不用先遍历找人 │ └─────────────────────────────────────────┘去重和查值是这两位的看家本领。第七个分数录进来，92 和 78 前面都有，set 伸手一收，重复的拦在门外。
#include <iostream> #include <set> #include <map> #include <string> using namespace std; int main() { int raw[7] = {78, 92, 55, 100, 88, 92, 78}; set<int> uniq(raw, raw + 7); cout << "去重后 " << uniq.size() << " 个："; for (set<int>::iterator it = uniq.begin(); it != uniq.end(); ++it) { cout << *it << " "; } cout << endl; map<string, int> scores; scores["张三"] = 78; scores["李四"] = 92; scores["王五"] = 55; scores["赵六"] = 100; scores["孙七"] = 88; cout << "李四考了 " << scores["李四"] << endl; cout << "班里共 " << scores.size() << " 人" << endl; if (scores.count("李四") == 1) { cout << "李四在册" << endl; } for (map<string, int>::iterator it = scores.begin(); it != scores.end(); ++it) { cout << it->first << " " << it->second << endl; } cout << endl; return 0; }去重后 5 个：55 78 88 92 100 李四考了 92 班里共 5 人 李四在册 孙七 88 张三 78 李四 92 王五 55 赵六 100set 的迭代器走出来就是排好序的，55 打头，100 收尾。map 用方括号加钥匙存取，scores 后面跟上钥匙名，一句话查到 92 分，不用遍历不用 if，钥匙本身就是下标。it->first 是钥匙，it->second 是值，一对一对往外递。
还有一对 unordered_set 和 unordered_map，按键排好的换成按键散列，查得更快，走出来没顺序。日常提一句，用到再翻。
2.4 容器适配器
stack 和 queue 不是新容器，是适配器，拿别人换接口。stack 后进先出，queue 先进先出，都只开一个口，不许你挑中间下手。
#include <iostream> #include <stack> #include <queue> using namespace std; int main() { stack<int> st; st.push(1); st.push(2); st.push(3); cout << "栈顶 " << st.top() << "，大小 " << st.size() << endl; while (!st.empty()) { cout << st.top() << " "; st.pop(); } cout << endl; queue<string> q; q.push("张三"); q.push("李四"); q.push("王五"); cout << "队头 " << q.front() << "，队尾 " << q.back() << endl; while (!q.empty()) { cout << q.front() << " "; q.pop(); } cout << endl; return 0; }栈顶 3，大小 3 3 2 1 队头 张三，队尾 王五 张三 李四 王五stack 的 top 看栈顶，pop 出栈，3 2 1 出去，后进先出。queue 的 front 是队头，back 是队尾，张三 李四 王五 排着队出去。还有 priority_queue，默认大头优先，提一句。
2.5 怎么选
容器一大家子，新手最常问的问题是用哪个。答案永远是先想清楚要干什么。
┌────────────────────────────────┐ │ 挑容器 │ ├────────────────────────────────┤ │ 先问自己要干什么 │ │ │ │ 只会一头加删 vector │ │ 两头都要插删 deque │ │ 中间频繁插删 list │ │ 查重、要排好 set │ │ 按键查值 map │ │ 后进先出 stack │ │ 先进先出 queue │ │ │ │ 拿不准就先 vector，够用 │ └────────────────────────────────┘只会一头加删，vector 够用，而且它 cache 友好，跑得最快。两头都要插删，换 deque。中间频繁插删，list。要查重要排好，set。按键查值，map。后进先出 stack，先进先出 queue。实在拿不准，先 vector，等它成为瓶颈再换，多数程序到不了那一步。
3. 迭代器
3.1 迭代器是个什么东西
容器挨个走一遍这事，第六章的指针能干，但每种容器长得不一样，指针认不出 list 的节点。STL 的答案是迭代器，一个泛化的指针，认位置不认地址。用法和指针像一个模子刻出来的。
┌───────────────────────────────────────────┐ │ 泛化的指针 │ ├───────────────────────────────────────────┤ │ 指针认地址，迭代器认位置 │ │ │ │ vector<int>::iterator it = v.begin(); │ │ │ │ *it 拿到那一格的东西 │ │ ++it 挪到下一格 │ │ it != v.end() 还没走到头 │ │ │ │ 换个容器，这套写法原样管用 │ └───────────────────────────────────────────┘begin 指向第一个，end 指向最后一个的后一格，是个哨兵，解引用它是犯法的。*it 拿到那一格的东西，++it 挪到下一格，it != v.end() 问走到头没有。这段配方在 vector、list、set、map 上原样管用，换个容器换个写法这件事不存在。
上一节 list 那段已经用它走过一遍，再看个 vector 的。
#include <iostream> #include <vector> using namespace std; int main() { vector<int> scores = {78, 92, 55, 100, 88}; for (vector<int>::iterator it = scores.begin(); it != scores.end(); ++it) { cout << *it << " "; } cout << endl; return 0; }78 92 55 100 88vector::iterator 这串字面意思是 vector 的迭代器类型，写在尖括号外面，第十三章的类模板语法在这里露脸。日常写循环推荐范围 for，短省事，要删元素或者倒着走时候再请出迭代器本尊。auto 也能替它，auto it = v.begin()，类型让编译器猜，C++11 的东西，提一句。
3.2 五种迭代器
迭代器按力气分五等，力气大的什么都能干，小的干不了大的。
┌─────────────────────────────────────────────┐ │ 五种迭代器 │ ├─────────────────────────────────────────────┤ │ 力气一层比一层大 │ │ │ │ 输入 只读，一遍过，cin │ │ 输出 只写，一遍过，cout │ │ 前向 只往前走，forward_list │ │ 双向 能进能退，list set map │ │ 随机访问 能跳能算，vector deque array │ │ │ │ 会跳的能替不会跳的，反过来不成 │ └─────────────────────────────────────────────┘输入迭代器只读，一遍过， cin 就是。输出迭代器只写，也是一遍过，cout 就是。前向只往前走，forward_list 和无序容器提供这种。双向能进能退，list set map 都是。随机访问力气最大，能跳能算，it + 3 直接跳到第四格，vector deque array 供着它。
为什么较这个真，因为算法的门槛写在明处。find 这种逐个看的，前向就够。sort 要跳着比的，非随机访问不可，这就是下一节要踩的坑。
3.3 失效这堂课
迭代器有个著名的坑，叫失效。2.1 节说过，vector 放不下就换院子整体搬家。搬完家，旧的 begin 和 end 指向被扔掉的旧院子，手里攥着的迭代器全部作废。这时候解引用，读到哪全看运气。
#include <iostream> #include <vector> using namespace std; int main() { vector<int> v; v.push_back(10); v.push_back(20); vector<int>::iterator it = v.begin(); v.reserve(10); v.push_back(30); v.push_back(40); cout << "留了余地，*it = " << *it << endl; return 0; }留了余地，*it = 10reserve 先把院子圈到十间，后面两次 push_back 都在余量里，不放量不搬家，it 指的地方纹丝不动，输出稳稳的 10。把 reserve 那行删掉再跑，it 作废，解引用读到哪全看运气，标准给这种行为起了个名字，叫未定义行为。程序没崩不代表没事，只是这次运气好。
┌───────────────────────────────────┐ │ 失效这堂课 │ ├───────────────────────────────────┤ │ push_back 触发放量 │ │ │ │ 旧 begin 指向被扔掉的旧院子 │ │ 旧 end 同上 │ │ it 读到哪全看运气 │ │ │ │ list 插删不失效，节点各住各的 │ └───────────────────────────────────┘规律好记。vector 和 deque 插删都可能搬家，erase 删掉一个，后面全体往前挪，被删位置往后都作废。list 是例外，节点各住各的，插删只改邻居的 next 和 prev，别人的迭代器一根毛都不掉。这也是 list 中间插删拿得出手的代价换来的。
躲坑的办法也简单，增删之后重新取一遍 begin 和 end，别攥着旧的不撒手。
4. STL 算法
4.1 算法不认容器
算法住在 里，是 STL 里最庞大的一支部队。它们有个共同脾气，不认容器，只认迭代器。
┌─────────────────────────────────┐ │ 算法不认容器 │ ├─────────────────────────────────┤ │ sort(v.begin(), v.end()); │ │ │ │ 算法 只认迭代器 │ │ 迭代器 知道怎么走 │ │ 容器 提供 begin 和 end │ │ │ │ 三层各管一层，谁也别越界 │ └─────────────────────────────────┘sort 收两个迭代器，不知道背后是 vector 还是 deque，也不想知道。它按迭代器的步子排序，随机访问的步子能跳，链表那种一步一脚的它使不上劲。三层分工明明白白，算法出套路，迭代器出脚力，容器出场地。谁也别越界，谁也能被换掉。今天写出 sort(v.begin(), v.end())，明天换个容器，这句原样编译。
4.2 常用算法过一遍
排序是算法里的头号招牌。第五章手写冒泡，交换要借临时变量，三个杯子换水不倒第三杯倒不成。当时说 swap 在 里现成的，本章连排序一起还账。
#include <iostream> #include <vector> #include <algorithm> #include <utility> using namespace std; int main() { vector<int> scores = {78, 92, 55, 100, 88}; sort(scores.begin(), scores.end()); cout << "升序："; for (int s : scores) cout << s << " "; cout << endl; reverse(scores.begin(), scores.end()); cout << "降序："; for (int s : scores) cout << s << " "; cout << endl; swap(scores[0], scores[scores.size() - 1]); cout << "首尾对调："; for (int s : scores) cout << s << " "; cout << endl; return 0; }升序：55 78 88 92 100 降序：100 92 88 78 55 首尾对调：55 92 88 78 100sort 默认升序，reverse 反手一个降序，swap 首尾对调。第五章那段冒泡，这里三个函数名。想降序排还有一条路，sort 加一个 greater()，函数对象第一次露面，知道有它就行。
查找计数也不在话下。find 挨个比对，找不着返回 end()。count_if 数满足条件的，条件是普通函数，C++11 的 lambda 也能当。accumulate 住 ，累加专用。
#include <iostream> #include <vector> #include <algorithm> #include <numeric> using namespace std; bool isFail(int s) { return s < 60; } int main() { vector<int> scores = {78, 92, 55, 100, 88}; vector<int>::iterator pos = find(scores.begin(), scores.end(), 92); if (pos != scores.end()) { cout << "92 在，下标 " << pos - scores.begin() << endl; } vector<int>::iterator miss = find(scores.begin(), scores.end(), 60); cout << "60 在吗 " << (miss != scores.end()) << endl; cout << "不及格人数 " << count_if(scores.begin(), scores.end(), isFail) << endl; int sum = accumulate(scores.begin(), scores.end(), 0); cout << "总分 " << sum << "，平均 " << (double)sum / scores.size() << endl; return 0; }92 在，下标 1 60 在吗 0 不及格人数 1 总分 413，平均 82.6三个细节说一句。find 的回报是迭代器不是下标，随机访问容器上减一下 begin 就折成下标，60 这种不听话的减不出来，所以先用 != 比过 end() 再说话。count_if 收普通函数名 isFail 就够，函数退化成指针递过去，STL 不挑食。总分 413 平均 82.6，和第五章手写那版一个数，现成的和手搓的在这件事上打成平手，平得好。
4.3 算法和容器的分工
认迭代器这条规矩，有时会绊人。list 中间插删天下无敌，sort 却不服务它，谁让它的迭代器不会跳。list 自己有个成员版 lst.sort()，专门补这个洞，用成员算法，别用全局的。
算法这张单子很长，排序查找计数累加复制删除轮换，几百个，常用的占一成。本书不抄单子，知道 里有座宝库，要用啥现翻，比硬背实惠。
本章小结
本章把 STL 的门推开了一条缝。
┌───────────────────────────────────────┐ │ 本章收口 │ ├───────────────────────────────────────┤ │ 一层一层往上收 │ │ │ │ 六大部件，容器迭代器算法挑大梁 │ │ 头文件光写字，大院还是那个 std │ │ vector 会长个，搬家后旧迭代器全废 │ │ set 管去重，map 管查值 │ │ 算法认迭代器不认容器，三层分工 │ │ │ │ 下一章异常处理，越界有个正经说法 │ └───────────────────────────────────────┘STL 是模板盖起来的楼，六大部件里容器、迭代器、算法挑大梁。头文件不带 .h，名字住 std 大院，第一章那句话原样管用。vector 最常用，会长个，扩容搬家之后旧迭代器全废，躲坑的办法是增删后重新取。set 管去重，map 管按键查值，插删看场合，拿不准先 vector。
迭代器是泛化的指针，begin 加 end 圈出半开区间，五种迭代器按力气分等，算法的门槛就写在迭代器会干什么上。算法不认容器只认迭代器，三层分工，各管一层，换来的是容器随便换、算法照样跑。
手写数组、手写链表、手写冒泡那三样本事没有白学，不知道底层的轮子怎么转，现成的用着也不踏实。到此 C++ 的常用招式差不多了，下一章讲异常处理，vector 下标越界、map 按键扑空这些事，有个正经的说法来接。
附录 A 速查卡
| 写法 | 含义 |
|---|---|
| #include | 请 vector 进场 |
| vector v | 声明一个空 vector |
| v.push_back(x) | 尾部加一个 |
| v.size() 与 v.capacity() | 个数与院子大小 |
| for (int x : v) | 范围 for 走一遍 |
| v.begin() 与 v.end() | 头迭代器与尾哨兵 |
| *it 与 ++it | 解引用与前进 |
| it->first 与 it->second | map 的钥匙与值 |
| lst.push_front(x) | list 头插 |
| set s | 去重有序集合 |
| map<string, int> m | 键值对，键有序 |
| sort(v.begin(), v.end()) | 升序排，随机访问专用 |
| find 与 count_if | 查找与条件计数 |
| accumulate(v.begin(), v.end(), 0) | 累加，住 |
| st.top() 与 q.front() | 栈顶与队头 |
附录 B 排错表
| 常见现象 | 病根 | 药方 |
|---|---|---|
| v[10] 输出没谱或直接崩 | 下标越界不检查 | 换 v.at(10)，或先和 size() 比 |
| at 越界后程序 terminate | out_of_range 没人接 | 异常处理那章 try catch 接 |
| sort 用到 list 上编译失败 | list 迭代器不是随机访问 | 用成员版 lst.sort() |
| map 查不存在的键得 0，表还胖了 | 方括号会顺手插入 | 先用 count 问在不在 |
| accumulate 报未声明 | 忘请 | 补头文件 |
| push_back 之后旧迭代器没谱 | 院子搬了家，旧的作废 | 重新取 begin 与 end |
| find 结果没比 end() 就解引用 | 没找到也当找到 | 先 != 比过再解引用 |
