map翻译为映射，map可以将任何基本类型（包括STL容器）映射到任何基本类型（包括STL容器）。

头文件：

#include<map>

1、map的定义

map<typemname1,typename2> mp;

map和其他STL容器在定义上有点不一样，因为map需要确定映射前类型（键key）和映射后类型（值value），所以需要在<>内填写两个类型，其中一个是键的类型，第二个是值的类型。如果是int型映射到int型，就相当于是普通的int型数组。

而如果是字符串到整型的映射，必须使用string而不能用char数组：

map<string,int> mp;

map的键和值也可以是STL容器，例如可以将一个set容器映射到一个字符串：

map<set<int>,string> mp;

2、map容器内元素的访问

map一般有两种访问方式：通过下标访问或通过迭代器访问。

（1）通过下标访问

和访问普通的数组是一样的，例如对一个定义为map<char,int> mp的map来说，就可以直接使用mp[‘c’]的方式来访问它对应的整数。于是，当建立映射时，就可以直接使用mp[‘c’]=20这样和普通数组一样的方式。但是要注意的是，map种的键是唯一的。

#include <iostream>
#include<map>
using namespace std;

int main() {
    map<char, int> mp;
    mp['c'] = 20;
    mp['c'] = 30;//20被覆盖
    printf("%d\n", mp['c']);//输出30
}

（2）通过迭代器访问

map迭代器的定义和其他STL容器迭代器定义的方式相同：

map<typename1,typename2>::iterator it;

map迭代器的使用方式和其他STL容器的迭代器不同，因为map的每一对映射都有两个typename，这决定了必须能通过一个it来同时访问键和值。事实上，map可以使用it->first来访问键，使用it->second来访问值。

#include<iostream> 
#include<map>

map会以键从小到大的顺序自动排序，即按照a<m<r的顺序排列这三对映射。这是由于map内部是使用红黑树实现的（set也是），在建立映射的过程种会自动实现从小到大的排序功能。

3、map常用函数实例解析

（1）find()

find(key)返回键为key的映射的迭代器，时间复杂度为O(logN)，N为map中映射的个数。如果未找到，它返回一个指向map末尾的迭代器，即map :: end()。

（2）erase()

erase()有两种用法：删除单个元素、删除一个区间内的所有元素。

①删除单个元素

删除单个元素有两种方法：

• mp.erase(it)，it为需要删除的元素的迭代器。时间复杂度为O(1)。
• mp.erase(key)，key为欲删除的映射的键。时间复杂度为O(logN)，N为map内元素的个数。

②删除一个区间内的所有元素。

mp.erase(first,last)，其中first为需要删除的区间的起始迭代器，而last则为需要删除的区间的末尾迭代器的下一个地址，也即为删除左闭右开的区间[first,last)。时间复杂度为O(last-first)。

（3）size()

size()用来获得map中映射的对数，时间复杂度为O(1)。

（4）clear()

clear()用来清空map中的所有元素，复杂度为O(N),其中N为map中元素的个数。

#include<iostream>
#include<map>
using namespace std;

int main() {
	map<char, int> mp;
	mp['a'] = 1;
	mp['b'] = 2;
	mp['c'] = 3;
	map<char, int>::iterator it = mp.find('b');
	printf("%c %d\n", it->first, it->second);//输出结果:b 2
	mp.erase(it);//删除b 2
	mp['b'] = 2;
	mp.erase('b');//删除键为b的映射，即b 2
	mp['b'] = 2;
	mp.erase(it, mp.end());//删除it之后的所有映射，即b 2和c 3
	mp['b'] = 2;
	mp['c'] = 3;
	printf("%d\n", mp.size());//3对映射
	mp.clear();//清空map
}