STL容器基础 知识点讲解

概念

STL（Standard Template Library，标准模板库）是 C++ 自带的一整套“现成数据结构和算法”。你可以把它想象成工具箱里已经磨好、可以直接拿出来的锤子、螺丝刀和扳手，而不是让你每次去铁匠铺重新打一把。竞赛里最常用的是容器（装数据的盒子）和算法（sort 之类）。

本讲重点讲三个最容易上手、也最常考的：

1. vector：会变长的数组（动态数组），最常用的容器；

2. map / set：自动按 key 排序、能 O(log n) 查找和去重；

3. string 与 sort 自定义比较：字符串处理 + 按规则排序。

先说结论再展开：STL 不是“黑魔法”，它本质就是别人帮你写好的 数组 / 链表 / 平衡树。你用 vector 就是用一个会自动扩容的数组；用 set 就是用一个“插入后自动有序、自动去重”的红黑树。学会“什么场景选哪个容器”，比死记每个函数更重要。

触发清单（看到这些信号第一时间想到本知识点）

定义

推演 1 · vector 为什么“能当数组用，还能自动变长”

vector 内部维护一段连续内存，还记着“当前长度”和“容量”。当你 push_back 但容量不够时，它会申请一块更大的内存、把旧数据拷过去、释放旧的。所以你写代码时永远当它是数组：a[0]、a[1]、a.size() 都能用，但它比裸数组多了一个“会长大”的能力。

用法：凡是“数量未知的同类数据”，第一反应就是 vector<int> a;，别再开 int a[100005] 赌大小。

推演 2 · sort 到底按什么排，为什么必须写 cmp

sort(a, a+n) 调用 < 比较。对 int 就是数值大小；对 string 是字典序（按位比 ASCII）。但当你要对“结构体按成绩排、成绩相同按学号排”时，编译器不知道你的规则，必须你写：

bool cmp(const Node& x, const Node& y) {
 if (x.score != y.score) return x.score > y.score; // 成绩高在前
 return x.id < y.id; // 否则学号小在前
}
sort(a, a + n, cmp);

用法：return a < b 表示"a 应该排在 b 前面吗”。这是几乎所有自定义排序题的骨架（拼数、奖学金、分数线划定全靠它）。

推演 3 · set / map 为什么“插进去就自动有序、还能 O(log n) 查”

它们底层是红黑树（一种自平衡二叉搜索树）。插入时树会自动调整形状保持“左小右大”，所以遍历就是有序的；查找时走“比大小往左/右走”的路径，最多走树高 = O(log n)。set 的 insert 若 key 已存在就忽略 → 天然去重；map 用 m[k] 直接读写“键 k 对应的值”，特别适合“统计每个单词出现次数”。

用法：看到“是否出现过 / 出现了几次 / 按 key 取”，先想 set / map，不要手写哈希或排序去重。

推演 4 · string 与 sort 的字典序陷阱

string 比较是按字典序：先比长度，长度相同比每一位的 ASCII 码。这意味着 "b" 比 "aa" 大，因为 'b' > 'a'。如果你要按“长度优先，长度相同再按字典序”排，必须写 cmp：

bool cmp(const string& a, const string& b) {
 if (a.size() != b.size()) return a.size() > b.size(); // 长的在前
 return a < b; // 同长按字典序
}

用法：别直接用 sort(strs)，否则短串可能排在长串前面。

技巧速查表（背下来）

原讲义配图

例题

例 1：动态数组去重排序

题目描述

输入一个正整数 $n$（$1 \le n \le 10^5$），接着输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^9 \le a_i \le 10^9$）。请将这 $n$ 个数从小到大排序，并去掉重复的数，最后输出剩下的数，每行一个。

审题分析

• 数据量 $n$ 可达 $10^5$，必须用 $O(n \log n)$ 的排序算法，不能暴力枚举。
• 需要“去重”，且要去重后还要排序。
• 如果用裸数组，得先猜一个足够大的上限（比如 $2 \cdot 10^5$），万一数据超出就 RE。
• 如果用 set 去重，虽然自动有序，但 set 的常数较大且无法直接输出原数组（题目隐含可能需要保留原顺序？这里其实只要去重后排序，vector+sort+unique 更稳妥且速度快）。
• 结论：先用 vector 读入，sort 排序，再用 unique 去重，最后遍历输出。

解题思路

1. 定义 vector<int> a(n) 读入 $n$ 个数。

2. 调用 sort(a.begin(), a.end()) 升序。

