07 STL 标准模板库容器

GESP 6-7 级CSP-J 高频CSP-S

级别标注：GESP 6 级（stack/queue 对应栈·队列考点）/ 7 级（哈希容器对应哈希表考点）（考级要求）/ 主体属 CSP-J 高频竞赛范围（竞赛进阶：vector/string/set/map/stack/queue/priority_queue/algorithm 全掌握）。

STL（Standard Template Library）是 C++ 标准库，提供通用容器、迭代器和算法，极大提高开发效率。竞赛中"会用手写数据结构是基本功，会用 STL 是效率"。

一、vector（动态数组）

自动扩容的数组，下标访问 O(1)。

C++ 实例

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;              // 动态数组：长度可自动增长
    v.push_back(3);             // 尾部插入元素
    v.push_back(1);
    v.push_back(4);
    cout << "size = " << v.size() << endl;   // 元素个数 3
    cout << "v[0] = " << v[0] << endl;       // 下标访问，同数组
    v.pop_back();               // 尾部删除一个元素
    cout << "尾部元素: " << v.back() << endl; // 1

    // 两种遍历方式：下标循环 / 范围 for
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << " ";
    cout << endl;
    for (int x : v) cout << x << " ";        // 范围 for（C++11+）
    cout << endl;

    // 清空、判空
    v.clear();                  // 清空所有元素
    cout << "empty? " << v.empty() << endl;  // 1（空为真）

    // 二维 vector：类似动态二维数组（3 行 4 列全 0）
    vector<vector<int>> grid(3, vector<int>(4, 0));
    return 0;
}

常见坑：遍历时用 i < v.size() 会因 size() 返回 size_t（无符号）在 v.size()==0 时产生巨大值，建议 (int)v.size() 显式转换或使用 size_t。

形象理解vector 像会自动变大的书柜：书放满了就自动换更大的柜子并把书搬过去（扩容），平时不用关心容量。尾部放书 push_back 很快，但从中间插书要“挪书”，较慢。

易错点v.size() 返回 size_t（无符号）：for (int i = 0; i < v.size(); i++) 在 v 为空时，v.size()==0 本身没问题，但一旦写成 i <= v.size()-1，v.size()-1 会变成巨大正数，循环直接越界——推荐写 (int)v.size() 或范围 for。

二、string（见 03 章，此处补充容器视角）

string 本质是 vector<char> 的增强版，支持 +、比较、substr 等。

三、set（有序集合，自动去重 + 排序）

基于红黑树，插入/删除/查找均为 O(log n)。

C++ 实例

#include <iostream>
#include <set>
using namespace std;
int main() {
    set<int> s;                 // 集合：自动去重 + 自动升序（红黑树）
    s.insert(5);
    s.insert(3);
    s.insert(5);                // 重复插入无效（已存在）
    s.insert(8);
    cout << "size = " << s.size() << endl;      // 3（5 只算一次）
    for (int x : s) cout << x << " ";           // 遍历即升序 3 5 8
    cout << endl;

    // 查找
    auto it = s.find(5);        // 返回迭代器
    if (it != s.end()) cout << "5 在集合中" << endl;
    if (s.count(5)) cout << "count() 也能判断存在" << endl;  // 存在返回 1

    // 删除
    s.erase(3);

    // 最小值/最大值
    cout << "最小: " << *s.begin() << "  最大: " << *s.rbegin() << endl;
    return 0;
}

multiset 允许重复元素；unordered_set 哈希实现，O(1) 平均，无序。

形象理解set 像自动整理的收藏夹：往里塞重复的卡片会被自动忽略（去重），而且永远按升序排好（红黑树）。查一张卡在不在，翻 log(n) 次就能确认。

考级视角“去重 + 排序 + 查存在”三合一场景优先 set。注意复杂度：插入/查找 O(log n)，笔试常考它与数组/哈希的复杂度对比；unordered_set 平均 O(1) 但无序。

四、map（键值对映射，自动按 key 排序）

C++ 实例

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
    map<string, int> score;     // 键值对映射：key → value（按 key 升序）
    score["Alice"] = 95;        // 键不存在时自动创建并赋值
    score["Bob"] = 88;
    score["Alice"] += 3;        // 修改已有键的值 → 98

    cout << "Alice = " << score["Alice"] << endl;  // 98
    // 注意：用 [] 访问不存在的键（如 score["Cathy"]）会插入默认值 0，容易踩坑

    if (score.count("Bob")) cout << "Bob 存在" << endl;   // count 判断键是否存在

    // 遍历：kv.first 是键，kv.second 是值
    for (auto &kv : score) {
        cout << kv.first << " : " << kv.second << endl;
    }

    // map 统计频率是竞赛经典用法
    map<int, int> freq;
    int arr[] = {3, 1, 2, 3, 3};
    for (int v : arr) freq[v]++;   // 等价 freq[v] = freq[v] + 1
    cout << "3 出现 " << freq[3] << " 次" << endl;
    return 0;
}

