从入门到实战

适用：GESP 四级～五级，兼顾六级

课时：90～120 分钟

主讲：______

---

• 课题：C++ STL 标准模板库入门与实战
• 适用：GESP 四级～五级，兼顾六级
• 课时：90～120 分钟，可拆两讲
• 教学目标

1. 理解 STL 的容器、迭代器、算法三大核心。

2. 掌握常用容器的声明、操作、遍历、复杂度和适用场景。

3. 能用 STL 解决排序、去重、括号匹配、单词统计、滑动窗口等问题。

4. 了解迭代器失效、map[] 插入、priority_queue 默认大根堆等易错点。

---

问题1：输入很多个数，但不知道个数，怎么存？

问题2：如何统计一篇文章中每个单词出现次数？

问题3：如何判断括号是否匹配？

问题4：如何每次快速取出当前最大值？

引出：这些都可以用 STL 容器高效解决。

---

手写栈

int st[100005], top = 0;
void push(int x) { st[++top] = x; }
void pop() { top--; }
int getTop() { return st[top]; }

STL 栈

stack<int> st;
st.push(x);
st.pop();
int t = st.top();

结论：STL 已经帮你写好了，而且更安全、更简洁。

---

STL = Standard Template Library，标准模板库。

本课主线：容器 → 存数据；迭代器 → 访问数据；算法 → 处理数据。

---

STL 容器
├── 序列式容器
│   ├── vector      动态数组
│   ├── deque       双端队列
│   └── string      字符串
│
├── 容器适配器
│   ├── stack           栈
│   ├── queue           队列
│   └── priority_queue  优先队列
│
└── 关联式容器
    ├── set / multiset
    ├── map / multimap
    └── unordered_set / unordered_map

本讲先学：vector、string、pair、stack、queue、deque、priority_queue、set、map、unordered_*。

---

一句话：vector 是最常用的动态数组。

特点

• 连续内存
• 支持下标访问
• 大小可变
• 尾部插入删除快
• 中间插入删除慢
• 不自动排序
• 允许重复元素

考点标注：【GESP 五级～六级｜CSP-J 核心】

头文件：#include <vector>

典型场景：存未知个数的数据、排序、二维数组、邻接表。

---

vector<int> a;                 // 空
vector<int> b(5);              // 5 个 0
vector<int> c(5, 3);           // 5 个 3
vector<int> d = {1, 2, 3};     // 1 2 3

vector<vector<int>> g(n, vector<int>(m)); // n 行 m 列

注意：vector<int> v(5); 不是容量为 5，而是有 5 个元素。

考点标注：【GESP 五级｜CSP-J 核心】

---

vector<int> v;
v.push_back(3);
v.push_back(1);
v.push_back(2);

cout << v.size() << endl; // 3
cout << v.front() << endl; // 3
cout << v.back() << endl;  // 2

v.pop_back();
cout << v.size() << endl; // 2

考点标注：【GESP 五级～六级｜CSP-J 核心】

---

方式1：下标遍历

for (int i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
}

方式2：迭代器遍历

for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    cout << *it << " ";
}

方式3：范围 for

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

方式4：auto 简化

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

考点标注：【GESP 五级～六级｜CSP-J 核心】

---

结论：适合频繁尾部插入、随机访问；不适合频繁中间插入删除。

考点标注：【GESP 六级｜CSP-J 核心】

---

操作序列：push(1) → push(2) → push(3) → push(4) → push(5)

详细分步脚本

1. 初始：v = []，size = 0，capacity = 0。
2. push(1)：容量不足，申请 capacity = 1，放入 1。

v = [1]，size = 1，capacity = 1。

1. push(2)：容量不足，申请 capacity = 2，复制旧元素 1，再放入 2。

v = [1, 2]，size = 2，capacity = 2。

1. push(3)：容量不足，申请 capacity = 4，复制旧元素 1、2，再放入 3。

v = [1, 2, 3]，size = 3，capacity = 4。

1. push(4)：容量足够，直接放入 4。

v = [1, 2, 3, 4]，size = 4，capacity = 4。

1. push(5)：容量不足，申请 capacity = 8，复制旧元素 1、2、3、4，再放入 5。

v = [1, 2, 3, 4, 5]，size = 5，capacity = 8。

观察点：容量按 1→2→4→8 增长；扩容时复制旧元素；扩容后原迭代器可能失效。

