C++ 竞赛入门
STL 总结
按需求选工具：容器与算法选择表、复杂度速查与选择自测。
STL 总结
读完能做什么
- 拿到一个任务，能先问“数据要按什么规则存、按什么规则取”，再说出该用哪种容器。
- 能说出
vector、set、map、queue、priority_queue处理同一组[3,1,3,2]时，各自观察到的结果有什么不同。 - 能根据“保存重复记录 / 按先来后到处理 / 统计出现次数 / 找第 k 小”选出对应工具。
- 能说出常见误区：
unique只合相邻、sort不稳定、map[]会插入、binary_search返回布尔值。
为什么需要它
学完前面各页，你手里多了一堆名字：vector、list、set、map、queue、stack、priority_queue、sort、find、unique……真正的难点不再是“某个函数怎么用”，而是遇到一道题，该选哪一个。
这一页不重复讲语法，只做一件事：把“需求”和“工具”对上号，并指出每个选择背后的理由。
它是什么
一句话：这是一张任务 → 工具的对照表，外加几条判断依据。
选择时先回答两个问题：数据要按什么规则保存？按什么规则取出来？
graph TD
A["拿到一个问题"] --> B{"数据按什么规则取用？"}
B -->|"按先后顺序一条条处理"| C["queue：先进先出"]
B -->|"后进的先处理"| D["stack：后进先出"]
B -->|"每次取最大或最优先"| E["priority_queue"]
B -->|"按下标随机访问"| F["vector 或 deque"]
B -->|"按键查找、要不要重复"| G["set 或 map"]
最小可运行示例
同一组数据 [3,1,3,2]，放进不同容器，看到的东西完全不同：
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v = {3, 1, 3, 2};
cout << "vector 保存原顺序：";
for (int x : v) cout << x << ' ';
cout << '\n';
set<int> s = {3, 1, 3, 2};
cout << "set 有序去重：";
for (int x : s) cout << x << ' ';
cout << '\n';
map<int, int> cnt;
for (int x : v) cnt[x]++;
cout << "map 逐项计数：";
for (const auto& p : cnt) cout << p.first << ':' << p.second << ' ';
cout << '\n';
queue<int> q;
for (int x : v) q.push(x);
cout << "queue 先进先出：";
while (!q.empty()) {
cout << q.front() << ' ';
q.pop();
}
cout << '\n';
priority_queue<int> pq;
for (int x : v) pq.push(x);
cout << "priority_queue 最大值优先：";
while (!pq.empty()) {
cout << pq.top() << ' ';
pq.pop();
}
cout << '\n';
return 0;
}输出：
vector 保存原顺序：3 1 3 2
set 有序去重：1 2 3
map 逐项计数：1:1 2:1 3:2
queue 先进先出：3 1 3 2
priority_queue 最大值优先：3 3 2 1 同一份输入，差别不在“算了什么”，而在你从容器里观察到的是什么：存储内容、计数结果，还是取出顺序。
一步步看变化
| 容器 | 你观察的是 | [3,1,3,2] 进去之后看到 |
为什么 |
|---|---|---|---|
vector |
存储内容 | 3 1 3 2 |
按原顺序保存，重复值也照样留着 |
set |
存储内容 | 1 2 3 |
自动去重并升序排列 |
map |
计数结果 | 1:1 2:1 3:2 |
把每个值当键，累加出现次数 |
queue |
取出顺序 | 3 1 3 2 |
先进先出，和入队顺序相同 |
priority_queue |
取出顺序 | 3 3 2 1 |
每次取出当前最大值 |
读这张表时要分清两件事：
vector和set比较的是存下来什么。queue和priority_queue比较的是取出来什么顺序（queue里确实还存着3 1 3 2，只是取出次序恰好一致；priority_queue每次弹最大）。map记录的是统计结果，原来的顺序和重复都不重要了。
逐项扩展核心操作
容器选择表
| 需求 | 选它 | 链接 |
|---|---|---|
| 按下标随机访问，主要在尾部增删 | vector |
vector 动态数组 |
| 两端都要能高效进出 | deque |
deque 双端队列 |
| 已知位置时频繁在中间插删 | list |
list 链表 |
| 后进先出 | stack |
stack 栈 |
| 先进先出 | queue |
queue 队列 |
| 每次取最大/最优元素 | priority_queue |
priority_queue 优先队列 |
| 有序且不重复 | set |
set 有序集合 |
| 有序且允许重复 | multiset |
set 有序集合 |
| 按键找到对应的值 | map |
map 键值映射 |
| 一个键对应多条记录 | multimap |
multimap 一键多值 |
| 两个相关值放在一起 | pair |
pair 二元组 |
| 处理字符串 | string |
string 字符串 |
| 一组二进制开关 | bitset |
bitset 位集 |
算法选择表
| 任务 | 选它 | 前提 | 链接 |
|---|---|---|---|
| 找出某个值在不在、在哪 | find |
无 | find 查找 |
| 找第一个满足条件的元素 | find_if |
需要一个判断条件 | find 查找 |
| 把数据按规则排序 | sort |
无 | sort 排序 |
| 排序且保持同值原顺序 | stable_sort |
无 | sort 排序 |
| 判断有序数据里有没有某值 | binary_search |
区间已按同一规则有序 | 二分查找 |
找第一个不小于 x 的位置 |
lower_bound |
区间已有序 | 二分查找 |
找第一个大于 x 的位置 |
upper_bound |
区间已有序 | 二分查找 |
| 合并相邻重复 | unique |
重复值已经相邻 | unique 去重 |
| 全体数值去重 | sort + unique + erase |
允许改变顺序 | unique 去重 |
| 找第 k 小 | nth_element |
1 <= k <= n |
nth_element 第 k 小 |
复杂度速查
| 操作 | 复杂度 | 说明 |
|---|---|---|
vector 下标访问 |
O(1) | 连续存放，直接定位 |
vector 尾部 push_back / pop_back |
摊还 O(1) | 偶尔扩容较贵，摊到多次操作上仍接近常数 |
vector 中间 insert / erase |
O(n) | 后面的元素要整体搬动 |
list 已知位置的 insert / erase |
O(1) | 但“找到那个位置”仍要 O(n) |
set / map 查找、插入、删除 |
O(log n) | 树结构维护有序 |
priority_queue push / pop |
O(log n) | top 是 O(1) |
stack / queue 的 push / pop / front |
O(1) | 只在端点操作 |
sort |
O(n log n) | 不保证同值原顺序 |
find |
O(n) | 从头线性查找 |
binary_search / lower_bound / upper_bound |
O(log n) | 前提是区间有序 |
unique |
O(n) | 顺着走一遍 |
nth_element |
平均 O(n) | 只保证第 k 小就位，不完成整体排序 |
什么时候选它、哪里容易错
unique 不是“全体去重”。 它只合并相邻的相等元素，不排序直接调用，[1,2,1] 一个也去不掉。要全体去重，得自己加 sort 把相等的值聚到一起。见 unique 去重。
sort 不保证同值元素的原顺序，stable_sort 才保证。 所以不要断言“不稳定排序后同分的次序是某某”；要保序就用 stable_sort。见 sort 排序。
map 的 operator[] 查不到会插入。 m[key] 在键不存在时会插入一个默认值，size() 变大；只查询用 find / count，它们不会插入。见 map 键值映射。
binary_search 返回的是布尔值，不是位置。 要位置得用 lower_bound / upper_bound，而且区间必须已经有序。见 二分查找。
priority_queue 的比较规则和 sort 方向相反。 sort 的规则写“谁在前”，priority_queue 的规则决定“谁在顶”；默认 less 时 sort 升序、priority_queue 取最大值。见 priority_queue 优先队列。
queue / stack 没有迭代器，不能遍历。 它们只开放两端操作，想看内容只能不断取出（或打印副本）。见 queue 队列、stack 栈。
set 的元素是常量，不能改。 想“改”一个键，只能删掉再插入。见 set 有序集合。
插删之后旧迭代器可能失效。 尤其 vector 扩容或中间插删时，之前记下的迭代器要重新获取。见 容器、迭代器与区间。
操作速查表
| 你的任务 | 一句话选择 |
|---|---|
| 按下标存一批数，长度不定 | vector |
| 两端进出 | deque |
| 已知位置频繁插删 | list |
| 后进先出 | stack |
| 先进先出 | queue |
| 每次要最大 / 最优先 | priority_queue |
| 去重并保持有序 | set |
| 按键找值 | map |
| 一个键多条记录 | multimap |
| 查找值 / 找第一个满足条件的 | find / find_if |
| 排序 / 保序排序 | sort / stable_sort |
| 在有序数据里查边界 | binary_search / lower_bound / upper_bound |
| 相邻去重 / 全体去重 | unique / sort + unique + erase |
| 找第 k 小 | nth_element |
动手检查：选择自测
先自己选，再展开折叠核对。
- 保存重复记录：要读入
n条成绩，其中可能有相同的分数，输出时还要保持输入顺序。用哪种容器？ - 按先来后到处理：有一批任务按到达顺序排队，必须严格按到达先后处理。用哪种容器？
- 统计出现次数：读入一串数，最后要输出每个不同的数出现了几次。用哪种容器？
- 找第 k 小：只想知道第 k 小的值是多少，不需要把整串数排好。用哪个算法？
参考结果与解释
vector：它按原顺序保存，也不去重，正好符合“保留重复、保持顺序”。用 vector 一路push_back即可。queue：先进先出。用 queue 读入时push，处理时front+pop，取出顺序就是到达顺序。map：把每个数当键，遇到一次就cnt[x]++，最后遍历输出键和计数，是逐项统计的标准做法。见 map。如果只关心“出现过没有”，用 set 就够了。nth_element：它让第 k 小的元素就位，但不把整串排好，平均 O(n)，比整体sort的 O(n log n) 更快。见 nth_element。验证下面程序：
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v = {7, 2, 5, 1, 9};
int k = 3;
nth_element(v.begin(), v.begin() + (k - 1), v.end());
cout << "第 " << k << " 小 = " << v[k - 1] << '\n';
return 0;
}输出：
第 3 小 = 5立即练习
本页是总结与选择页，重点在“根据需求选工具”，已经有选择自测；具体的 OJ 题目按各个专题页的「立即练习」安排，这里不再重复。