映射在数学中指两个集合之间元素相互“对应”的关系 ,在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中。可以看成是两个成员变量firstsecond的结构体,并且重载了<运算符(先比较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的函数,可以去参考文档,竞赛掌握这些差不多就够了


立志做一名攻城狮