考点标注：【GESP 六级｜CSP-S 可能涉及】

---

题目：输入 n 个整数，从小到大排序后输出。

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

int main() {
    int n;
    cin >> n;

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

    sort(a.begin(), a.end());

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

    return 0;
}

逐行讲解：vector<int> a; 定义动态数组；a.push_back(x); 尾部插入；sort(a.begin(), a.end()); 排序；for (int x : a) 范围 for 遍历。

复杂度：O(n log n)

考点标注：【GESP 五级｜CSP-J 核心】

---

易错1：size() 是无符号数

for (int i = 0; i < v.size(); i++) // 可能有警告
// 建议
for (int i = 0; i < (int)v.size(); i++)

易错2：扩容后迭代器失效

auto it = v.begin();
v.push_back(1);
// it 可能失效

易错3：reserve 和 resize 不同

v.reserve(100); // 容量变成 100，但 size 还是 0
v.resize(100);  // size 变成 100

易错4：[] 不检查越界

cout << v[100]; // 危险

考点标注：【GESP 六级｜CSP-J 常见坑】

---

一句话：专门处理字符串的容器，本质类似 vector<char>，但封装了大量字符串函数。

头文件：#include <string>

string s = "hello";
cout << s.size() << endl;        // 5
cout << s.substr(1, 3) << endl;  // "ell"
cout << s.find("ll") << endl;    // 2
s += " world";
cout << s << endl;               // "hello world"

考点标注：【GESP 四级引入，五级深化｜CSP-J 核心】

---

遍历方式：下标、迭代器、范围 for。

复杂度

• 随机访问 O(1)
• 尾部追加均摊 O(1)
• substr O(len)
• find 通常 O(n*m)

易错点

• cin >> s 遇空格停止。
• 读整行要用 getline(cin, s)。
• s[i] 不检查越界。

动画演示：字符数组与字符串关系；substr 截取范围。

代码讲解：统计字符串长度、查找子串位置、字符串反转。

考点标注：【GESP 四级～五级｜CSP-J 核心】

---

一句话：把两个数据打包成一个整体。

头文件：#include <utility>（通常被其他头文件间接包含）

pair<int, int> p;
pair<int, string> p2 = {1, "Tom"};
auto p3 = make_pair(3, 4);

核心操作：p.first、p.second；比较时先比 first，再比 second。

典型应用：成绩排序、map 元素类型、存坐标。

易错点：pair 比较规则可能和题目要求不一致，需要自定义排序时写比较函数。

vector<pair<int, string>> v;
v.push_back({90, "Tom"});
v.push_back({95, "Jerry"});
sort(v.begin(), v.end(), greater<>());

考点标注：【GESP 五级｜CSP-J 核心 / CSP-S 明确要求】

---

一句话：栈是后进先出 LIFO 的容器。

push →  [ 3 ]
        [ 2 ]
        [ 1 ]
        栈底

特点：只能从栈顶插入和删除；不支持下标访问；不支持迭代器遍历。

头文件：#include <stack>

典型场景：括号匹配、表达式求值、十进制转二进制、DFS 非递归。

考点标注：【GESP 五级初步，六级深化｜CSP-J 核心】

---

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

复杂度：入栈、出栈、取栈顶均为 O(1)。

考点标注：【GESP 五级～六级｜CSP-J 核心】

---

操作序列：push(1) → push(2) → push(3) → pop() → push(4) → pop() → pop()

详细分步脚本

1. 初始：栈为空，st = []。
2. push(1)：1 入栈。st = [1]，栈顶为 1。
3. push(2)：2 入栈。st = [1, 2]，栈顶为 2。
4. push(3)：3 入栈。st = [1, 2, 3]，栈顶为 3。
5. pop()：删除栈顶 3。st = [1, 2]，栈顶为 2。
6. push(4)：4 入栈。st = [1, 2, 4]，栈顶为 4。
7. pop()：删除栈顶 4。st = [1, 2]，栈顶为 2。
8. pop()：删除栈顶 2。st = [1]，栈顶为 1。

观察点：每次只能操作栈顶；后进先出。

考点标注：【GESP 五级｜CSP-J 核心】

---

题目：给定一个只包含 ()、[]、{} 的字符串，判断括号是否匹配。

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

