ACM竞赛必备：C++ STL核心容器与算法实战速查指南

1. 项目概述：为什么我们需要这份总结

搞ACM竞赛的，或者正在向这个方向努力的兄弟，估计都经历过这个阶段：面对一道题，思路有了，但就是卡在代码实现上——要么是某个STL容器的用法记混了，要么是手写一个复杂功能（比如排序、去重）时效率低下还容易写错。比赛时，时间就是生命，每一秒都弥足珍贵。这时候，一份清晰、准确、能快速查阅的“武器库”总结，其价值不亚于一个可靠的队友。

这份“ACM常用C++函数和STL总结”，本质上就是一个为竞赛编程量身定制的速查手册和实战指南。它不追求大而全的C++语法讲解，而是精准聚焦于那些在算法竞赛中出场率最高、最能帮你节省时间、提升代码稳定性的核心工具。我当年打比赛，从校赛到区域赛，笔记本里就有一份自己不断增补的类似清单，后来带学弟学妹，这份清单更是成了入门必修课。今天，我就把自己这些年积累下来的、经过无数次比赛验证的“干货”系统地整理出来，希望能帮你绕过我踩过的坑，把精力更多地集中在算法思维本身。

2. STL容器：你的数据结构“瑞士军刀”

STL容器是C++标准模板库的基石，也是ACM选手最亲密的伙伴。选对容器，往往意味着成功了一半。

2.1 序列式容器：vector,deque,list

vector（动态数组）：这绝对是使用频率最高的容器，没有之一。它提供了类似数组的随机访问（O(1)），尾部插入删除高效（均摊O(1)），虽然中间插入删除是O(n)，但在竞赛中，我们大量使用的场景是预先分配好空间（reserve）或直接push_back，最后再进行排序或遍历。

注意：vector在空间不足重新分配时，会进行“复制-构造-析构”，对于存有大量数据的vector，频繁的push_back可能导致性能抖动。一个常用技巧是，如果事先知道或能估算数据量的大致范围，使用reserve(n)预先分配空间，可以避免多次重新分配。

deque（双端队列）：全称double-ended queue。它支持在头部和尾部进行高效的插入和删除操作（O(1)）。这个名字在热词里被专门提到，说明它的特性备受关注。当你需要实现一个滑动窗口，或者BFS（广度优先搜索）时，deque比vector更合适，因为BFS通常从队列头取元素，向队列尾加元素。不过，deque的随机访问效率略低于vector，中间插入删除也更慢。

list（双向链表）：在需要频繁在序列中间进行插入和删除操作时，list的O(1)复杂度是巨大的优势。但它的缺点也很明显：不支持随机访问（不能通过下标直接获取元素），内存开销比vector大（每个元素需要存储前后指针）。在ACM中，list的使用场景相对较少，通常只在特定链表算法题中直接使用，或者当我们需要一个高效的“插入删除中间元素”的容器时才会考虑。

2.2 关联式容器：set,map, 及其无序版本

set/multiset：基于红黑树实现，元素自动排序且唯一（multiset允许重复）。查找、插入、删除的复杂度都是O(log n)。当你需要维护一个动态的有序集合，并频繁检查某个元素是否存在、或需要找到最接近某个值的元素时，set是首选。例如，处理“实时数据流的中位数”或“维护一个可插入删除的有序排名列表”。

map/multimap：同样是红黑树，存储的是键值对（key-value）。map的key唯一。它提供了基于key的快速查找（O(log n)）。在竞赛中，map常被用作高效的“哈希表”（在C++11之前），用于计数、建立映射关系。比如统计字符串中每个字符出现的次数：map<char, int> charCount;

unordered_set/unordered_map(C++11)：基于哈希表实现。它们的查找、插入、删除在平均情况下是O(1)，最坏情况（哈希冲突严重）是O(n)。在大多数ACM竞赛场景中，如果不需要元素有序，优先使用unordered_map和unordered_set，它们的平均性能远优于map和set。这也是很多选手从“传统”转向“现代”C++竞赛编程的一个重要习惯改变。

