第 2 章：STL 标准模板库

STL 是 C++ 在竞赛中最大的优势。掌握 STL，等于掌握了竞赛的"武器库"。

---

概览

STL（Standard Template Library，标准模板库）是 C++ 内置的一套通用数据结构和算法。在竞赛中，STL 能帮你省去大量手写代码的时间。

STL 组成

graph TD
    STL["STL 标准模板库"] --> CONT["容器 Containers"]
    STL --> ALGO["算法 Algorithms"]
    STL --> ITER["迭代器 Iterators"]

    CONT --> SEQ["序列容器<br/>vector, deque, array"]
    CONT --> ASSOC["关联容器<br/>set, map"]
    CONT --> UNORD["无序容器<br/>unordered_set, unordered_map"]
    CONT --> ADAPT["容器适配器<br/>stack, queue, priority_queue"]

    ALGO --> SORT["排序 sort"]
    ALGO --> SEARCH["查找 lower_bound"]
    ALGO --> MISC["其他 unique, reverse"]

    ITER --> IT["迭代器<br/>begin(), end(), rbegin()"]

    style STL fill:#2196F3,color:#fff
    style CONT fill:#4CAF50,color:#fff
    style ALGO fill:#FF9800,color:#fff
    style ITER fill:#9C27B0,color:#fff

容器复杂度速查

容器	随机访问	头部插入	尾部插入	查找	有序
vector	O(1)	O(n)	O(1)*	O(n)	否
deque	O(1)	O(1)*	O(1)*	O(n)	否
set	-	-	-	O(log n)	是
map	-	-	-	O(log n)	是
unordered_set	-	-	-	O(1)*	否
unordered_map	-	-	-	O(1)*	否
list	-	O(1)	O(1)	O(n)	否

*均摊时间复杂度

注：list（双向链表）在竞赛中极少用到，本书未单独展开，用法见 cppreference。

---

2.1 序列容器

2.1.1 vector — 动态数组（最常用）

vector 是竞赛中使用频率最高的容器，本质上是一个可以自动扩容的数组。

graph LR
    subgraph "vector 内存模型"
        A["data: [10] [20] [30] [40] [50] |  |  "] --> B["size = 5"]
        A --> C["capacity = 7"]
    end

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

int main() {
    // ---- 创建 vector ----
    vector<int> v1;               // 空 vector
    vector<int> v2(10);           // 10 个元素，初始化为 0
    vector<int> v3(10, 42);       // 10 个元素，全部为 42
    vector<int> v4 = {1, 2, 3};  // 初始化列表
    vector<int> v5(v4);           // 拷贝 v4

    // ---- 访问元素 ----
    cout << v4[0] << endl;        // 下标访问: 1
    cout << v4.at(1) << endl;     // 带边界检查的访问: 2
    cout << v4.front() << endl;   // 第一个元素: 1
    cout << v4.back() << endl;    // 最后一个元素: 3

    // ---- 增删元素 ----
    v1.push_back(10);  // 在末尾添加元素
    v1.push_back(20);
    v1.push_back(30);
    v1.pop_back();     // 删除末尾元素

    // 在指定位置插入（效率较低，O(n)）
    v1.insert(v1.begin() + 1, 15);  // 在位置 1 插入 15

    // 删除指定位置元素（效率较低，O(n)）
    v1.erase(v1.begin());  // 删除第一个元素

    // ---- 大小相关 ----
    cout << v1.size() << endl;     // 元素个数
    cout << v1.empty() << endl;    // 是否为空（1为空，0为非空）
    v1.clear();                    // 清空所有元素
    v1.resize(100);               // 调整大小为 100

    // ---- 遍历方式 ----
    vector<int> nums = {3, 1, 4, 1, 5, 9};

    // 方式1：下标遍历
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }
    cout << endl;

    // 方式2：迭代器遍历
    for (auto it = nums.begin(); it != nums.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 方式3：range-based for（最简洁，推荐）
    for (int x : nums) {
        cout << x << " ";
    }
    cout << endl;

    // 方式4：用引用可以修改元素
    for (int &x : nums) {
        x *= 2;  // 每个元素翻倍
    }

    // ---- 排序 ----
    sort(nums.begin(), nums.end());         // 升序排序
    sort(nums.rbegin(), nums.rend());       // 降序排序（反向迭代器）

    // ---- 二维 vector ----
    int rows = 3, cols = 4;
    vector<vector<int>> grid(rows, vector<int>(cols, 0));
    grid[1][2] = 42;
    cout << grid[1][2] << endl;

    return 0;
}

vector 的使用场景

• 替代数组：几乎所有需要数组的地方都可以用 vector
• 动态增长：不确定数据量大小时使用
• 二维数组：vector<vector<int>> 替代 int a[100][100]
• 函数返回值：可以安全地从函数中返回

2.1.2 deque — 双端队列

deque（double-ended queue）支持在两端高效地插入和删除元素。

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

int main() {
    deque<int> dq;

    // 两端操作都是 O(1)
    dq.push_back(3);   // 尾部添加: [3]
    dq.push_back(4);   // 尾部添加: [3, 4]
    dq.push_front(2);  // 头部添加: [2, 3, 4]
    dq.push_front(1);  // 头部添加: [1, 2, 3, 4]

    // 访问元素（支持随机访问，O(1)）
    cout << dq[0] << endl;   // 1
    cout << dq.back() << endl; // 4

    // 两端删除
    dq.pop_front();  // 删除头部: [2, 3, 4]
    dq.pop_back();   // 删除尾部: [2, 3]

    // 遍历
    for (int x : dq) {
        cout << x << " ";  // 2 3
    }
    cout << endl;

    return 0;
}

deque vs vector

操作	vector	deque
尾部增删	O(1) 均摊	O(1)
头部增删	O(n)	O(1)
随机访问	O(1)	O(1)
内存连续性	连续	分段连续

