46. STL与算法竞赛：常用STL技巧、输入输出优化、时间优化策略

算法竞赛，说白了就是一场「时间与空间的博弈」。我参加过不少比赛，也带过团队，发现很多选手不是不会算法，而是被STL的用法和输入输出卡住了。今天我就把压箱底的一些技巧拿出来，咱们好好聊聊。

46.1 常用STL容器与算法技巧

我个人习惯把STL容器分成三类：序列式、关联式、无序关联式。竞赛中，vector、set、map、unordered_map 是出场率最高的。

vector 的「预分配」技巧

很多新手喜欢这样写：

vector<int> v;
for (int i = 0; i < n; ++i) {
    v.push_back(i);
}

嗯，这里要注意。每次 push_back 都可能触发扩容，导致 O(n) 的拷贝。我在项目中遇到过，一个百万级的数据插入，光扩容就花了半秒。

更好的做法：

vector<int> v;
v.reserve(n);  // 预分配内存
for (int i = 0; i < n; ++i) {
    v.push_back(i);
}

或者直接用构造函数：

vector<int> v(n);
iota(v.begin(), v.end(), 0);  // 需要 <numeric>

set 与 map 的「查找优化」

很多人用 set 时，喜欢这样判断元素是否存在：

if (s.find(x) != s.end()) { ... }

其实 count 更简洁：

if (s.count(x)) { ... }

但注意，count 在 set 中要么是 0 要么是 1，性能一样。不过 multiset 里 count 是 O(k) 的，k 是元素个数。我曾经踩过这个坑，在 multiset 里用 count 查了十万次，直接超时。

unordered_map 的「哈希冲突」

为什么有时候 unordered_map 比 map 还慢？说白了就是哈希冲突太严重。你可以自定义哈希函数：

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = 
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

unordered_map<int, int, custom_hash> mp;

这个技巧我在 Codeforces 上用过很多次，能有效防止被卡哈希。

46.2 输入输出优化

你想想看，算法再快，输入输出慢了也是白搭。我见过太多选手，算法 O(n log n)，结果输入用了 cin 不加优化，硬生生被 IO 拖成 O(n²) 的感觉。

关闭同步流

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

这三行代码，是竞赛选手的「起手式」。原理很简单：C++ 的 cin/cout 默认和 C 的 stdio 同步，保证混用不出错。但竞赛中你根本不会混用，所以关掉它。

使用 '\n' 而非 endl

endl 不仅换行，还会刷新缓冲区。频繁刷新会拖慢速度。我建议一律用 '\n'：

cout << x << '\n';  // 比 endl 快很多

自定义快读

如果数据量极大（比如 10⁶ 级别），可以考虑手写快读：

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return x * f;
}

这个函数比 cin 快 3-5 倍。我在处理大整数输入时，几乎必用。

46.3 时间优化策略

时间优化，说白了就是「少做事」和「快做事」。下面几个策略是我多年比赛积累下来的。

避免不必要的拷贝

传参时尽量用引用：

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

如果不加引用，每次调用都会拷贝整个 vector，O(n) 的代价。我曾经在递归函数里忘了加引用，结果 10⁵ 的数据跑了 5 秒，加上引用后 0.3 秒。

使用 emplace 代替 insert/push

emplace_back 直接在容器内构造对象，省去了临时对象的拷贝：

vector<pair<int, int>> v;
v.emplace_back(1, 2);  // 比 push_back({1, 2}) 快

提前 break 与剪枝

很多循环其实可以提前结束。比如查找第一个满足条件的元素：

for (int i = 0; i < n; ++i) {
    if (check(i)) {
        // 找到了，直接 break
        break;
    }
}

别小看这个 break，在数据随机分布时，平均能省一半时间。

用数组代替 vector（极端情况）

如果数据量固定且不大，直接用原生数组：

int arr[100005];  // 比 vector<int> arr(100005) 快一点

但要注意栈空间限制。如果数组太大（比如 10⁷），还是用 vector 或 new 分配在堆上。

46.4 知识体系总览

下面这张图，是我整理的 STL 竞赛技巧核心脉络：

46.5 实战案例：快速统计频率

最后，咱们看一个综合案例。统计一个数组中每个数字出现的次数，并输出频率最高的前 K 个。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    
    unordered_map<int, int, custom_hash> freq;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        ++freq[x];
    }
    
    // 用优先队列取前 k 个
    priority_queue<pair<int, int>> pq;
    for (auto& [val, cnt] : freq) {
        pq.emplace(cnt, val);
    }
    
    for (int i = 0; i < k && !pq.empty(); ++i) {
        cout << pq.top().second << ' ' << pq.top().first << '\n';
        pq.pop();
    }
    
    return 0;
}

这个代码里，我用了 unordered_map 加自定义哈希，输入输出优化，以及 emplace 代替 push。每个细节都抠一点，整体性能就能提升不少。

好了，这一章的内容就到这里。记住，STL 是工具，不是银弹。理解底层原理，才能用得得心应手。

---

公众号:蓝海资料掘金营，微信deep3321