二十四、映射类

Ⅰ . Map 类

01 Map 的介绍

template <class Key,   // map::key_type
          class T,     // map::mapped_type
          class Compare = less<Key>,    // map::key_compare
          class Alloc = allocator<pair<const Key, T>>  // map::allocator_type
          > class map;

STL 的 map 是关联容器，按照特定顺序存储关联，由键和值组成键值对，key 通常用于排序和唯一地标识元素，value 中存储与 key 关联的内容。

key 和 value 的类型可以不同，在 map 内部，key 和 value 通过成员类型 value_type 绑定。

value_type 实际上就是 pair 类型

typedef pair value_type;

底层基于红黑树，是一种自平衡的二叉搜索树，能确保在插入和删除元素时维持良好的性能。

map 通常被实现为二叉搜索树，更准确的说是平衡二叉搜索树。

在内部，map 中的元素按照 key 进行比较排序的。

map 还支持下标访问。

02 pair 类型

map 的 insert 接口就是一个 value_type ，我们先弄明白什么是 value_type。

value_type 实际上就是 pair 类型，在 map 中称为键值对，定义如下：

typedef pair<const Key, T> value_type;

pair 是在库里面就定义好的， SGI-STL 中关于键值对的定义如下：

template<class T1, class T2>
struct pair {
	typedef T1 fisrt_type;
	typedef T2 second_type;
 
	T1 first;
	T2 second;
	pair() 
		: first(T1())
		, second(T2())
	{}
	pair(const T1& a, const T2& b)
		: first(a)
		, second(b) 
	{}
};

03 map 的插入

我们假设 dict 变量的数据类型为 map<string, string>，我们可以如何插入数据呢？

① 我们可以直接调用 pair 的构造函数来进行插入：

	dict.insert(pair<string, string>("sort", "排序"));

② 我们也可以直接使用匿名对象的方式来写：

	pair<string, string> kv("insert", "插入");
	dict.insert(kv);

③ 我们还可以使用 make_pair ：

	dict.insert(make_pair("left", "左边"));

make_pair 是一个函数模板，使用时不需要声明参数，可以自动推导出对应的类型。

我们来看一下 make_pair 的底层实现：

template<class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y) {
    return (pair<T1, T2>(x, y) );
}

④ 还可以直接使用 {}：

	dict.insert({ "right","右边" });

这得益于 C++ 11 支持类型转换，可以用大括号进行初始化。

04 map 的遍历

map<string, string>::iterator it = dict.begin();

这里的类型实在太长，我们可以使用 auto 关键字来代替：

auto it = dict.begin();

如果按照之前直接解引用的方式来遍历 map 的话，会发现似乎不行。

这是因为本质上 C++ 不支持一次返回两个值，但我们可以把这些返回值打包成一个数据结构---- pair。

这里返回值需要返回迭代器中节点的数据，可惜 pair 不支持流插入和流提取。

这里有两种办法，第一种就是分别提取 first 和 second：

	auto it = dict.begin();
	while (it != dict.end())
	{
		cout << (*it).first << ":" << (*it).second << " ";
		it++;
	}

运行结果如下：

我们看到， map 也是会自动排序的。当然，我们还可以用 -> 操作符：

	auto it = dict.begin();
	while (it != dict.end())
	{
		cout << it->first << ":" << it->second << " ";
		it++;
	}

当然，map 同样支持范围 for 来遍历：

	for (auto& kv : dict)
	{
		cout << kv.first << ":" << kv.second << " ";
	}

05 统计次数

现在我们要统计一些数据，比如统计这些水果出现的次数：

"苹果", "西瓜", "苹果", "香蕉", "草莓", "柠檬"
"西瓜", "苹果", "柠檬", "柠檬", "西瓜", "橙子"
"草莓", "柠檬", "香蕉", "苹果", "橙子", "柠檬"

我们就可以使用 map 来存储，pair 我们使用 string + int 来组合：

map<string, int> count_map;   // 统计水果的个数