经验：如果不需要头部操作，优先用 vector（缓存更友好）。需要双端操作时用 deque。

2.1.3 array — 固定大小数组（C++11）

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

int main() {
    // array 是固定大小的数组，比原生数组更安全
    array<int, 5> arr = {1, 2, 3, 4, 5};

    // 和 vector 类似的接口
    cout << arr.size() << endl;   // 5
    cout << arr.front() << endl;  // 1
    cout << arr.back() << endl;   // 5

    // 支持随机访问
    arr[2] = 10;
    cout << arr.at(2) << endl;   // 10

    // 可以直接比较（原生数组不行）
    array<int, 5> arr2 = {1, 2, 3, 4, 5};
    if (arr == arr2) {
        cout << "equal" << endl;
    }

    return 0;
}

array 在竞赛中的使用

竞赛中 array 用得不多，因为原生数组和 vector 已经够用。但 array 的好处是：可以用 == 比较，可以作为函数参数传值。

---

2.2 关联容器

2.2.1 set — 有序集合（自动去重）

set 基于红黑树实现，元素自动排序且不重复。

graph TD
    subgraph "set 内部结构（红黑树）"
        ROOT["5"] --> LEFT["3"]
        ROOT --> RIGHT["8"]
        LEFT --> LL["1"]
        LEFT --> LR["4"]
        RIGHT --> RL["7"]
        RIGHT --> RR["9"]
    end

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

int main() {
    set<int> s;

    // 插入元素（自动排序，自动去重）
    s.insert(3);
    s.insert(1);
    s.insert(4);
    s.insert(1);  // 重复，不会插入
    s.insert(5);
    s.insert(9);

    // s = {1, 3, 4, 5, 9}

    // 遍历（有序输出）
    for (int x : s) {
        cout << x << " ";  // 1 3 4 5 9
    }
    cout << endl;

    // 查找
    if (s.find(4) != s.end()) {
        cout << "找到了 4" << endl;
    }

    // count 也能判断是否存在（因为 set 元素不重复，返回 0 或 1）
    if (s.count(7) == 0) {
        cout << "7 不存在" << endl;
    }

    // 删除
    s.erase(4);  // 删除值为 4 的元素
    // s = {1, 3, 5, 9}

    // 大小
    cout << s.size() << endl;  // 4

    // ---- lower_bound / upper_bound ----
    // lower_bound(x): 返回 >= x 的第一个元素的迭代器
    // upper_bound(x): 返回 > x 的第一个元素的迭代器
    auto it = s.lower_bound(5);
    if (it != s.end()) {
        cout << ">= 5 的第一个元素: " << *it << endl;  // 5
    }

    return 0;
}

2.2.2 multiset — 有序多重集合（允许重复）

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

int main() {
    multiset<int> ms;

    // 允许重复元素
    ms.insert(1);
    ms.insert(1);
    ms.insert(1);
    ms.insert(3);
    ms.insert(5);

    // ms = {1, 1, 1, 3, 5}

    // count 返回出现次数
    cout << ms.count(1) << endl;  // 3

    // 删除会删除所有值为 x 的元素
    ms.erase(1);  // 删除所有 1
    // ms = {3, 5}

    // 如果只想删除一个
    ms.insert(7);
    ms.insert(7);
    ms.insert(7);
    auto it = ms.find(7);
    if (it != ms.end()) {
        ms.erase(it);  // 只删除一个 7
    }
    // ms = {3, 5, 7, 7}

    for (int x : ms) {
        cout << x << " ";  // 3 5 7 7
    }
    cout << endl;

    return 0;
}

multiset 的竞赛用途

• 维护一个可以重复的有序序列
• 支持 O(log n) 的插入、删除、查找
• *ms.begin() 取最小值，*ms.rbegin() 取最大值
• 经典用法：滑动窗口求中位数、维护前 k 大/小的值

2.2.3 map — 有序映射（键值对）

map 是竞赛中非常常用的数据结构，相当于"万能数组"——下标可以是任意类型。

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

int main() {
    map<string, int> mp;

    // 插入（三种方式）
    mp["apple"] = 3;                        // 最常用
    mp.insert({"banana", 5});               // insert 方式
    mp.insert(make_pair("cherry", 7));      // make_pair 方式

    // 访问
    cout << mp["apple"] << endl;  // 3
    cout << mp.at("banana") << endl;  // 5

    // 注意：访问不存在的 key 会自动创建（值为 0）
    cout << mp["not_exist"] << endl;  // 输出 0，并且 mp 中新增了这个键

    // 安全的查找方式
    if (mp.find("apple") != mp.end()) {
        cout << "apple 存在" << endl;
    }

    // 或者用 count
    if (mp.count("apple")) {
        cout << "apple 存在" << endl;
    }

    // 遍历（按 key 有序输出）
    for (auto &p : mp) {
        cout << p.first << " -> " << p.second << endl;
    }
    // 按字典序输出：
    // apple -> 3
    // banana -> 5
    // cherry -> 7
    // not_exist -> 0

    // 删除
    mp.erase("not_exist");

    // ---- 竞赛中的常见用法：统计频率 ----
    vector<int> nums = {1, 2, 3, 2, 1, 2, 3, 3, 3};
    map<int, int> freq;
    for (int x : nums) {
        freq[x]++;
    }
    for (auto &p : freq) {
        cout << p.first << " 出现 " << p.second << " 次" << endl;
    }
    // 1 出现 2 次
    // 2 出现 3 次
    // 3 出现 4 次

    return 0;
}

2.2.4 multimap — 有序多重映射

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