int main() {
    string s;
    cin >> s;

    stack<char> st;
    bool ok = true;

    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) { ok = false; break; }
            char t = st.top(); st.pop();
            if (c == ')' && t != '(') ok = false;
            if (c == ']' && t != '[') ok = false;
            if (c == '}' && t != '{') ok = false;
        }
    }

    if (!st.empty()) ok = false;
    cout << (ok ? "YES" : "NO") << endl;
    return 0;
}

思路：左括号入栈；右括号找栈顶匹配；最后栈必须为空。

复杂度：O(n)

考点标注：【GESP 五级｜CSP-J 核心】

---

易错1：pop() 不返回元素

int x = st.pop(); // 错误
// 正确
int x = st.top();
st.pop();

易错2：空栈取栈顶

if (!st.empty()) {
    cout << st.top();
}

易错3：不能遍历

for (auto x : st) // 错误

栈只能不断 top() + pop()。

考点标注：【GESP 五级｜CSP-J 常见坑】

---

一句话：队列是先进先出 FIFO 的容器。

出队 ← [1] [2] [3] ← 入队
       队首      队尾

头文件：#include <queue>

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

复杂度：入队、出队、访问队首队尾均为 O(1)。

考点标注：【GESP 五级初步，六级深化｜CSP-J 核心】

---

操作序列：push(1) → push(2) → push(3) → pop() → push(4) → pop()

详细分步脚本

1. 初始：队列为空，q = []。
2. push(1)：1 从队尾入队。q = [1]，队首 1，队尾 1。
3. push(2)：2 从队尾入队。q = [1, 2]，队首 1，队尾 2。
4. push(3)：3 从队尾入队。q = [1, 2, 3]，队首 1，队尾 3。
5. pop()：队首 1 出队。q = [2, 3]，队首 2，队尾 3。
6. push(4)：4 从队尾入队。q = [2, 3, 4]，队首 2，队尾 4。
7. pop()：队首 2 出队。q = [3, 4]，队首 3，队尾 4。

观察点：队尾进，队首出；先进先出。

考点标注：【GESP 五级｜CSP-J 核心】

---

题目：模拟食堂排队，输出每个人打饭顺序。

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

int main() {
    queue<string> q;
    q.push("Tom");
    q.push("Jerry");
    q.push("Alice");

    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    return 0;
}

输出：Tom Jerry Alice

思路：先来的人先入队；每次取队首，然后出队；直到队列为空。

考点标注：【GESP 五级｜CSP-J 核心】

---

一句话：两端都能高效插入删除的队列。

头文件：#include <deque>

deque<int> dq;
dq.push_back(2);
dq.push_front(1);
dq.push_back(3);

cout << dq.front() << endl; // 1
cout << dq.back() << endl;  // 3

dq.pop_front();
dq.pop_back();

复杂度：随机访问 O(1)，两端插入删除 O(1)，中间 O(n)。

典型应用：滑动窗口最大值。

考点标注：【GESP 涉及较少｜CSP-S 明确要求】

---

题目：数组 [1, 3, -1, -3, 5, 3, 6, 7]，窗口大小 k = 3。

操作序列：遍历数组，维护单调递减双端队列。

详细分步脚本

1. i=0, x=1：队列空，加入下标 0。dq = [0]，窗口未满。
2. i=1, x=3：3 > 1，弹出队尾 0，加入下标 1。dq = [1]。
3. i=2, x=-1：-1 < 3，加入下标 2。dq = [1, 2]。窗口满，输出 a[1]=3。
4. i=3, x=-3：-3 < -1，加入下标 3。检查队首下标 1 是否过期？1 <= 3-3=0？否。dq = [1, 2, 3]，输出 a[1]=3。
5. i=4, x=5：5 > -3，弹出 3；5 > -1，弹出 2；5 > 3，弹出 1；加入下标 4。dq = [4]，输出 a[4]=5。
6. i=5, x=3：3 < 5，加入下标 5。dq = [4, 5]，输出 a[4]=5。
7. i=6, x=6：6 > 3，弹出 5；6 > 5，弹出 4；加入下标 6。dq = [6]，输出 a[6]=6。
8. i=7, x=7：7 > 6，弹出 6；加入下标 7。dq = [7]，输出 a[7]=7。

输出：3 3 5 5 6 7

观察点：队列存下标；队首始终是窗口最大值；过期下标从队首弹出。

