STL 容器与算法选型指南：让你的竞赛代码跑得飞快

在信息学奥赛中，时间就是分数。即使算法思路正确，如果使用的 STL 容器或算法不合适，程序很可能超时。就像你整理书包——用合适的收纳方式，取书快、放书稳；用错了方法，翻来翻去还容易丢东西。STL 的性能优化其实就是“选对工具、用好方法”，让程序在时间限制内顺利完成。

从图书馆理书的比喻说起

想象你要整理一个图书馆的书籍，你有几种工具：

手推车（vector）：可以快速搬运大堆书，也能随手抽出一本（随机访问）。但如果在车中间插一本书，就得把后面的书全部挪一遍（插入/删除慢）。
纸箱串（list）：可以轻松在中间插入或抽走一本书（链表 O(1)），但想找其中第 10 本书，你必须从第一本数起（随机访问慢）。
标签索引系统（map/set）：根据书名（键）快速定位书籍（O(log n)），但每次新增或移走一本书都要修改索引，稍微麻烦。
哈希标签墙（unordered_map/unordered_set）：也是按书名查找，但速度更快（平均 O(1)），不过如果书名（哈希值）重复太多，查找就变慢（最坏 O(n)）。

在写代码时，你需要根据数据操作的特点（增、删、改、查的频率）来选择容器，否则就会像“用叉子喝汤”一样低效。

一、容器选择：根据操作特点选对容器

1. 顺序容器

容器	特点	适合场景	类似生活例子
`vector`	底层连续内存，随机访问 O(1)，末尾插入/删除均摊 O(1)，中间插入/删除 O(n)	需要频繁按下标读取，很少在中间改动的数据，比如存储所有学生的考试成绩	你的一排书架：想看第 3 本书，直接走过去拿；但要在中间塞一本新书，后面的书都得挪动
`list`	双向链表，已知位置插入/删除 O(1)，随机访问 O(n)	需要大量在中间插入或删除，很少随机访问，比如维护一个随时需要添加/移除人的排队队伍	一条长长的队伍，可以随时在某个人后面插队或拉走一个人（如果知道他在哪里），但要找到第 10 个人得从头数
`deque`	双端队列，两端插入/删除 O(1)，随机访问 O(1)（但比 vector 略慢）	需要从两端快速操作，比如算法中的双端处理	食堂取餐排队：既可以从后面加入，也可以从前面离开（比如 VIP 优先）

新手常见错误：

在 vector 前面频繁插入：比如 v.insert(v.begin(), x)，因为每次都要把所有元素后移，复杂度 O(n)。等你处理完 10 万个数据，程序可能已经超时了。应该改用 deque 或 list。
对 list 频繁随机访问：比如用 std::next(l.begin(), 1000) 取第 1000 个元素，每次都要从头遍历，非常慢。应改用 vector 或 deque。

代码示例：选择正确的容器

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <chrono>
using namespace std;

int main() {
    const int N = 100000;

    // 例子1：频繁在头部插入 -> 用 deque 比 vector 快很多
    // 用 vector
    vector<int> vec;
    auto start = chrono::steady_clock::now();
    for (int i = 0; i < N; ++i) vec.insert(vec.begin(), i); // 每次 O(n)
    auto end = chrono::steady_clock::now();
    cout << "vector front insert: "
         << chrono::duration_cast<chrono::milliseconds>(end - start).count()
         << " ms" << endl;

    // 用 deque
    deque<int> deq;
    start = chrono::steady_clock::now();
    for (int i = 0; i < N; ++i) deq.push_front(i); // 每次 O(1)
    end = chrono::steady_clock::now();
    cout << "deque front insert: "
         << chrono::duration_cast<chrono::milliseconds>(end - start).count()
         << " ms" << endl;

    // 例子2：中间插入频繁 -> 用 list 比 vector 快
    vector<int> vec2;
    for (int i = 0; i < N; ++i) vec2.push_back(i);
    start = chrono::steady_clock::now();
    for (int i = 0; i < 1000; ++i) {
        vec2.insert(vec2.begin() + N/2, i); // 每次移动 N/2 个元素
    }
    end = chrono::steady_clock::now();
    cout << "vector middle insert: "
         << chrono::duration_cast<chrono::milliseconds>(end - start).count()
         << " ms" << endl;

    list<int> lst;
    for (int i = 0; i < N; ++i) lst.push_back(i);
    auto it = lst.begin();
    advance(it, N/2); // 先找到中间位置（list 需要 O(n) 找到位置）
    start = chrono::steady_clock::now();
    for (int i = 0; i < 1000; ++i) {
        lst.insert(it, i); // 插入 O(1)
    }
    end = chrono::steady_clock::now();
    cout << "list middle insert: "
         << chrono::duration_cast<chrono::milliseconds>(end - start).count()
         << " ms" << endl;

    return 0;
}