int main() {
    // multimap 允许同一个 key 对应多个 value
    multimap<string, int> scores;

    scores.insert({"Alice", 90});
    scores.insert({"Alice", 85});
    scores.insert({"Bob", 92});
    scores.insert({"Bob", 88});

    // 查找某个 key 的所有值
    auto range = scores.equal_range("Alice");
    for (auto it = range.first; it != range.second; ++it) {
        cout << it->first << ": " << it->second << endl;
    }
    // Alice: 90
    // Alice: 85

    return 0;
}

2.2.5 unordered_set / unordered_map — 哈希容器

无序容器基于哈希表实现，查找/插入/删除都是 O(1) 的平均时间复杂度。

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

int main() {
    // ---- unordered_set：无序集合 ----
    unordered_set<int> us;
    us.insert(3);
    us.insert(1);
    us.insert(4);
    us.insert(1);  // 重复，不插入

    // O(1) 查找
    if (us.count(3)) {
        cout << "3 存在" << endl;
    }

    // 注意：遍历顺序是不确定的！
    for (int x : us) {
        cout << x << " ";  // 顺序不确定
    }
    cout << endl;

    // ---- unordered_map：无序映射 ----
    unordered_map<string, int> ump;
    ump["hello"] = 1;
    ump["world"] = 2;

    // O(1) 查找
    cout << ump["hello"] << endl;  // 1

    // 遍历顺序不确定
    for (auto &p : ump) {
        cout << p.first << " -> " << p.second << endl;
    }

    return 0;
}

有序容器 vs 无序容器

特性	set/map	unordered_set/unordered_map
底层实现	红黑树	哈希表
查找复杂度	O(log n)	O(1) 平均，O(n) 最坏
是否有序	有序	无序
自定义 key	需要 < 运算符	需要哈希函数
竞赛中常用 key	int, string, pair	int, string

经验：如果需要有序遍历或范围查询，用 set/map。如果只需要快速查找，用 unordered_set/unordered_map。

Codeforces 反哈希（hack）：unordered 容器可能被卡成 O(n²)

unordered_map/unordered_set 的 O(1) 只是平均复杂度。GCC 默认的整数哈希是恒等映射（hash(x) = x），出题人或 hack 者可以专门构造一组 key，让它们全部落进同一个桶，查找退化成 O(n)，整个程序退化成 O(n²) 直接 TLE。这在 Codeforces 上是真实存在的攻击手段（尤其是 Div. 1/2 的 hack 阶段和 system test）。

解决办法：自定义一个带随机种子的哈希函数（splitmix64），让对手无法预测：

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        // FIXED_RANDOM 每次运行都不同，对手无法预测
        static const uint64_t FIXED_RANDOM =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

// 用法：把第三个（set 是第二个）模板参数换成 custom_hash 即可
unordered_map<long long, int, custom_hash> safe_map;
unordered_set<long long, custom_hash> safe_set;

经验：在 Codeforces 上用整数做 key 时，要么加上 custom_hash，要么干脆用 map（O(log n) 但稳定不会被卡）。平时 OJ 刷题（洛谷等）数据固定，一般不用担心。

---

2.3 容器适配器

2.3.1 stack — 栈

栈是"后进先出"（LIFO）的数据结构。

graph TD
    subgraph "stack 操作"
        A["入栈 push"] --> B["栈顶元素 top"]
        B --> C["出栈 pop"]
    end

    subgraph "栈的状态变化"
        S1["[]"] -->|"push(1)"| S2["[1]"]
        S2 -->|"push(2)"| S3["[1, 2]"]
        S3 -->|"push(3)"| S4["[1, 2, 3] ← 栈顶"]
        S4 -->|"pop()"| S5["[1, 2]"]
    end

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

int main() {
    stack<int> st;

    // 入栈
    st.push(1);
    st.push(2);
    st.push(3);

    // 栈顶元素
    cout << st.top() << endl;  // 3

    // 出栈
    st.pop();  // 删除栈顶元素
    cout << st.top() << endl;  // 2

    // 大小和判空
    cout << st.size() << endl;  // 2
    cout << st.empty() << endl; // 0（非空）

    // 遍历（只能从栈顶开始逐个弹出）
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;  // 2 1

    return 0;
}

stack 的竞赛用途

• 括号匹配
• 表达式求值
• DFS 中模拟递归栈
• 单调栈（求下一个更大/更小元素）

2.3.2 queue — 队列

队列是"先进先出"（FIFO）的数据结构。

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

int main() {
    queue<int> q;

    // 入队
    q.push(1);
    q.push(2);
    q.push(3);

    // 队首和队尾
    cout << q.front() << endl;  // 1（队首）
    cout << q.back() << endl;   // 3（队尾）

    // 出队
    q.pop();  // 删除队首
    cout << q.front() << endl;  // 2

    // 大小和判空
    cout << q.size() << endl;  // 2
    cout << q.empty() << endl; // 0

    // 遍历
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;  // 2 3

    return 0;
}

queue 的竞赛用途

• BFS（广度优先搜索）的核心数据结构
• 拓扑排序
• 滑动窗口问题

2.3.3 priority_queue — 优先队列（堆）

优先队列每次弹出的都是最大（或最小）的元素，本质是一个堆。

graph TD
    subgraph "最大堆（默认）"
        MAX["10"] --> ML["7"]
        MAX --> MR["9"]
        ML --> MLL["3"]
        ML --> MLR["5"]
        MR --> MRL["8"]
        MR --> MRR["6"]
    end
    style MAX fill:#f44336,color:#fff

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

