登录以参加训练计划
第四周 · STL 原创专项训练
这份题单共 18 题:STL001–STL015 为 15 道基础与应用题,STL016–STL018 为 3 道选做题,其中 STL018 是进阶练习。训练使用 C++17,围绕“选对容器、读懂接口、处理边界、解释复杂度”展开。
目录按八章组织。章节之间不设置“必须 AC 前一章才能进入下一章”的硬门槛,可以按自己的基础选择顺序。题号链接可直接打开题面,章节说明包含对应接口和练习建议。
开始训练: 点击右侧 “参加训练”,启用章节列表并记录做题进度。也可以直接点击下面表格里的题号查看题面。
建议先从 STL001 动态清单 开始;STL016–STL018 可以留作选做。
怎样练一题
先把样例逐步写成容器状态,再独立实现。每做完一题,至少自己补充空容器或最小规模、重复值、端点和整数范围四类检查;不适用空容器的题,改查单元素或完整区间。调试时记录“输入触发了什么情况、哪个接口使用不当、怎样修正”,比只记录 AC 次数更有帮助。
建议每天安排 1.5–2 小时,可以把这份“第四周”题单拉到两周完成。一次训练可参考:15–20 分钟阅读接口与手算样例,45–60 分钟独立实现和调试,20–30 分钟补边界、写简短复盘或重做一种解法。时间分配可以调整,选做题也可以留待以后继续,不要求在固定天数内完成。
第一章:动态序列
| 题目 | 主练 STL | 建议练法与检查点 |
|---|---|---|
| STL001 动态清单 | vector |
用 push_back、back、pop_back、size、empty 维护尾部。GET 是 0 基下标;先检查负数和越界,再访问。自己构造连续弹空和重复编号。 |
| STL002 文本拼接站 | string |
练 append 或 +=、substr、insert、find。CUT 保留半开区间 [l,r),substr 第二参数是 r-l;串尾允许插入。区分空串、空区间、首次匹配和 string::npos。 |
先完成下面的小实验一,再写动态清单。字符串题用于练接口,数据限制还包括输入字符串总长、修改输出总长和累计 FIND 工作量;构造自己的测试时也要遵守题面预算。一次插入、截取或查找的代价与字符串长度有关,不能把所有字符串操作都当作 O(1)。
第二章:排序去重
| 题目 | 主练 STL | 建议练法与检查点 |
|---|---|---|
| STL003 编号归档 | sort、unique、erase、set |
必做两解:先排序,再 erase(unique(begin,end),end);另用 set 插入并升序输出。比较相同输入、不同数量重复值下的逻辑和容器大小。 |
| STL004 三维任务排序 | 自定义 sort 比较器 |
按 priority 降序、deadline 升序、id 升序逐字段比较。手造第一字段相同、前两字段都相同的记录,检查第三字段规则。 |
unique 只把不同元素放到区间前部并返回新的逻辑终点,不会改变 vector::size();没有 erase 就没有真正缩小容器。未排序时,它也只消除相邻重复。set 会自动去重并保持排序,但不能保存多份相同键。
比较器必须满足严格弱序。相同对象与自身比较应返回 false,不要用 <= 或 >= 代替 < 或 >;也不要直接用整数相减作为布尔比较结果。sort 默认不是稳定排序,需要的平局规则应写完整。
第三章:栈与队列
| 题目 | 主练 STL | 建议练法与检查点 |
|---|---|---|
| STL005 指令计算栈 | stack |
练 push、top、pop。二元运算先弹出右操作数,再弹出左操作数;用减法和负数除法检查顺序。数字与中间结果用 long long。 |
| STL006 服务窗口 | queue |
用 push 加到队尾,front 查看队头,先读值再 pop。FRONT 不删除;重复编号是不同等待记录;自己测试空窗口和多次查看队头。 |
stack::pop 和 queue::pop 都不返回被删除的值。需要输出时,先读取 top 或 front。访问栈顶、队头、队尾前先处理空容器。C++17 的整数除法向 0 取整,例如 -7/3 为 -2;除数与操作数顺序都要按题面执行。
第四章:双端与优先队列
| 题目 | 主练 STL | 建议练法与检查点 |
|---|---|---|
| STL007 双端传送带 | deque、reverse |
练两端的 push_front、push_back、pop_front、pop_back,以及 front、back。先写实际翻转版本,明确一次 reverse 是 O(当前长度),核对空容器和多次翻转。 |
| STL008 紧急任务池 | priority_queue、pair、比较器 |
先理解默认大根堆,再处理“priority 大者先出,同优先级 id 小者先出”。不要直接用默认 pair<priority,id> 大根堆后期待较小 id 优先。 |
| STL009 最小合并账本 | 小根堆、64 位累加 | 用 priority_queue<T,vector<T>,greater<T>> 反复取两个最小重量。练“取出—相加—放回”,检查 n=1、零重量和固定手续费。用小规模手算理解合并顺序。 |
priority_queue::top 的意义由比较规则决定;默认数值堆的 top 是最大值,greater 对应小根堆。它不提供按序遍历接口,想依次取出要反复 top、pop。固定手续费在一次完整合并过程里支付 n-1 次,仍要与每次合并重量一起累计。不要因为单个重量能放进 int,就用 int 保存总费用。
第五章:关联映射
| 题目 | 主练 STL | 建议练法与检查点 |
|---|---|---|
| STL010 成绩映射表 | map,再用 unordered_map 重做 |
SET 写入或覆盖,FIND 用 find,ERASE 用删除返回值,COUNT 看不同键数。重点检查“查询不存在姓名后,COUNT 不应改变”。两种容器实现保持相同题意。 |
| STL011 稀疏棋盘 | map<pair<int,int>,long long> |
把两个坐标作为一个键。分别处理不存在、存在且值为 0、覆盖、重复删除。不能用值为 0 来表示删除或不存在。 |
完成小实验二后,再做这两题。map::operator[] 是可写访问接口:键不存在时会插入键和默认构造的值。保存整数分数时,这个默认值通常是 0,因而不能用 m[name] 来判断姓名是否存在。查询应使用 find 并检查是否等于 end();写入或覆盖时则可以有意使用 []。
| 选择依据 | map / set |
unordered_map / unordered_set |
|---|---|---|
| 键的组织与遍历 | 按比较器保持有序,默认升序 | 哈希组织,遍历顺序不等于输入顺序或排序顺序 |
| 单次典型操作复杂度 | 查找、插入、删除 O(log n) | 查找、插入、删除平均或期望 O(1),严重碰撞时单次可能 O(n) |
| 是否适合有序邻近查询 | 可用成员 lower_bound、upper_bound |
不提供这类有序定位接口 |
| 预留空间 | 没有哈希桶 reserve 接口 |
reserve 可预留桶容量,降低重哈希次数;不能消除碰撞或保证 O(1) |
题目不需要键序时可以比较两种实现的写法和本地表现,但不要据一次计时断言哈希容器一定更快。选择容器还应考虑是否需要排序、邻近查找、稳定的操作复杂度和额外空间。
第六章:二分与哈希应用
| 题目 | 主练 STL | 建议练法与检查点 |
|---|---|---|
| STL012 区间定位仪 | sort、lower_bound、upper_bound |
先排序。lower 找第一个 >=x 的位置,upper 找第一个 >x 的位置;用迭代器差算小于、等于、大于的数量。空数组、所有值相同和返回 end() 都要覆盖。 |
| STL013 差值配对 | unordered_map 频数,或排序二分 |
按有序下标对计数。C=0 时,同值频数 f 的贡献是 f*(f-1),不能平方或除以 2。答案、频数乘积和 x-C 用 64 位;可用排序二分另解对照。 |
| STL014 有限缓存 | queue 与 unordered_set 协作 |
队列保存 FIFO 顺序,集合负责判定是否命中;淘汰时两边同步删除。命中不移动位置,不能写成 LRU。检查容量 0、重复命中、淘汰后再次请求和最终输出顺序。 |
二分操作的前提是区间满足相应排序或分区条件。对排序后的 vector,lower_bound 与 upper_bound 可在 O(log n) 时间定位,返回值可以是 end();用于计数可以相减,只有解引用前必须确认它不是 end()。
对 set 或 map 应优先调用容器成员 lower_bound。把它们的迭代器传给通用 std::lower_bound,比较次数虽可为 O(log n),迭代器移动仍可能是 O(n)。此外,map、set 的迭代器不支持减法;需要距离时的 std::distance 也不是常数时间。
第七章:排列枚举
| 题目 | 主练 STL | 建议练法与检查点 |
|---|---|---|
| STL015 字典序通行码 | sort、next_permutation |
先排序到最小排列,用 do…while 输出当前排列再推进。验证一个字符、全部相同、重复字母和输入本来逆序的情况。数量应等于不同排列数。 |
next_permutation 生成字典序的下一个排列;没有后继时返回 false,并把序列恢复为最小排列。直接从任意输入顺序开始会漏掉更小的排列,只写 while(next_permutation(...)) 则容易漏掉第一项。相同字母形成的相同字符串不应重复输出。
如果长度为 L、不同排列数为 P,枚举总工作量与 P·L 有关。9 个互异字符有 362880 个排列,需要认真处理输出;不要把阶乘规模的枚举当成线性遍历。
第八章:选做综合
| 题目 | 主练 STL | 建议练法与检查点 |
|---|---|---|
| STL016 首次出现档案(选做) | unordered_set 与 vector |
集合判重,首次出现时立即写入向量,最后按向量顺序输出。练 insert(x).second;不要直接遍历哈希集合当作首次出现顺序。 |
| STL017 邻近坐标(选做) | set::lower_bound、前驱 |
先处理空集合,再定位右侧候选;必要时比较前驱。返回 begin 不能直接 prev,返回 end 不能解引用。同距离选较小值,精确命中返回该值。 |
| STL018 窗口极值索引(进阶选做) | 两个单调 deque |
队列保存原数组下标,先淘汰过期项,再维护单调性。删除尾部时只淘汰严格更差的值,保留相等值以得到最早位置。自己检查 k=1、k=n、全相等和极值滑出窗口。 |
这三题适合把前面学过的接口组合起来。STL017 的候选只需要第一个不小于查询值的坐标及其前驱;STL018 则要进一步解释“为什么被淘汰的下标不可能成为未来所需答案”。单调队列中每个下标至多入队、出队一次,才能得到 O(n) 总时间,而不是因为代码里用了 deque 就自动变成 O(n)。
两周参考安排
| 天数 | 建议内容 |
|---|---|
| 第 1 天 | 小实验一;STL001;复盘负下标与空容器。 |
| 第 2 天 | STL002;整理 substr、insert、find 的参数和返回值。 |
| 第 3 天 | STL003 的 sort+unique+erase 解法,再写 set 解法。 |
| 第 4 天 | STL004;小实验三中的 pair 字典序;手造排序平局。 |
| 第 5 天 | STL005、STL006;比较后进先出和先进先出。 |
| 第 6 天 | 小实验三中的 deque;STL007、STL008。 |
| 第 7 天 | STL009;补查费用范围,回顾本周容易出错的题。 |
| 第 8 天 | 小实验二;STL010 的 map 解法及查询不插入的检查。 |
| 第 9 天 | STL010 用 unordered_map 重做;STL011;记录容器选择理由。 |
| 第 10 天 | STL012;用重复值和空数组手算二分返回位置。 |
| 第 11 天 | STL013;对照 C=0 与 C>0,有余力再写排序二分解。 |
| 第 12 天 | STL014、STL015;分别检查 FIFO 命中规则和首排列。 |
| 第 13 天 | 选做 STL016、STL017,或先补前面尚未完成的基础题。 |
| 第 14 天 | 尝试 STL018、解释单调队列不变量;或集中重做错题并整理总结。 |
当天卡在某题时,可以保留自己的实现与反例,先阅读接口定义或练下一道独立题,再回头处理。参考安排用于分配练习,不承诺固定时间内完成。最后建议挑两道曾经出错的题,关掉旧代码重新写一遍。
三个接口小实验
这些是独立的小程序,不是题目的标准答案。建议先预测输出再运行,并用自己的语言解释容器为什么变化。
小实验一:vector 的 reserve、resize 与安全 erase
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v{10, 20};
v.reserve(8);
cout << v.size() << ' ' << (v.capacity() >= 8) << '\n';
v.resize(4);
for (int x : v) cout << x << ' ';
cout << '\n';
for (auto it = v.begin(); it != v.end(); ) {
if (*it == 0) it = v.erase(it);
else ++it;
}
for (int x : v) cout << x << ' ';
cout << '\n';
}
预期三行依次是 2 1、10 20 0 0、10 20(忽略行尾空格)。reserve(8) 只要求容量至少达到 8,不增加元素,也不保证容量恰好等于 8;resize(4) 真正改变大小,新增的 int 元素为 0。erase 返回删除位置之后的有效迭代器,删除分支不要再额外自增,否则会跳过紧邻元素。
小实验二:map 的 find 与 operator[]
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map<string, int> score{{"lin", 80}};
auto it = score.find("mei");
cout << (it == score.end()) << ' ' << score.size() << '\n';
cout << score["mei"] << ' ' << score.size() << '\n';
}
预期输出是 1 1、0 2。find 未找到 mei,返回 end,大小仍为 1;随后 [] 插入 mei 和默认整数值 0,大小变为 2。把容器改成 unordered_map 后重做,观察本实验的查询与插入语义一致;若增加遍历输出,不要期待无序容器按姓名排序。
小实验三:pair 的默认字典序与 deque 的两端操作
#include <algorithm>
#include <deque>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int main() {
vector<pair<int, int>> a{{2, 9}, {1, 8}, {2, 3}};
sort(a.begin(), a.end());
for (auto p : a) cout << p.first << ',' << p.second << ' ';
cout << '\n';
deque<int> d{1, 2, 3};
d.push_front(0);
d.push_back(4);
d.pop_front();
d.pop_back();
reverse(d.begin(), d.end());
for (int x : d) cout << x << ' ';
cout << '\n';
}
预期两行是 1,8 2,3 2,9、3 2 1。pair 默认先比较 first,first 相同再比较 second;这正是字典序,不是两个字段同时“小于”。deque 支持两端操作和随机访问迭代器,可以使用这里的 reverse;实际翻转会遍历元素。
提交前容易漏掉的细节
- 读值与删除分开。
pop、pop_back、pop_front不返回元素;空容器不能直接访问front、back、top。 - 迭代器有有效期。 vector 重新分配存储会使全部旧迭代器、指针、引用失效;erase 会使删除位置及其后的迭代器、引用失效。没有重新分配时,尾部 push_back 也会使旧 end 失效。修改 string 后不要依赖旧指针或迭代器继续操作。
- 不同容器的规则不同。 map、set 插入不会使已有元素迭代器失效,erase 只使被删除元素的迭代器失效;哈希容器发生 rehash 会使迭代器失效。deque 两端插入会使迭代器失效,但已有元素的引用仍有效。不要在删除元素后继续使用指向它的迭代器,也不要把一个容器的规则套给另一个。
- 查询不能偷偷写入。 map/unordered_map 的
[]可以插入新键;需要“存在吗”时使用 find,检查 end 后再读取值。遍历哈希表时通过[]插入还可能触发 rehash,使当前迭代器失效。 - 容器顺序与题目顺序分清。 set/map 默认按键排序;哈希遍历顺序没有题意要求的保证。首次出现顺序、FIFO 顺序和自定义任务优先级都应显式保存或比较。
- 二分与前驱先看端点。 end 不能解引用,begin 不能直接取前驱。对 set/map 使用成员 lower_bound;对 vector 的通用 lower_bound 先满足排序条件。
- 整型宽度看整个表达式。 若两个 int 先相乘,即使之后赋给 long long 也可能已溢出;需要时先写
1LL * a * b。STL009、STL013 的总量以及 STL005 的中间数应使用 64 位。 - 复杂度要把整串操作算进去。 vector 尾部增长是均摊 O(1),deque 翻转是 O(n),堆的 push/pop 是 O(log n),排序是 O(n log n),哈希查找是平均或期望 O(1) 而不是无条件 O(1)。自己的测试仍须满足各题累计预算。
复盘时可以回答四个问题:为什么选这个容器;用了哪些返回值;哪些边界必须先判断;每个元素或操作最多被处理多少次。能说清这些,再尝试换一种容器或算法重做。
教程与接口查阅
以下仅提供阅读链接。建议按当前章节查阅相关接口,并结合自己的代码验证;本训练说明不复制第三方教程正文。
- OI Wiki:C++ 标准库
- OI Wiki:容器
- OI Wiki:算法
- OI Wiki:无序容器
- B站:ACM 新生 STL,BV1L8411y7th
- B站:黑马 STL,BV1et411b73Z,第 185 集
- cppreference:C++ Containers library(英文)
来源记录
Codex为d&f算法网独立编写,公开算法概念,不使用第三方题面/数据/代码。
- 参加人数
- 4
- 创建人