考点标注：【GESP 涉及较少｜CSP-S 明确要求】

---

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    deque<int> dq; // 存下标
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) cout << a[dq.front()] << " ";
    }
    return 0;
}

复杂度：O(n)

考点标注：【GESP 涉及较少｜CSP-S 明确要求】

---

一句话：优先队列会自动把最大或最小元素放在堆顶。

头文件：#include <queue>

priority_queue<int> pq; // 默认大根堆
pq.push(3); pq.push(1); pq.push(5);
cout << pq.top() << endl; // 5

priority_queue<int, vector<int>, greater<int>> pq2; // 小根堆
pq2.push(3); pq2.push(1); pq2.push(5);
cout << pq2.top() << endl; // 1

复杂度：top() O(1)，push() / pop() O(log n)。

考点标注：【GESP 五级～六级｜CSP-J 核心 / CSP-S 明确要求】

---

操作序列：push(3) → push(1) → push(5) → push(2) → pop()

详细分步脚本

1. 初始：堆为空。
2. push(3)：堆 [3]，堆顶 3。
3. push(1)：1 放入末尾，向上调整。

堆 [3, 1]，堆顶 3。

1. push(5)：5 放入末尾，向上调整。

5 与父节点 3 交换。堆 [5, 1, 3]，堆顶 5。

1. push(2)：2 放入末尾，向上调整。

2 与父节点 1 交换。堆 [5, 2, 3, 1]，堆顶 5。

1. pop()：删除堆顶 5。

末尾 1 移到堆顶，向下调整：1 与较大孩子 3 交换，再与 2 交换。

最终堆 [3, 2, 1]，堆顶 3。

观察点：堆顶始终最大；插入和删除后会自动调整；内部不是完全有序。

考点标注：【GESP 六级｜CSP-J 核心】

---

易错点

• 默认是大根堆，不是小根堆。
• 自定义结构体需要重载 < 或写比较器。
• pop() 不返回元素。

priority_queue<int> pq;
pq.push(10);
pq.push(5);
pq.push(20);

cout << pq.top() << endl; // 20
pq.pop();
cout << pq.top() << endl; // 10

考点标注：【GESP 五级～六级｜CSP-J 核心】

---

一句话：set 是有序、自动去重的集合；multiset 允许重复。

头文件：#include <set>

set<int> s;
multiset<int> ms;

特点

• 自动升序排列
• set 不允许重复，multiset 允许
• 插入、删除、查找 O(log n)
• 不支持下标访问
• 元素不可直接修改

典型场景：去重并排序、动态维护有序集合、查找前驱后继。

考点标注：【GESP 五级～六级｜CSP-J 核心 / CSP-S 明确要求 multiset】

---

set<int> s;
s.insert(3);
s.insert(1);
s.insert(2);
s.insert(3); // 重复，不插入

cout << s.size() << endl; // 3
if (s.find(2) != s.end()) cout << "2 存在";
s.erase(2);

for (int x : s) cout << x << " ";
// 输出：1 2 3

考点标注：【GESP 五级～六级｜CSP-J 核心】

---

操作序列：insert(3) → insert(1) → insert(2) → insert(3) → insert(5) → insert(1)

详细分步脚本

1. 初始：s = {}。
2. insert(3)：插入 3。s = {3}。
3. insert(1)：1 < 3，插入到左边。s = {1, 3}。
4. insert(2)：1 < 2 < 3，插入到中间。s = {1, 2, 3}。
5. insert(3)：3 已存在，不插入。s = {1, 2, 3}。
6. insert(5)：5 > 3，插入到右边。s = {1, 2, 3, 5}。
7. insert(1)：1 已存在，不插入。s = {1, 2, 3, 5}。

观察点：自动升序；重复元素被忽略；底层红黑树自动调整。

考点标注：【GESP 五级｜CSP-J 核心】

---

复杂度：插入、删除、查找均为 O(log n)；遍历 O(n)。

易错点

• 不能下标访问：cout << s[0]; 错误。
• erase(x) 删除所有等于 x 的元素；删一个要用迭代器。
• set 元素不可修改，需先删再插。

multiset<int> ms = {1, 1, 2, 3};
auto it = ms.find(1);
if (it != ms.end()) ms.erase(it); // 只删一个 1

考点标注：【GESP 六级｜CSP-J 常见坑 / CSP-S 注意 multiset】