int main() {
    // ---- 最大堆（默认）----
    priority_queue<int> max_heap;

    max_heap.push(3);
    max_heap.push(1);
    max_heap.push(4);
    max_heap.push(1);
    max_heap.push(5);

    // 每次弹出最大的
    while (!max_heap.empty()) {
        cout << max_heap.top() << " ";  // 5 4 3 1 1
        max_heap.pop();
    }
    cout << endl;

    // ---- 最小堆 ----
    // 方法1：使用 greater<int>
    priority_queue<int, vector<int>, greater<int>> min_heap;

    min_heap.push(3);
    min_heap.push(1);
    min_heap.push(4);
    min_heap.push(1);
    min_heap.push(5);

    // 每次弹出最小的
    while (!min_heap.empty()) {
        cout << min_heap.top() << " ";  // 1 1 3 4 5
        min_heap.pop();
    }
    cout << endl;

    // ---- 存储 pair 的优先队列 ----
    // 按 first 降序（默认比较 pair 的 first）
    priority_queue<pair<int, string>> pq;
    pq.push({100, "Alice"});
    pq.push({90, "Bob"});
    pq.push({95, "Charlie"});

    while (!pq.empty()) {
        auto [score, name] = pq.top();  // C++17 结构化绑定
        cout << name << ": " << score << endl;
        pq.pop();
    }
    // Alice: 100
    // Charlie: 95
    // Bob: 90

    // ---- 自定义比较：按 second 降序 ----
    // 方法：使用 lambda（C++11）或者重载运算符
    // 这里用更简单的写法：取负数
    priority_queue<pair<int, int>> pq2;
    // 如果想按 second 排序，可以交换 pair 中 first 和 second 的位置

    return 0;
}

priority_queue 的竞赛用途

• Dijkstra 最短路算法
• 求第 k 大/小元素
• 贪心问题（每次取最大/最小）
• 合并 k 个有序序列
• 带权 BFS

priority_queue 的注意事项

• 默认是最大堆（大顶堆），不是最小堆
• 最小堆需要写 priority_queue<int, vector<int>, greater<int>>
• 没有 clear() 方法，重新创建比清空更方便
• 自定义结构体放入优先队列需要重载 operator<

---

2.4 字符串：string 类的常用操作

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

int main() {
    // ---- 创建和赋值 ----
    string s1 = "hello";
    string s2("world");
    string s3(5, 'a');  // "aaaaa" 重复字符
    string s4 = s1;     // 拷贝

    // ---- 基本操作 ----
    cout << s1.size() << endl;      // 长度: 5
    cout << s1.length() << endl;    // 等同于 size(): 5
    cout << s1.empty() << endl;     // 是否为空: 0
    cout << s1[0] << endl;          // 下标访问: h
    cout << s1.at(1) << endl;       // 带检查的访问: e

    // ---- 拼接 ----
    string s = s1 + " " + s2;  // "hello world"
    s += "!";                   // "hello world!"
    s.push_back('?');           // "hello world!?"

    // ---- 比较（直接用运算符）----
    string a = "abc", b = "abd";
    if (a < b) cout << "abc < abd" << endl;  // 字典序比较

    // ---- 子串 ----
    string sub = s.substr(0, 5);  // 从位置 0 开始，长度 5: "hello"
    cout << sub << endl;

    // ---- 查找 ----
    size_t pos = s.find("world");  // 返回位置 6
    if (pos != string::npos) {
        cout << "找到了，位置: " << pos << endl;
    }

    // 查找所有出现位置
    string text = "abcabcabc";
    string pattern = "abc";
    pos = 0;
    while ((pos = text.find(pattern, pos)) != string::npos) {
        cout << "在位置 " << pos << " 找到" << endl;
        pos += pattern.length();
    }
    // 在位置 0 找到
    // 在位置 3 找到
    // 在位置 6 找到

    // ---- 替换和删除 ----
    string str = "hello world";
    str.replace(6, 5, "cpp");  // 从位置6开始，替换5个字符: "hello cpp"
    str.erase(5, 1);           // 从位置5开始，删除1个字符: "hellocpp"

    // ---- 插入 ----
    str.insert(5, " ");  // 在位置5插入: "hello cpp"

    // ---- 数字和字符串转换 ----
    int n = 42;
    string num_str = to_string(n);       // int -> string: "42"
    int back = stoi(num_str);            // string -> int: 42
    double d = stod("3.14");             // string -> double: 3.14
    long long big = stoll("1234567890"); // string -> long long

    // ---- 字符串分割（手写）----
    string line = "hello world cpp stl";
    vector<string> tokens;
    string token;
    istringstream iss(line);
    while (iss >> token) {
        tokens.push_back(token);
    }
    for (auto &t : tokens) {
        cout << "[" << t << "] ";
    }
    cout << endl;
    // [hello] [world] [cpp] [stl]

    // ---- 字符判断（来自 cctype）----
    char ch = 'A';
    cout << isalpha(ch) << endl;  // 是字母: 1
    cout << isdigit('3') << endl; // 是数字: 1
    cout << isupper(ch) << endl;  // 是大写: 1
    cout << tolower(ch) << endl;  // 转小写: 97（'a' 的 ASCII）
    cout << (char)toupper('a') << endl; // 转大写: A

    return 0;
}

string 在竞赛中的高频操作

• s.size() 取长度
• s.substr(pos, len) 取子串
• s.find(t) 查找子串
• s += t 拼接
• to_string(n) 数字转字符串
• stoi(s) 字符串转数字

---

2.5 算法库

2.5.1 sort — 排序（最常用）

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

// 方法1：普通比较函数
// 注意：C++ 不允许在函数内部定义函数，比较函数必须写在 main 外面
bool cmp_desc(int a, int b) {
    return a > b;  // 降序
}