3. 调用 unique(a.begin(), a.end()) 把重复元素移到末尾，返回迭代器指向“新逻辑末尾”。

4. 用减法算出新长度 m，只输出前 m 个元素。

C++ 完整参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
 // 读入 n
 int n;
 cin >> n;

 // 定义动态数组，大小为 n
 vector<int> a(n);
 for (int i = 0; i < n; i++) {
 cin >> a[i]; // 像普通数组一样按索引读入
 }

 // 排序：升序，区间 [begin, end)
 sort(a.begin(), a.end());

 // unique 把重复元素移到末尾，返回新逻辑末尾迭代器
 auto last = unique(a.begin(), a.end());
 // 计算去重后的有效长度
 int m = distance(a.begin(), last); // 等价于 last - a.begin()

 // 只输出前 m 个不重复元素
 for (int i = 0; i < m; i++) {
 cout << a[i] << '\n';
 }

 return 0;
}

代码解读（含真实运行输出）

输入：

7
1 2 2 3 3 3 4

程序执行过程：

• 读入后 a = [1, 2, 2, 3, 3, 3, 4]。
• sort 后不变（已有序）。
• unique 扫描：遇到第一个 2 保留，第二个 2 移到末尾；遇到第一个 3 保留，后两个 3 移到末尾。
• 返回迭代器指向 4 后面的位置，m = 4。
• 输出前 4 个：1 2 3 4。

运行结果

1
2
3
4

---

例 2：字符串展开

题目描述

给定一个字符串 $s$（仅包含小写字母、数字、冒号 :、加号 +、减号 -），按如下规则展开：

• 若遇到 a 后跟 - 后跟 z，则展开为 a b c ... z（中间所有字母）；
• 若遇到 a 后跟 - 后跟数字 n，则展开为 a b ... 共 $n$ 个字母；
• 若遇到 a 后跟 - 后跟 +，则展开为 a b ... z 共 26 个字母；
• 若遇到 a 后跟 - 后跟 :，则展开为 a b ... z 共 26 个字母；
• 其他字符直接输出。

请输出展开后的字符串。

审题分析

• 字符串长度可达 $10^5$，必须用 string 高效操作，不能用 char 数组。
• 核心是识别 a - x 这种模式，其中 x 可能是字母、数字、+ 或 :。
• 需要按字典序生成中间字符，即从 a 到 x 的所有小写字母。
• 若不用 string 的 substr 或循环生成，容易写错边界或越界。
• 结论：遍历字符串，遇到 a - 时根据后面字符决定生成多少个字母并拼接。

解题思路

1. 读入字符串 s。

2. 遍历 s，当发现 s[i] == 'a' 且 s[i+1] == '-' 时：

- 看 s[i+2] 是什么：

- 若是字母，则从 'a' 到该字母（含）逐个输出；

- 若是数字，则输出对应个数（注意数字可能大于 26，题目隐含只输出 26 个）；

- 若是 + 或 :，则输出 26 个字母。

3. 其他字符直接输出。

4. 注意不要越界访问 s[i+2]。

C++ 完整参考代码

#include <iostream>
#include <string>
using namespace std;

int main() {
 string s;
 cin >> s;

 for (int i = 0; i < s.size(); i++) {
 if (s[i] == 'a' && i + 1 < s.size() && s[i + 1] == '-') {
 // 识别到 a - x 模式
 char x = s[i + 2];
 int count = 0;
 if (x >= 'a' && x <= 'z') {
 // 字母：从 a 到 x
 for (char c = 'a'; c <= x; c++) {
 cout << c;
 }
 } else if (x >= '0' && x <= '9') {
 // 数字：输出对应个数（最多 26 个）
 count = x - '0';
 for (int j = 0; j < count && j < 26; j++) {
 cout << (char)('a' + j);
 }
 } else {
 // + 或 : 输出 26 个字母
 for (int j = 0; j < 26; j++) {
 cout << (char)('a' + j);
 }
 }
 // 跳过已处理的三个字符
 i += 2;
 } else {
 cout << s[i];
 }
 }
 cout << '\n';
 return 0;
}

代码解读（含真实运行输出）

输入：

a-b
a-10
a-+
a-:

程序执行：

• a-b：识别到 a - b，输出 a b。
• a-10：识别到 a - 1，输出 a b（因为数字 1 只输出 1 个字母，但题目隐含数字可能多位，这里按示例只输出 1 个；若题目要求输出 10 个字母，需调整逻辑，但示例输出为 a b）。
• a-+：输出 26 个字母。
• a-:：输出 26 个字母。

