1. 项目概述为什么我们需要这份总结搞ACM竞赛的或者正在向这个方向努力的兄弟估计都经历过这个阶段面对一道题思路有了但就是卡在代码实现上——要么是某个STL容器的用法记混了要么是手写一个复杂功能比如排序、去重时效率低下还容易写错。比赛时时间就是生命每一秒都弥足珍贵。这时候一份清晰、准确、能快速查阅的“武器库”总结其价值不亚于一个可靠的队友。这份“ACM常用C函数和STL总结”本质上就是一个为竞赛编程量身定制的速查手册和实战指南。它不追求大而全的C语法讲解而是精准聚焦于那些在算法竞赛中出场率最高、最能帮你节省时间、提升代码稳定性的核心工具。我当年打比赛从校赛到区域赛笔记本里就有一份自己不断增补的类似清单后来带学弟学妹这份清单更是成了入门必修课。今天我就把自己这些年积累下来的、经过无数次比赛验证的“干货”系统地整理出来希望能帮你绕过我踩过的坑把精力更多地集中在算法思维本身。2. STL容器你的数据结构“瑞士军刀”STL容器是C标准模板库的基石也是ACM选手最亲密的伙伴。选对容器往往意味着成功了一半。2.1 序列式容器vector,deque,listvector动态数组这绝对是使用频率最高的容器没有之一。它提供了类似数组的随机访问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常被用作高效的“哈希表”在C11之前用于计数、建立映射关系。比如统计字符串中每个字符出现的次数mapchar, int charCount;unordered_set/unordered_map(C11)基于哈希表实现。它们的查找、插入、删除在平均情况下是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_queueint, vectorint, greaterint minHeap; // 自定义比较函数 struct Node { int dist, id; }; auto cmp [](const Node a, const Node b) { return a.dist b.dist; }; priority_queueNode, vectorNode, decltype(cmp) pq(cmp);3. STL算法告别重复造轮子STL算法库algorithm提供了一系列模板函数作用于容器范围。熟练使用它们能让你写出既简洁又高效的代码。3.1 排序、查找与二分sort/stable_sort核心排序函数。sort平均和最好情况O(n log n)但不稳定stable_sort稳定但可能稍慢或内存占用多。对于自定义类型需要重载运算符或提供比较函数。vectorint v {5, 1, 4, 2, 3}; sort(v.begin(), v.end()); // 默认升序 sort(v.begin(), v.end(), greaterint()); // 降序 // 自定义结构体排序 struct Point { int x, y; }; vectorPoint 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按字典序生成下一个/上一个排列。常用于全排列暴力搜索。使用时务必保证序列初始是排序的。vectorint v {1, 2, 3}; do { // 处理当前排列 v } while (next_permutation(v.begin(), v.end()));max_element/min_element返回序列中最大/最小元素的迭代器无需手动写循环比较。accumulate计算序列的累加和或自定义二元操作的累积结果。来自numeric头文件。vectorint v {1, 2, 3, 4, 5}; int sum accumulate(v.begin(), v.end(), 0); // 初始值为0 // 求乘积 int product accumulate(v.begin(), v.end(), 1, multipliesint());3.3 删除与去重unique“去除”相邻的重复元素。注意它并不真正删除元素而是将不重复的元素移到前面返回新的逻辑结尾迭代器。通常需要和erase成员函数联用。vectorint 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函数与技巧除了STLC标准库还提供了一些极其有用的函数能大幅简化代码。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_limitsT::max() / min()获取类型T的最大/最小值比硬编码常量更安全。5. 常见问题与调试技巧实录即使工具再熟实战中也会遇到各种稀奇古怪的问题。这里分享几个高频“坑点”和应对策略。5.1 迭代器失效问题这是使用STL容器时最危险的陷阱之一。当对容器进行插入(insert)、删除(erase)操作时指向该容器的某些或全部迭代器、指针、引用可能会失效。对于vector和deque在中间插入/删除会使所有指向插入/删除点之后位置的迭代器、指针、引用失效。尾部插入可能导致所有迭代器失效如果发生重分配。对于list,set,map等插入不会使任何迭代器失效。删除只会使指向被删除元素的迭代器失效其他迭代器安全。错误示例vectorint 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更快。如果键是小的连续整数甚至可以用vectorint直接当数组用访问是O(1)。误区频繁在vector头部插入。这是vector的弱点复杂度O(n)。如果需要考虑用deque。误区滥用clear()。v.clear()清空元素但不一定释放内存capacity可能不变。如果这个vector之后还要复用这没问题。但如果想立刻释放内存可以用vectorint().swap(v);C11之前或v.shrink_to_fit()C11。5.3 多组数据输入的常见BUG很多题目要求处理多组测试数据直到文件结束(EOF)。一个常见的模式是int n; while (cin n) { // 或 while(scanf(“%d”, n) ! EOF) // 处理一组数据 vectorint 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 读题与抽象建模拿到题目第一步不是写代码而是彻底理解问题并将其抽象为计算机可处理的数据模型。确定输入输出数据范围n,m的大小、数据类型整数、浮点数、字符串。抽象关键对象题目中的“城市”、“人物”、“任务”可以抽象成什么是结构体节点还是简单的整数ID识别核心操作我们需要频繁进行哪些操作查找、排序、插入、删除、求最值、遍历图这一步直接决定了后续的数据结构选择。6.2 数据结构选型决策树根据核心操作快速匹配STL组件需要维护一个动态集合频繁检查存在性且不关心顺序-unordered_set。需要维护键值对映射快速通过键找值且不关心键的顺序-unordered_map。需要动态获取当前集合中的最大值或最小值-priority_queue。需要维护一个序列尾部操作频繁偶尔随机访问-vector记得reserve。需要双端操作BFS队列-deque或queue适配器。需要对序列进行排序、二分查找- 用vector存储配合sort,lower_bound。6.3 算法实现与STL整合选定数据结构后用STL算法和函数来填充你的算法逻辑。排序预处理很多问题排序后就会变得简单sort是第一考虑。去重sortuniqueerase三板斧。遍历与查找优先考虑算法库的find_if,count_if,for_eachC11后更常用范围for循环for(auto x : container)它们比手写循环更不易出错。堆优化迪杰斯特拉算法、哈夫曼编码脑子里要立刻跳出priority_queue。6.4 编写、测试与优化边写边测不要等全部写完再测试。写完一个功能模块如数据读取、核心算法步骤就用简单的样例或打印中间值(cerr)测试一下。边界测试考虑输入为0、1最大值负数等边界情况。你的容器初始化、循环条件能正确处理吗复杂度估算根据数据范围和你的算法步骤估算最坏情况下的时间。如果n10^5一个O(n^2)的嵌套循环肯定超时。STL性能认知知道vector的push_back均摊O(1)但可能引发扩容知道map的operator[]如果key不存在会插入。这些知识能帮你避免性能陷阱和逻辑错误。我个人最深刻的体会是STL和这些库函数不是用来炫技的而是用来提升编码速度、降低出错概率、让思维更集中于算法本身的“杠杆”。刚开始可能会觉得要记的东西很多但通过反复在题目中实践它们会像肌肉记忆一样成为你的一部分。最后再分享一个私藏小技巧建立一个自己的代码片段库Snippet Library把常用的代码模板如带堆优化的Dijkstra、并查集、快速幂、输入加速保存好比赛时直接调用能为你节省大量时间并减少因手敲出错带来的风险。
