STL 速查
标准模板库（STL）是 C++ 竞赛的"工具箱"：容器装数据，算法处理数据。掌握下面这些就够用了。
一、容器
vector 动态数组 最常用
- 随机访问 O(1)，尾部插入 O(1)
- 支持排序、二分查找等算法
vector<int> a; // 空数组
a.push_back(3); a.push_back(1); // 尾部加元素
a.size(); // 元素个数
a[0]; a.back(); // 访问
a.pop_back(); // 删尾部
sort(a.begin(), a.end()); // 升序排序string 字符串 文本处理
- 支持
+拼接、==比较 find / substr / stoi / to_string非常常用
string s = "abc";
s += "def"; // "abcdef"
s.size(); // 长度 6
s.substr(1, 3); // "bcd"
s.find("cd"); // 下标 2，找不到返回 string::npos
int x = stoi("42"); // 字符串转整数
string t = to_string(42); // 整数转字符串stack / queue 栈与队列
- 栈：后进先出，
top看栈顶 - 队列：先进先出，
front看队首
stack<int> st;
st.push(1); st.push(2);
st.top(); // 2
st.pop(); // 出栈
queue<int> q;
q.push(1); q.push(2);
q.front(); // 1
q.pop(); // 出队priority_queue 优先队列（堆） 贪心 / 最短路
- 默认大根堆：
top()返回最大值 - 小根堆写法：
priority_queue<int, vector<int>, greater<int>>
priority_queue<int> big; // 大根堆
big.push(3); big.push(5);
big.top(); // 5
priority_queue<int, vector<int>, greater<int>> small; // 小根堆
small.push(3); small.push(5);
small.top(); // 3set 集合 去重 + 有序
- 元素不重复、自动升序，增删查 O(log n)
- 适用：判重、找前驱后继
set<int> s;
s.insert(3); s.insert(3); // 重复插入无效
s.count(3); // 0 或 1（是否在集合中）
s.erase(3);
s.begin(); s.rbegin(); // 最小 / 最大map 键值对 字典
- 按键自动升序，增删查 O(log n)
unordered_map无序但 O(1)，适合只查不改顺序
map<string, int> score;
score["tom"] = 90;
score["amy"] = 85;
cout << score["tom"]; // 90
// 遍历（按键升序）
for (auto &it : score)
cout << it.first << " " << it.second << endl;二、常用算法
sort 排序
- 默认升序；可传自定义比较器
- 对 pair 先比 first 再比 second
sort(a.begin(), a.end()); // 升序
sort(a.begin(), a.end(), greater<int>()); // 降序
sort(a.begin(), a.end(),
[](int x, int y){ return x > y; }); // 自定义（lambda）reverse / swap / fill
reverse(a.begin(), a.end()); // 反转
swap(x, y); // 交换两个变量
fill(a.begin(), a.end(), 0); // 数组全部赋 0
// C 风格数组：
memset(a, 0, sizeof(a)); // 快，但只适合 0 / -1find / count / accumulate
find(a.begin(), a.end(), 5); // 返回迭代器，找不到=a.end()
count(a.begin(), a.end(), 5); // 出现次数
int sum = accumulate(a.begin(), a.end(), 0); // 求和（初始0）
int mx = *max_element(a.begin(), a.end());
int mn = *min_element(a.begin(), a.end());binary_search / lower_bound 二分
- 要求数组已排序
lower_bound：第一个 ≥ x 的位置upper_bound：第一个 > x 的位置
binary_search(a.begin(), a.end(), 5); // 是否存在 5
auto it = lower_bound(a.begin(), a.end(), 5);
int idx = it - a.begin(); // 第一个≥5的下标
auto it2 = upper_bound(a.begin(), a.end(), 5);
int cnt = it2 - it; // 等于5的个数unique 去重
- 只去掉相邻重复，一般先 sort 再用
sort(a.begin(), a.end());
auto last = unique(a.begin(), a.end());
a.erase(last, a.end()); // 真正的去重后数组next_permutation 全排列
sort(a.begin(), a.end()); // 从最小排列开始
do {
// 处理当前排列 a[0..n-1]
} while (next_permutation(a.begin(), a.end()));