2. 关联容器

关联容器用于快速查找，但每种容器对“顺序”和“速度”的要求不同。

容器	底层结构	插入/删除/查找效率	是否有序	适合场景
`set` / `map`	红黑树（平衡二叉搜索树）	O(log n)	是，默认升序	需要有序地遍历数据，或需要支持 `lower_bound`/`upper_bound` 等范围查询
`unordered_set` / `unordered_map`	哈希表	平均 O(1)，最坏 O(n)	否	只关心是否存在或对应值，不关心顺序，且哈希函数均匀

生活例子：

set：像按编号排列的文件夹，每次插入新文件后仍然保持顺序，找文件时按编号二分查找（O(log n)）。
unordered_set：像你把文件扔进一个带标签的抽屉，每个标签对应一组文件，找文件时先看标签（哈希），再在组里找（理想情况只有 1 个文件）。

新手常见错误：

数据量大且不需要有序时用了 set/map：比如在 10^5 个整数中查重，用 set 插入和查找 O(log n) 可能能过，但用 unordered_set 平均快 3~5 倍。不过要注意，如果输入数据故意让你的哈希冲突（比如所有数模某个质数相同），unordered_set 会退化成 O(n) 链表，此时反而比 set 慢。这时可以自定义哈希函数。
错误地认为 unordered_set 总是更快：小数据量（比如 n<1000）时，set 的红黑树常数更小，反而可能更快。最好在本地测试。

代码示例：set vs unordered_set 查找效率

#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>
#include <chrono>
#include <random>
using namespace std;

int main() {
    const int N = 100000;
    vector<int> data(N);
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, N*10);
    for (int i = 0; i < N; ++i) data[i] = dis(gen);

    // set 插入
    set<int> st;
    auto start = chrono::steady_clock::now();
    for (int v : data) st.insert(v);
    auto end = chrono::steady_clock::now();
    cout << "set insert: "
         << chrono::duration_cast<chrono::milliseconds>(end - start).count()
         << " ms" << endl;

    // unordered_set 插入
    unordered_set<int> ust;
    start = chrono::steady_clock::now();
    for (int v : data) ust.insert(v);
    end = chrono::steady_clock::now();
    cout << "unordered_set insert: "
         << chrono::duration_cast<chrono::milliseconds>(end - start).count()
         << " ms" << endl;

    // 查找测试：随机查 10000 次
    vector<int> queries(10000);
    for (int& q : queries) q = dis(gen);

    start = chrono::steady_clock::now();
    for (int q : queries) {
        bool found = (st.find(q) != st.end());
    }
    end = chrono::steady_clock::now();
    cout << "set find: "
         << chrono::duration_cast<chrono::microseconds>(end - start).count()
         << " us" << endl;

    start = chrono::steady_clock::now();
    for (int q : queries) {
        bool found = (ust.find(q) != ust.end());
    }
    end = chrono::steady_clock::now();
    cout << "unordered_set find: "
         << chrono::duration_cast<chrono::microseconds>(end - start).count()
         << " us" << endl;

    return 0;
}

3. 容器适配器

stack：后进先出，通常底层用 deque。适合需要栈的场景，如括号匹配、深度优先搜索。
queue：先进先出，底层也是 deque。适合广度优先搜索、任务调度。
priority_queue：最大堆（默认），底层用 vector。插入 O(log n)，取最大值 O(1)。需要最小堆时用 priority_queue<int, vector<int>, greater<int>>。适合合并有序序列、求第 k 大元素等。

注意：priority_queue 默认的 greater 是 greater<int>（注意头文件 functional），比较方式要小心。

二、算法选择：用对 STL 算法

STL 算法库中很多函数都是经过高度优化的，不要自己手写同样的功能（除非你确定能写得更好）。

1. 排序

