map 是有序键值对容器，它的元素的键是唯一的．搜索、移除和插入操作拥有对数复杂度．map 通常实现为 红黑树（红黑树是一种自平衡的二叉搜索树．每个节点额外存储了一个 color 字段 ("RED" or "BLACK")，用于确保树在插入和删除时保持平衡）．
设想如下场景：现在需要存储一些键值对，例如存储学生姓名对应的分数：Tom 0，Bob 100，Alan 100．但是由于数组下标只能为非负整数，所以无法用姓名作为下标来存储，这个时候最简单的办法就是使用 STL 中的 map．
map 重载了 operator[]，可以用任意定义了 operator < 的类型作为下标（在 map 中叫做 key，也就是索引）：
map<Key, T> yourMap;其中，Key 是键的类型，T 是值的类型，下面是使用 map 的实例：
map<string, int> mp;map 中不会存在键相同的元素，multimap 中允许多个元素拥有同一键．multimap 的使用方法与 map 的使用方法基本相同．
插入与删除操作
- 可以直接通过下标访问来进行查询或插入操作．例如
mp["Alan"]=100． - 通过向
map中插入一个类型为pair<Key, T>的值可以达到插入元素的目的，例如mp.insert(pair<string,int>("Alan",100));； erase(key)函数会删除键为key的 所有 元素．返回值为删除元素的数量．erase(pos): 删除迭代器为 pos 的元素，要求迭代器必须合法．erase(first,last): 删除迭代器在 [𝑓𝑖𝑟𝑠𝑡,𝑙𝑎𝑠𝑡)
范围内的所有元素．clear()函数会清空整个容器．
在利用下标访问 map 中的某个元素时，如果 map 中不存在相应键的元素，会自动在 map 中插入一个新元素，并将其值设置为默认值（对于整数，值为零；对于有默认构造函数的类型，会调用默认构造函数进行初始化）．
当下标访问操作过于频繁时，容器中会出现大量无意义元素，影响 map 的效率．因此一般情况下推荐使用 find() 函数来寻找特定键的元素．
使用样例
map 用于存储复杂状态
在搜索中，我们有时需要存储一些较为复杂的状态（如坐标，无法离散化的数值，字符串等）以及与之有关的答案（如到达此状态的最小步数）．map 可以用来实现此功能．其中的键是状态，而值是与之相关的答案．下面的示例展示了如何使用 map 存储以 string 表示的状态．
// 存储状态与对应的答案
map<string, int> record;
// 新搜索到的状态与对应答案
string status; int ans;
// 查找对应的状态是否出现过
map<string, int>::iterator it = record.find(status);
if (it == record.end()) {
// 尚未搜索过该状态，将其加入状态记录中
record[status] = ans;
// 进行相应操作……
} else {
// 已经搜索过该状态，进行相应操作……
}遍历容器
可以利用迭代器来遍历关联式容器的所有元素．
set<int> s;
using si = set<int>::iterator;
for (si it = s.begin(); it != s.end(); it++) cout << *it << endl;需要注意的是，对 map 的迭代器解引用后，得到的是类型为 pair<Key, T> 的键值对．
在 C++11 中，使用范围 for 循环会让代码简洁很多：
set<int> s; for (auto x : s) cout << x << endl;对于任意关联式容器，使用迭代器遍历容器的时间复杂度均为 𝑂(𝑛)．
虽然 map 很强，但不是万能的：
- 时间复杂度：
map底层是红黑树，每次操作（插入、查询）的时间复杂度是 O(logN)。- 如果是数组直接访问，复杂度是 。
- 如果题目时间限制非常非常紧（例如 0.5s 处理 106 数据），
map可能会超时。
- 替代方案
unordered_map：- 底层是哈希表。
- 平均时间复杂度 ，通常比
map快。 - 缺点：在最坏情况下（哈希冲突）会退化到 ；且不支持按顺序遍历（
map是自动排序的）。 - 建议：一般先用
map，如果超时了（TLE），再尝试改成unordered_map。
文章评论