int main() {
    // ---- 基本排序 ----
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

    sort(v.begin(), v.end());  // 升序排序
    // v = {1, 1, 2, 3, 4, 5, 6, 9}

    sort(v.rbegin(), v.rend());  // 降序排序（反向迭代器）
    // v = {9, 6, 5, 4, 3, 2, 1, 1}

    // ---- 自定义比较函数 ----
    // 方法1：普通函数（定义在 main 上方）
    sort(v.begin(), v.end(), cmp_desc);

    // 方法2：lambda 表达式（更常用，语法见第 1 章 1.9 节）
    sort(v.begin(), v.end(), [](int a, int b) {
        return a > b;  // 降序
    });

    // ---- 结构体排序 ----
    struct Student {
        string name;
        int score;
    };

    vector<Student> students = {
        {"Alice", 90},
        {"Bob", 85},
        {"Charlie", 95},
        {"David", 90}
    };

    // 按分数降序，分数相同按名字升序
    sort(students.begin(), students.end(), [](const Student &a, const Student &b) {
        if (a.score != b.score) return a.score > b.score;
        return a.name < b.name;
    });

    for (auto &s : students) {
        cout << s.name << ": " << s.score << endl;
    }
    // Charlie: 95
    // Alice: 90
    // David: 90
    // Bob: 85

    // ---- 对数组排序 ----
    int arr[] = {5, 3, 1, 4, 2};
    int n = 5;
    sort(arr, arr + n);  // 数组排序

    // ---- 字符串排序 ----
    string str = "dcba";
    sort(str.begin(), str.end());  // "abcd"

    // ---- pair 排序 ----
    // pair 默认按 first 升序，first 相同按 second 升序
    vector<pair<int, int>> pairs = {{3, 1}, {1, 4}, {1, 2}, {2, 3}};
    sort(pairs.begin(), pairs.end());
    // (1, 2), (1, 4), (2, 3), (3, 1)

    return 0;
}

2.5.2 lower_bound / upper_bound — 二分查找

这两个函数在有序序列中进行二分查找，竞赛中非常高频。

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

int main() {
    vector<int> v = {1, 2, 2, 2, 3, 4, 5};

    // lower_bound(first, last, x): 返回第一个 >= x 的元素的迭代器
    auto it1 = lower_bound(v.begin(), v.end(), 2);
    cout << "第一个 >= 2 的位置: " << it1 - v.begin() << endl;  // 1

    // upper_bound(first, last, x): 返回第一个 > x 的元素的迭代器
    auto it2 = upper_bound(v.begin(), v.end(), 2);
    cout << "第一个 > 2 的位置: " << it2 - v.begin() << endl;  // 4

    // 利用 upper - lower 可以计算元素出现次数
    int count = upper_bound(v.begin(), v.end(), 2) - lower_bound(v.begin(), v.end(), 2);
    cout << "2 出现了 " << count << " 次" << endl;  // 3

    // ---- 在 set 中使用 ----
    set<int> s = {1, 3, 5, 7, 9};
    auto it = s.lower_bound(4);  // 返回指向 5 的迭代器
    cout << *it << endl;  // 5

    // ---- 在降序序列中使用 ----
    // 需要用 greater<int>()，此时：
    // lower_bound 返回第一个 <= x 的位置
    // upper_bound 返回第一个 < x 的位置
    vector<int> desc = {9, 7, 5, 3, 1};
    auto it3 = lower_bound(desc.begin(), desc.end(), 5, greater<int>());
    cout << "降序中第一个 <= 5 的位置: " << it3 - desc.begin() << endl;  // 2

    // ---- 竞赛中的常见用法：离散化 ----
    // 假设值域很大但数量不多，可以用二分做"值到下标"的映射
    vector<int> values = {100, 300, 200, 500, 400};
    vector<int> sorted_vals = values;
    sort(sorted_vals.begin(), sorted_vals.end());
    sorted_vals.erase(unique(sorted_vals.begin(), sorted_vals.end()), sorted_vals.end());
    // sorted_vals = {100, 200, 300, 400, 500}

    for (int x : values) {
        int idx = lower_bound(sorted_vals.begin(), sorted_vals.end(), x) - sorted_vals.begin();
        cout << x << " -> " << idx << endl;
    }

    return 0;
}

2.5.3 nth_element — 第 k 大/小元素

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

int main() {
    vector<int> v = {5, 3, 1, 4, 2, 8, 7, 6};

    // nth_element: 将第 k 小的元素放到正确位置
    // 其左边的都 <= 它，右边的都 >= 它（但不保证完全有序）
    nth_element(v.begin(), v.begin() + 2, v.end());
    cout << "第 3 小的元素: " << v[2] << endl;  // 3

    // 求第 k 大
    nth_element(v.begin(), v.begin() + 2, v.end(), greater<int>());
    cout << "第 3 大的元素: " << v[2] << endl;

    // 复杂度：O(n)，比 sort 的 O(n log n) 更快
    // 适合只需要找第 k 大/小，不需要完全排序的场景

    return 0;
}

2.5.4 unique — 去重

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

int main() {
    // unique 只去除相邻的重复元素，所以必须先排序
    vector<int> v = {1, 3, 2, 1, 3, 2, 1};

    sort(v.begin(), v.end());
    // v = {1, 1, 1, 2, 2, 3, 3}

    // unique 返回去重后"逻辑末尾"的迭代器
    auto new_end = unique(v.begin(), v.end());
    // v = {1, 2, 3, 2, 1, 3, 3}
    //            ↑ new_end 指向这里

    // 真正删除多余的元素
    v.erase(new_end, v.end());
    // v = {1, 2, 3}

    for (int x : v) {
        cout << x << " ";
    }
    cout << endl;

    // 经典写法（一行搞定去重）
    vector<int> v2 = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    sort(v2.begin(), v2.end());
    v2.erase(unique(v2.begin(), v2.end()), v2.end());
    // v2 = {1, 2, 3, 4, 5, 6, 9}

    return 0;
}

2.5.5 reverse — 反转

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

int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    reverse(v.begin(), v.end());
    // v = {5, 4, 3, 2, 1}

    // 反转部分
    reverse(v.begin() + 1, v.begin() + 4);
    // v = {5, 2, 3, 4, 1}

    // 字符串反转
    string s = "hello";
    reverse(s.begin(), s.end());
    cout << s << endl;  // "olleh"

    return 0;
}