std::sort：快速排序的优化版（introsort），平均 O(n log n)，通常是最快的通用排序。适用于 vector、deque、array，但不适用于 list（list 有成员函数 list::sort）。
std::stable_sort：归并排序，稳定（相等元素相对顺序不变），但需要额外内存 O(n)，且常数略大。仅在需要稳定性时使用。
对 list 排序必须用 lst.sort()，否则编译报错。

新手常见错误：

对 list 使用 std::sort：编译会报错，因为 list 的迭代器不是随机访问迭代器。
用 sort 排序非常小的数组：比如只有 5 个元素时，手写选择排序可能更快，但通常 sort 也很快，不必过度优化。

2. 查找

线性查找：std::find（O(n)），适用于无序容器或有序但元素很少。
二分查找：std::binary_search、std::lower_bound、std::upper_bound，要求所在序列已经有序（如 vector 先 sort）。O(log n)。
关联容器自带的 find：set::find 和 map::find 是 O(log n) 的成员函数，比 std::find 快很多。unordered_set::find 平均 O(1)。
注意：不要对 set 或 map 使用 std::find（它只会线性搜索），而应该用成员函数 s.find(val)。

例子：有一个排好序的整数数组（vector），你需要快速判断某个数是否存在，就用 std::binary_search；如果需要知道它插入的位置，用 std::lower_bound。

3. 其他常用算法

std::accumulate：求和或自定义累加（O(n)）。
std::max_element / std::min_element：求最大最小值（O(n)）。
std::copy：复制区间到另一个容器（O(n)）。
std::fill：用同一个值填充区间（O(n)）。

三、具体优化技巧：细节决定成败

1. 用 `reserve` 预先分配内存

vector 在插入元素时，如果容量不够，会重新申请两倍大小的内存，并将原有元素移动/拷贝到新内存。这个过程很慢。如果你大概知道需要存储多少个元素，预先调用 reserve(n) 就能避免多次扩容。

vector<int> scores;              // 考试成绩
scores.reserve(50000);           // 知道有 5 万个学生，提前分配空间
for (int i = 0; i < 50000; ++i) scores.push_back(i);

如果不加 reserve，可能发生 20 次左右的重新分配（2 的幂次增长），每次拷贝大量数据，耗费时间。

注意：reserve 只增加容量，不改变大小（size），不会创建元素。而 resize 会创建元素。

2. 用 `emplace_back` 代替 `push_back`

对于复杂对象（如 pair<string, int> 或自定义结构体），push_back 需要先构造临时对象再拷贝或移动进容器，而 emplace_back 直接在容器内部构造，省略了临时对象，效率更高。

struct Student {
    string name;   // 姓名
    int score;     // 分数
    Student(string n, int s) : name(move(n)), score(s) {}
};

vector<Student> students;
students.reserve(1000);

// 好的写法：用 emplace_back，在容器内直接构造
students.emplace_back("Alice", 95);   // 直接在 vector 尾部构造

// 效率较低的写法：
students.push_back(Student("Bob", 87)); // 先构造临时 Student，再拷贝进去

对于基本类型（int、double 等），push_back 和 emplace_back 没有区别。

3. 遍历时缓存 `end()`

在循环遍历容器（特别是旧编译器）时，每次判断条件都会调用 v.end()，如果容器很大，这可能浪费一点时间。更优雅的做法是提前把 end 存下来：

// 不推荐：每次循环都调用 v.end()
for (auto it = v.begin(); it != v.end(); ++it) { ... }

// 推荐：缓存 end
for (auto it = v.begin(), end = v.end(); it != end; ++it) { ... }

现代编译器通常会对简单情况做优化（将 end() 内联为常量），但养成习惯总没错，尤其是需要跨编译器时。

4. 避免不必要的拷贝

函数参数尽量传引用（尤其是大容器），避免整个容器被拷贝。

// 错误：每次调用都拷贝整个 vector
int totalScore(vector<int> data) {
    return accumulate(data.begin(), data.end(), 0);
}

// 正确：传常量引用，不拷贝
int totalScore(const vector<int>& data) {
    return accumulate(data.begin(), data.end(), 0);
}

对于需要修改容器的函数，可以传引用（非 const）。

5. 选择正确的关联容器

10^5 级别以上且不需要有序时，优先使用 unordered_map 或 unordered_set。但如果哈希冲突严重（例如键都是 1、101、201……模 100 相同），性能会退化。此时可以自定义哈希函数，例如对整数使用更好的哈希：

