STL进阶

关联容器

有序（默认 < 排序）
插入位置取决于值，不可指定位置
查找 O(log n)（红黑树实现）
双向迭代器

共有成员函数

函数	说明
`find(val)`	查找，返回迭代器，失败返回 `end()`
`lower_bound(val)`	第一个 ≥ val 的位置
`upper_bound(val)`	第一个 > val 的位置
`count(val)`	统计等于 val 的元素数
`insert(val)`	插入
`erase(iter)`	删除

[lower_bound, upper_bound) 恰好等于目标元素区间。

set / multiset

头文件 <set>
set：元素唯一，不可重复
multiset：允许重复

#include <set>
set<int> s;
s.insert(3); s.insert(1); s.insert(2);  // 自动排序: 1 2 3
s.erase(2);
if (s.find(3) != s.end()) { /* 找到了 */ }

multiset<int> ms;
ms.insert(1); ms.insert(1);  // 重复允许

map / multimap

头文件 <map>
存储 pair<const Key, Value>
map：key 唯一；multimap：允许重复 key
[] 运算符：key 不存在时自动插入默认值

#include <map>
map<string, int> m;
m["cpp"] = 90;            // 若 "cpp" 不存在则插入
m.insert({"py", 85});
m.insert(make_pair("js", 80));
for (auto& [k, v] : m) { /* 按 key 排序遍历 */ }

multimap<string, int> mm;
mm.insert({"a", 1});
mm.insert({"a", 2});      // key "a" 重复

容器适配器

stack

头文件 <stack>，默认底层 deque
push / pop / top / empty / size
无迭代器，只能访问栈顶

queue

头文件 <queue>，默认底层 deque
push / pop / front / back / empty / size

priority_queue

头文件 <queue>，默认底层 vector
默认大根堆（最大元素在队首）
小根堆写法：priority_queue<int, vector<int>, greater<int>> pq;
push / pop / top / empty / size

priority_queue<int> pq;
pq.push(3); pq.push(1); pq.push(5);
pq.top();  // 5（最大）
pq.pop();  // 移除 5

常用算法一览

头文件 <algorithm>、<numeric>

算法	说明
`sort(b, e)`	排序，需随机迭代器
`stable_sort(b, e)`	稳定排序
`find(b, e, val)`	线性查找
`binary_search(b, e, val)`	二分查找（有序），需随机迭代器
`lower_bound(b, e, val)`	首个 ≥ val
`count(b, e, val)`	计数
`reverse(b, e)`	反转
`max_element(b, e)`	最大元素位置
`next_permutation(b, e)`	下一排列
`accumulate(b, e, init)`	累加（`<numeric>`）