---

一句话：map 是有序键值对容器，按 key 自动排序；multimap 允许重复 key。

头文件：#include <map>

map<string, int> mp;
multimap<int, string> mmp;

特点

• 每个元素是 pair<const Key, Value>
• 按 key 升序
• map 的 key 唯一，multimap 可重复
• 插入、删除、查找 O(log n)
• map 支持 mp[key]，multimap 不支持 []

典型场景：单词频率统计、姓名到成绩映射、有序字典。

考点标注：【GESP 五级～六级｜CSP-J 核心 / CSP-S 明确要求 multimap】

---

map<string, int> mp;
mp["apple"]++;
mp["apple"]++;
mp["banana"]++;

cout << mp["apple"] << endl;   // 2
cout << mp.size() << endl;     // 2
if (mp.count("cherry")) cout << "存在";

for (auto& [key, value] : mp) {
    cout << key << " " << value << endl;
}

考点标注：【GESP 五级～六级｜CSP-J 核心】

---

操作序列：mp["banana"]=2 → mp["apple"]=3 → mp["cherry"]=1 → mp["apple"]=5

详细分步脚本

1. 初始：mp = {}。
2. mp["banana"] = 2：插入键 banana，值 2。

mp = {banana: 2}。

1. mp["apple"] = 3：插入键 apple，值 3。

按 key 排序：apple < banana。

mp = {apple: 3, banana: 2}。

1. mp["cherry"] = 1：插入键 cherry，值 1。

按 key 排序：apple < banana < cherry。

mp = {apple: 3, banana: 2, cherry: 1}。

1. mp["apple"] = 5：键 apple 已存在，覆盖旧值。

mp = {apple: 5, banana: 2, cherry: 1}。

观察点：按 key 自动排序；key 重复时覆盖旧值；底层红黑树保持有序。

考点标注：【GESP 五级｜CSP-J 核心】

---

易错1：mp[key] 会插入默认值

map<string, int> mp;
cout << mp["hello"]; // 输出 0，但 mp 中插入了 hello
cout << mp.size();   // 1
// 只查不插：
if (mp.find("hello") != mp.end()) { ... }

易错2：map 的 key 不可修改

for (auto p : mp) p.first = "new"; // 错误

易错3：multimap 没有 []

multimap<int, string> mmp;
mmp[1] = "Tom"; // 错误

易错4：自定义类型作 key 需要比较器

struct Node { int x, y; };
map<Node, int> mp; // 需要重载 <

考点标注：【GESP 六级｜CSP-J 常见坑 / CSP-S 要求】

---

一句话：基于哈希表，平均 O(1) 查找，但不保证顺序。

#include <unordered_set>
#include <unordered_map>

unordered_set<int> us;
unordered_map<string, int> ump;
us.insert(3);
ump["apple"] = 2;

考点标注：【GESP 七级重点｜CSP-S 要求】

---

哈希函数：h(x) = x % 7

操作序列：insert(10) → insert(3) → insert(17) → insert(24)

详细分步脚本

1. 初始：7 个桶，全部为空。

桶下标：0 1 2 3 4 5 6。

1. insert(10)：计算 10 % 7 = 3，放入桶 3。

桶 3：10。

1. insert(3)：计算 3 % 7 = 3，放入桶 3。

发生哈希冲突，使用链表挂在后面。

桶 3：10 → 3。

1. insert(17)：计算 17 % 7 = 3，放入桶 3。

桶 3：10 → 3 → 17。

1. insert(24)：计算 24 % 7 = 3，放入桶 3。

桶 3：10 → 3 → 17 → 24。

观察点：哈希冲突；冲突严重时查找变慢；遍历顺序与插入顺序无关。

考点标注：【GESP 七级｜CSP-S 要求】

---

考点标注：【GESP 五级～七级｜CSP-J/S 综合】

---

• 需要下标访问？→ vector
• 需要尾部频繁插入删除？→ vector
• 需要后进先出？→ stack
• 需要先进先出？→ queue
• 需要两端插入删除？→ deque
• 需要动态取最大/最小？→ priority_queue
• 需要有序且去重？→ set
• 需要有序键值对？→ map
• 需要快速查找、不要求有序？→ unordered_set / unordered_map

考点标注：【GESP 五级～七级｜CSP-J/S 综合】

---