struct CustomHash {
    size_t operator()(int x) const {
        // 简单的混合，减少冲突
        return x ^ (x >> 16);
    }
};
unordered_set<int, CustomHash> us;

另外，如果数据有序很重要（例如需要按顺序输出），或者需要 lower_bound，则必须用 set/map。

6. 使用 `std::string` 的 `reserve` 和 `append`

频繁用 += 拼接字符串（如循环中逐字符添加）会导致多次内存重新分配。预先 reserve 足够的空间，然后用 append 或 += 都能提高效率。

string result;              // 结果字符串
result.reserve(1000000);    // 事先知道大概长度
for (int i = 0; i < 1000000; ++i) {
    result += 'a';           // 由于已有容量，不会频繁分配
}

如果不用 reserve，拼接 100 万个字符可能发生数十次重新分配，耗时显著增加。

四、完整可运行示例：性能对比

下面的代码对比了不同容器和算法的性能，帮你直观感受“选择正确工具”的重要性。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <chrono>
#include <random>
#include <unordered_set>
using namespace std;

int main() {
    const int N = 100000;
    // 生成随机数据
    vector<int> data(N);
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, N);
    for (int& v : data) v = dis(gen);

    // 1. 比较 vector 排序 vs set 插入（排好序）
    auto start = chrono::steady_clock::now();
    vector<int> sorted_data = data;
    sort(sorted_data.begin(), sorted_data.end());
    auto end = chrono::steady_clock::now();
    cout << "vector sort: "
         << chrono::duration_cast<chrono::milliseconds>(end - start).count()
         << " ms" << endl;

    start = chrono::steady_clock::now();
    set<int> s;
    for (int v : data) s.insert(v);
    end = chrono::steady_clock::now();
    cout << "set insert (creates sorted order): "
         << chrono::duration_cast<chrono::milliseconds>(end - start).count()
         << " ms" << endl;

    // 2. 比较 vector 二分查找 vs unordered_set 查找
    sort(data.begin(), data.end()); // 先排序
    start = chrono::steady_clock::now();
    for (int i = 0; i < 1000; ++i) {
        int target = dis(gen);
        bool found = binary_search(data.begin(), data.end(), target);
    }
    end = chrono::steady_clock::now();
    cout << "binary_search on vector: "
         << chrono::duration_cast<chrono::microseconds>(end - start).count()
         << " us" << endl;

    unordered_set<int> us(data.begin(), data.end());
    start = chrono::steady_clock::now();
    for (int i = 0; i < 1000; ++i) {
        int target = dis(gen);
        bool found = (us.find(target) != us.end());
    }
    end = chrono::steady_clock::now();
    cout << "unordered_set find: "
         << chrono::duration_cast<chrono::microseconds>(end - start).count()
         << " us" << endl;

    // 3. 比较 vector 有 reserve 和没有 reserve 的插入时间
    vector<int> no_reserve;
    start = chrono::steady_clock::now();
    for (int i = 0; i < N; ++i) no_reserve.push_back(i);
    end = chrono::steady_clock::now();
    cout << "vector push_back without reserve: "
         << chrono::duration_cast<chrono::microseconds>(end - start).count()
         << " us" << endl;

    vector<int> with_reserve;
    with_reserve.reserve(N);
    start = chrono::steady_clock::now();
    for (int i = 0; i < N; ++i) with_reserve.push_back(i);
    end = chrono::steady_clock::now();
    cout << "vector push_back with reserve: "
         << chrono::duration_cast<chrono::microseconds>(end - start).count()
         << " us" << endl;

    return 0;
}

运行结果（不同机器有差异，但趋势一致）：

vector sort 比 set insert 快很多，因为 vector 排序是原地操作，而 set 插入需要平衡调整和节点分配。
unordered_set find 通常比 binary_search 快，因为哈希查找常数虽大但 O(1)。
加上 reserve 后，push_back 时间减少到原来的 1/3 甚至更少。

五、Python 中的等价优化思路

虽然本文主要讲 C++ STL，但 Python 中也有类似的知识点。

列表（list） 相当于 vector，尾部添加 O(1)，中间插入 O(n)。频繁在开头插入或删除请用 collections.deque。
字典（dict）和集合（set） 基于哈希，平均 O(1) 查找。需要有序时用 collections.OrderedDict（Python 3.7+ 的 dict 默认保持插入顺序，但无法按键排序）。
排序用 sorted() 或 list.sort()（原地），都是 Timsort，平均 O(n log n)。
二分查找 用 bisect 模块，前提是列表已排序。

