第 3 章：C++ STL —— 你的武器库

在算法竞赛中，STL 主要分为两大类：容器 (Containers) 和 算法 (Algorithms)。我们需要掌握的是其中最实用的部分。

3.1 Vector：变长数组

它是“数组”的升级版。你不需要预先知道要存多少个数，它会自动扩容。

头文件：#include <vector>
声明：vector<int> v; （定义一个存整数的空列表）
常用操作：
- v.push_back(x): 在尾部插入元素 x（ $O(1)$ ）。
- v.size(): 返回元素个数。
- v[i]: 像数组一样通过下标访问（ $O(1)$ ）。
- v.clear(): 清空数组。

🔥 竞赛实战技巧：

初始化：vector<int> v(n, 0); （定义一个长度为 n，初始值全为 0 的数组）。
遍历：现代 C++ 推荐使用 for (auto x : v) 遍历。
排序：sort(v.begin(), v.end());。

vector<int> v;
v.push_back(10);
v.push_back(5);
v.push_back(20);
 
// 排序后 v 变为 {5, 10, 20}
sort(v.begin(), v.end()); 
 
for(int x : v) cout << x << " "; // 输出 5 10 20

3.2 String：字符串神器

别再用 C 语言的 char s[100] 了，string 拥有动态长度和极其方便的拼接功能。

头文件：#include <string>
常用操作：
- s += 'a': 拼接字符或字符串。
- s.length() 或 s.size(): 获取长度。
- s.substr(pos, len): 截取子串，从下标 pos 开始截取 len 长度。
- s.find("abc"): 查找子串第一次出现的位置，找不到返回 string::npos。

🔥 竞赛实战技巧：字符串可以直接比大小（字典序），这在排序时非常有用。

string s = "hello";
s += " world"; // s 变为 "hello world"
cout << s.substr(0, 5); // 输出 "hello"

3.3 Set & Map：自动排序与查找

这两个容器的底层通常是红黑树，这意味着插入、删除、查找的复杂度都是 $O(\log N)$ （非常快）。

3.3.1 Set (集合)

它的特性是：自动去重 + 自动排序。如果你往 set 里丢进 3, 1, 3, 2，它会存成 {1, 2, 3}。

头文件：#include <set>
操作：s.insert(x), s.erase(x), s.count(x) (检查 x 是否存在)。

3.3.2 Map (映射)

这是 STL 中最强大的工具之一。你可以把它理解为**“超级数组”**，它的下标可以是任何东西（字符串、负数、甚至另一个容器）。

头文件：#include <map>
声明：map<string, int> mp; （建立一个从字符串到整数的映射）。
场景：统计单词出现的次数。

map<string, int> mp;
mp["apple"] = 5;
mp["banana"] = 2;
mp["apple"]++; // "apple" 的值变成了 6
 
cout << mp["apple"]; // 输出 6

⚠️ 注意：map 的访问也是 $O(\log N)$ 的，比普通数组 $O(1)$ 慢一点，不要在时间非常紧张（如 $10^7$ 次操作）时滥用。

3.4 Stack, Queue & Priority Queue：数据结构三剑客

3.4.1 Stack (栈)

特性：先进后出 (LIFO)。场景：括号匹配、单调栈、DFS。

st.push(x): 入栈。
st.top(): 查看栈顶元素。
st.pop(): 弹出栈顶。

3.4.2 Queue (队列)

特性：先进先出 (FIFO)。场景：BFS（广度优先搜索）。

q.push(x): 入队。
q.front(): 查看队头。
q.pop(): 弹出队头。

3.4.3 Priority Queue (优先队列/堆)

特性：不管你按什么顺序 push 进去，top() 永远也是最大（默认）或最小的那个元素。底层是堆（Heap）。场景：贪心算法、Dijkstra 最短路。

priority_queue<int> pq; // 默认是大根堆（最大的在上面）
pq.push(10);
pq.push(5);
pq.push(20);
 
cout << pq.top(); // 输出 20
pq.pop();         // 弹出 20
cout << pq.top(); // 输出 10

如果要建立小根堆（最小的在上面）： priority_queue<int, vector<int>, greater<int>> pq;

3.5 Algorithm：一行代码顶十行

在 <algorithm> 头文件里，藏着很多黑魔法。

sort (排序)： sort(v.begin(), v.end()); // 默认从小到大 sort(v.begin(), v.end(), greater<int>()); // 从大到小 自定义排序：写一个 cmp 函数。
unique (去重)：通常配合 sort 使用。它不真正删除元素，而是把重复的移到后面。 标准去重模板：
```
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
```
lower_bound / upper_bound (二分查找)： 必须在有序数组中使用。
- lower_bound(beg, end, val): 返回第一个 $\ge val$ 的数的迭代器（位置）。
- upper_bound(beg, end, val): 返回第一个 $> val$ 的数的迭代器。
获取下标：int index = lower_bound(v.begin(), v.end(), 5) - v.begin();

next_permutation (全排列)：自动把数组变成下一个字典序排列。

vector<int> p = {1, 2, 3};
do {
    // 输出当前排列
} while (next_permutation(p.begin(), p.end()));

3.6 还有一个特殊的：Pair

有时候我们需要把两个东西绑在一起，比如坐标 $(x, y)$ 。

声明：pair<int, int> p;
赋值：p = {3, 4}; 或 p = make_pair(3, 4);
访问：p.first 是第一个元素，p.second 是第二个。
排序特性：sort 对 pair 排序时，默认先比 first，如果相等再比 second。这在处理区间问题时极其方便。

🧠 本章小结与练习

STL 是算法竞赛的基石。你不需要一下子背下所有函数的参数，用得多了自然就记住了。

练习作业：在洛谷上搜索并尝试解决 P1059 [NOIP2006 普及组] 明明的随机数。

题目大意：给你 $N$ 个整数，要求你先去重，再排序，最后输出。
提示：你可以尝试用 set 做这道题，代码会短得惊人；也可以用 vector + sort + unique 来练习。

接下来，我们将进入算法的核心领域——如何衡量你的代码快不快？