#include<map>

map 容器是一个键值对 key-value 的映射。 其内部实现是一颗以 key 为关键码的红黑树。map 的 key 和 value 可以是任意类型，其中 key 必须定义“小于号”运算符，声明方法为：

map<key_type,value_type> name;

例如：

map<long long, bool> vis;

map<string, int> hash;

map< pair<int, int>, vector<int> >test;

在很多时候，map 容器被当作 Hash 表使用，建立从复杂信息 key (如字符串) 到简单信息 value (如一定范围内的整数)的映射。

因为map 基于平衡树实现，所以它的大部分操作的时间复杂度都在 $O(\log{n})$ 级别，略慢于使用 Hash 函数实现的传统 Hash 表。 从 C++11 开始，STL 中新增 unordered_map 等基于 Hash 的容器，在后面介绍。

size()/empty()/clear()/begin()/end()

与 set 类似，分别为元素个数、是否为空、清空、首迭代器、尾迭代器。

迭代器

map 的迭代器与 set 一样，也是“双向访问迭代器”。对 map 的迭代器解除引用后，将得到一个二元组 pair<key_type,value_type>.

insert()/erase()

与 set 类似，分别为插入、删除。 insert 的参数是 pair<key_type,value_type> , erase 的参数可以是 key 或者 迭代器。

map<int,int> h;
 h.insert(make_pair(1,2)),h.insert(make_pair(2,3));
 map<int,int>::iterator it = h.begin();
 map<int ,int> p = *it;
 h.erase(it),h.erase(2);
 cout << p.first << ' ' << p.second <<'\n';

find( )

h.find(x) 在变量名为 h 的 map 中查找 key 为 x 的二元组，并返回指向该二元组的迭代器。 若不存在，返回 h.end( )。时间复杂度为 $O(\log{n})$ 。

[] 操作符

h[key] 返回 key 映射到的 value 的引用，时间复杂度为 $O(\log{n})$.

[ ] 操作符是 map 最吸引人的地方。 我们可以很方便地通过 h[key] 来得到 key 对应的 value , 还可以对 h[key] 进行赋值操作，改变 key 对应的 value.

需要特别注意的是，若查找的 key 不存在 ，则执行 h[key] 后，h 会自动新建一个二元组（key,zero），并返回 zero 的引用 。 这里 zero 表示一个广义“零值”，如整数 0、空字符串等。如果查找之后不对 h[key] 进行赋值，那么时间一长， h 会包含很多无用的“零值二元组”，白白地占用了空间，降低了程序运行效率。强烈建议读者在用 [] 操作符查询之前，先用 find 方法检查 key 的存在性。

【实例】用 map 统计字符串出现的次数

给定 $n$ 个字符串，$m$ 个问题，每个问题询问一个字符串出现的次数。

$n \leq 20000,m\leq 20000$ , 每个字符串长度都不超过 $20$。

map<string ,int> h;
char str[25];
for(int i=1;i<=n;i++){
     scanf("%s",str);h[str]++    
 }
for(int i=1;i<=m;i++){
     scanf("%s",str);
     if(h.find(str)==h.end())puts("0");
     else printf("%d\n",h[str]);
 }

学习完毕

{{ select(1) }}

• YES
• NO