C++ STL在竞赛中的正确打开方式

如果你问一个算法竞赛选手：“你平时写代码最离不开什么？” 答案很可能不是某个高深的算法，而是 C++ STL。从 vector 到 sort，从 set 到 priority_queue，STL 几乎出现在每一份 AC 代码中。

但 STL 是一把双刃剑。用得好，它可以让你在十分钟内写完一道需要手写平衡树的题目；用得不好，它会让你的程序在极限数据下 TLE（超时）或 MLE（内存超限），而你甚至不知道问题出在哪里。

本文不打算罗列 STL 的所有容器和函数——那是文档做的事。我们要聊的是：在算法竞赛环境下，STL 的正确打开方式、常见陷阱以及性能优化建议。全文约 2000 字，适合已经了解 STL 基础、希望在竞赛中更高效使用它的读者。

一、STL 对竞赛的意义：速度与安全

竞赛编程的核心目标是：在有限的时间内，写出正确且高效的代码。STL 带来的好处是显而易见的：

1. 开发效率：实现一个动态数组手写需要管理内存扩容，而 vector 一行声明即可。手写红黑树几乎不可能，但 set 和 map 开箱即用。

2. 代码安全：经过百万开发者检验的 STL 实现，远比手写的数据结构更少 bug。迭代器、内存管理由库负责，你可以专注于算法逻辑。

3. 性能可靠：STL 的实现通常非常高效（例如 std::sort 是内省排序，综合了快速排序、堆排序和插入排序的优点）。

然而，这些优势是有前提的：你必须知道 什么场景用哪个容器、哪些操作是昂贵的、如何避免不必要的拷贝和重复计算。下面我们分容器和算法两部分展开。

二、容器篇：选对才能跑得快

1. vector：最常用的动态数组

vector 是竞赛中最常用的容器，没有之一。它可以替代 C 风格数组，同时支持动态扩容。

正确用法：

• 预先 reserve 容量以减少重新分配。如果你知道最终元素个数大约为 N，在循环 push_back 之前调用 vec.reserve(N)。

• 使用 emplace_back 而非 push_back 来避免临时对象的构造（对复杂类型有效，对基本类型差别不大）。

• 遍历时优先使用下标 [] 或 for (int x : vec)，而不是迭代器（可读性更高）。

常见误区：

• 在循环中频繁 insert 或 erase 非尾部位置，这些操作是 O(n) 的，可能导致程序从 O(n) 退化到 O(n²)。

• 误以为 vector<bool> 是普通容器。实际上它是模板特化，采用位压缩，operator[] 返回的是一个代理类，不能取地址，且多线程下不安全。竞赛中建议用 vector<char> 代替。

2. set / map：有序的平衡树

底层是红黑树，插入、删除、查找都是 O(log n)。适合需要维护有序集合或键值对的场景。

正确用法：

• 需要集合有序且频繁插入删除时，用 set 而不是排序后的 vector（因为 vector 的插入删除是 O(n)）。

• 对于 map，查找键是否存在时，不要用 if (mp[key] == value)，因为 operator[] 会在键不存在时插入一个默认值，改变容器大小。应该用 mp.find(key) != mp.end()。

• 如果需要顺序遍历，set 和 map 的迭代器是升序的，可以直接 for (auto it = s.begin(); it != s.end(); ++it)。

性能陷阱：

• set 和 map 的内存开销较大（每个节点至少三个指针 + 颜色），比 unordered_set 慢一倍以上。如果不需要有序，优先考虑哈希版本。

• 自定义类型作为键时，必须定义 operator<，且要保证严格弱序（即比较结果必须一致，不能出现 a < b 和 b < a 同时为 true）。

3. unordered_set / unordered_map：哈希表

C++11 引入的哈希容器，平均 O(1) 的插入与查询，在竞赛中极具吸引力。

正确用法：

• 当不需要元素有序且数据量较大（例如 1e5~1e7）时，使用哈希表比 set 快很多。

• 提前调用 reserve 可以减少 rehash 次数，这在已知大致元素数量时非常关键。

深坑预警：

• 哈希容器的最坏复杂度是 O(n)，当哈希碰撞严重时可能退化为链表。某些出题人会构造恶意数据导致 TLE（例如对 int 类型，默认哈希就是自身值，若插入连续整数则碰撞极少；但若插入 x 和 x+65536 之类，可能冲突）。防御方法：自定义哈希函数，例如 struct custom_hash { size_t operator()(int x) const { return x ^ (x >> 16); } }。

• 在代码中同时使用 unordered_map 和 iostream 可能导致性能下降，因为某些实现中 unordered_map 会调用全局 new，而 iostream 的同步会干扰。建议关闭同步：ios::sync_with_stdio(false); cin.tie(0);。

4. priority_queue：优先队列（堆）

默认是大根堆（less<T>），小根堆需要 priority_queue<int, vector<int>, greater<int>>。

正确用法：

• 用于 Dijkstra 算法、 Huffman 树等需要动态取极值的场景。

• 需要自定义比较时，可以传入 lambda 表达式（C++11 起），但注意 lambda 类型需作为模板参数：priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);

注意：

• priority_queue 没有迭代器，不能遍历内部元素。

• 修改队列中的元素值（比如 Dijkstra 中的松弛操作）不能直接改，通常采用“允许旧值留在堆中，遇到时跳过”的策略。