import time
import random
from collections import deque

N = 100000
data = [random.randint(0, N) for _ in range(N)]

# 比较列表排序
start = time.time()
sorted_data = sorted(data)
print(f"list sort: {(time.time()-start)*1000:.2f} ms")

# set 构造
start = time.time()
s = set(data)
print(f"set from list: {(time.time()-start)*1000:.2f} ms")

# 二分查找
import bisect
data.sort()
start = time.time()
for _ in range(1000):
    target = random.randint(0, N)
    i = bisect.bisect_left(data, target)
    found = (i < len(data) and data[i] == target)
print(f"bisect: {(time.time()-start)*1000:.3f} ms")

# set 查找
start = time.time()
for _ in range(1000):
    target = random.randint(0, N)
    found = target in s
print(f"set in: {(time.time()-start)*1000:.3f} ms")

注意：Python 的 set in 成员检测非常快，因为内部也是哈希。但 bisect 二分查找常数小，当查找次数少时也很快。

六、常见错误避坑指南

在需要频繁按顺序遍历时用了 unordered_*：虽然查找快，但范围遍历（比如求最值、求和）还是需要整个遍历，此时有序容器（vector）更高效。unordered_* 遍历顺序无意义，且缓存不友好。
误以为 std::sort 总是最稳定：std::sort 不保证稳定（相等元素顺序可能改变）。需要稳定排序时用 std::stable_sort。
在 list 上调用 std::sort：编译错误。必须用 lst.sort()。
对 set 或 map 使用 std::find：std::find 只会线性遍历，应该用成员函数 find()。
忘记 <algorithm> 头文件：使用 sort、binary_search 等需要 #include <algorithm>；使用 accumulate 需要 <numeric>。
使用 vector<bool> 的坑：vector<bool> 不是真正的 bool 数组，它是按位压缩的，访问返回的是代理对象，不能取地址，也慢于普通 vector<char>。如果不需要空间极致优化，用 vector<char> 替代，速度更快。
在循环中频繁调用 vector::size() 或 end() 可能带来微小开销：虽然现代编译优化，但为了代码清晰和可移植，建议缓存一次。

七、总结与拓展

选择容器：根据操作频率（插入/删除/查找）和顺序需求，选择 vector、deque、list、set、unordered_set 等。
使用 STL 算法：不要重复造轮子，它们经过了最优实现。
优化内存：reserve 和 shrink_to_fit（释放多余内存）。
避免不必要的拷贝：传引用、用 emplace_back。
在竞赛中：如果 STL 仍然太慢，考虑手写简化版容器（如数组模拟邻接表），但大多数情况下 STL 足够。

相关知识点指引：

迭代器失效问题：了解在插入/删除时，哪些容器的迭代器会失效，避免踩坑。
移动语义与右值引用：深入理解 emplace_back 和 push_back 的区别。
自定义哈希函数：用于 unordered_* 容器，处理复杂键类型。
std::allocator：了解内存分配机制，不过竞赛中很少需要手动控制。
Python 中的 collections 模块：deque、defaultdict、Counter 等，也是高效编程的好帮手。

记住，性能优化不是一开始就做的，而是在算法正确的前提下，针对耗时操作进行局部优化。先用最简单的 STL 组合实现功能，如果超时，再用 reserve、换容器等技巧。希望这篇文章能帮你写出又快又简洁的竞赛代码！

STL在竞赛中的性能优化技巧

STL 容器与算法选型指南：让你的竞赛代码跑得飞快

从图书馆理书的比喻说起

一、容器选择：根据操作特点选对容器

1. 顺序容器

2. 关联容器

3. 容器适配器

二、算法选择：用对 STL 算法

1. 排序

2. 查找

3. 其他常用算法

三、具体优化技巧：细节决定成败

1. 用 `reserve` 预先分配内存

2. 用 `emplace_back` 代替 `push_back`

3. 遍历时缓存 `end()`

4. 避免不必要的拷贝

5. 选择正确的关联容器

6. 使用 `std::string` 的 `reserve` 和 `append`

四、完整可运行示例：性能对比

五、Python 中的等价优化思路

六、常见错误避坑指南

七、总结与拓展

例题精讲