STL 的其他用法（先不看）¶
迭代器¶
迭代器用来访问、遍历容器中的元素，可以先理解成“指向某个位置的工具”，但不一定就是普通指针。
auto 让编译器确定类型。这里也可以把 auto 写成 vector<int>::iterator。
begin 指向第一个元素，end 是尾后位置。 end 不能解引用，空容器的 begin 就等于 end。
vector 添加元素时，如果重新分配了存储空间，原来的迭代器、元素指针、引用都会失效。
删除元素也可能让原来的迭代器失效。修改容器后，不能不加判断就继续使用旧位置。
vector 二分查找¶
需要头文件 <algorithm>。下面按默认的从小到大顺序，先排序，再查找。
vector<int> A = {8, 3, 5, 5};
sort(A.begin(), A.end());
auto low = lower_bound(A.begin(), A.end(), 5);
auto up = upper_bound(A.begin(), A.end(), 5);
cout << low - A.begin() << ' ' << up - A.begin(); // 输出1 3
lower_bound 找第一个大于等于目标的位置，upper_bound 找第一个大于目标的位置。
可能找不到，先检查是否等于 end，再解引用。
这里找到的是排序后的位置，原来的输入顺序已经改变。
vector 去重¶
unique 只合并相邻的重复元素。要把相同值都去掉重复，先排序。
vector<int> A = {3, 1, 3, 2, 2};
sort(A.begin(), A.end());
auto it = unique(A.begin(), A.end());
A.erase(it, A.end());
for (int x : A) cout << x << ' '; // 输出1 2 3
unique 返回新的逻辑结尾，但不会缩小 vector 的 size，还要用 erase 删掉后面的部分。
熟悉以后，可以合成一行：
这行之前，A 仍然要先排好序。排序去重不会保留原来的输入顺序。
set 的最值与查找¶
需要头文件 <set>。下面使用默认的从小到大顺序。
最小值、最大值
rbegin 指向反向遍历的第一个元素，也就是这里最大的元素。
第一个大于等于 x 的数
第一个大于 x 的数
最后一个小于 x 的数
没有更小的数时，不能把 begin 再往前减。set 的迭代器也不能像 vector 那样直接相减求下标。
set 查找边界，先用它自己的 lower_bound、upper_bound 成员函数。
multiset，多重集合¶
需要头文件 <set>。与 set 不同，相同的整数可以存多份，默认仍然有序。
只删除一份，先找到一个位置
按值删除，会删掉所有相同的值
find 没找到时返回 end，不能把 end 传给删除单个位置的 erase。
priority_queue，优先队列¶
需要头文件 <queue>。默认是大根堆，每次优先取最大的数，不是按进入队列的顺序取。
priority_queue<int> q;
q.push(3);
q.push(5);
q.push(7);
q.push(2);
cout << q.top() << '\n'; // 输出7
q.pop();
cout << q.top() << '\n'; // 输出5
q.push(6);
cout << q.top(); // 输出6
top 访问堆顶，pop 删除堆顶、不返回它。空队列不能调用 top、pop。
小根堆，优先取最小值
还需要 <vector>、<functional>。
不必为了实现小根堆，统一把数取负。最小负整数直接取相反数，还可能超出类型范围。
bitset，一组二进制位¶
需要头文件 <bitset>，位数在定义时确定。
bitset<16> a; // 全部是0
bitset<16> b(0xfa2); // 0000111110100010
bitset<16> c(string("0101111001")); // 0000000101111001
使用 string 构造时，还需要头文件 <string>。
下标从最低位开始，最低位是 0。
| 写法 | 作用 |
|---|---|
bt.test(i) |
第i位是否为1 |
bt.any() |
是否至少有一个1 |
bt.all() |
是否全部是1 |
bt.set() |
全部置1 |
bt.set(i, 0) |
第i位置0 |
bt.set(i) |
第i位置1 |
bt.reset(i) |
第i位置0 |
bt.reset() |
全部置0 |
bt.flip(i) |
翻转第i位 |
bt.flip() |
翻转所有位 |
bt.to_string() |
转成由0、1组成的字符串 |
bt.to_ullong() |
转成unsigned long long，数值要能放下 |
访问下标时，也要保证不越界。
八位补码，转成有符号整数
先打表，把 -128 到 127 的八位补码，与对应的整数关联起来。
#include <iostream>
#include <string>
#include <map>
#include <bitset>
using namespace std;
map<string, int> mp;
void init() {
for (int i = -128; i <= 127; i++) {
bitset<8> bit(i);
mp[bit.to_string()] = i;
}
}
int main() {
init();
string s;
cin >> s;
if (mp.count(s) != 0) cout << mp[s];
else cout << "Invalid";
return 0;
}
输入 11111111，输出 -1；输入 10000000，输出 -128。
这里按八位补码解释，不是把所有二进制串都当成非负整数。输入必须恰好是八个 0 或 1。
array，固定长度数组¶
需要头文件 <array>。长度固定，不能像 vector 那样 push_back。
它支持 size、begin、end，下标仍然从 0 开始。普通局部 array 不初始化，也不能直接读取其中的 int 值。
next_permutation，下一个排列¶
需要头文件 <algorithm>，按字典序把当前排列改成下一个排列。
字典序就是从左往右比较，第一个不同的位置，数小的排在前面。比如 1 3 2 在 2 1 3 前面。
生成下一个排列
下面是代码片段，用普通数组演示：
int a[] = {1, 2, 3};
next_permutation(a, a + 3);
for (int i = 0; i < 3; i++) cout << a[i] << ' '; // 输出1 3 2
范围是左闭右开，原数组会被修改。 这里处理 a[0] 到 a[2]。
找到下一个排列，返回 true；已经是最大排列，就恢复成最小排列，返回 false。
int a[] = {3, 2, 1};
bool flag = next_permutation(a, a + 3);
cout << flag << '\n'; // 输出0，表示false
for (int i = 0; i < 3; i++) cout << a[i] << ' '; // 输出1 2 3
枚举所有不同的排列
先从小到大排序，再用 do-while，先输出当前排列，再生成下一个。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> A = {1, 2, 3};
sort(A.begin(), A.end());
do {
for (int x : A) cout << x << ' ';
cout << '\n';
} while (next_permutation(A.begin(), A.end()));
return 0;
}
输出：
先排序，才能从最小排列开始，不漏掉前面的排列。 直接写 while，会先生成下一个，漏掉初始排列。
有重复元素也可以用。比如 1 1 2，依次得到 1 1 2、1 2 1、2 1 1，不会重复输出相同排列。
字符串也能用
需要 <string>，下面的代码片段输出 acb：
排列个数增长很快。 n 个不同元素有 \(n!\) 种排列，只适合枚举规模较小的情况。
补充：prev_permutation，上一个排列
用法相同，改成上一个字典序更小的排列；没有上一个，就恢复成最大排列，返回 false。