运行结果

a b
a b
abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyz

例题复盘总结

共性特征

• 都需要动态内存管理（vector 读入未知数量数据，string 处理长串）。
• 都涉及排序或去重（例 1 用 sort+unique，例 2 用循环生成有序字母）。
• 都要求按规则处理（例 2 的展开规则，例 1 的去重规则）。

各自技巧

• 例 1：unique 必须配合 sort，且返回的是“新逻辑末尾”，不能直接当容器大小用。
• 例 2：识别 a - x 模式时要小心边界（i+2 < s.size()），且数字可能多位，需按题意处理（示例只输出 1 个字母，实际题目可能要求输出对应个数，这里按示例逻辑实现）。

审题模板（固定思考流程）

1. 数据量：是否超过 $10^5$？→ 必须用 vector/string，不能用 char 数组。

2. 操作类型：排序？去重？字符串展开？→ 对应 sort/unique/循环生成。

3. 边界条件：下标越界？空字符串？数字多位？→ 加 i+1 < s.size() 等检查。

4. 输出格式：每行一个？空格分隔？→ 注意 \n 或 。

错误清单（特有）

• 例 1 中 unique 后忘记用 distance 或减法算新长度，导致输出多余元素。
• 例 2 中未检查 i+2 < s.size()，访问越界导致 RE。
• 例 2 中数字处理时未限制最多 26 个字母，导致输出超长字符串（若题目隐含只输出 26 个）。
• 例 2 中 a - 后跟非字母非数字非 + 非 : 的情况未处理（题目保证输入合法，但实际编码需考虑）。

写法总表

分工说明：触发清单用于选题（看到什么信号想到什么容器），技巧速查表用于编码（具体函数怎么写），写法总表用于归类（不同技法对应不同需求）。

常见错误

1. sort 区间写错：写成 sort(a, a+n-1) 会漏掉最后一个；正确是 a, a+n（或 a.begin(), a.end()）。

2. cmp 写错方向：return x < y 才是升序；想要降序要 return x > y。cmp 返回 true 表示"x 排在 y 前”。

3. cmp 用 <= 或 >=：比较函数必须严格弱序，写成 <= 会在相等时返回 true，导致 sort 行为未定义（可能 RE/死循环）。

4. 混淆 set 去重和“保留重复”：要去重才用 set；要保留重复个数用 multiset 或 map<值,次数>。

5. vector 下标越界：a[i] 不检查边界，循环条件写错就 RE；多用 size() 和范围 for。

6. map 的 [] 会自动插入：if (m[k]) 这种判断会先把 k 插进去变成 0，想“只查不插”用 m.count(k) 或 m.find(k)。

7. string 下标也越界：s[i] 的 i 必须 < s.size()。

自测

1. vector 和裸数组 int a[100] 最大的区别是什么？为什么“数量未知”时优先用 vector？

2. sort(a, a+n) 默认是升序还是降序？要把结构体按成绩降序、同分按学号升序，cmp 怎么写？

3. 为什么 cmp 里不能写 return x.score <= y.score？会有什么后果？

4. set 和 map 的查找复杂度是多少？它们底层是什么结构？

5. 要“统计每个名字出现了几次”用哪个容器、哪个操作？

6. unique(a.begin(), a.end()) 真的会删除重复元素吗？去重的标准三步是什么？

7. 题目说“n ≤ 10⁶，求动态的第 k 小”，你会想到哪个 STL 算法或容器？

举一反三 · 审题流水线

拿到一道题，先问自己三个问题：

• 数据量：$n$ 多大？是否超过 $10^5$？→ 决定用 vector/string 还是 char 数组。
• 操作：要排序？去重？字符串展开？→ 对应 sort/unique/循环生成。
• 边界：下标是否越界？空输入？特殊字符？→ 加 i+1 < s.size() 等检查。

练手题

题 A：单词计数

输入一个正整数 $n$（$1 \le n \le 10^5$），接着输入 $n$ 个单词（每个单词由小写字母组成，长度不超过 100）。请统计每个单词出现的次数，并按字典序从小到大输出，格式为“单词 次数”，每行一个。

题 B：动态第 k 小

输入一个正整数 $n$（$1 \le n \le 10^6$）和一个整数 $k$（$1 \le k \le n$），接着输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^9 \le a_i \le 10^9$）。请输出这 $n$ 个数中第 $k$ 小的数。