课程 · C++ 速查 · STL 专题

STL 专题

适用信息学奥赛的 C++ 标准库。一个板块一页,从头读到尾就能学会 —— 每页六段:这是什么 → 完整动作表(带复杂度)→ 可运行的例子 → ⭐ 这一节最容易错的地方 → 本书哪一章真的用到它 → 练习(答案折叠)。

12 个板块已写好 12 块122 条动作32 处陷阱49 道题36 个真实指针
先读这一段,它解释了为什么这个模块存在

正课 53 章是按算法排的,不是按 C++ 语法排的。于是有些东西会出现得很早、讲得很晚。 量过一遍全书 code/ 下两千多份代码:

vector< 1534 份 string 675 份 sort( 272 份 queue< 179 份 array< 126 份 priority_queue 88 份 set< 94 份 lower_bound 38 份

而没有任何一章教过它们本身怎么用、怎么选、哪些写法会 WA。 算法全都会用,工具全都没学过 —— 而 OI 里扣分最多的恰恰是工具的坑。

vector 从第 1 章就在用,而讲透它的一整章到现在还没有。 这个模块就是补那一块。

和 C++ 速查 什么关系 —— 别用错那一张

两页是同一件事的两根轴,形状故意不同:

  • C++ 速查 是查的表。一屏能 Ctrl-F 完, 假设你已经会变量、if、for、函数和普通数组。 忘了某个写法怎么写,去那儿。
  • STL 专题(这一份)是学的课。从「这是什么」讲起,含可运行例子和练习。零基础从第 1 块读起,读三块就能覆盖 OI 里 90% 的 STL 用法。

速查里的每一条 STL 都加了「想学 →」指向这里,但两份刻意不合并: 合并的后果是速查那一页再也不能一屏看完。

⚠ 这一页不重复正课 —— 它指的是「本书哪一章真的用到它」

每个板块末尾都有一张表,列的是这份代码在书里真的出现在哪一章的哪一份文件里, 而且那串 probe 是逐字验过的(check:docs 第 ⑳ 条)。

★ 顺带你会发现书里已经有几份专门讲 STL 的代码,它们和这个模块是配套的,不是重复:

code/10-sorting/stl.cpp(为什么排序一律用 std::sort) ·code/08-binary-search/stl.cpp(lower_bound / upper_bound)  · code/22-lis/stl.cpp(LIS 的 O(n log n) 写法)  · code/37-heap/stl.cpp(priority_queue 那三个模板参数)

九个板块

顺序不是按 STL 官方分类排的,是按依赖 + OI 里的出错频率排的: 先学用得最多、最容易错的,不学「C++ 有但 OI 不用」的东西。

第 0 块 C++ 上路先知道这几句

开始学 →

认出每份代码前两行都在干什么,知道 auto 是什么,知道读一行和读一个词的区别,以及 size() 为什么不能直接和 int 比。

8 条动作 · 3 处陷阱  · 2 道例题 + 3 道练习 ·   · 用到的章:第 1 章第 1 章

第 1 块 前置知识:比较器和「把函数当参数传」

开始学 →

搞清 sort 问的那个问题「a 该排在 b 前面吗」是什么,并学会把一个自己写的函数交给 sort。

9 条动作 · 3 处陷阱  · 2 道例题 + 2 道练习 ·   · 用到的章:第 10 章第 10 章第 16 章

第 2 块 vector:常用的几种写法

开始学 →

学会 vector 的常用动作:开一个、往后加、按下标取、遍历一遍、把要留的挑出来。

14 条动作 · 1 处陷阱  · 2 道例题 + 2 道练习 ·   · 用到的章:第 1 章第 29 章第 53 章

第 3 块 string:读一整行、切词、找子串

开始学 →

学会读一整行和读一个词的区别,以及拼接、截子串、找子串这三件常用的事。

13 条动作 · 3 处陷阱  · 2 道例题 + 2 道练习 ·   · 用到的章:第 47 章第 47 章第 40 章第 48 章

第 4 块 sort:排序和自定义比较器

开始学 →

学会 sort 的升序/降序/只排一段,以及要按多个条件排时怎么写比较器。

12 条动作 · 4 处陷阱  · 2 道例题 + 2 道练习 ·   · 用到的章:第 10 章第 10 章第 34 章

第 5 块 lower_bound 和 upper_bound:在排好序的数组上找

开始学 →

学会用这两个函数在一个排好序的数组里找位置,以及数一个区间里有多少个数。

8 条动作 · 3 处陷阱  · 2 道例题 + 2 道练习 ·   · 用到的章:第 8 章第 22 章

第 6 块 queue / stack / deque:一头动还是两头动

开始学 →

学会三个容器的常用动作,认准「谁从哪头进出」,以及 BFS 那五句骨架。

12 条动作 · 3 处陷阱  · 2 道例题 + 2 道练习 ·   · 用到的章:第 14 章第 35 章第 35 章

第 7 块 priority_queue:每次拿走最大的那个

开始学 →

学会堆的四个动作,以及「最小的先出」时那串三个参数的模板怎么写。

8 条动作 · 3 处陷阱  · 2 道例题 + 2 道练习 ·   · 用到的章:第 19 章第 37 章第 37 章第 32 章

第 8 块 map:键 → 值的一张表

开始学 →

学会「键 → 值」的 map:计数、映射、增查删遍历,最要紧的是分清 m[k] 和 m.count(k)。

8 条动作 · 2 处陷阱  · 2 道例题 + 2 道练习 ·   · 用到的章:第 45 章第 49 章

第 9 块 set:去重、查在不在、从小到大

开始学 →

学会自动去重、自动有序的 set:增、查、删、遍历,以及什么时候该用它而不是 map。

7 条动作 · 1 处陷阱  · 2 道例题 + 2 道练习 ·   · 用到的章:第 3 章第 36 章

第 10 块 bitset / array / pair:三个顺手的小件

开始学 →

学会三个「个数写死」的现成小件:pair 自带比较规则、array 长度写死、bitset 当一排开关。

13 条动作 · 3 处陷阱  · 2 道例题 + 2 道练习 ·   · 用到的章:第 23 章第 11 章第 11 章第 49 章

第 11 块 对拍与随机数据:让 bug 自己跑出来

开始学 →

学会 mt19937 造可复现的随机数据、把边界塞进生成器、用 assert 自查,以及暴力与正解对拍的骨架。

10 条动作 · 3 处陷阱  · 2 道例题 + 2 道练习 ·   · 用到的章:第 8 章第 21 章第 8 章第 27 章

⚠ 一个贯穿全模块的规矩

这一模块里凡是靠未定义行为出错的演示,输出都不做成样例 —— 比如 v[1000000] 越界读、拿减法当比较器。 它们在正文里只贴代码,并说清「换个编译器可能完全不一样」。

原因很实在:2026-10-05 写第 2 块时就实测到,同一个表达式在同一台机器上 因为「编译期折叠」还是「运行期算」而给出相反的答案。能做成样例的只有确定的那一半 —— 这个模块每一条数字都是这么分的。

下一步

零基础:从第 1 块 vector 开始,按顺序读三块。
已经会写题、只是查不动手:直接点上面你想查的那一块的「开始学」。
只想快速查一个写法:去 C++ 速查,一屏 Ctrl-F 更快。