如果你刚开始刷算法竞赛题，大概率经历过这种绝望：题目思路想明白了，代码却写得又长又容易崩，光是一个排序就要手写二三十行，调半天还出边界问题。这其实不是你菜，而是你还没学会用 STL。《算法竞赛入门经典（第2版）》第5章 "C++ 与 STL 入门" 解决的就是这个问题，它把 C++ 里最常用的容器和算法函数摊开讲了一遍，让新手从"只会写 C 风格循环加数组"快速切换到"用现成容器优雅地解题"。我这本书大概读了四遍，每次带新人也都先推这一章，今天把我自己整理的代码笔记和踩坑经验写出来，配合书上的核心知识点，方便你直接参考复现。1. 第5章到底在讲什么：先搞清知识地图1.1 从C到C++：这本书默认你只会C这本书前面几章基本都是 C 语言风格，到了第5章突然切到 C++，很多人在这里卡一下。原因很简单：竞赛里 C++ 的 STL 能省掉大量底层代码，而作者默认读者只有 C 语言基础，所以先花了一小节专门讲"从 C 到 C++"的过渡语法。这里最核心的转变有三个：输入输出从 scanf/printf 换成 cin/cout 或者两者混用；字符数组换成 string；指针换成了更安全的引用。很多人纠结到底要不要把输入输出全部换成 cin/cout，我的建议是不用强迫自己换。竞赛里最稳的做法是 scanf/printf 配合 string 的 c_str()，或者干脆在 main 开头写一行 ios::sync_with_stdio(false) 然后放心用 cin/cout。两种方案都有自己的适用场景，后面我会单独讲。还有一点要提前做好心理准备：STL 的名字听着吓人，但这一章涉及的容器其实都是"开箱即用"的工具，你不用知道红黑树怎么旋转，只要知道 set 能自动去重排序就够了。底层原理可以等后面有时间再补，先把接口用熟。1.2 语法"前菜"：引用、string、结构体构造函数书上第一个例子就用了引用。引用可以用一句话概括：它是变量的别名，操作引用就是在操作原变量。int a = 3; int &b = a; // b 是 a 的别名 b = 5; printf("%d\n", a); // 输出 5为什么竞赛代码里喜欢用引用？两个原因。第一，写 swap 这样的函数不用指针，代码清爽；第二，传参时可以避免拷贝，尤其当参数是 vector 或 string 这种大对象时，传引用能省下一大笔时间。后面讲容器时，很多函数参数都写成 const string& 这种形式，你要能看懂，const 表示"只读不修改"，& 表示"别拷贝"。string 就更不用说了。用 char 数组存字符串最痛苦的是要自己管长度、管越界，用 strcpy/strcat 还得小心翼翼。string 把这些坑全填了：s.length() 直接得到长度s + t 直接拼接s.substr(pos, len) 取子串s.find(x) 查找，找不到时返回 string::npos字符串之间可以直接用 <、>、== 按字典序比较唯一要注意的是 printf 不能直接打印 string，得写成 printf("%s", s.c_str())。如果你用 cout 就没有这个问题。再就是结构体构造函数，书上写了 Point 的例子：struct Point { int x, y; Point(int x = 0, int y = 0): x(x), y(y) {} };这里有个细节很多人初看会懵：构造函数参数列表里的 x 和成员变量 x 重名了，所以要用初始化列表 : x(x), y(y) {}。圆括号里是参数，等号左边是成员，读起来是"把参数 x 赋给成员 x"。给所有参数带上默认值很重要，因为 map 的 operator[] 在没有对应键时会默认构造一个临时对象，如果 Point 没有默认构造参数，编译器会直接报错。1.3 容器选型的核心思路第5章的核心其实是 STL 容器，这一章要掌握的是六个：vector、set、map、stack、queue、priority_queue，外加两个算法函数 sort 和 lower_bound。我见过太多人把这几个容器当成孤立 API 去背，背完就忘。实际上它们是一条线下来的：vector 解决"数组长度不确定"的问题，set 解决"高效判断元素是否存在、自动去重"的问题，map 解决"键值对查找"的问题，stack 和 queue 解决特定的访问顺序问题，priority_queue 解决"每次都取最大或最小"的问题。拿到一道题，第一件事不是想"我用哪个容器"，而是想"这个题的核心操作是什么"，操作决定容器。这章每个容器后面都跟着一个例题：vector 配木块问题，set 配安迪的第一个字典，map 配反片语，priority_queue 配丑数。我的建议是不要跳过例题只看容器语法，例题才是容器真正的用武之地。光会 push_back 不叫会 vector，能判断出"这题该用 vector"才算入门。2. 容器代码笔记：vector、set、map 实操2.1 vector：动态数组的正确打开方式vector 是最基础的容器，本质是自动扩容的数组。你不需要关心容量上限，push_back 往里塞东西就行。但它也有短板：在中间插入或删除的代价很高，所以 vector 适合"只在尾部增删 + 随机访问"的场景。基本操作：#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> v; // 空 vector v.push_back(3); // 尾部追加，不是 push v.push_back(1); v.push_back(2); sort(v.begin(), v.end()); // 排序，需要 <algorithm> for (int i = 0; i < (int)v.size(); i++) cout << v[i] << " "; cout << "\n"; for (int x : v) cout << x << " "; // 范围 for，C++11 之后可用 cout << "\n"; return 0; }几个容易记混的点。第一，push_back 不是 push，很多人第一反应写 v.push(3)，编译直接报错。第二，v.size() 返回无符号整数，把它和 int 负数比较会出问题。比如空 vector 的 v.size() - 1 不是 -1，而是一个巨大的正数，遍历时 if (i < v.size() - 1) 这种判断就会莫名其妙成立。正确写法是把 size 强转为 int，或者用范围 for 绕开下标。第三，resize 和 reserve 不一样，resize 会改变元素数量，新增元素用默认值填充；reserve 只是预分配空间，不改变大小。频繁 push_back 导致多次扩容时会慢，提前 reserve 是常用的优化手段。书上木块问题整道题都在用 vector 做"取尾部、删尾部、移到另一堆"的操作，这几个操作换个容器都很别扭，但在 vector 上就是家常便饭。这道题值得完整敲一遍。2.2 set：有序集合与自动去重set 的中文叫集合，有两个特性：元素不能重复，内部自动排好序。这两个特性都是基于红黑树实现的，插入、删除、查找都是 O(log n)。如果用数组去重可能要两层循环 O(n^2)，set 就是帮你省这个时间的。#include <iostream> #include <set> using namespace std; int main() { set<int> s; s.insert(5); s.insert(1); s.insert(5); // 重复插入无效 cout << s.count(5) << "\n"; // 1，count 用于判断是否存在 cout << s.size() << "\n"; // 2，5 只被算一次 for (int x : s) cout << x << " "; // 输出 1 5，已排序 cout << "\n"; s.erase(1); // 按值删除 return 0; }set 的操作提醒三点。第一，count 只有 0 和 1 两种返回值，用来判断键是否存在比 find 写法简洁，别拿它当计数器用，想统计出现次数请用 map。第二，set 的迭代器是双向迭代器，不支持随机加减，你不能写 s.begin() + 2，想取第几个元素只能循环走。第三，遍历时删除元素是经典坑，正确姿势在后面的常见问题里专门讲。顺便提一句，set 还有个变种 multiset 允许重复元素，书后练习里偶尔用到。先理解 set，再补 multiset 就很容易。2.3 map：带下标访问的平衡树map 是这一章里我个人觉得最常用的容器。它存键值对，内部也是红黑树，自动按键排序。用法像数组下标，但下标可以是任意类型。比如统计每个字符串出现次数，用 map 一行解决：#include <iostream> #include <map> #include <string> using namespace std; int main() { map<string, int> cnt; string words[] = {"apple", "banana", "apple"}; for (string w : words) cnt[w]++; // 键不存在时自动创建，int 默认 0 for (auto p : cnt) cout << p.first << " " << p.second << "\n"; // 按键的字典序输出：apple 2 banana 1 return 0; }这里的核心知识点是：cnt[w] 在键 w 不存在时会自动插入一个键值对，int 的默认值是 0，所以 cnt[w]++ 不需要提前判断。这是竞赛里很爽的懒人写法，但它有代价：如果只是想查一下键在不在，用 cnt[w] 会无意中把键插进去，污染数据。这种情况用 cnt.count(w) 判断，或者用 cnt.find(w)，找到的迭代器指向一个 pair。map 遍历时 p 是一个 pair，p.first 是键，p.second 是值。数据量大时建议写成 for (auto &p : cnt)，加引用避免拷贝。书上反片语那道题是 map 的标准应用：把每个单词标准化（转小写后排序），用标准化结果做键，原始单词做值，最后输出只出现一次的单词。这个思路很经典，它是很多真正竞赛题的原型。3. stack、queue、priority_queue：三种队列的战场3.1 stack 与 queue 的基础模板stack 和 queue 是结构上完全相反的两个容器。栈是后进先出，像一摞盘子，只能从顶上拿；队列是先进先出，像排队买票，先来的先办。#include <iostream> #include <stack> #include <queue> using namespace std; int main() { stack<int> st; st.push(1); st.push(2); cout << st.top() << "\n"; // 2，栈顶 st.pop(); // 出栈 cout << st.top() << "\n"; // 1 queue<int> q; q.push(1); q.push(2); cout << q.front() << "\n"; // 1，队头 q.pop(); // 出队 cout << q.front() << "\n"; // 2 return 0; }注意 stack 的操作是 top()，queue 是 front() 和 back()。stack 没有 front，queue 没有 top，这两个很容易混。另外 empty() 判断要养成习惯，在空栈或空队列上调用 top/pop 是未定义行为，本地可能不报错，OJ 上直接 Runtime Error。书上团体队列那道题会用到 queue 的组合技巧：用队列存团体编号，再用多个队列存每个团体内部的成员。这是"队列套队列"的思路，初学者会觉得绕，但它把 queue 的适用范围拓展得很清楚，理解了它，后面碰到复杂的模拟题心态会稳很多。3.2 priority_queue：默认是大根堆，别搞反了优先队列是竞赛神器，它每次弹出的是当前所有元素里最大的那个。内部实现是二叉堆，插入和弹出的复杂度都是 O(log n)。很多人第一次用会犯一个经典错误：以为弹出的是最小的，结果数据一跑全错。#include <iostream> #include <queue> using namespace std; int main() { priority_queue<int> pq; pq.push(3); pq.push(5); pq.push(1); cout << pq.top() << "\n"; // 输出 5，默认大根堆 pq.pop(); // 移除 5 cout << pq.top() << "\n"; // 输出 3 return 0; }如果你想要小根堆，要把模板参数补齐：priority_queue<int, vector<int>, greater<int>> pq; // 小根堆这里很多人会把 greater 和 less 搞反。记忆方式是：less 对应默认的大根堆，它会认为"小的排后面"，所以堆顶是大的；greater 反过来，认为"大的排后面"，堆顶就是小的。这个知识点只能靠多写几次形成肌肉记忆，比赛前一紧张确实容易写反，我建议调试时先打印 top() 验证一下。自定结构体放进 priority_queue 时，重载 operator< 的方向更要小心。堆顶是"小于关系中的最大值"，所以让分数高的排在前的结构体，反而要写 return score < other.score，这个逻辑反直觉，建议写完之后用一个三个元素的用例实测一遍。3.3 完整套路：丑数这道题怎么用 priority_queue书上的丑数题是理解 priority_queue 的最佳案例。题目大意是质因数只有 2、3、5 的数叫丑数，问第 1500 个丑数是多少。暴力从小到大找肯定超时，正确思路是用一个小根堆，先把 1 放进去，每次弹出最小数，再把它乘以 2、3、5 推进去，配合 set 去重，弹出的第 1500 个数就是答案。#include <iostream> #include <set> #include <queue> using namespace std; int main() { priority_queue<long long, vector<long long>, greater<long long>> pq; set<long long> seen; pq.push(1); seen.insert(1); long long x = 1; for (int i = 1; i <= 1500; i++) { x = pq.top(); pq.pop(); for (long long f : {2LL, 3LL, 5LL}) { long long nx = x * f; if (!seen.count(nx)) { seen.insert(nx); pq.push(nx); } } } cout << "The 1500'th ugly number is " << x << ".\n"; return 0; }这段代码有几个细节值得抠。第一，用 long long 而不是 int，因为丑数增长很快，第 1500 个已经接近 8.6 亿，后面的更大。第二，for (long long f : {2LL, 3LL, 5LL}) 是 C++11 的初始化列表遍历，如果编译器太老，改成三次重复的 push 语句即可。第三，set 在这里兼任"已入堆标记"，防止同一个丑数被 2×3 和 3×2 两条不同路径重复推进堆里，这是枚举类题目里通用的去重技巧，优先级队列加集合的组合以后会反复用到。4. 排序与检索：sort、lower_bound、unique 三剑客4.1 sort 的正确姿势sort 是 STL 里使用频率最高的算法函数。它支持数组和 vector，默认从小到大排序，复杂度 O(n log n)，底层是内省排序，最坏情况下不会退化到 O(n^2)，比自己手写快排稳。#include <iostream> #include <algorithm> using namespace std; int main() { int a[] = {4, 2, 9, 1}; sort(a, a + 4); // 数组：传首地址和尾后地址 for (int i = 0; i < 4; i++) cout << a[i] << " "; cout << "\n"; sort(a, a + 4, greater<int>()); // 降序 sort(a, a + 4, [](int x, int y) { return x > y; }); // lambda 写法 return 0; }自定义比较函数有一个硬性规则：必须满足"严格弱序"。简单说就是两个元素相等时，比较函数必须返回 false，不管参数顺序怎么传。写成 return x <= y 就是反例，sort 内部做条件判断时可能直接崩掉。正确的写法是 return x < y 或 return x > y。结构体排序是高频内容。写一个结构体数组，想按某个成员排序，最方便是在结构体里重载小于号：struct Student { int score; string name; bool operator<(const Student& other) const { return score > other.score; // 分数高的排前面 } };重载之后，sort(a, a + n) 就自动按你定义的规则排。注意 const 别漏，有的编译器漏了能通过，换一个就报"no match for operator<"，这是竞赛里最常见的编译错误之一。4.2 lower_bound 与去重组合拳排序之后往往跟着检索。lower_bound 是 STL 提供的二分查找，返回第一个大于等于给定值的位置，只适用于有序序列。书上大理石在哪儿的检索部分就是这个用法：sort(a, a + n); int p = lower_bound(a, a + n, x) - a; if (p < n && a[p] == x) printf("%d found at position %d\n", x, p + 1); else printf("%d not found\n", x);lower_bound 返回的是指针或迭代器，减去首地址得到下标。判断时注意越界：如果所有元素都小于 x，lower_bound 返回尾后位置，p 可能等于 n，此时直接访问 a[p] 就越界了，所以必须先判断 p < n。和 lower_bound 经常一起出现的是 unique，它去除相邻重复元素。注意是"相邻"，所以要先 sort 再 unique 才能整体去重。unique 返回去重后新序列的尾后迭代器，想真正删掉后面多余的元素，在 vector 上要配合 erase：sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());这行代码是竞赛里的去重标配，建议背下来。很多人只写 unique 忘了 erase，结果 size 没变，重复元素只是被移到末尾了，看着没问题，一输出就露馅。5. 常见问题与排查技巧实录5.1 迭代器失效问题迭代器失效是 STL 新手最容易踩的深坑。vector 在 push_back 扩容时，所有迭代器都会失效；set 用 erase 删除元素后，指向被删元素的迭代器也失效。最常见的错误是边遍历边删除：// 错误写法：erase 之后 it 已经失效 for (set<int>::iterator it = s.begin(); it != s.end(); it++) { if (*it % 2 == 0) s.erase(it); }C++11 之后 erase 会返回下一个有效迭代器，正确写法是：for (auto it = s.begin(); it != s.end(); ) { if (*it % 2 == 0) it = s.erase(it); else it++; }vector 的 erase 也返回迭代器，处理方式类似。这个细节很多入门书讲得不够清楚，都是自己调几次才能领悟，提前记住能省不少调试时间。5.2 cin/cout 太慢怎么办从 C 切到 C++ 后，很多人发现程序跑得比以前慢，以为是 STL 的性能问题。其实大部分是输入输出在拖后腿。cin 和 cout 默认和 stdio 保持同步，效率很低。解决办法只有一行：ios::sync_with_stdio(false); cin.tie(0);第一行取消同步，第二行解除 cin 和 cout 的绑定。写完后 cin/cout 速度接近 scanf/printf。注意一点：一旦开了 sync_with_stdio(false)，就不要混用 cin 和 scanf，否则数据可能错乱。要么全用 cout，要么全用 printf，不要一把梭。5.3 常见报错速查表我把新手阶段最容易撞上的问题整理成一张表，遇到报错可以回来对着查：报错现象可能原因解决办法编译提示没有 begin/end忘写对应容器头文件补全 #include 等printf 输出 string 出错string 不是 char*用 s.c_str() 或改用 coutmap 查 key 时数据莫名变多operator[] 会插入新键用 count 或 find 代替priority_queue 弹出最大值默认是大根堆加 greater 变最小堆sort 自定义比较时崩溃比较函数不满足严格弱序改为 return x < y空容器上调用 top/front没判 empty先 empty() 再取元素结构体放入 set/map 报错没有重载 operator<在结构体里补一个 operator<size() 和负数比较异常size_type 是无符号数强转 int 再比较这张表不是让你背的，是让你真遇到问题时回来看。如果编译报错里出现类似"no match for operator<"的英文，第一反应就应该是"结构体是不是没写重载"。5.4 关于头文件：不要只写一个万能头文件很多 OJ 支持 #include <bits/stdc++.h> 万能头文件，一次包含全部标准库。比赛时图省事用它对结果没影响，比赛只求 AC 不看头文件规范。但平时练习我不建议只写它，原因是你会搞不清每个容器到底依赖哪个头文件。理解"set 在里、map 在里、sort 在 里"这件事，对你以后阅读复杂代码、定位编译错误都有帮助。折中方案：平时练习写标准头文件，比赛时随意。6. 我的学习路线与补充建议把这一章完整过一遍，大概需要 3 到 5 天，看之前 C 语言基础而定。我建议的顺序是：先跑一遍书上示例代码，改几个参数体会每个容器的行为；再把每个容器对应的例题独立敲一遍，不要复制；最后从章末练习题里挑三道容器题做掉。这个过程不用追求一天刷完，容器之间的差异需要睡一觉才能沉淀进脑子里。从我带过的学生经验看，最容易出的问题反而是"学完就忘"。今天学了 map，一个星期后遇到统计字符串频率的题，还是下意识开两个数组硬顶。这很正常，唯一解药是多用。你可以挑一道旧题，强制自己用 STL 重写一遍，比如以前用数组标记的题目换成 map，以前手写排序的换成 sort。重写过程中你会不断碰到迭代器、类型相关的坑，踩过一次就记住了。最后再分享一个小技巧：遇到不确定的容器用法，别急着翻书，先写一个十行以内的小程序跑一下。我到现在还会这么干，比如 set 的 erase 返回值、map 的 emplace 行为，与其猜，不如让编译器告诉我。这种实验驱动的学习方式，比背任何笔记都管用。把第5章打扎实，后面刷题的速度会明显上一个台阶。
如果你刚开始刷算法竞赛题，大概率经历过这种绝望：题目思路想明白了，代码却写得又长又容易崩，光是一个排序就要手写二三十行，调半天还出边界问题。这其实不是你菜，而是你还没学会用 STL。《算法竞赛入门经典（第2版）》第5章 "C++ 与 STL 入门" 解决的就是这个问题，它把 C++ 里最常用的容器和算法函数摊开讲了一遍，让新手从"只会写 C 风格循环加数组"快速切换到"用现成容器优雅地解题"。我这本书大概读了四遍，每次带新人也都先推这一章，今天把我自己整理的代码笔记和踩坑经验写出来，配合书上的核心知识点，方便你直接参考复现。1. 第5章到底在讲什么：先搞清知识地图1.1 从C到C++：这本书默认你只会C这本书前面几章基本都是 C 语言风格，到了第5章突然切到 C++，很多人在这里卡一下。原因很简单：竞赛里 C++ 的 STL 能省掉大量底层代码，而作者默认读者只有 C 语言基础，所以先花了一小节专门讲"从 C 到 C++"的过渡语法。这里最核心的转变有三个：输入输出从 scanf/printf 换成 cin/cout 或者两者混用；字符数组换成 string；指针换成了更安全的引用。很多人纠结到底要不要把输入输出全部换成 cin/cout，我的建议是不用强迫自己换。竞赛里最稳的做法是 scanf/printf 配合 string 的 c_str()，或者干脆在 main 开头写一行 ios::sync_with_stdio(false) 然后放心用 cin/cout。两种方案都有自己的适用场景，后面我会单独讲。还有一点要提前做好心理准备：STL 的名字听着吓人，但这一章涉及的容器其实都是"开箱即用"的工具，你不用知道红黑树怎么旋转，只要知道 set 能自动去重排序就够了。底层原理可以等后面有时间再补，先把接口用熟。1.2 语法"前菜"：引用、string、结构体构造函数书上第一个例子就用了引用。引用可以用一句话概括：它是变量的别名，操作引用就是在操作原变量。int a = 3; int &b = a; // b 是 a 的别名 b = 5; printf("%d\n", a); // 输出 5为什么竞赛代码里喜欢用引用？两个原因。第一，写 swap 这样的函数不用指针，代码清爽；第二，传参时可以避免拷贝，尤其当参数是 vector 或 string 这种大对象时，传引用能省下一大笔时间。后面讲容器时，很多函数参数都写成 const string& 这种形式，你要能看懂，const 表示"只读不修改"，& 表示"别拷贝"。string 就更不用说了。用 char 数组存字符串最痛苦的是要自己管长度、管越界，用 strcpy/strcat 还得小心翼翼。string 把这些坑全填了：s.length() 直接得到长度s + t 直接拼接s.substr(pos, len) 取子串s.find(x) 查找，找不到时返回 string::npos字符串之间可以直接用 <、>、== 按字典序比较唯一要注意的是 printf 不能直接打印 string，得写成 printf("%s", s.c_str())。如果你用 cout 就没有这个问题。再就是结构体构造函数，书上写了 Point 的例子：struct Point { int x, y; Point(int x = 0, int y = 0): x(x), y(y) {} };这里有个细节很多人初看会懵：构造函数参数列表里的 x 和成员变量 x 重名了，所以要用初始化列表 : x(x), y(y) {}。圆括号里是参数，等号左边是成员，读起来是"把参数 x 赋给成员 x"。给所有参数带上默认值很重要，因为 map 的 operator[] 在没有对应键时会默认构造一个临时对象，如果 Point 没有默认构造参数，编译器会直接报错。1.3 容器选型的核心思路第5章的核心其实是 STL 容器，这一章要掌握的是六个：vector、set、map、stack、queue、priority_queue，外加两个算法函数 sort 和 lower_bound。我见过太多人把这几个容器当成孤立 API 去背，背完就忘。实际上它们是一条线下来的：vector 解决"数组长度不确定"的问题，set 解决"高效判断元素是否存在、自动去重"的问题，map 解决"键值对查找"的问题，stack 和 queue 解决特定的访问顺序问题，priority_queue 解决"每次都取最大或最小"的问题。拿到一道题，第一件事不是想"我用哪个容器"，而是想"这个题的核心操作是什么"，操作决定容器。这章每个容器后面都跟着一个例题：vector 配木块问题，set 配安迪的第一个字典，map 配反片语，priority_queue 配丑数。我的建议是不要跳过例题只看容器语法，例题才是容器真正的用武之地。光会 push_back 不叫会 vector，能判断出"这题该用 vector"才算入门。2. 容器代码笔记：vector、set、map 实操2.1 vector：动态数组的正确打开方式vector 是最基础的容器，本质是自动扩容的数组。你不需要关心容量上限，push_back 往里塞东西就行。但它也有短板：在中间插入或删除的代价很高，所以 vector 适合"只在尾部增删 + 随机访问"的场景。基本操作：#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> v; // 空 vector v.push_back(3); // 尾部追加，不是 push v.push_back(1); v.push_back(2); sort(v.begin(), v.end()); // 排序，需要 <algorithm> for (int i = 0; i < (int)v.size(); i++) cout << v[i] << " "; cout << "\n"; for (int x : v) cout << x << " "; // 范围 for，C++11 之后可用 cout << "\n"; return 0; }几个容易记混的点。第一，push_back 不是 push，很多人第一反应写 v.push(3)，编译直接报错。第二，v.size() 返回无符号整数，把它和 int 负数比较会出问题。比如空 vector 的 v.size() - 1 不是 -1，而是一个巨大的正数，遍历时 if (i < v.size() - 1) 这种判断就会莫名其妙成立。正确写法是把 size 强转为 int，或者用范围 for 绕开下标。第三，resize 和 reserve 不一样，resize 会改变元素数量，新增元素用默认值填充；reserve 只是预分配空间，不改变大小。频繁 push_back 导致多次扩容时会慢，提前 reserve 是常用的优化手段。书上木块问题整道题都在用 vector 做"取尾部、删尾部、移到另一堆"的操作，这几个操作换个容器都很别扭，但在 vector 上就是家常便饭。这道题值得完整敲一遍。2.2 set：有序集合与自动去重set 的中文叫集合，有两个特性：元素不能重复，内部自动排好序。这两个特性都是基于红黑树实现的，插入、删除、查找都是 O(log n)。如果用数组去重可能要两层循环 O(n^2)，set 就是帮你省这个时间的。#include <iostream> #include <set> using namespace std; int main() { set<int> s; s.insert(5); s.insert(1); s.insert(5); // 重复插入无效 cout << s.count(5) << "\n"; // 1，count 用于判断是否存在 cout << s.size() << "\n"; // 2，5 只被算一次 for (int x : s) cout << x << " "; // 输出 1 5，已排序 cout << "\n"; s.erase(1); // 按值删除 return 0; }set 的操作提醒三点。第一，count 只有 0 和 1 两种返回值，用来判断键是否存在比 find 写法简洁，别拿它当计数器用，想统计出现次数请用 map。第二，set 的迭代器是双向迭代器，不支持随机加减，你不能写 s.begin() + 2，想取第几个元素只能循环走。第三，遍历时删除元素是经典坑，正确姿势在后面的常见问题里专门讲。顺便提一句，set 还有个变种 multiset 允许重复元素，书后练习里偶尔用到。先理解 set，再补 multiset 就很容易。2.3 map：带下标访问的平衡树map 是这一章里我个人觉得最常用的容器。它存键值对，内部也是红黑树，自动按键排序。用法像数组下标，但下标可以是任意类型。比如统计每个字符串出现次数，用 map 一行解决：#include <iostream> #include <map> #include <string> using namespace std; int main() { map<string, int> cnt; string words[] = {"apple", "banana", "apple"}; for (string w : words) cnt[w]++; // 键不存在时自动创建，int 默认 0 for (auto p : cnt) cout << p.first << " " << p.second << "\n"; // 按键的字典序输出：apple 2 banana 1 return 0; }这里的核心知识点是：cnt[w] 在键 w 不存在时会自动插入一个键值对，int 的默认值是 0，所以 cnt[w]++ 不需要提前判断。这是竞赛里很爽的懒人写法，但它有代价：如果只是想查一下键在不在，用 cnt[w] 会无意中把键插进去，污染数据。这种情况用 cnt.count(w) 判断，或者用 cnt.find(w)，找到的迭代器指向一个 pair。map 遍历时 p 是一个 pair，p.first 是键，p.second 是值。数据量大时建议写成 for (auto &p : cnt)，加引用避免拷贝。书上反片语那道题是 map 的标准应用：把每个单词标准化（转小写后排序），用标准化结果做键，原始单词做值，最后输出只出现一次的单词。这个思路很经典，它是很多真正竞赛题的原型。3. stack、queue、priority_queue：三种队列的战场3.1 stack 与 queue 的基础模板stack 和 queue 是结构上完全相反的两个容器。栈是后进先出，像一摞盘子，只能从顶上拿；队列是先进先出，像排队买票，先来的先办。#include <iostream> #include <stack> #include <queue> using namespace std; int main() { stack<int> st; st.push(1); st.push(2); cout << st.top() << "\n"; // 2，栈顶 st.pop(); // 出栈 cout << st.top() << "\n"; // 1 queue<int> q; q.push(1); q.push(2); cout << q.front() << "\n"; // 1，队头 q.pop(); // 出队 cout << q.front() << "\n"; // 2 return 0; }注意 stack 的操作是 top()，queue 是 front() 和 back()。stack 没有 front，queue 没有 top，这两个很容易混。另外 empty() 判断要养成习惯，在空栈或空队列上调用 top/pop 是未定义行为，本地可能不报错，OJ 上直接 Runtime Error。书上团体队列那道题会用到 queue 的组合技巧：用队列存团体编号，再用多个队列存每个团体内部的成员。这是"队列套队列"的思路，初学者会觉得绕，但它把 queue 的适用范围拓展得很清楚，理解了它，后面碰到复杂的模拟题心态会稳很多。3.2 priority_queue：默认是大根堆，别搞反了优先队列是竞赛神器，它每次弹出的是当前所有元素里最大的那个。内部实现是二叉堆，插入和弹出的复杂度都是 O(log n)。很多人第一次用会犯一个经典错误：以为弹出的是最小的，结果数据一跑全错。#include <iostream> #include <queue> using namespace std; int main() { priority_queue<int> pq; pq.push(3); pq.push(5); pq.push(1); cout << pq.top() << "\n"; // 输出 5，默认大根堆 pq.pop(); // 移除 5 cout << pq.top() << "\n"; // 输出 3 return 0; }如果你想要小根堆，要把模板参数补齐：priority_queue<int, vector<int>, greater<int>> pq; // 小根堆这里很多人会把 greater 和 less 搞反。记忆方式是：less 对应默认的大根堆，它会认为"小的排后面"，所以堆顶是大的；greater 反过来，认为"大的排后面"，堆顶就是小的。这个知识点只能靠多写几次形成肌肉记忆，比赛前一紧张确实容易写反，我建议调试时先打印 top() 验证一下。自定结构体放进 priority_queue 时，重载 operator< 的方向更要小心。堆顶是"小于关系中的最大值"，所以让分数高的排在前的结构体，反而要写 return score < other.score，这个逻辑反直觉，建议写完之后用一个三个元素的用例实测一遍。3.3 完整套路：丑数这道题怎么用 priority_queue书上的丑数题是理解 priority_queue 的最佳案例。题目大意是质因数只有 2、3、5 的数叫丑数，问第 1500 个丑数是多少。暴力从小到大找肯定超时，正确思路是用一个小根堆，先把 1 放进去，每次弹出最小数，再把它乘以 2、3、5 推进去，配合 set 去重，弹出的第 1500 个数就是答案。#include <iostream> #include <set> #include <queue> using namespace std; int main() { priority_queue<long long, vector<long long>, greater<long long>> pq; set<long long> seen; pq.push(1); seen.insert(1); long long x = 1; for (int i = 1; i <= 1500; i++) { x = pq.top(); pq.pop(); for (long long f : {2LL, 3LL, 5LL}) { long long nx = x * f; if (!seen.count(nx)) { seen.insert(nx); pq.push(nx); } } } cout << "The 1500'th ugly number is " << x << ".\n"; return 0; }这段代码有几个细节值得抠。第一，用 long long 而不是 int，因为丑数增长很快，第 1500 个已经接近 8.6 亿，后面的更大。第二，for (long long f : {2LL, 3LL, 5LL}) 是 C++11 的初始化列表遍历，如果编译器太老，改成三次重复的 push 语句即可。第三，set 在这里兼任"已入堆标记"，防止同一个丑数被 2×3 和 3×2 两条不同路径重复推进堆里，这是枚举类题目里通用的去重技巧，优先级队列加集合的组合以后会反复用到。4. 排序与检索：sort、lower_bound、unique 三剑客4.1 sort 的正确姿势sort 是 STL 里使用频率最高的算法函数。它支持数组和 vector，默认从小到大排序，复杂度 O(n log n)，底层是内省排序，最坏情况下不会退化到 O(n^2)，比自己手写快排稳。#include <iostream> #include <algorithm> using namespace std; int main() { int a[] = {4, 2, 9, 1}; sort(a, a + 4); // 数组：传首地址和尾后地址 for (int i = 0; i < 4; i++) cout << a[i] << " "; cout << "\n"; sort(a, a + 4, greater<int>()); // 降序 sort(a, a + 4, [](int x, int y) { return x > y; }); // lambda 写法 return 0; }自定义比较函数有一个硬性规则：必须满足"严格弱序"。简单说就是两个元素相等时，比较函数必须返回 false，不管参数顺序怎么传。写成 return x <= y 就是反例，sort 内部做条件判断时可能直接崩掉。正确的写法是 return x < y 或 return x > y。结构体排序是高频内容。写一个结构体数组，想按某个成员排序，最方便是在结构体里重载小于号：struct Student { int score; string name; bool operator<(const Student& other) const { return score > other.score; // 分数高的排前面 } };重载之后，sort(a, a + n) 就自动按你定义的规则排。注意 const 别漏，有的编译器漏了能通过，换一个就报"no match for operator<"，这是竞赛里最常见的编译错误之一。4.2 lower_bound 与去重组合拳排序之后往往跟着检索。lower_bound 是 STL 提供的二分查找，返回第一个大于等于给定值的位置，只适用于有序序列。书上大理石在哪儿的检索部分就是这个用法：sort(a, a + n); int p = lower_bound(a, a + n, x) - a; if (p < n && a[p] == x) printf("%d found at position %d\n", x, p + 1); else printf("%d not found\n", x);lower_bound 返回的是指针或迭代器，减去首地址得到下标。判断时注意越界：如果所有元素都小于 x，lower_bound 返回尾后位置，p 可能等于 n，此时直接访问 a[p] 就越界了，所以必须先判断 p < n。和 lower_bound 经常一起出现的是 unique，它去除相邻重复元素。注意是"相邻"，所以要先 sort 再 unique 才能整体去重。unique 返回去重后新序列的尾后迭代器，想真正删掉后面多余的元素，在 vector 上要配合 erase：sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());这行代码是竞赛里的去重标配，建议背下来。很多人只写 unique 忘了 erase，结果 size 没变，重复元素只是被移到末尾了，看着没问题，一输出就露馅。5. 常见问题与排查技巧实录5.1 迭代器失效问题迭代器失效是 STL 新手最容易踩的深坑。vector 在 push_back 扩容时，所有迭代器都会失效；set 用 erase 删除元素后，指向被删元素的迭代器也失效。最常见的错误是边遍历边删除：// 错误写法：erase 之后 it 已经失效 for (set<int>::iterator it = s.begin(); it != s.end(); it++) { if (*it % 2 == 0) s.erase(it); }C++11 之后 erase 会返回下一个有效迭代器，正确写法是：for (auto it = s.begin(); it != s.end(); ) { if (*it % 2 == 0) it = s.erase(it); else it++; }vector 的 erase 也返回迭代器，处理方式类似。这个细节很多入门书讲得不够清楚，都是自己调几次才能领悟，提前记住能省不少调试时间。5.2 cin/cout 太慢怎么办从 C 切到 C++ 后，很多人发现程序跑得比以前慢，以为是 STL 的性能问题。其实大部分是输入输出在拖后腿。cin 和 cout 默认和 stdio 保持同步，效率很低。解决办法只有一行：ios::sync_with_stdio(false); cin.tie(0);第一行取消同步，第二行解除 cin 和 cout 的绑定。写完后 cin/cout 速度接近 scanf/printf。注意一点：一旦开了 sync_with_stdio(false)，就不要混用 cin 和 scanf，否则数据可能错乱。要么全用 cout，要么全用 printf，不要一把梭。5.3 常见报错速查表我把新手阶段最容易撞上的问题整理成一张表，遇到报错可以回来对着查：报错现象可能原因解决办法编译提示没有 begin/end忘写对应容器头文件补全 #include 等printf 输出 string 出错string 不是 char*用 s.c_str() 或改用 coutmap 查 key 时数据莫名变多operator[] 会插入新键用 count 或 find 代替priority_queue 弹出最大值默认是大根堆加 greater 变最小堆sort 自定义比较时崩溃比较函数不满足严格弱序改为 return x < y空容器上调用 top/front没判 empty先 empty() 再取元素结构体放入 set/map 报错没有重载 operator<在结构体里补一个 operator<size() 和负数比较异常size_type 是无符号数强转 int 再比较这张表不是让你背的，是让你真遇到问题时回来看。如果编译报错里出现类似"no match for operator<"的英文，第一反应就应该是"结构体是不是没写重载"。5.4 关于头文件：不要只写一个万能头文件很多 OJ 支持 #include <bits/stdc++.h> 万能头文件，一次包含全部标准库。比赛时图省事用它对结果没影响，比赛只求 AC 不看头文件规范。但平时练习我不建议只写它，原因是你会搞不清每个容器到底依赖哪个头文件。理解"set 在里、map 在里、sort 在 里"这件事，对你以后阅读复杂代码、定位编译错误都有帮助。折中方案：平时练习写标准头文件，比赛时随意。6. 我的学习路线与补充建议把这一章完整过一遍，大概需要 3 到 5 天，看之前 C 语言基础而定。我建议的顺序是：先跑一遍书上示例代码，改几个参数体会每个容器的行为；再把每个容器对应的例题独立敲一遍，不要复制；最后从章末练习题里挑三道容器题做掉。这个过程不用追求一天刷完，容器之间的差异需要睡一觉才能沉淀进脑子里。从我带过的学生经验看，最容易出的问题反而是"学完就忘"。今天学了 map，一个星期后遇到统计字符串频率的题，还是下意识开两个数组硬顶。这很正常，唯一解药是多用。你可以挑一道旧题，强制自己用 STL 重写一遍，比如以前用数组标记的题目换成 map，以前手写排序的换成 sort。重写过程中你会不断碰到迭代器、类型相关的坑，踩过一次就记住了。最后再分享一个小技巧：遇到不确定的容器用法，别急着翻书，先写一个十行以内的小程序跑一下。我到现在还会这么干，比如 set 的 erase 返回值、map 的 emplace 行为，与其猜，不如让编译器告诉我。这种实验驱动的学习方式，比背任何笔记都管用。把第5章打扎实，后面刷题的速度会明显上一个台阶。