2.5.6 next_permutation — 全排列

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

int main() {
    // next_permutation 生成下一个排列（字典序）
    vector<int> v = {1, 2, 3};

    // 注意：必须从最小排列开始，才能生成所有排列
    do {
        for (int x : v) cout << x << " ";
        cout << endl;
    } while (next_permutation(v.begin(), v.end()));
    // 输出：
    // 1 2 3
    // 1 3 2
    // 2 1 3
    // 2 3 1
    // 3 1 2
    // 3 2 1

    // 如果不是从最小排列开始
    vector<int> v2 = {2, 1, 3};
    next_permutation(v2.begin(), v2.end());
    // v2 = {2, 3, 1}（不会回到 1 2 3）

    // 字符串全排列
    string s = "abc";
    sort(s.begin(), s.end());
    do {
        cout << s << endl;
    } while (next_permutation(s.begin(), s.end()));

    // 上一个排列
    // prev_permutation(v.begin(), v.end());

    return 0;
}

其他常用算法

// max_element / min_element：最大/最小元素的迭代器
auto it = max_element(v.begin(), v.end());
cout << *it << endl;

// accumulate：求和（需要 #include <numeric>）
#include <numeric>
int sum = accumulate(v.begin(), v.end(), 0);  // 初始值为 0

// count：计数
int cnt = count(v.begin(), v.end(), 3);  // 3 出现了几次

// fill：填充
fill(v.begin(), v.end(), 0);  // 全部填充为 0

// copy：复制
copy(v.begin(), v.end(), another_v.begin());

// swap：交换
swap(v[0], v[1]);

---

2.6 迭代器基础与 range-based for 循环

迭代器简介

迭代器是一种"智能指针"，用于遍历容器中的元素。不同容器的迭代器接口统一，这是 STL 的核心设计思想。

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

int main() {
    vector<int> v = {10, 20, 30, 40, 50};

    // 迭代器的基本用法
    vector<int>::iterator it = v.begin();  // 指向第一个元素
    cout << *it << endl;   // 10（解引用）
    ++it;                  // 移动到下一个
    cout << *it << endl;   // 20

    // auto 简化声明
    auto it2 = v.begin();
    auto it3 = v.end();  // 指向"末尾之后"，不是最后一个元素

    // 遍历：经典写法
    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 反向迭代器
    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        cout << *it << " ";  // 50 40 30 20 10
    }
    cout << endl;

    // 常量迭代器（不能修改元素）
    for (auto it = v.cbegin(); it != v.cend(); ++it) {
        cout << *it << " ";
        // *it = 100;  // 编译错误！
    }
    cout << endl;

    // 迭代器做算术
    auto mid = v.begin() + v.size() / 2;  // 指向中间元素
    cout << *mid << endl;  // 30

    // 两个迭代器之间的距离
    int dist = v.end() - v.begin();
    cout << dist << endl;  // 5

    return 0;
}

range-based for 循环（C++11）

range-based for 是遍历容器最简洁的方式，竞赛中推荐使用。

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

int main() {
    vector<int> v = {1, 2, 3, 4, 5};

    // 基本形式
    for (int x : v) {
        cout << x << " ";  // 1 2 3 4 5
    }
    cout << endl;

    // 使用引用可以修改元素
    for (int &x : v) {
        x *= 2;
    }
    // v = {2, 4, 6, 8, 10}

    // 使用 const 引用（不修改，避免拷贝，推荐用于大对象）
    vector<string> strs = {"hello", "world", "cpp"};
    for (const string &s : strs) {
        cout << s << " ";
    }
    cout << endl;

    // auto 自动推导类型（最常用的写法）
    for (auto &x : v) {
        cout << x << " ";
    }
    cout << endl;

    // map 的 range-based for
    map<string, int> mp = {{"a", 1}, {"b", 2}};
    for (auto &[key, value] : mp) {  // C++17 结构化绑定
        cout << key << " -> " << value << endl;
    }

    // C++11/14 的写法
    for (auto &p : mp) {
        cout << p.first << " -> " << p.second << endl;
    }

    // 初始化列表
    for (int x : {1, 2, 3, 4, 5}) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

range-based for 的建议

• 读取元素时用 for (const auto &x : v) 避免拷贝
• 修改元素时用 for (auto &x : v)
• 简单类型（int 等）可以直接用 for (int x : v)

---

2.7 常用工具

2.7.1 pair — 二元组

pair 是竞赛中使用频率最高的小工具，用于存储两个值。

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

int main() {
    // 创建 pair
    pair<int, int> p1 = {1, 2};
    pair<int, int> p2 = make_pair(3, 4);
    pair<string, int> p3 = {"Alice", 90};

    // 访问元素
    cout << p1.first << " " << p1.second << endl;  // 1 2

    // C++17 结构化绑定
    auto [a, b] = p1;
    cout << a << " " << b << endl;  // 1 2

    // 比较（先比较 first，first 相同再比较 second）
    pair<int, int> x = {1, 3};
    pair<int, int> y = {1, 2};
    if (x > y) {
        cout << "x > y" << endl;  // 因为 first 相同，3 > 2
    }

    // 可以放入 set/map
    set<pair<int, int>> sp;
    sp.insert({1, 3});
    sp.insert({1, 2});
    sp.insert({2, 1});

    for (auto &p : sp) {
        cout << "(" << p.first << "," << p.second << ") ";
    }
    cout << endl;
    // (1,2) (1,3) (2,1)  按字典序排列

    // pair 的常见用途：存储边（图论）
    vector<pair<int, int>> edges;
    edges.push_back({1, 2});
    edges.push_back({2, 3});
    edges.push_back({1, 3});

    // pair 的常见用途：带权值的点
    // 例如 BFS 中 {距离, 节点编号}
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 1});  // 距离 0，节点 1

    return 0;
}

