18道原创 STL 题:15道基础与应用、3道选做。使用 C++17,按八章组织。

登录以参加训练计划

第四周 · 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)。自己的测试仍须满足各题累计预算。

复盘时可以回答四个问题:为什么选这个容器;用了哪些返回值;哪些边界必须先判断;每个元素或操作最多被处理多少次。能说清这些,再尝试换一种容器或算法重做。

教程与接口查阅

以下仅提供阅读链接。建议按当前章节查阅相关接口,并结合自己的代码验证;本训练说明不复制第三方教程正文。

来源记录

Codex为d&f算法网独立编写,公开算法概念,不使用第三方题面/数据/代码。

章节 1. 动态序列

开放

题目 尝试 AC 难度
STL001   动态清单 3 2 1
STL002   文本拼接站 1 1 1

章节 2. 排序去重

开放

题目 尝试 AC 难度
STL003   编号归档 1 1 1
STL004   三维任务排序 1 1 1

章节 3. 栈与队列

开放

题目 尝试 AC 难度
STL005   指令计算栈 1 1 2
STL006   服务窗口 1 1 1

章节 4. 双端与优先队列

开放

题目 尝试 AC 难度
STL007   双端传送带 1 1 1
STL008   紧急任务池 1 1 2
STL009   最小合并账本 1 1 2

章节 5. 关联映射

开放

题目 尝试 AC 难度
STL010   成绩映射表 1 1 1
STL011   稀疏棋盘 1 1 2
 
参加人数
4
创建人