我们可以用迭代器进行检查，如果这个元素在 map 中次数++，如果不在就把元素插入到 map 中。

	string arr[] = {
		"苹果", "西瓜", "苹果", "香蕉", "草莓", "柠檬",
		"西瓜", "苹果", "柠檬", "柠檬", "西瓜", "橙子",
		"草莓", "柠檬", "香蕉", "苹果", "橙子", "柠檬"
	};
	map<string, int> count_map;
	for (auto& str : arr)
	{
		auto it = count_map.find(str);
		if (it != count_map.end())
			it->second++;
		else
			count_map.insert(make_pair(str, 1));
	}
	for (auto& kv : count_map)
	{
		cout << kv.first << ":" << kv.second << endl;
	}

运行结果如下：

我们还可以直接使用 operator[] 来实现：

for (auto& str : arr) 
{
	count_map[str]++;
}

06 operator[]

我们先来看看它的底层实现：

mapped_type& operator[] (const key_type& k) 
{
	return (*((this->insert(make_pair(k, mapped_type()))).first)).second;
}

为了清晰一些，我们可以这样拆解：

mapped_type& operator[] (const key_type& k) 
{
	pair<iterator, bool> ret = insert(make_pair(k, mapped_type()));
	// return (*(ret.first)).second;
	return ret.first->second;
}

目的在于关联容器中通过键访问元素，如果元素不存在，则插入一个具有默认值的新元素，并返回对这个元素的引用。首先 const key_type& k 是传入的键，表示要查找或插入的元素的键值。make_pair(k, mapped_type()) 创建了一个 pair 对象，该对象的第一个元素是传入的键 k，第二个元素是使用 mapped_type 的默认构造函数创建的默认值。this->insert(...) 调用关联容器的 insert 函数，该函数用于将一个键-值对插入容器中。返回值是一个 pair，其 first 成员指向插入的元素，second 成员指示是否插入成功。(this->insert(...).first) 获取返回的 std::pair 对象的 first 成员，即指向插入的元素的迭代器。*((this->insert(...).first)) 解引用上一步中获取的迭代器，得到插入的元素。(*((this->insert(...).first)).second 再次解引用，获取插入的元素的 second 成员，即与传入的键关联的值。return (*((this->insert(...).first)).second; 返回通过 operator[] 访问或插入的元素的引用。

我们再来看看神奇的 [] 是怎么实现的：

for (auto& str : arr) 
{
	count_map[str]++;
}

如果是第一次出现，就先插入。插入成功后会返回插入的节点中的次数 0 的引用，对它++后变为 1。如果是第二次插入，插入失败，会返回它所在节点的迭代器的次数，再++。

Ⅱ . multimap 类

01 不去重

对于一个单词，如果我们想同时记录它的两个意思，这时我们就可以使用 multimap 类，和 multiset 一样，只排序不去重。

void test_multimap() 
{
	multimap<string, string> dict;
	dict.insert(make_pair("left", "左边"));
	dict.insert(make_pair("left", "剩余"));
}

这种情况如果是在 map 中，第二次 insert 是会失败的，但在 multimap 中是成功的。

02 不支持 operator[]

map 和 multimap 函数接口差不多，但是 multimap 并不支持 operator[] ！

这也是情理之中的，主要原因是它允许存储相同键的多个元素，主要原因是 multimap 一对多。

int main() 
{
    multimap<int, std::string> myMultimap;
 
    myMultimap.insert(std::make_pair(1, "apple"));
    myMultimap.insert(std::make_pair(1, "apricot"));
    myMultimap.insert(std::make_pair(2, "banana"));
 
    // 下面这行代码会引发问题，因为有两个键为1的元素
    cout << myMultimap[1] << endl;
 
    return 0;
}

这里的 myMultimap[1] 就无法明确地确定返回哪个值，因为有两个键为 1 的元素。因此，multimap 不提供 operator[] 的方式插入。

如果我们想获取 multimap 中特定键的所有值，我们就老老实实用迭代器遍历，或者使用 equal_range 函数来获取键对应的范围：

auto range = myMultimap.equal_range(1);
for (auto it = range.first; it != range.second; ++it) {
    cout << "Value: " << it->second << std;
}