# `set`
包含不同元素的有序集合容器，集合内的元素不重复。使用比较操作，底层是红黑树（平衡树）。
头文件：`<set>`
定义：`set<类型, 比较器> 容器名`，可以用初始化列表或另一个 `set` 初始化。不指定比较器时使用默认的 `<` 比较规则进行排序。
`set` 的模板参数为 `set<typename, compare>`（实际上还有一个模板参数）。
`set<int> s, t = {1, 2, ..., M}, a = t`，时间复杂度为 $O(1), O(M \log M), O(M)$。
## 基本操作
迭代器相关内容请参考 [迭代器](迭代器.md)。
令 $N$ 为当前容器 `s` 的大小，$x$ 为元素，`it` 为迭代器。
下面的复杂度记号指代时间复杂度。
### 修改
- `s.clear()` 清空，$O(N)$
- `s.insert()` 插入元素
- `s.insert(x)`，$O(\log N)$
- 如果插入之前容器内存在元素 `x`，则不插入
- `s.insert({1, 2, ..., M})`，$O(M \log (M + N))$
- `s.erase()` 删除元素，$O(\log N)$
- `s.erase(x)` 删除元素 $x$，容器不包含指定元素则不删除
- `s.erase(it)` 删除 `it` 指向的元素，`it` 是指向当前集合 `s` 的迭代器
- `it` 不能为尾迭代器
- 调用 `s.erase(it)` 后，迭代器 `it` 立即失效，不能再对该迭代器进行使用和操作
- `s.swap(other), swap(s, other)`，将容器和 $other$ 交换，$O(1)$
- `swap` 数组的时间复杂度为 $O(N)$
- 要求两个容器的模板参数一致
- `=`
- `s = other`，用容器赋值，$O(|N| + |other|)$
- `s = {1, 2, ..., M}`，用初始化列表赋值，$O((N + M) \log (N + M))$
```cpp
std::set<int> s = {10, 20, 30, 40, 50};
auto it = s.find(30);
s.erase(it);
// 以下所有操作都是未定义行为：
// std::cout << *it << std::endl; // 错误！解引用失效迭代器
// ++it; // 错误！使用失效迭代器
// if (it == s.end()) {} // 错误！比较失效迭代器
```
### 查找
- `s.count(x)`，返回容器内 $x$ 的数量，$O(\log N)$
- `s.find(x)`，返回容器内指向值为 $x$ 的元素的迭代器，如果不存在则返回 `.end()`，$O(\log N)$
- `s.lower_bound(x)` 和 `s.upper_bound(x)`，返回容器内指向大于等于和大于 $x$ 的第一个元素的迭代器，如果不存在则返回 `s.end()`，$O(\log N)$。
- 不是二分，需要跟 `lower_bound(), upper_bound()` 区分
- 直接用 `set<int> s; lower_bound(s.begin(), s.end(), x)` 时间复杂度线性 $O(N)$
- `s.empty()` 和 `s.size()`，时间 $O(1)$
- `s.begin()` 和 `s.end()`，时间 $O(1)$
### 比较
定义 `set<typename> lhs, rhs`。
对于 `==, !=`，当 `lhs, rhs` 大小不同时，`lhs == rhs, lhs != rhs` 的比较次数为 $O(1)$（因为只需要判断大小），其余情况对两个容器内所有元素排序后进行字典序比较，时间 $O(N)$。
对于 `<, <=, >, >=`，使用字典序比较，时间 $O(N)$。
## 比较器
请参考 [自定义比较器](自定义比较器.md)。
语法结构同 `priority_queue`，但是不用像 `priority_queue` 的比较器反过来写比较规则。可以使用比较器函数对象，可以重载运算符。
```cpp
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
struct Node {
int a, b;
bool operator<(const Node &i) const {
return a > i.a;
}
bool operator>(const Node &i) const {
return b > i.b;
}
};
set<Node, greater<Node>> s;
set<Node, less<Node>> ss;
int main() {
s = {{10, 1}, {5, 2}, {1, 100}};
ss = {{10, 1}, {5, 2}, {1, 100}};
for (auto x : s) {
cout << x.a << ' ' << x.b << '\n';
}
cout << '\n';
for (auto x : ss) {
cout << x.a << ' ' << x.b << '\n';
}
return 0;
}
/*
output:
1 100
5 2
10 1
10 1
5 2
1 100
*/
```
### `set` 上比较器的细节
令比较器为 `comp(a, b)`。
`set` 不直接使用 `==` 运算符，而是通过比较器（`comp`）判断两元素的相等关系。
`set` 中判断两元素 $a, b$ 相等的条件为 `!comp(a, b) && !comp(b, a)`（联想比较器什么时候返回真）。
当使用 `set` 存储内容不同但关键字相同的元素时，会有如下场景。
```cpp
struct Node {
int a, id; // 值，编号
};
struct cmp {
bool operator()(const Node &i, const Node &j) const {
return i.a < j.a;
}
} f;
int main() {
set<Node, cmp> s;
s.insert({1, 3}), s.insert({1, 5}), s.insert({-1, -1});
for (Node x : s) {
cout << x.a << ' ' << x.id << '\n';
}
return 0;
}
/*
output:
-1 -1
1 3
*/
```
如果对于内容不同但关键字相同的元素也需要存储，则比较器应为：
```cpp
struct Node {
int a, id;
};
struct cmp {
bool operator()(const Node &i, const Node &j) const {
return i.a < j.a || i.a == j.a && i.id < j.id;
}
};
int main() {
set<Node, cmp> s;
s.insert({1, 3}), s.insert({1, 5}), s.insert({-1, -1});
for (Node x : s) {
cout << x.a << ' ' << x.id << '\n';
}
return 0;
}
/*
output:
-1 -1
1 3
1 5
*/
```
## 基本使用
```cpp
#include <set>
using namespace std;
set<int> s;
s.insert(3);
s.insert(2);
s.insert(5);
cout << s.count(3) << "\n"; // 1
cout << s.count(4) << "\n"; // 0
s.erase(3);
s.insert(4);
cout << s.count(3) << "\n"; // 0
cout << s.count(4) << "\n"; // 1
```
### 比较器相关
```cpp
struct Node {
int x, id;
bool operator <(const Node &i) const {
return x < i.x || x == i.x && id < i.id;
}
};
struct cmp {
bool operator()(const Node &i, const Node &j) {
return i.x > j.x || i.x == j.x && i.id < j.id;
}
}
set<Node> s1; // 按 x 从小到大、x 相同时 id 从小到大
set<Node, cmp> s2; // 按 x 从大到小、x 相同时 id 从小到大
```
```cpp
struct Node {
int x, id;
};
struct comp {
bool operator ()(const Node &i, const Node &j) const {
return i.x < j.x; // 如果 id 不同，应为 return i.x < j.x || i.x == j.x && i.id < j.id;
}
};
set<Node, comp> s;
s.insert({1, 2});
s.insert({1, 3}); // 两元素视为相等
cout << s.size(); // 1
```
### 遍历
```cpp
set<int> s = {2,5,6,8};
cout << s.size() << "\n"; // 4
for (int x : s) {
cout << x << "\n";
}
for (auto it = s.begin(); it != s.end(); it++) {
cout << *it << '\n';
}
```
不要在遍历时执行 `.insert`、`.erase` 等修改容器的操作，否则 `RE`、`WA`。
如果需要对容器进行修改，请参考[这里](map.md#在遍历时进行修改和删除)。
### lower_bound, upper_bound 相关
一定要注意迭代器的各种边界问题。
```cpp
set<int> s;
s.insert(1); // [1]
s.insert(14); // [1, 14]
s.insert(9); // [1, 9, 14]
s.insert(2); // [1, 2, 9, 14]
auto it = s.lower_bound(3); // 指向值 9
cout << *prev(it); // 访问 < 3 的最大元素 2
cout << *s.upper_bound(7) << '\n'; // 9
cout << *s.upper_bound(9) << '\n'; // 14
cout << *s.lower_bound(5) << '\n'; // 9
cout << *s.lower_bound(9) << '\n'; // 9
cout << *s.begin() << '\n'; // 1
auto it = s.end();
cout << *(--it) << '\n'; // 14
s.erase(s.upper_bound(6)); // [1, 2, 14]
auto it = s.find(x);
if (it != s.end()) { // 找到元素 x
} else { // 没找到元素 x
}
```
思考题：如何找到集合中离 $x$ 最近的元素？
```cpp
auto it = s.lower_bound(x);
if (it == s.begin()) {
cout << *it << "\n";
} else if (it == s.end()) {
it--;
cout << *it << "\n";
} else {
int a = *it; it--;
int b = *it;
if (x - b < a - x) cout << b << "\n";
else cout << a << "\n";
}
// 如果一开始插入一个极小值和一个极大值，不需要做分类讨论
s.insert({-INF, INF});
auto it = s.lower_bound(x);
int a = *it; it--;
int b = *it;
if (x - b < a - x) cout << b << "\n";
else cout << a << "\n";
```
## `multiset`
有序多重集合，集合内可以存储相同元素。
头文件、定义、初始化、绝大部分操作和成员与 `set` 一致，有几个特殊点需要记住。
令 $N$ 为多重集容器大小，$x$ 为容器中的一个元素，`multiset<int> s`，令 $M$ 为 $x$ 在多重集中出现的次数。
- `s.count(x)`，返回 $x$ 在多重集中的出现次数，$O(\log N + M)$
- `s.erase(x)`，删除多重集容器内**所有**值为 $x$ 的元素，$O(\log N + M)$
- 如果只想快速 $O(\log N)$ 查找是否存在元素 $x$、删除一个值为 $x$ 的元素，使用 `s.find(x) != s.end()` 和 `auto it = s.find(x); if (it != s.end()) s.erase(it)`。直接删除尾迭代器报错。
```cpp
// multiset 的 erase 操作
multiset<int> ms;
ms.insert(1); // [1]
ms.insert(14); // [1, 14]
ms.insert(9); // [1, 9, 14]
ms.insert(2); // [1, 2, 9, 14]
ms.insert(9); // [1, 2, 9, 9, 14]
ms.insert(9); // [1, 2, 9, 9, 9, 14]
cout << ms.count(4) << '\n'; // 0
cout << ms.count(9) << '\n'; // 3
cout << ms.count(14) << '\n'; // 1
ms.erase(ms.find(9));
cout << ms.count(9) << '\n'; // 2
ms.erase(9);
cout << ms.count(9) << '\n'; // 0
```
## 参考资料
[关联式容器](https://oi-wiki.org/lang/csl/associative-container/)
[迭代器](https://oi-wiki.org/lang/csl/iterator/)