映射在数学中指两个集合之间元素相互“对应”的关系 ，在C++的STL库中也有这样的一个容器:map
我们称映射的集合为关键字集合（key），被映射的集合称为值集合（value）
在使用map之前还是需要加上头文件
#include<map> using namespace std;
构造映射表
在C++中如果我们要定义一个映射表，只需要声明：map<T1,T2> m 这样我们就声明了一个映射表m，它从T1类型映射到T2类型。比如如果我们定义map<string,int> m，构建了一个从字符串到整数的映射，这样我们就可以把一个字符串和一个整数关联起来
插入一对映射
通过使用insert()函数向集合中插入一个新的映射，参数是一个pair。
pair是一个标准库的类型，定义在头文件utility中。可以看成是两个成员变量first和second的结构体，并且重载了<运算符（先比较first再比较second）。当我们创建一个pair时，必须提供两个类型。
我们可以像这样顶一个保存string和int的pair ： pair<string , int>p;
make_pair（v1,v2）函数由v1和v2初始化的pair，类型可以从v1和v2的类型推断出来。
我们向映射表中加入新映射对的时候就是通过插入pair来实现的。如果插入的key之前已经存在，将不会用插入新的value替代原来的value，也就是这次的插入是无效的。
#include<map>
#include<string>
#include<utility>
using namespace std;
int main()
{
map<string , int> dict; //dict时一个从string到int的映射，存放每个名字对应的班级编号，初始时为空
dict.insert(make_pair("tom" , 1));//{"tom"->1}
dict.insert(make_pair("jone" , 2));//{"tom"->1,"jone"->2}
dict.insert(make_pair("Mary" , 1));//{"tom"->1,"jone"->2,"Mary"->1}
dict.insert(make_pair("tom" , 1));//插入无效，已经有对应的映射了
return 0;
}
访问映射
在C++中访问映射和访问数组一样，直接用[]就可以访问。比如dict["tom"]，就可以获取"Tom"所在的班级，如果没有对"Tom"做映射的话，此时你可以访问dict["Tom"]，系统会自动为"Tom"生成一个映射，其value为对应类型的默认值（比如int的默认值时0，string的默认值时空字符串）
并且我们可以之后再给映射赋予新的值，比如dict["Tom"]=3，这样为我们提供了另一种插入手段。实际上，我们常常通过访问下标的方式来插入映射，而不是通过insert插入一个pair来实现
当然有些时候，我们不希望系统自动为我们生成映射，这时候我们需要检测"Tom"是否已经有映射了，如果有映射再继续访问。这时就需要用count()函数来进行判断
#include<iostream>
#include<map>
#include<string>
#include<utility>
using namespace std;
int main()
{
map<string , int> dict;
dict.insert(make_pair("tom" , 1));//{"tom"->1}
dict.insert(make_pair("jone" , 2));//{"tom"->1,"jone"->2}
dict.insert(make_pair("Mary" , 1));//{"tom"->1,"jone"->2,"Mary"->1}
cout<<"Mary is in class" << dict["Mary"]<<endl;//访问
cout<<"Tom is in class" << dict["Tom"]<<endl;
return 0;
}
map常用的函数总结
| 函数 | 功能 | 时间复杂度 |
| insert | 插入一对映射 | O(log n) |
| count | 判断关键字是否存在 | O(log n) |
| size | 获取映射对个数 | O(1) |
| clear | 清空 | O(n) |
| erase | 删除 | O(log n) |
上面的功能函数差不多已经可以满足我们大部分的需求了，更多关于map的函数，可以去参考文档，竞赛掌握这些差不多就够了
Comments | NOTHING