在编程过程中，如果需要建立字符(或者字符串)与整数之间的映射;判断大整数或者其他类型数据是否存在;甚至是字符串和字符串之间的映射。此时我们应当想到map，因为map可以将任何基本类型(包括STL容器)映射到任何基本类型(包括STL容器)。map和其他的STL容器有点不一样，因为map需要确定映射前类型(键key)和映射后类型(值value),所以需要在<>内填写两个类型。需要注意的是:map中的键是唯一的，而且map会以键从小到大的顺序自动排序(这是由于map内部是使用红黑树实现的，set也是，在建立映射的过程中会自动实现从小到大的排序功能)。如果需要使用map，必须包含头文件#include
1、map的定义:map<typename1,typename2> name;例如:
map<string,int> name;//如果是字符串到整型的映射，必须使用string而不能用char数组
map<set<int>,string> name;//将一个set容器映射到一个字符串
2、map容器内元素的访问
(1)通过下标访问，例如：一个定义为map<char,int> name的map来说，可以直接使用name['c']来访问对应的整数。
(2)通过迭代器访问,其定义是:map<typename1,typename2>::iterator it;但map迭代器的使用方式和其他STL容器的迭代器不同,因为map的每一对映射都有两个typename,此时我们可以使用it->first来访问键，使用it->second来访问值。
#include<stdio.h>
#include<iostream>
#include<map>
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;
}
return 0;
}
上述程序中出现了去a的首地址的begin()函数,那么就不得不提到end()函数。与begin()函数不同的是,end()函数作为迭代器的末尾标志,取的是尾元素地址的下一个地址,不存储任何元素。
另外,map的迭代器不支持it<a.end()的写法,因此循环条件只能用it!=a.end()。除此之外,迭代器还实现了两种自加操作:it++和++it(自减操作同理)。
3、map常用的函数
(1)find(key):用以返回键为key的映射的迭代器，时间复杂度为O(logN)。map<char,int>::iterator it=mp.find('b')
(2)size():用来获得map中映射的对数，时间复杂度为O(1)。
(3)clear():用来清空map中的所有元素，时间复杂度为O(N)。
(4)erase():有两种用法:删除单个元素,删除一个区间内的所有元素。删除单个元素有两种用法:mp.erase(it),it位所需要删除元素的迭代器,时间复杂度O(1);mp.erase(key),key为欲删除的映射的键,时间复杂度为O(logN)。删除一个区间内的所有元素:mp.erase(first,last),first为起始迭代器,而last为删除区间的末尾迭代器的下一个地址。时间复杂度为O(last-first)。
