一、map 的介绍 

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

 

二、map 的定义

map 需要确定映射前类型（键 key）和映射后类型（值 value），所以需要在 <> 内填写两个类型，其中第一个是键的类型，第二个是值的类型。

map<typename1,typename2> mp;

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

map<string,int> mp;

map<set<int>,string> mp;

 

三、map 中内容的访问
 

（1）通过下标访问

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

注意： map 中的键是唯一的。

#include <stdio.h>
#include <map>
using namespace std;

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

 

（2）通过迭代器访问

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

map<typename1,typename2>：：iterator it；

typename1 和 typename2 就是定义 map 时填写的类型，这样就得到了迭代器 it 。

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

#include <stdio.h>
#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++)
	{
		printf("%c %d\n", it->first, it->second);
	}
	return 0;
}

map 会以键从小到大的顺序自动排序。这是由于 map 内部是使用红黑树实现的（set 也是），在建立映射的过程中会自动实现从小到大的排序功能。

 

四、map 常用函数实例解析

 

（1）  find ( )

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

#include <stdio.h>
#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);
	return 0;
}

 

（2）erase()

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

（1）mp.erase(it) 用于删除单个元素，it 为需要删除的元素的迭代器。时间复杂度为 O（1）。

#include <stdio.h>
#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');
	mp.erase(it);   // 删除 b 2
	for (map<char, int>::iterator it = mp.begin(); it != mp.end(); it++)
	{
		printf("%c %d\n", it->first, it->second);
	}
	return 0;
}

（2）mp.erase(key) 用于删除单个元素，key 为需要删除的映射的键。时间复杂度为 O（logN），N 为 map 内元素的个数。

#include <stdio.h>
#include <map>
using namespace std;

int  main()
{
	map<char, int> mp;
	mp['a'] = 1;
	mp['b'] = 2;   
	mp['c'] = 3;
	mp.erase('b');   // 删除键为 b 的映射，即 b 2
	for (map<char, int>::iterator it = mp.begin(); it != mp.end(); it++)
	{
		printf("%c %d\n", it->first, it->second);
	}
	return 0;
}

 

2.  删除一个区间内的所有元素：

mp.erase(first,last) 即删除 [first,last) 内的所有元素。其中 first 为所需要删除区间的起始迭代器，而 last 则为所需要删除区间的末尾迭代器的下一个地址。时间复杂度为 O（last-first）。

#include <stdio.h>
#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');  //令 it 指向键为 b 的映射
	mp.erase(it,mp.end());   // 删除 it 之后的所有映射，即 b 2 和 c 3
	for (map<char, int>::iterator it = mp.begin(); it != mp.end(); it++)
	{
		printf("%c %d\n", it->first, it->second);
	}
	return 0;
}

 

 

（3）size()

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

mp.size()

 

（4）clear()

clear() 用以清空 map 中的所有元素，时间复杂度为 O（N），其中 N 为 map 中元素的个数。

mp.clear()

#include <stdio.h>
#include <map>
using namespace std;

int  main()
{
	map<char, int> mp;
	mp['a'] = 1;
	mp['b'] = 2;   
	mp['c'] = 3;
	printf("%d\n", mp.size());
	mp.clear();
	printf("%d\n", mp.size());
	return 0;
}

 

五、vector的常见用途
 

（1）需要建立字符（或字符串）与整数之间映射的题目，使用 map 可以减少代码量。

（2）判断大整数或者其他类型数据是否存在的题目，可以把 map 当 bool 数组用。

（3）字符串和字符串的映射也有可能会遇到。

 

map 的键和值是唯一的，而如果一个键需要对应多个值，就只能用 multimap。

unordered_map 以散列代替 map 内部的红黑树实现，使其可以用来处理只映射而不按 key 排序的需求，速度比 map 要快得多。