实操心得：unordered_map在查找不存在的key时，会自动插入一个默认构造的value。有时这并非我们本意。因此，检查key是否存在时，更推荐使用count(key)方法（返回0或1），而非直接通过if(mp[key])来判断，后者会无意中改变map。

2.3 容器适配器：stack,queue,priority_queue

它们基于底层容器（默认deque或vector）提供特定的接口。

stack和queue：分别用于后进先出（LIFO）和先进先出（FIFO）的场景。语法简单，常用于模拟递归（栈）、BFS（队列）。

priority_queue（优先队列，即堆）：这是算法竞赛中的神器。默认是大顶堆（最大元素在顶部）。它能在O(log n)时间内插入元素和取出最大/最小元素。迪杰斯特拉（Dijkstra）最短路径算法、哈夫曼编码、以及任何需要动态获取当前最大/最小值的场景，都离不开它。

// 小顶堆的定义方式，务必牢记 priority_queue<int, vector<int>, greater<int>> minHeap; // 自定义比较函数 struct Node { int dist, id; }; auto cmp = [](const Node& a, const Node& b) { return a.dist > b.dist; }; priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);

3. STL算法：告别重复造轮子

STL算法库（<algorithm>）提供了一系列模板函数，作用于容器范围。熟练使用它们，能让你写出既简洁又高效的代码。

3.1 排序、查找与二分

sort/stable_sort：核心排序函数。sort平均和最好情况O(n log n)，但不稳定；stable_sort稳定但可能稍慢或内存占用多。对于自定义类型，需要重载<运算符或提供比较函数。

vector<int> v = {5, 1, 4, 2, 3}; sort(v.begin(), v.end()); // 默认升序 sort(v.begin(), v.end(), greater<int>()); // 降序 // 自定义结构体排序 struct Point { int x, y; }; vector<Point> points; sort(points.begin(), points.end(), [](const Point& a, const Point& b) { if (a.x == b.x) return a.y < b.y; return a.x < b.x; });

lower_bound/upper_bound/binary_search：在已排序的序列中进行二分查找。

• lower_bound(first, last, val)：返回第一个大于等于val的元素迭代器。
• upper_bound(first, last, val)：返回第一个大于val的元素迭代器。
• binary_search(first, last, val)：仅返回是否存在，不返回位置。

find/find_if：线性查找（O(n)）。在未排序的vector或list中查找元素，或在关联容器中查找（虽然关联容器有自己更快的.find()成员函数）。

3.2 排列、最值与数值操作

next_permutation/prev_permutation：按字典序生成下一个/上一个排列。常用于全排列暴力搜索。使用时务必保证序列初始是排序的。