map 高频用途：统计出现次数（频次表）、把一类对象映射到 id、图的邻接表（与 vector 结合）。

形象理解map 像班级点名册：姓名（key）对应成绩（value）。score["Alice"] = 95 就是“记下 Alice 考了 95”。点名册自动按姓名排序，翻起来方便。

易错点用 [] 访问不存在的 key 会自动插入默认值（int 插 0）——查存在性请用 count() 或 find()。用 freq[v]++ 统计频次是正确用法（就是要插入）。

五、stack（栈，LIFO 后进先出）

C++ 实例

#include <iostream>
#include <stack>
using namespace std;
int main() {
    stack<int> st;              // 栈：后进先出（像叠盘子）
    st.push(1);                 // 入栈
    st.push(2);
    st.push(3);
    cout << "栈顶: " << st.top() << endl;   // 3（只看不弹）
    st.pop();                                // 弹出栈顶 3
    cout << "栈顶: " << st.top() << endl;   // 2
    cout << "空? " << st.empty() << "  大小: " << st.size() << endl;
    return 0;
}

经典应用：括号匹配、表达式求值、逆波兰、DFS（递归本质是栈）、单调栈。

形象理解栈像一叠盘子：后放的盘子在最上面，先拿走的也是它（后进先出）。只能从顶端放取，不能从中间抽。

考级视角递归的底层实现就是栈（调用栈）：每次函数调用压栈、返回出栈。GESP 6 级要求会用数组模拟栈，记住 top = -1 表示空，st[++top] 入栈、top-- 出栈。

六、queue（队列，FIFO 先进先出）

C++ 实例

#include <iostream>
#include <queue>
using namespace std;
int main() {
    queue<int> q;               // 队列：先进先出（像食堂排队）
    q.push(1);                  // 入队（队尾）
    q.push(2);
    q.push(3);
    cout << "队首: " << q.front() << " 队尾: " << q.back() << endl; // 1 3
    q.pop();                    // 出队（弹队首 1）
    cout << "队首: " << q.front() << endl;   // 2
    cout << "空? " << q.empty() << " 大小: " << q.size() << endl;
    return 0;
}

经典应用：BFS（广度优先搜索）、拓扑排序、约瑟夫环。

形象理解队列像食堂排队打饭：先来的先打饭（先进先出），后来的排后面。只能从队尾进、队首出。

考级视角BFS（广度优先搜索）就是靠队列实现的“逐层扩散”。GESP 6 级考数组模拟队列：[head, tail) 左闭右开，head==tail 为空。

七、deque（双端队列）

C++ 实例

#include <iostream>
#include <deque>
using namespace std;
int main() {
    deque<int> dq;              // 双端队列：头尾都能进出
    dq.push_back(1);            // 尾部插入
    dq.push_front(0);           // 头部插入
    dq.push_back(2);
    cout << dq.front() << " " << dq.back() << endl;  // 0 2
    dq.pop_front();             // 弹头部
    dq.pop_back();              // 弹尾部
    cout << dq.front() << endl;  // 1
    return 0;
}

用途：滑动窗口/单调队列（O(n) 求区间最值）、BFS 双端处理边权 0/1。

形象理解deque 像两头都能开的通道：前后都能进出，适合“滑动窗口”这种同时从两端操作的场景。

易错点单调队列里存的是下标不是值，判断过期元素用 dq.front() <= i - k 才能准确弹出窗口外的元素。存值会导致窗口边界判断困难。

八、priority_queue（优先队列/堆）

默认大根堆（队首最大）；小根堆写法 priority_queue<int, vector<int>, greater<int>>。

C++ 实例

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
    priority_queue<int> pq;               // 优先队列（默认大根堆：top 最大）
    pq.push(5);
    pq.push(1);
    pq.push(9);
    cout << "最大值: " << pq.top() << endl;  // 9
    pq.pop();                               // 弹出最大值 9
    cout << "最大值: " << pq.top() << endl;  // 5

    // 小根堆：top 最小，模板参数为 greater<int>
    priority_queue<int, vector<int>, greater<int>> pq2;
    pq2.push(5); pq2.push(1); pq2.push(9);
    cout << "最小值: " << pq2.top() << endl;  // 1
    return 0;
}

