# map
不使用 `multimap`。
## 介绍
`map` 是包含键值对 `<key, value>` 的有序映射关联容器，可以看做是 `key` 映射到 `value`。`map` 要求所有的映射的 `key` 是互不相同的（唯一的），而 `value` 可以重复。
`map` 的底层是红黑树。所有映射按照 `key` 排序，并较为快速地兼顾了查询、插入、删除操作。
使用 `map` 需要包含头文件 `<map>`。
定义：`map<key 类型, value 类型, 比较器> 容器名`（还有一个模板参数，不提及），比较器可以不传入。默认比较器为 `<` 规则。
## 成员函数
迭代器相关内容请参考 [迭代器](迭代器.md)。
`map` 的插入、删除、查找操作都是 $O(\log N)$ 的，其中$N$ 为映射对数量。
定义一个 `map<int, int> m, p;`，以下操作的时间复杂度均为 $O(\log N)$。
- `m[x]`，返回 `x` 映射到的 `value` 的引用。如果 `m` 中不存在 `key` 为 `x` 的映射，会新建一个 `x` 到 `int `类型默认值 $0$ 的映射 `<x, 0>`。
- 如果 `value` 类型为 `string`，则新建了一个 `<x, "">` 的映射对。
- 对于 `value` 类型的其他情况，以此类推。
- 你可以将 `map` 容器视为一个“万能”的数组！
- `m[x] = y`，将 `x` 映射到的 `value` 修改为 `y`。如果 `m` 中不存在 `key` 为 $x$ 的映射，则新建一个映射 `<x, y>`。
- 也可以用 `m.insert({x, y})`，这里不在详细介绍 `.insert()` 的用法。
- `m.count(x)`，返回 `m` 中有多少个 `key` 为 `x` 的映射，即判断是否存在 `key` 为 `x` 的映射。
- `m.erase(x)`，删除 `key` 为 `x` 的映射，如果不存在 `key` 为 `x` 的映射则不删除。
- `m.erase(it)`，删除 `it` 迭代器指向的映射，要求 `it` 不能为 `m` 的尾迭代器 `m.end()`。
- `m.find(x)`，返回 `key` 为 `x` 的映射的迭代器，如果不存在 `key` 为 `x` 的映射则返回 `m` 的尾迭代器 `m.end()`。
- 查找映射、判断映射是否存在应使用 `.count()` 或者 `.find()` 而非 `[]`，这样可以加快效率。
- `m.lower_bound(x), m.upper_bound(x)`，返回第一个 `key` 大于等于和大于 `x` 的映射的迭代器。
以下操作的时间复杂度均为 $O(1)$
- `m.begin(), m.end()`，返回指向 `m` 的头尾迭代器。
- `m.empty()`，返回 `m` 是否为空。
- `m.size()`，返回 `m` 所包含的映射对数量。
- `m.clear()`，其中容器 `m`。
- `m.swap(p)`，交换容器 `m` 和 `p`，也可以使用代码 `swap(m, p)`。
### 基本使用
```cpp
map<int, int> m;
map<int, int> h[100]; // 定义 100 个 map 容器
m[1] = 5; // [(1, 5)]
m[3] = 14; // [(1, 5); (3, 14)]
m[2] = 7; // [(1, 5); (2, 7); (3, 14)]
m[0] = -1; // [(0, -1); (1, 5); (2, 7); (3, 14)]
m.erase(2); // [(0, -1); (1, 5); (3, 14)]
cout << m[1] << endl; // 5
cout << m.count(7) << endl; // 0
cout << m.count(1) << endl; // 1
cout << m[2] << endl; // 0，若不存在映射则新建一个映射 (2, 0)
```
## 遍历容器
`map` 中存储映射的方式是使用 C++ `pair`。如果你定义了一个 `map<string, int> m`，那么所有的映射都是类型 `pair<string, int>`，使用 `.first` 和 `.second` 可以取出 `pair` 中的第 $1, 2$ 个元素。
可以使用如下方式遍历：
```cpp
for (const auto &x : m) { // 常引用
cout << x.first << " " << x.second << endl;
}
for (auto x : m) { // 将容器 m 中的每个映射依次拷贝给 x
cout << x.first << " " << x.second << endl;
}
for (pair<string, int> x : m) { // 同上
cout << x.first << " " << x.second << endl;
}
// .first 是第一个元素 string 类型，.second 是第二个元素 int 类型
```
当你只需要遍历容器而不涉及到修改、删除操作时，推荐使用第一种遍历方法。需要注意到常引用和拷贝的区别。
## 在遍历时进行修改和删除
由于在遍历时可以使用引用，你可以用下述方式修改映射中的 `value`：
```cpp
for (auto &x : m) {
x.second = 1234; // 把所有映射的 value 改为 1234
}
```
```cpp
map<string, int> h = {{"zsc", 250}};
auto it = h.find("zsc"); // it 为指向 key 为 "zsc" 的迭代器
it->second = 0; // 将 "zsc" 映射的 `value` 修改为 0
```
你可以在遍历时修改映射的 `value`，但不能增加新的映射、删除已有映射，否则会 RE。以下代码是一个错误的示例。
```cpp
map<int, int> m;
for (int i = 0; i < 10; ++i) {
m[i] = i;
}
for (auto &it : m) {
cout << "Current Key: " << it.first << endl;
m.erase(it.first);
}
```
因此你要删除时，你可以拷贝一个新 `map` 来删除，或者将需要删除的 `key` 记录下来最后删除。
### 拷贝新 map
```cpp
map<int, int> m, M;
for (int i = 0; i < 10; ++i) {
m[i] = i;
}
int current_iteration = 0;
for (const auto &it : m) {
if (current_iteration % 3 == 0) {
M[it.first] = it.second;
}
current_iteration++;
}
swap(m, M);
cout << "映射: " << endl;
for (const auto &it : m) {
cout << it.first << " " << it.second << endl;
}
/*
* 映射:
* 0 0
* 3 3
* 6 6
* 9 9
*/
```
### 记录后删除
```cpp
map<int, int> m;
for (int i = 0; i < 10; ++i) {
m[i] = i;
}
vector<int> to_erase;
int current_iteration = 0;
for (const auto &it : m) {
if (current_iteration % 3 == 0) {
to_erase.push_back(it.first);
}
current_iteration++;
}
for (int key : to_erase) {
m.erase(key);
}
cout << "剩余的映射:" << endl;
for (const auto &it : m) {
cout << it.first << " " << it.second << endl;
}
/*
* 剩余的映射:
* 1 1
* 2 2
* 4 4
* 5 5
* 7 7
* 8 8
*/
```
## 比较器
请参考 [自定义比较器](自定义比较器.md)。
比较器的细节同 `set`。
## lower_bound, upper_bound
```cpp
map<int, int> m;
m[3] = 5; // [(3, 5)]
m[11] = 4; // [(3, 5); (11, 4)]
m[10] = 491; // [(3, 5); (10, 491); (11, 4)]
cout << m.lower_bound(10)->first << " " << m.lower_bound(10)->second
<< '\n'; // 10 491
cout << m.upper_bound(10)->first << " " << m.upper_bound(10)->second
<< '\n'; // 11 4
m.erase(11); // [(3, 5); (10, 491)]
if (m.upper_bound(10) == m.end()) {
cout << "end" << endl; // Prints end
}
```
## 参考资料
[关联式容器](https://oi-wiki.org/lang/csl/associative-container/)。