考点标注：【GESP 六级｜CSP-J 核心】

---

什么是迭代器：访问容器元素的“指针式工具”。

vector<int> v = {1, 2, 3};
auto it = v.begin(); // 指向 1
auto ie = v.end();   // 指向 3 后面，不是 3

for (auto it = v.begin(); it != v.end(); it++) {
    cout << *it << " ";
}

范围 for 的本质

for (int x : v) cout << x << " ";
// 等价于
for (auto it = v.begin(); it != v.end(); it++) {
    int x = *it;
    cout << x << " ";
}

考点标注：【GESP 五级～六级｜CSP-J 核心】

---

操作序列：vector<int> v = {1,2,3}; auto it = v.begin(); v.push_back(4);

详细分步脚本

1. 创建 v = {1, 2, 3}。

假设 capacity = 3，内存地址为 A。

1. it = v.begin()：it 指向地址 A 的第一个元素 1。
2. v.push_back(4)：容量不足，申请新内存地址 B，capacity 变为 6。

将 1、2、3 复制到 B，再放入 4。

v 的数据现在在地址 B。

1. 原来的 it 仍指向地址 A。

地址 A 已被释放，所以 it 失效。

继续使用 *it 会导致未定义行为。

观察点：vector 扩容后，所有指向旧内存的迭代器、指针、引用都会失效。

考点标注：【GESP 六级～七级｜CSP-S 要求】

---

迭代器失效

• vector 扩容后全部失效。
• vector 中间插入删除后部分失效。
• map / set 删除只影响被删元素。

考点标注：【GESP 六级～七级｜CSP-S 要求】

---

头文件：#include <algorithm>

考点标注：【GESP 五级～六级｜CSP-J 核心】

---

vector<int> v = {3, 1, 2};
sort(v.begin(), v.end()); // {1, 2, 3}
sort(v.begin(), v.end(), greater<int>()); // {3, 2, 1}

struct Student { string name; int score; };
bool cmp(const Student& a, const Student& b) {
    if (a.score != b.score) return a.score > b.score;
    return a.name < b.name;
}
sort(v.begin(), v.end(), cmp);

复杂度：O(n log n)

注意：比较器必须满足严格弱序，不能用 <=。

考点标注：【GESP 五级｜CSP-J 核心】

---

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

vector<int> v = {1, 1, 2, 2, 3, 3};
sort(v.begin(), v.end());
auto it = unique(v.begin(), v.end());
v.erase(it, v.end()); // {1, 2, 3}

unique 原理：把不重复元素移到前面；返回第一个重复位置；必须配合 sort 使用；本身不删除元素，需要 erase。

复杂度：O(n)

考点标注：【GESP 六级｜CSP-J 核心】

---

初始：v = {1, 1, 2, 2, 3, 3}

详细分步脚本

1. 排序后：v = {1, 1, 2, 2, 3, 3}。
2. 设置写指针 w = 1，读指针 r = 1。
3. r = 1，v[r] = 1，与 v[w-1] = 1 相同，跳过。
4. r = 2，v[r] = 2，与 v[w-1] = 1 不同，写入 v[w] = 2，w = 2。

v = {1, 2, 2, 2, 3, 3}。

1. r = 3，v[r] = 2，与 v[w-1] = 2 相同，跳过。
2. r = 4，v[r] = 3，与 v[w-1] = 2 不同，写入 v[w] = 3，w = 3。

v = {1, 2, 3, 2, 3, 3}。

1. r = 5，v[r] = 3，与 v[w-1] = 3 相同，跳过。
2. 返回迭代器指向下标 3。

v.erase(it, v.end()) 后：v = {1, 2, 3}。

观察点：unique 只移动元素，不真正删除；返回第一个无效位置；必须排序后才能去重。

考点标注：【GESP 六级｜CSP-J 核心】

---

数组：v = {1, 2, 2, 2, 3, 5}

查找：lower_bound(v.begin(), v.end(), 2)，即第一个 ≥ 2 的位置。

详细分步脚本

1. 左边界 L = 0，右边界 R = 6（end()）。
2. 中间 mid = (0+6)/2 = 3，v[3] = 2。

2 >= 2，记录答案 ans = 3，向右收缩 R = 3。

1. 中间 mid = (0+3)/2 = 1，v[1] = 2。

2 >= 2，记录答案 ans = 1，向右收缩 R = 1。

