上个文章我们学习了STL关联式容器——set的使用，本篇文章我们将介绍另一组关联式容器map。

关于关联式容器和键值对的概念在上篇文有讲到 ->键值对。这里不再赘述

一、map的介绍

map 的底层也是基于红黑树实现的，其内部元素根据键自动升序排列。

• map是关联式容器，它按照特定的次序存储键值对pair（key和值value组成的元素）。
• 键值key和实值value的类型可能不同，在map的内部，key与value通过成员类型 value_type绑定在一起，为其取别名称为pair。
• 在内部，map中的元素总是按照键值key进行比较排序的。
• map容器中元素的键值key不能被修改，但是元素的值value可以被修改

map与set相比区别如下：

存储内容上，set 存储键，map 存储键值对（ pair 类型）；

元素访问上，set 仅支持访问键，map 则可通过键访问对应值，且值支持修改。

二、map的使用

构造函数

主要有以下三种构造：

// 构造一个key为string类型，value为int类型的空容器
map<string, int> m1;

// 拷贝构造key为string类型，value为int类型的m1容器的复制品
map<string, int> m2(m1); 

// 使用迭代器拷贝构造m2容器某段区间的复制品
map<string, int> m3(m2.begin(), m2.end());

insert

将对应的键值对直接插入进去（会按照搜索的规则到达相应的位置），并返回一个 pair<iterator,bool>，跟set是一样的，bool是用来判断插入成功或者失败，因为map也是不支持键值冗余的。

每个插入的键值对都是pair的匿名构造，为了提高效率，c++中提供了一个make_pair的接口

这是几种常用元素插入方式：

因为 map 中元素的键是唯一的，所以插入操作会检查被插入元素的键是否已经存在，如果存在相等的健值，则不插入该元素，并返回包含重复键的元素的迭代器（如果该重载函数有返回值）。

第一个重载函数（单个元素插入）的返回值：是一个 pair

• 当插入成功时，pair 的第一个元素是指向新元素的迭代器，第二个元素是 true；
• 当因有重复键而插入失败时，pair 的第一个元素是指向包含重复键的元素的迭代器，第二个元素是 false。

erase

下面是指定位置迭代器删除和指定元素删除

重载operator[ ]

operator[]在map里实现的功能很强大。可以快速实现插入或修改功能。

调用[]等同于调用这个：

(*((this->insert(make_pair(k,mapped_type()))).first))

分布解析如下

1. this->insert(make_pair(k, mapped_type())):
   1. this 指针指向当前对象。
   2. insert 是当前对象的一个成员函数。
   3. make_pair (k, mapped_type ()) 创建了一个键值对，其中 k 是键，mapped_type () 是默认构造的值。
   4. insert 函数将这个键值对插入到当前对象中，并返回一个 pair，其中 first 是一个迭代器，指向插入的键值对，second 是一个布尔值，表示插入是否成功。
2. (this->insert(make_pair(k, mapped_type()))).first:
   1. 从 insert 函数返回的 pair 中取出 first，即指向插入的键值对的迭代器。
3. *((this->insert(make_pair(k, mapped_type()))).first):
   1. 对迭代器进行解引用，得到插入的键值对。
4. (*((this->insert(make_pair(k, mapped_type()))).first)).second:
   1. 从解引用的键值对中取出 second，即插入的值。

实际上就是这三步：

1. 调用 insert 函数插入键值对。
2. 拿出从 insert 函数获取到的迭代器。
3. 返回该迭代器位置元素的值 value。

对应分解代码如下：

mapped_type& operator[] (const key_type& k)
{
	//1、调用insert函数插入键值对
	pair<iterator, bool> ret = insert(make_pair(k, mapped_type()));
	//2、拿出从insert函数获取到的迭代器
	iterator it = ret.first;
	//3、返回该迭代器位置元素的值value
	return it->second;
}

operator[]的本质：给[]一个Key，如果存在，就返回Key对应val的引用。如果不存在，就插入Key，然后val给的是缺省值(string缺省值就是"") 。

下面是一个举例：

遍历

不能直接对迭代器解引用，因为里面有两个值。

可以范围for传引用访问。

三、multimap

multimap 容器与 map 容器的底层实现一样，都是平衡搜索树（红黑树），其次两者所提供的成员函数的接口都是基本一致的

唯一的不同点是multimap 允许键值冗余，即 multimap 容器当中存储的元素是可以重复的。

multimap没有重载[]，所以只能使用insert。multimap不能重载[]，因为已经允许冗余了，如果key有多个，就不知道返回哪个key对应的val。

void test()
{
	//是否插入看的是key,不是value
 
	//multimap支持key冗余,无论value是否一样
	multimap<int, string> mul_map;
	mul_map.insert({ 1, "Hello" });
	mul_map.insert({ 1, "Hi" });
	mul_map.insert({ 2,"Hehe" });
	mul_map.insert({ 3,"nice" });
	mul_map.insert({ 3,"nice" });
	

	cout << "multimap:" << endl;
	for (const auto& e : mul_map)
	{
		cout << e.first << " " << e.second << endl;
	}
}

由于 multimap 容器允许键值冗余，因此两个容器中成员函数 find 和 count 的意义也有所不同：

成员函数 find	功能
map 对象	返回值是键值为 key 的元素的迭代器
multimap 对象	返回底层搜索树中序的第一个键值为 key 的元素的迭代器

成员函数 count	功能
map 对象	键值为 key 的元素存在则返回 1，不存在则返回 0（find 成员函数可代替）
multimap 对象	返回键值为 key 的元素个数（find 成员函数不可代替）