Ⅰ.map
map可以翻译为映射，是 STL 中常用的容器。其实，数组就是一种映射。比如 int a[100]; 定义了一个 int 到 int 的映射，而 a[5] = 25; 就是把 5 映射到 25 。数组总是将 int 类型映射到其他基本类型（称为数组的基本型），这同时也带了一个问题，有时候希望把 string 映射成一个 int ，数组就不方便了。这时候就可以使用 map，map 可以将任何基本类型（包括 STL 容器）映射到任何基本类型（包括 STL 容器）。
map 的用途至少有以下三种情形：
需要建立字符（串）与整数之间的映射，使用 map 可以减少代码量。
判断大整数（比如几千位）或者其他类型数据是否存在，可以把map当布尔类型数组使用（哈希表）。
字符串与字符串之间的映射。
要使用 map ，必选先添加map头文件，即 #include<map> ，同时必须要有 using namespace std。
定义一个 map 的方法如下：
map<typename1,typename2> name;
其中，typename1 是映射前的类型（键key）,typename2是映射后的类型（值value），name为映射的名字。
普通 int 数组 a 就是 “map<int,int> a”。而如果是字符串到整型的映射，就必须使用string而不能使用char，即 map<string,int> a，map的键和值也可以 STL 容器，比如 map<set<int>,string> mp。当然需要注意的是：map的键是唯一的。
Ⅱ. map的访问
访问 map 的元素有两种方式，一种是通过下标访问；另一种是通过迭代器访问。
① 通过下标访问就像普通的数组元素访问，例如先定义 “map<char,int> mp”,然后就可以通过 mp['c'] 的方式来访问它对应的元素，如 mp['c'] = 124。
② 通过迭代器访问，先做如下定义：
map<typename1,typename2>::iterator it;
因为 map 的每一对映射都有两个typename，所以使用 “it->first”来访问键，而使用 “it->second”来访问值。例如：
#include<bits/stdc++.h>
using namespace std;
int main(){
map<char,int> mp;
mp['m'] = 20;
mp['r'] = 30;
mp['a'] = 40;
for(map<char,int>::iterator it = mp.begin(); it != mp.end();it++){
cout<<it->first<<" "<<it->second<<endl;
}
return 0;
}
程序输出如下：
a 40
m 20
r 30
可以看出，map在建立映射的同时，会自动实现按照键从小到大排序。这是因为map内部是使用“红黑树”实现的（set也是）。
从c++更新以来，有了新的关键字 auto，也可以实现 map 遍历。
注意：dev-c++编译时默认使用的是C98标准，所以才会出错，如需支持C11标准，只需在编译选项中修改配置参数。
在编译器下面的编译时加入以下命令前打勾，并在输入框内，输入-std=c++11。即可。
#include<bits/stdc++.h>
using namespace std;
int main(){
map<char,int> mp;
mp['m'] = 20;
mp['r'] = 30;
mp['a'] = 40;
for(auto i:mp){
cout<<i.first<<" "<<i.second<<endl;
}
return 0;
}
Ⅲ. map的常用函数
map的常用函数有find、size、erase、clear、count等。
① find() 和 size()
find(key)是返回键为key的映射的迭代器，时间复杂度为O(logN)，N为map中映射的对数。size()用来获得map中映射的对数，时间复杂度为O(1)。例如，以下一段代码输出“3 b 30”。
#include<bits/stdc++.h>
using namespace std;
int main(){
map<char,int> mp;
mp['a'] = 20;
mp['b'] = 30;
mp['c'] = 40;
printf("%d ",mp.size());
map<char,int>::iterator it = mp.find('b');
printf("%c %d",it->first,it->second);
return 0;
}
② erase( )
erase( )可以删除单个元素，也可以删除一个区间内的所有元素。删除单个元素可以使用erase(it)，其中it是为要删除的元素的迭代器，时间复杂度是O(1)。也可以使用erase(key)，其中key为要删除的映射的键，时间复杂度为O(logN)。例如，以下一段代码输出“a 20 c 40”。
#include<bits/stdc++.h>
using namespace std;
int main(){
map<char,int> mp;
mp['a'] = 20;
mp['b'] = 30;
mp['c'] = 40;
map<char,int>::iterator it = mp.find('b');
mp.erase(it);//或者把两句语句改成mp.erase('b');总的时间复杂度一样。
for(map<char,int>::iterator it = mp.begin();it != mp.end();it++)
printf("%c %d ",it->first,it->second);
return 0;
}
删除一个区间内的所有元素用erase(first,last)。其中，first为区间的起始迭代器；last为区间的末尾迭代器的下一个地址，也就是左闭右开的区间[first,last]。其中时间复杂度为O(last-first)。
例如，以下一段代码输出“a 20”。
#include<bits/stdc++.h>
using namespace std;
int main(){
map<char,int> mp;
mp['a'] = 20;
mp['b'] = 30;
mp['c'] = 40;
map<char,int>::iterator it = mp.find('b');
mp.erase(it,mp.end());
for(map<char,int>::iterator it = mp.begin();it != mp.end();it++)
printf("%c %d ",it->first,it->second);
return 0;
}
③ clear()
clear()用来清空map,时间复杂度为O(n)。
④ count(key)
由于map不包含重复的key，因此m.count(key)取值为0，或者1，表示是否包含。
在map中，由key查找value时，首先要判断map中是否包含key。
如果不检查，直接返回map[key]，可能会出现意想不到的行为。如果map包含key，没有问题，如果map不包含key，使用下标有一个危险的副作用，会在map中插入一个key的元素，value取默认值，返回value。也就是说，map[key]不可能返回null。