映射在数学中指两个集合之间元素相互“对应”的关系 ,在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