C++ STL 竞赛入门题单

从 string、vector 和常用算法起步，练习栈、队列、list、关联容器与优先队列在竞赛中的选择和使用。

0 / 0 已完成

C++ STL 竞赛入门题单

这份题单面向已经会 C++ 基础语法、但还没有 STL 实战经验的同学。做题时先问：我要保存什么、最常做什么操作、是否需要有序或去重；再选择容器或算法，不要把 STL 当成要背的接口表。

一、string：把文本当作可操作的序列

string 适合读入、扫描、修改文本。注意 getline 与 cin 的换行问题，以及下标访问前先确认没有越界。

二、vector 与 pair：动态保存同类数据和多字段记录

元素数量运行时才确定，或要整体传给算法时，优先考虑 vector。pair 能把紧密相关的两个值绑在一起；排序前要先写清“第一关键字、第二关键字”的顺序。

三、常用 <algorithm>：排序后再利用顺序

这一节练习 sort、reverse、lower_bound / upper_bound、unique + erase 和 next_permutation。二分查找的前提是区间已经按同一规则排序；unique 只把不重复元素移到前面，不能忘记再 erase。

四、stack：处理最近尚未匹配的对象

遇到括号匹配、后缀表达式，或“最后进入的元素先处理”时使用栈。每次 top() 或 pop() 前，都要保证栈非空。

五、queue 与 list：按顺序处理和局部插删

queue 对应先进先出事件；弹出元素前先判断非空。list 只在已经定位到位置、又需要频繁插入或删除时才值得考虑；竞赛中多数连续存储需求仍优先选 vector 或数组。

六、set 与 map：去重、计数和按键查找

只关心“是否出现过”时用 set；要把键映射到次数或信息时用 map。map[key] 会在键不存在时创建它，纯查询时要留意这一点；有序性是它们比哈希容器更适合入门题的原因。

七、priority_queue：动态维护当前最值

priority_queue 适合不断加入元素、同时反复取当前最大或最小值。默认是大根堆；需要最小值时明确写出比较规则，并检查堆为空的边界。

八、综合练习：从操作需求反推工具

下面几题不再直接提示使用哪一种 STL。先列出每种操作的频率和顺序要求，再决定是否需要 pair、有序容器、堆或算法组合。

复盘要求

每道题完成后补充：

text
我选择的容器或算法：
它支持的关键操作及复杂度：
为什么数组、另一个容器或暴力做法不合适：
本题最容易遗漏的边界：