2.7.2 tuple — 多元组

当需要存储 3 个或更多值时，使用 tuple。

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

int main() {
    // 创建 tuple
    tuple<int, string, double> t = {1, "Alice", 3.14};

    // 访问元素（用 get）
    cout << get<0>(t) << endl;  // 1
    cout << get<1>(t) << endl;  // Alice
    cout << get<2>(t) << endl;  // 3.14

    // C++17 结构化绑定
    auto [id, name, val] = t;
    cout << id << " " << name << " " << val << endl;

    // make_tuple
    auto t2 = make_tuple(2, "Bob", 2.72);

    // tie 解包
    int a;
    string b;
    double c;
    tie(a, b, c) = t;
    cout << a << " " << b << " " << c << endl;

    // 比较（和 pair 类似，按元素顺序逐个比较）
    auto t3 = make_tuple(1, "Alice", 3.0);
    auto t4 = make_tuple(1, "Alice", 4.0);
    if (t3 < t4) {
        cout << "t3 < t4" << endl;  // 第三个元素 3.0 < 4.0
    }

    // 竞赛中的常见用途：存储多维信息
    // 例如：{权重, 起点, 终点}
    vector<tuple<int, int, int>> graph;
    graph.push_back({5, 1, 2});
    graph.push_back({3, 2, 3});
    graph.push_back({7, 1, 3});

    // 按权重排序
    sort(graph.begin(), graph.end());

    for (auto &[w, u, v] : graph) {
        cout << u << " -> " << v << " (weight: " << w << ")" << endl;
    }

    return 0;
}

2.7.3 bitset — 位集合

bitset 用于高效地进行位操作，在状态压缩 DP 中非常有用。

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

int main() {
    // 创建 bitset
    bitset<8> bs1;            // 8 位，初始为 0: 00000000
    bitset<8> bs2(42);        // 42 的二进制: 00101010
    bitset<8> bs3("1010");    // 从字符串: 00001010

    cout << bs2 << endl;  // 00101010

    // 访问和修改位
    bs1[2] = 1;           // 设置第 2 位
    bs1.set(5);            // 设置第 5 位
    bs1.reset(2);          // 清除第 2 位
    bs1.flip(0);           // 翻转第 0 位

    cout << bs1 << endl;  // 00100001

    // 常用操作
    cout << bs2.count() << endl;  // 3（1 的个数）
    cout << bs2.size() << endl;   // 8（总位数）
    cout << bs2.any() << endl;    // 1（是否有 1）
    cout << bs2.none() << endl;   // 0（是否全为 0）
    cout << bs2.all() << endl;    // 0（是否全为 1）

    // 位运算
    bitset<8> a("11001010");
    bitset<8> b("10101100");
    cout << (a & b) << endl;  // AND: 10001000
    cout << (a | b) << endl;  // OR:  11101110
    cout << (a ^ b) << endl;  // XOR: 01100110
    cout << (~a) << endl;     // NOT: 00110101

    // 转换为数值
    cout << bs2.to_ulong() << endl;   // 42
    cout << bs2.to_string() << endl;  // "00101010"

    // ---- 竞赛中的应用：状态压缩 ----
    // 例：用 bitset 表示集合 {0, 2, 5}
    bitset<10> state;
    state[0] = 1;
    state[2] = 1;
    state[5] = 1;
    cout << "集合: " << state << endl;  // 0000100101

    // 枚举 state 的所有非空子集（位掩码枚举）
    // bitset 不支持减法，先用 to_ulong() 转成整数再枚举
    int st = (int)state.to_ulong();  // {0, 2, 5} -> 0000100101 = 37
    for (int s = st; s; s = (s - 1) & st) {
        cout << bitset<10>(s) << endl;
    }
    // s = (s - 1) & st 会从大到小、不重不漏地枚举所有非空子集（空集不进循环）：
    // 0000100101  0000100100  0000100001  0000100000
    // 0000000101  0000000100  0000000001  （共 2^3 - 1 = 7 个）

    return 0;
}

bitset 在竞赛中的用途

• 状态压缩：用一个整数表示一个集合
• 高效位运算：比直接用 int 更安全（不会溢出）
• 大集合操作：bitset<10000> 只需约 1.25KB 内存
• 筛素数：埃氏筛用 bitset 可以省内存

2.7.4 pb_ds 扩展（选学）

set 有一个天生的短板：它没法在 O(log n) 内回答"x 排第几"和"第 k 小是谁"。GNU 编译器自带的扩展库 pb_ds（Policy-Based Data Structures）中的 __gnu_pbds::tree 补上了这块——它用起来和 set 几乎一样，但额外支持两个"名次树"操作：

• order_of_key(x)：返回严格小于 x 的元素个数（即 x 的排名减 1）
• find_by_order(k)：返回第 k 小元素的迭代器（k 从 0 开始）

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>  // pb_ds 容器
#include <ext/pb_ds/tree_policy.hpp>      // 名次树策略
using namespace std;
using namespace __gnu_pbds;

// 名次树：用法和 set 一样，额外支持按排名查询
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update> ordered_set;

int main() {
    ordered_set s;
    for (int x : {10, 30, 20, 50, 40}) s.insert(x);
    cout << s.order_of_key(30) << endl;   // 严格小于 30 的个数: 2（30 排名第 3）
    cout << *s.find_by_order(0) << endl;  // 第 1 小（下标从 0 开始）: 10
    cout << *s.find_by_order(4) << endl;  // 第 5 小: 50
    return 0;
}

复杂度：底层是红黑树，insert / erase / order_of_key / find_by_order 全部 O(log n)。

例题：洛谷 P3369【模板】普通平衡树