1. 中间 mid = (0+1)/2 = 0，v[0] = 1。

1 < 2，向左收缩 L = 1。

1. L == R，结束。返回 ans = 1，即下标 1。

upper_bound 类似：找第一个 > 2 的位置，最终返回下标 4。

观察点：必须有序；lower_bound 返回第一个 ≥ x；upper_bound 返回第一个 > x；找不到返回 end()。

考点标注：【GESP 五级～六级｜CSP-J 核心】

---

vector<int> v = {1, 2, 2, 2, 3, 5};
auto it1 = lower_bound(v.begin(), v.end(), 2); // 下标 1
auto it2 = upper_bound(v.begin(), v.end(), 2); // 下标 4
cout << it2 - it1 << endl; // 3，即 2 的个数

set<int> s = {1, 2, 3, 5};
auto it = s.lower_bound(2);
cout << *it << endl; // 2

复杂度：O(log n)

易错点：必须有序；set / map 用成员函数；找不到时返回 end()。

考点标注：【GESP 五级～六级｜CSP-J 核心】

---

vector<int> v = {1, 2, 3};
auto it = find(v.begin(), v.end(), 2);
if (it != v.end()) cout << "找到：" << *it << endl;

int c = count(v.begin(), v.end(), 2); // 1

auto itMax = max_element(v.begin(), v.end());
cout << *itMax << endl; // 3

auto itMin = min_element(v.begin(), v.end());
cout << *itMin << endl; // 1

复杂度：O(n)

注意：返回的是迭代器，不是值。

考点标注：【GESP 五级｜CSP-J 核心】

---

题目：输入 n 个学生的姓名和成绩，按成绩从高到低排序。成绩相同按姓名升序。

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

struct Student { string name; int score; };

bool cmp(const Student& a, const Student& b) {
    if (a.score != b.score) return a.score > b.score;
    return a.name < b.name;
}

int main() {
    int n; cin >> n;
    vector<Student> v(n);
    for (int i = 0; i < n; i++) cin >> v[i].name >> v[i].score;
    sort(v.begin(), v.end(), cmp);
    for (auto s : v) cout << s.name << " " << s.score << endl;
    return 0;
}

复杂度：O(n log n)

考点标注：【GESP 五级｜CSP-J 核心】

---

题目：输入 n 个整数，去重并从小到大排序。

方法1：set

set<int> s;
for (int i = 0; i < n; i++) { int x; cin >> x; s.insert(x); }
for (int x : s) cout << x << " ";

方法2：vector + sort + unique

vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
sort(v.begin(), v.end());
auto it = unique(v.begin(), v.end());
v.erase(it, v.end());
for (int x : v) cout << x << " ";

复杂度：O(n log n)

考点标注：【GESP 五级～六级｜CSP-J 核心】

---

题目：给定一个字符串，只包含 ()、[]、{}，判断是否匹配。

输入：([{}]) → 输出：YES

输入：([)] → 输出：NO

思路：左括号入栈；右括号与栈顶匹配；最后栈空则合法。

代码：见 stack 部分。

复杂度：O(n)

考点标注：【GESP 五级｜CSP-J 核心】

---

题目：输入若干单词，统计每个单词出现次数，按字典序输出。

map<string, int> mp;
string word;
while (cin >> word) mp[word]++;
for (auto& [key, value] : mp)
    cout << key << " " << value << endl;

复杂度：O(n log n)

考点标注：【GESP 五级｜CSP-J 核心】

---

题目：给定 n 个整数，求第 k 小元素。

方法1：set

set<int> s;
for (int i = 0; i < n; i++) { int x; cin >> x; s.insert(x); }
auto it = s.begin();
for (int i = 1; i < k; i++) it++;
cout << *it << endl;

方法2：vector + sort

sort(v.begin(), v.end());
cout << v[k - 1] << endl;

复杂度：O(n log n)

考点标注：【GESP 六级｜CSP-J 核心】

---

题目：给定数组和窗口大小 k，输出每个窗口的最大值。

核心STL：deque 或 priority_queue

代码：见 deque 部分。

复杂度：deque O(n)，priority_queue O(n log n)

考点标注：【GESP 涉及较少｜CSP-S 明确要求】

---

题目：给定 n 个整数和目标值 target，判断是否存在两个数之和为 target。