经典应用：堆排序、Huffman 编码、Dijkstra 最短路、合并果子（哈夫曼）。"合并果子"：每次取两堆最小合并，用到小根堆。

合并果子示例（贪心 + 小根堆）

C++ 实例

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
    int n; cin >> n;
    priority_queue<int, vector<int>, greater<int>> h;  // 小根堆
    for (int i = 0; i < n; i++) { int x; cin >> x; h.push(x); }
    long long ans = 0;        // 总代价可能很大，用 long long
    // 哈夫曼思想：每次取两堆最小的合并（贪心）
    while (h.size() > 1) {
        int a = h.top(); h.pop();   // 最小的一堆
        int b = h.top(); h.pop();   // 第二小的一堆
        ans += a + b;               // 合并代价累加
        h.push(a + b);              // 合并后的新堆入堆
    }
    cout << ans << endl;   // 最小体力/总代价
    return 0;
}

形象理解优先队列像自动按轻重排序的货架：push 任意重量，top() 永远给你最重（大根堆）或最轻（小根堆）的那个，不用自己维护顺序。

考级视角“合并果子”是 GESP/CSP 经典题：每次合并两堆最轻的果子，体力最少。用小根堆（greater<int>）每次取两个最小值合并再放回。注意答案可能超 int，用 long long。

九、algorithm 常用函数

C++ 实例

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int a[5] = {3, 1, 4, 1, 5};
    sort(a, a + 5);                                  // 数组排序（默认升序）
    reverse(a, a + 5);                               // 反转区间

    vector<int> v = {3, 1, 4, 1, 5};
    sort(v.begin(), v.end());                        // vector 排序（迭代器区间）
    cout << "最大值: " << *max_element(v.begin(), v.end()) << endl;

    int cnt = count(v.begin(), v.end(), 1);          // 统计元素 1 出现次数
    cout << "1 出现 " << cnt << " 次" << endl;

    int sum = 0;
    for (int x : v) sum += x;                        // 求和（也可用 accumulate）
    cout << "和: " << sum << endl;

    // 去重两件套：必须先排序，unique 把重复元素移到末尾，erase 删掉
    auto last = unique(v.begin(), v.end());
    v.erase(last, v.end());
    for (int x : v) cout << x << " ";
    cout << endl;
    return 0;
}

unique 去重模板（必记）：

C++ 实例

sort(v.begin(), v.end());                              // 1) 排序（unique 只去相邻重复）
v.erase(unique(v.begin(), v.end()), v.end());        // 2) unique 去重 + erase 删尾部

形象理解algorithm 像万能工具箱：sort 排序、reverse 反转、max_element 找最大、count 计数，一把起子一个用途，记住名字就能用。

易错点unique 只去相邻重复，用之前必须 sort。标准去重模板 v.erase(unique(v.begin(), v.end()), v.end()) 背下来，笔试填空和赛场手写都用得上。

十、易错点 / 常见坑点

⚠️ v.size() 是 size_t 无符号，for (int i=0; i<v.size(); i++) 当 v 为空会越界循环 → 转 (int) 或用 size_t。
⚠️ iterator 失效：vector 增删会使已有迭代器失效，遍历删除要小心（用 erase 的返回值）。
⚠️ 访问 map 不存在的 key（用 []）会自动插入默认值；判断存在用 count 或 find。
⚠️ priority_queue 默认是大根堆，取最小值要用 greater<>。
⚠️ 结构体要进 priority_queue/set 需提供比较规则（operator< 或自定义比较器）。
⚠️ unique 只去"相邻重复"，务必先 sort。
⚠️ endl 会刷新缓冲区较慢，多输出建议用 '\n'（性能优化见 19 章）。

十一、考级要求 vs 竞赛进阶

考级要求：stack/queue 容器与原理（GESP 6 级），哈希类容器（unordered_map/unordered_set，GESP 7 级）；vector/string/set/map 等主体属 CSP-J 竞赛范围。部分考级要求能手动实现栈/队列，STL 作为辅助。
竞赛进阶（CSP-J/NOIP）：全套 STL 熟练运用是时间优势的重要来源；priority_queue 与 map 是高频得分点；要求理解"STL 背后即手写结构"，遇到自定义需求能改比较器。

十二、课内练习建议

用 vector 读入 n 个数并统计、排序、去重。
用 map 统计一段文本中每个单词出现次数。
用 stack 判断括号序列是否匹配。
实现"合并果子"最小体力问题（优先队列）。
用 vector 存储并遍历图（邻接表，为 11 章打基础）。