题意：维护一个可重集合，支持 6 种操作（n ≤ 10^5）：插入 x、删除一个 x、查询 x 的排名、查询排名为 x 的数、求 x 的前驱、求 x 的后继。

tree 和 set 一样会去重，处理重复值的标准技巧是存 pair<值, 插入时间戳>：

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// 第二关键字用"插入时间戳"区分重复值
typedef tree<pair<int, int>, null_type, less<pair<int, int>>,
             rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ordered_set t;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int op, x;
        cin >> op >> x;
        if (op == 1) t.insert({x, i});                    // 插入 x
        else if (op == 2) t.erase(t.lower_bound({x, 0})); // 删除一个 x
        else if (op == 3)                                 // x 的排名
            cout << t.order_of_key({x, 0}) + 1 << "\n";
        else if (op == 4)                                 // 排名为 x 的数
            cout << t.find_by_order(x - 1)->first << "\n";
        else if (op == 5)                                 // x 的前驱（小于 x 的最大数）
            cout << t.find_by_order(t.order_of_key({x, 0}) - 1)->first << "\n";
        else                                              // x 的后继（大于 x 的最小数）
            cout << t.find_by_order(t.order_of_key({x + 1, 0}))->first << "\n";
    }
    return 0;
}

总复杂度 O(n log n)，代替手写平衡树，是 pb_ds 在竞赛中最经典的用法。

pb_ds 的常见坑

• 仅 GNU G++ 可用：Codeforces、洛谷、AtCoder 等主流 OJ 的 GCC 环境都支持，但 clang（macOS 默认编译器）和 MSVC 编译不过。本地是 Mac 的同学需要另装 GCC 或只在 OJ 上测试。
• tree 默认去重：和 set 一样，相同的值只保留一个。需要可重集合时用上面的 pair<值, 时间戳> 技巧。网上流传的把 less 换成 less_equal 的写法会让 erase(值) 失效，不推荐。
• find_by_order(k) 的 k 从 0 开始；k 越界时返回 end()，解引用前要确认存在。
• order_of_key 统计的是严格小于的个数，求排名要 +1。

---

2.8 竞赛模板汇总

2.8.1 快读快写模板

#include <cstdio>
using namespace std;

// 快速读入（处理大数据量时使用）
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * f;
}

inline long long readll() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * f;
}

// 快速输出
inline void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

inline void writeln(int x) {
    write(x);
    putchar('\n');
}

2.8.2 常用宏定义合集

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

// ---- 类型别名 ----
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;

// ---- 常用宏 ----
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

// ---- 调试宏（本地调试用，提交时注释掉）----
#define dbg(x) cerr << #x << " = " << (x) << endl
#define dbg2(x, y) cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << endl

// ---- 常用常量 ----
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const double eps = 1e-9;
const double PI = acos(-1.0);
const int dx[] = {0, 0, 1, -1};  // 方向数组：上下左右
const int dy[] = {1, -1, 0, 0};

// ---- 常用函数 ----
template<typename T> inline T mn(T x, T y) { return x < y ? x : y; }
template<typename T> inline T mx(T x, T y) { return x > y ? x : y; }
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lcm(T a, T b) { return a / gcd(a, b) * b; }

// 快速幂
ll qpow(ll base, ll exp, ll mod) {
    ll res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

2.8.3 完整竞赛模板

/*
 * ACM 竞赛完整模板
 * 使用方法：复制此模板，在 solve() 函数中写解题逻辑
 */
#include <bits/stdc++.h>
using namespace std;

// ===== 类型别名 =====
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

// ===== 宏定义 =====
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define dbg(x) cerr << #x << " = " << (x) << endl

// ===== 常量 =====
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1e9 + 7;
const double eps = 1e-9;
const int MAXN = 1e6 + 5;

// ===== I/O 优化 =====
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

// ===== 解题函数 =====
void solve() {
    // 在这里写你的解题逻辑
    int n;
    cin >> n;

    // 示例：读入数组
    vi a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 示例：排序
    sort(all(a));

    // 示例：输出
    for (int i = 0; i < n; i++) {
        cout << a[i] << " \n"[i == n - 1];
    }
}

// ===== 主函数 =====
int main() {
    fast_io();

    int t = 1;
    // cin >> t;  // 多组测试数据时取消注释
    while (t--) {
        solve();
    }

    return 0;
}

使用模板的注意事项

1. fast_io() 开启后不要混用 cin/cout 和 scanf/printf
2. MAXN 的大小根据题目要求调整
3. 多组测试数据时记得初始化（清空数组、重置变量等）
4. 提交前删除调试用的 dbg 输出

---

STL 使用场景总结

问题类型	推荐容器/算法
需要动态数组	vector
需要快速查找（有序）	set / map
需要快速查找（无序）	unordered_set / unordered_map
需要排序	sort
需要取最大/最小	priority_queue 或 *max_element
需要 BFS	queue
需要 DFS	stack（或递归）
需要去重	set 或 sort + unique
需要二分查找	lower_bound / upper_bound
需要第 k 大/小	nth_element
需要全排列	next_permutation
需要存储键值对	map 或 pair
需要统计频率	map<T, int>
需要位运算	bitset

---

本章练习

• 用 vector 实现一个简单的栈
• 用 map 统计一段文本中每个单词出现的次数
• 用 set 对一组整数去重并排序
• 用 priority_queue 求一组数中第 k 大的数
• 用 sort + 自定义比较函数对学生按成绩排序
• 用 lower_bound 在有序数组中查找某个值
• 用 next_permutation 输出 {1, 2, 3, 4} 的所有排列
• 用 bitset 实现一个简单的埃氏筛求素数
• 整理自己的 STL 使用笔记，记录每种容器的时间复杂度

---

参考

• OI-Wiki - STL 容器
• OI-Wiki - STL 算法
• 代码随想录 - STL 详解
• CppReference - STL