unordered_set<int> s;
for (int i = 0; i < n; i++) {
    int x; cin >> x;
    if (s.count(target - x)) { cout << "YES"; return 0; }
    s.insert(x);
}
cout << "NO";

复杂度：平均 O(n)

考点标注：【GESP 七级｜CSP-J 提高 / CSP-S 入门】

---

1. 关于 vector，下列说法正确的是？

A. 自动去重

B. 支持下标访问

C. 中间插入 O(1)

D. 不能排序

答案：B

2. stack 的特点是什么？

A. 先进先出

B. 后进先出

C. 自动排序

D. 支持下标访问

答案：B

3. queue 的插入和删除位置是？

A. 队首插入，队尾删除

B. 队尾插入，队首删除

C. 两端都可以插入删除

D. 随机位置

答案：B

4. priority_queue<int> 默认是什么堆？

A. 小根堆

B. 大根堆

C. 无序

D. 平衡树

答案：B

---

5. stack 的 pop() 返回值是什么？

A. 返回栈顶元素

B. 返回栈底元素

C. 不返回元素

D. 返回布尔值

答案：C

6. vector 扩容后，原来的迭代器可能？

A. 仍然有效

B. 失效

C. 自动更新

D. 变成常量

答案：B

7. 小根堆的正确写法是？

A. priority_queue<int> pq;

B. priority_queue<int, vector<int>, greater<int>> pq;

C. priority_queue<int, vector<int>, less<int>> pq;

D. queue<int> pq;

答案：B

8. 括号匹配最适合用哪个容器？

A. vector

B. stack

C. queue

D. priority_queue

答案：B

---

9. set 的特点是？

A. 允许重复，有序

B. 不允许重复，有序

C. 允许重复，无序

D. 不允许重复，无序

答案：B

10. map 的 key 是否可重复？

A. 可以

B. 不可以

C. 取决于编译器

D. 取决于值

答案：B

11. mp[key] 访问不存在的 key 会发生什么？

A. 报错

B. 返回 0，但不插入

C. 插入默认值并返回

D. 程序崩溃

答案：C

12. unique 使用前必须做什么？

A. 反转

B. 排序

C. 清空

D. 删除

答案：B

---

13. lower_bound(x) 返回什么？

A. 第一个 > x 的位置

B. 第一个 ≥ x 的位置

C. 最后一个 ≥ x 的位置

D. 最后一个 > x 的位置

答案：B

14. unordered_map 的底层结构是？

A. 红黑树

B. 哈希表

C. 数组

D. 链表

答案：B

15. set 能否用下标访问？

A. 能

B. 不能

C. 只能读

D. 只能写

答案：B

16. sort 默认排序顺序是？

A. 降序

B. 升序

C. 随机

D. 按输入顺序

答案：B

---

1. 数字重排最大数

输入一串数字字符，重新排列，使得到的整数最大，不能有前导零。

1. 明明的随机数

输入 n 个整数，去重并排序输出。

1. 括号匹配

判断只含 ()、[]、{} 的字符串是否匹配。

1. 成绩排序

输入 n 个学生姓名和成绩，按成绩从高到低排序。

1. 单词频率统计

输入若干单词，统计每个单词出现次数，按字典序输出。

---

1. 第 k 小元素

求第 k 小元素。

1. 滑动窗口最大值

用 deque 或 priority_queue 解决。

1. 集合操作模拟

实现插入、删除、查找、输出有序集合。

1. 学生信息管理

按成绩排序，成绩相同按姓名排序。

1. 两数之和

判断是否存在两个数之和为 target。

---

1. 动态中位数

用两个堆维护中位数。

1. 区间合并

用 map 或 set 合并重叠区间。

1. 哈希表去重与统计

用 unordered_map 完成频率统计与去重。

1. 自定义优先队列比较器

定义结构体，按自定义规则出队。

---

STL 三大核心：容器、迭代器、算法。

容器选择口诀

• 动态数组：vector
• 字符串：string
• 二元组：pair
• 栈：stack
• 队列：queue
• 双端队列：deque
• 堆：priority_queue
• 有序去重：set
• 键值映射：map
• 哈希快查：unordered_map

易错点回顾

• 迭代器失效
• unique 前需排序
• map[] 会插入
• priority_queue 默认大根堆
• stack / queue 的 pop() 不返回元素

答疑与练习