map翻译为映射:也是常用的STL容器。众所周知，在定义数组时(如int array[100] )其实是定义了个从 int 型到 int 型的映射，比如array[0]=25 array[4]= 36就分别是将0射到25、将4映射到36.。一个double型数组则是将int 型映射到double型，例db[0]=3.14,db[1]=0.01。但是，无论是什么类型，它总是将int 型映射到其他类型。这似乎表现出一个弊端:当需要以其他类型作为关键字来做映射时，会显得不太方便。 例如有一本字典， 上面提供了很多的字符串和对应的页码，如果要用数组来表示“字符串-页码”这样的对应关系，就会感觉不太好操作。这时，就可以用到map,因为map可以将任何基本类型(包括STL 容器)映射到任何基本类型(包括STL容器)，也就可以建立string型到int型的映射。
还可以来看一个情况:这次需要判断给定的一些数字 在某个文件中是否出现过。按照正常的思路，可以开一个bool型hashTable[max size], 通过判断hashTable[x]为true还是false 来确定x是否在文件中出现。但是这会碰到一个问题，如果这些数字很大(例如有几千位)，那么这个数组就会开不了。而这时map就可以派上用场，因为可以把这些数字当成一些字符串，然后建立sring至int 的映射(或是直接建立int至int的映射)。

需要的头文件：

#include<map>

需要的其他东西:

using namespace std;

map的定义

单独定义一个map:

map<typename1, typename2> mp;

map和其他STL容器在定义上有点不一样，因为map需要确定映射前类型(键key)和映射后类型(值 value ),所以需要在<>内填写两个类型，其中第一个是键的类型，第二个是值的类型。如果是int型映射到int型，就相当于是普通的int型数组。
而如果是字符串到整型的映射，必须使用string而不能用char数组:

map<string , int > mp;

这是因为char数组作为数组，是不能作为键值的。如果想用字符串做映射，必须用string。
map的键和值也可以是STL容器，例如可以将一个set容器映射到一个字符串:

map<set<int>,string> mp;

map容器内元素的访问

map一般有两种方式访问: 通过下标访问或通过迭代器访问。下面分别讨论这两种访问方式。
(1)通过下标访问
和访问普通的数组是一样的，例如对一个定义为map<char , int > mp的 map来说,就可以直接使用mp[ ’ c ’ ] 的方式
来访问它对应的整数。于是，当建立映射时，就可以直接使用mp[ ‘c’ ]=20这样和普通数组一样的方式。
但是要注意的是，map中的键是唯一的，也就是说，下面的代码将输出30:

(2)通过迭代器访问
map迭代器的定义和其他STL容器迭代器定义的方式相同:

map< typename1 , typename2 >::iterator it;

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

在上面这个例子中，it->first是当前映射的键，it->second是当前映射的值。
你从上图可以发现一个特别有意思的现象：map会以键从小到大的顺序自动排序，即按a<m<r的顺序排列这三对映射。
这是由于map内部是使用红黑树实现的(set也是),在建立映射的过程中会自动实现从小到大的排序功能。

map常用的函数

(1)find()
find(key)返回键为key的映射的迭代器，时间复杂度为O(logN),N为map中映射的个数。

(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中元素的个数。

map的常见用途

• 需要建立字符(或字符串)与整数之间映射的数目，使用map可以减少代码量。
• 判断大整数或者其他类型数据是否存在的题目，可以把map当bool数组使用。
• 字符串和字符串的映射也很有可能会遇到。

延伸:map的键和值是唯一的，而如果一个键需要对应多个值，就只能用multimap。
另外C++11标准中还增加了unordered_map,以散列代替map内部的红黑树实现，
使其可以用来处理只映射而不按key排序的需求，速度要比map要快的多。