5. deque：双端队列

支持 O(1) 的头尾插入删除。在滑动窗口最值问题中常用（与单调队列配合）。

性能特点：下标访问比 vector 稍慢，但差异不大。如果只需要尾部操作，还是用 vector。

三、算法篇：用好函数，事半功倍

1. sort：最强排序

std::sort(begin, end) 平均 O(n log n)，对付 1e6 个 int 毫无压力。

最佳实践：

• 对 vector 排序：sort(v.begin(), v.end())。

• 需要稳定排序时用 stable_sort（归并排序，额外 O(n) 内存）。

• 对自定义类型排序，可以传入 lambda：sort(v.begin(), v.end(), [](const Node& a, const Node& b){ return a.val < b.val; })。

• 只求前 k 个最大/小元素时，用 nth_element（O(n)）代替 sort。

2. 二分查找：lower_bound / upper_bound

在有序序列中找第一个大于等于/大于某值的位置。复杂度 O(log n)。

注意：

• lower_bound 返回的是迭代器，检查是否找到时不要用 *it == target，因为可能返回 end()。应该先判断 it != vec.end() && *it == target。

• 在 set / map 上使用二分时，直接调用成员函数 s.lower_bound(x) 比 lower_bound(s.begin(), s.end(), x) 快得多（后者是线性遍历）。

• upper_bound 对 set 而言，可用 s.upper_bound(x) 获取第一个大于 x 的元素。

3. 去重与离散化

unique 函数将相邻重复元素移到末尾，返回新结尾迭代器。通常与 sort 配合实现去重：

sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());

这是竞赛中离散化的标准步骤。注意 unique 只去除相邻重复，所以必须提前排序。

4. 排列生成：next_permutation

用于生成下一个字典序排列，常用于暴力枚举全排列（n ≤ 10 时可用）。

特性：如果当前序列是最后一个排列，返回 false 且序列变为第一个排列。使用前通常先 sort。

四、性能优化：从“能用”到“高效”

竞赛中时间宝贵，STL 的使用习惯直接决定你这道题能不能 AC。

1. 关闭 IO 同步

在代码开头加上：

ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

这样可以使 cin / cout 接近 scanf / printf 的速度。注意之后不能再混用 C 和 C++ 的 IO。

2. 尽量使用 const T& 传递容器

避免不必要的拷贝。例如：

void process(const vector<int>& v) { ... }

3. 避免不必要的临时构造

使用 emplace_back 而不是 push_back 尤其是在容器内有复杂对象时。对于基本类型，差别不大。

4. 迭代器失效问题

• vector 在插入或删除时可能导致所有迭代器失效（尤其在扩容时）。

• set / map 的迭代器在插入删除时只有被删除元素的迭代器失效，其余不变。

• 常见错误：for (auto it = v.begin(); it != v.end(); ++it) { if (...) v.erase(it); } —— 这会在 erase 后导致 it 失效，应该使用 it = v.erase(it)（C++11 起 erase 返回下一个迭代器）。

5. 空间换时间：reserve 和 shrink_to_fit

vector 频繁 push_back 会导致多次重新分配和拷贝。reserve 可以预先分配容量。如果之后需要释放多余容量，可用 shrink_to_fit（但这不是强制性的）。

五、STL 的局限性：什么时候应该放弃 STL？

虽然 STL 很强大，但竞赛中有些场景必须手写数据结构：

1. 需要 O(1) 空间且内存极度紧张：比如在某些嵌入式环境或内存限制为 4MB 的题目中，vector 的开销（容量、大小指针）可能成为负担。

2. 需要直接操作内存块：例如用 memset、memcpy 批量处理时，原生数组更方便。

3. 需要特殊的平衡树（如 splay、treap）：STL 的 set 不支持 split/merge 等操作，也无法维护序列的翻转。

4. 常数极其敏感：在某些 O(n log n) 但 n=2e5 的题目中，unordered_map 的常数可能比手写哈希表大；sort 递归深度较大时也可能略慢于手写基数排序。

但注意：除非你能证明 STL 是瓶颈，否则优先使用 STL。因为手写数据结构更容易出错，调试成本远高于性能收益。

六、总结与检查清单

STL 的正确打开方式，本质上是一种 “知其所长，避其所短” 的工程思维。为了方便记忆，这里列出竞赛前的 STL 自查清单：

• 是否关闭了 IO 同步（使用 cin/cout 时）？

• 容器类型是否选得恰当？要有序用 set，要快速查找用 unordered_set，要动态数组用 vector，要优先队列用 priority_queue？

• 频繁插入/删除是否发生在容器尾部？如果不是，考虑改用 list（但 list 在竞赛中用得很少）或者改变算法。

• 是否使用了不必要的拷贝？参数传递时加 & 了吗？

• 是否在 map 上误用了 [] 导致意外插入了元素？

• 二分查找时是否用了成员函数而非全局函数（对于关联容器）？

• 遍历删除时是否有迭代器失效问题？

• 哈希容器是否自定义了哈希函数以防卡常？

最终，STL 只是工具，真正的核心仍然是算法思维。但一个熟练掌握 STL 的选手，可以在同样时间内多写两道题，或者在最后十分钟从容地调试出正解。这，就是 STL 在竞赛中的正确打开方式。

愿你的代码中，只有 AC，没有 TLE 和 RE。