vector<int> v = {1, 2, 3}; do { // 处理当前排列 v } while (next_permutation(v.begin(), v.end()));

max_element/min_element：返回序列中最大/最小元素的迭代器，无需手动写循环比较。

accumulate：计算序列的累加和（或自定义二元操作的累积结果）。来自<numeric>头文件。

vector<int> v = {1, 2, 3, 4, 5}; int sum = accumulate(v.begin(), v.end(), 0); // 初始值为0 // 求乘积 int product = accumulate(v.begin(), v.end(), 1, multiplies<int>());

3.3 删除与去重

unique：“去除”相邻的重复元素。注意，它并不真正删除元素，而是将不重复的元素移到前面，返回新的逻辑结尾迭代器。通常需要和erase成员函数联用。

vector<int> v = {1, 1, 2, 2, 3, 3, 3, 4}; // 先排序，使相同元素相邻 sort(v.begin(), v.end()); // unique 返回去重后的“新结尾” auto new_end = unique(v.begin(), v.end()); // 擦除后面的无效元素 v.erase(new_end, v.end()); // v 变为 {1, 2, 3, 4}

remove/remove_if：与unique类似，也是将满足条件的元素移到末尾并返回新结尾，需要配合erase使用，用于删除特定值或满足条件的元素。

4. 实用C++函数与技巧

除了STL，C++标准库还提供了一些极其有用的函数，能大幅简化代码。

4.1 字符串处理 (<string>)

字符串在竞赛中无处不在，string类比C风格字符串(char[])安全、方便得多。

• getline(cin, str)：读取一行，包括空格。
• str.substr(pos, len)：提取子串。
• str.find(sub_str)：查找子串，返回位置或string::npos。
• stoi/stol/stod：字符串转数字。比sscanf或atoi更安全现代。
• to_string(num)：数字转字符串。彻底告别sprintf。

踩坑记录：cin >> str会以空白字符（空格、换行）为分隔。如果题目输入中字符串可能包含空格，一定要用getline。但要注意，混合使用cin >>和getline时，cin >>会留下换行符在输入流，导致接下来的getline读到空行。解决方法是在cin >>后加cin.ignore()。

4.2 数学函数 (<cmath>)

• pow,sqrt,abs：乘方、开方、绝对值。
• ceil,floor,round：向上、向下、四舍五入取整。
• log,log10：自然对数、常用对数。
• sin,cos,tan等三角函数，参数是弧度制。

特别注意浮点数比较：由于精度问题，不要直接用==比较浮点数。应该判断两者差的绝对值是否小于一个极小值（epsilon）。

const double EPS = 1e-9; bool isEqual(double a, double b) { return fabs(a - b) < EPS; }

4.3 输入输出加速

这是ACM竞赛中一个经典的、至关重要的技巧。C++的cin/cout为了兼容C的stdio，默认是同步的，导致速度较慢。在需要读入大量数据（如10^5以上）时，关闭同步流可以带来数倍的性能提升。

ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // 如果同时使用cout，也解绑

使用后，严禁将cin/cout与scanf/printf混用，否则会导致输入输出顺序混乱。

4.4 位运算与实用函数

• __builtin_popcount(x)：GCC/Clang内置函数，计算整数x的二进制表示中1的个数。竞赛环境通常支持，非常方便。
• bitset：固定大小的位序列，支持位运算，常用于状态压缩、布尔数组优化。
• numeric_limits<T>::max() / min()：获取类型T的最大/最小值，比硬编码常量更安全。

5. 常见问题与调试技巧实录

即使工具再熟，实战中也会遇到各种稀奇古怪的问题。这里分享几个高频“坑点”和应对策略。

5.1 迭代器失效问题

这是使用STL容器时最危险的陷阱之一。当对容器进行插入(insert)、删除(erase)操作时，指向该容器的某些或全部迭代器、指针、引用可能会失效。

• 对于vector和deque：在中间插入/删除，会使所有指向插入/删除点之后位置的迭代器、指针、引用失效。尾部插入可能导致所有迭代器失效（如果发生重分配）。
• 对于list,set,map等：插入不会使任何迭代器失效。删除只会使指向被删除元素的迭代器失效，其他迭代器安全。

错误示例：

vector<int> v = {1, 2, 3, 4, 5}; for (auto it = v.begin(); it != v.end(); ++it) { if (*it % 2 == 0) { v.erase(it); // 致命错误！erase后，it失效，再++行为未定义 } }

正确做法：利用erase的返回值（它返回被删除元素之后元素的有效迭代器）。

for (auto it = v.begin(); it != v.end(); ) { if (*it % 2 == 0) { it = v.erase(it); // 接收返回值，更新it } else { ++it; } }

5.2 容器选择与性能误区

• 误区：所有查找都用map。如果不需要顺序，unordered_map更快。如果键是小的连续整数，甚至可以用vector<int>直接当数组用，访问是O(1)。
• 误区：频繁在vector头部插入。这是vector的弱点，复杂度O(n)。如果需要，考虑用deque。
• 误区：滥用clear()。v.clear()清空元素，但不一定释放内存（capacity可能不变）。如果这个vector之后还要复用，这没问题。但如果想立刻释放内存，可以用vector<int>().swap(v);（C++11之前）或v.shrink_to_fit()（C++11）。

5.3 多组数据输入的常见BUG

很多题目要求处理多组测试数据，直到文件结束(EOF)。一个常见的模式是：

int n; while (cin >> n) { // 或 while(scanf(“%d”, &n) != EOF) // 处理一组数据 vector<int> data(n); for (int i = 0; i < n; ++i) cin >> data[i]; // ... 计算并输出结果 }

关键点：每组数据开始前，要确保所有用于存储的容器是干净的。如果定义在while循环外部，必须在循环内部开始处用.clear()清空，或者更简单，直接将容器定义在while循环内部。

5.4 调试与输出技巧

• 局部调试：在关键位置使用cerr输出调试信息。cerr是标准错误流，不影响cout的正常输出判题。

  cerr << “当前值: “ << x << “, 迭代器位置: “ << distance(v.begin(), it) << endl;

• 断言：使用assert(condition)来自检。在本地调试时，如果条件为假，程序会中止并报错，方便定位。提交时可以通过定义NDEBUG宏（通常编译器有-DNDEBUG选项）来禁用所有断言。
• 输出格式：务必仔细检查输出格式，末尾的空格、换行，浮点数的精度(cout << fixed << setprecision(2) << value)，大小写等。格式错误会导致“Presentation Error”甚至“Wrong Answer”。

6. 从知识到实战：构建你的解题框架

掌握了这些函数和容器，如何将它们融会贯通，应用到具体解题中？我分享一下我的思考框架。

6.1 读题与抽象建模

拿到题目，第一步不是写代码，而是彻底理解问题，并将其抽象为计算机可处理的数据模型。

1. 确定输入输出：数据范围（n,m的大小）、数据类型（整数、浮点数、字符串）。
2. 抽象关键对象：题目中的“城市”、“人物”、“任务”可以抽象成什么？是结构体节点？还是简单的整数ID？
3. 识别核心操作：我们需要频繁进行哪些操作？查找、排序、插入、删除、求最值、遍历图？这一步直接决定了后续的数据结构选择。

6.2 数据结构选型决策树

根据核心操作，快速匹配STL组件：

• 需要维护一个动态集合，频繁检查存在性，且不关心顺序？->unordered_set。
• 需要维护键值对映射，快速通过键找值，且不关心键的顺序？->unordered_map。
• 需要动态获取当前集合中的最大值或最小值？->priority_queue。
• 需要维护一个序列，尾部操作频繁，偶尔随机访问？->vector（记得reserve）。
• 需要双端操作（BFS队列）？->deque或queue适配器。
• 需要对序列进行排序、二分查找？-> 用vector存储，配合sort,lower_bound。

6.3 算法实现与STL整合

选定数据结构后，用STL算法和函数来填充你的算法逻辑。

• 排序预处理：很多问题排序后就会变得简单，sort是第一考虑。
• 去重：sort+unique+erase三板斧。
• 遍历与查找：优先考虑算法库的find_if,count_if,for_each（C++11后更常用范围for循环for(auto& x : container)），它们比手写循环更不易出错。
• 堆优化：迪杰斯特拉算法、哈夫曼编码，脑子里要立刻跳出priority_queue。

6.4 编写、测试与优化

1. 边写边测：不要等全部写完再测试。写完一个功能模块（如数据读取、核心算法步骤），就用简单的样例或打印中间值(cerr)测试一下。
2. 边界测试：考虑输入为0、1，最大值，负数等边界情况。你的容器初始化、循环条件能正确处理吗？
3. 复杂度估算：根据数据范围和你的算法步骤，估算最坏情况下的时间。如果n=10^5，一个O(n^2)的嵌套循环肯定超时。
4. STL性能认知：知道vector的push_back均摊O(1)，但可能引发扩容；知道map的operator[]如果key不存在会插入。这些知识能帮你避免性能陷阱和逻辑错误。

我个人最深刻的体会是，STL和这些库函数不是用来炫技的，而是用来提升编码速度、降低出错概率、让思维更集中于算法本身的“杠杆”。刚开始可能会觉得要记的东西很多，但通过反复在题目中实践，它们会像肌肉记忆一样成为你的一部分。最后，再分享一个私藏小技巧：建立一个自己的代码片段库（Snippet Library），把常用的代码模板（如带堆优化的Dijkstra、并查集、快速幂、输入加速）保存好，比赛时直接调用，能为你节省大量时间，并减少因手敲出错带来的风险。