⚡【C++要笑着学】(31) 映射类：map 类 | pair 类型 (value_type) | map 的插入和遍历 | map 的 operator[] | multimap 类

   C++ 表情包趣味教程 👉 《C++要笑着学》

• 💭 写在前面：本章我们继续讲解 STL，讲解 STL 的 map 类。我们将详细介绍 map 类的基础概念，包括 pair 类型（value_type）的应用和插入元素的方法。随后，我们将深入研究 Map 的遍历方式以及统计元素出现次数的几种方式。最后我们再简单介绍一下不去重版本的 multimap，建议通过查看官方文档的方式辅助学习。

目录

Ⅰ. Map 类

0x00 引入：Map 的介绍

0x01 pair 类型（value_type）

0x02 map 的插入（insert）

0x03 map 的遍历

0x04 统计次数的方式

0x05 map::operator[]

Ⅱ. multimap 类

0x00 引入：不去重的 multi

0x01 multimap 不支持 operator[]

0x02 mutimap 的删除

Ⅰ. Map 类

0x00 引入：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 通常用于排序和唯一地标识元素，value 中存储与 key 关联的内容。

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

 value_type 实际上就是 pair 类型：

typedef pair value_type;

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

map 通常被实现为二叉搜索树，更准确地说是平衡二叉搜索树（红黑树）。

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

map 还支持下标访问符，在 [ ] 中放入 key，就可以找到与 key 对应的 value，我们下面会细说。

0x01 pair 类型（value_type）

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) 
	{}
};

实际上 pair 的定义远没有我们想象中的复杂，里面就定义了一个 first 和一个 second。

0x02 map 的插入（insert）

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

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

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

② 似乎比较麻烦？我们可以用匿名对象的方式来写：

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

这就体现了匿名对象的优势了，这里调用 pair 的构造函数来构造一块这样的对象出来。

③ 还有更爽的方式，调用神奇的 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) );
}

• 🔑 分析：可以看到，自动推导出参数类型的同时也构造出 pair 的匿名对象并返回，并且还会推举为 inline。本质上其实还是调用 pair 的构造函数，只是它把推导参数的任务交给了编译器去完成。

④ 还有更强大的方式插入，直接用 { } ：

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

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

再上一章讲解 set 的示例中我们也用到了这一方法：

set<int> s = {4, 2, 4, 6, 1, 0};

（我们将在后续讲解 C++11 时作详细解释）

❓ 推荐使用什么方式进行插入？

• 推荐使用匿名对象或 make_pair 的方式进行插入，个人还是更喜欢用 make_pair 的方式。

0x03 map 的遍历

和其他容器的迭代器一样，加上 :: 小尾巴后就可以召唤出属于 map 的迭代器了：

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

map 的迭代器的底层相似于链表的迭代器。这里的类型真的是很长，写起来很费劲……

让我们掌声有请 auto 关键字：

auto it = dict.begin();

下面我们来写遍历部分，我们发现似乎不行：

当然不行！本质上是因为 C++ 不支持一次返回两个值，这里的 * 就是 it->operator*() 。

但是可以打包，我们可以把这些返回值打包成一个结构数据 —— pair 

这里返回值需要返回迭代器中节点的数据，节点的数据是 pair，可惜 pair 并不支持 流 (stream) ：

• error C2679: 二元“<<”: 没有找到接受“std::pair<const std::string,std::string>”类型的右操作数的运算符(或没有可接受的转换)

这里有两种方法，第一种方法就是在 *it 中分别提取 first 和 second：

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

 🚩 运行结果如下：

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

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

对于 map 的手动遍历，个人还是更倾向于使用 -> 的方式。

（但是考虑到向下兼容的情况，还是 *. 更加包容，这个我们下面会探讨一下）

当然，map 同样支持甜甜的 范围 for 来遍历，这里建议加上 & 提效：

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

一般我们将其命名为 ，因为这里我们取到的就是一对对 pair。

0x04 统计次数的方式

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

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

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

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

我们先用 “最老实” 的方式来进行统计，用迭代器进行检查。

检查很简单，如果这个元素在 map 中就 次数++，如果不在就将元素 insert 到 map 中：

map<string, int> count_map;
for (auto& str : arr) {
	map<string, int>::iterator it = count_map.find(str);
	if (it != count_map.end()) {
		it->second++;
	}
	else {
		count_map.insert(make_pair(str, 1);
	}
}

💬 代码演示：我们打印一下看看效果如何

void test_map2() {
	string arr[] = {
		"苹果", "西瓜", "苹果", "香蕉", "草莓", "柠檬",
		"西瓜", "苹果", "柠檬", "柠檬", "西瓜", "橙子",
		"草莓", "柠檬", "香蕉", "苹果", "橙子", "柠檬"
	};

	// 统计
	map<string, int> count_map;
	for (auto& str : arr) {
		map<string, int>::iterator 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;
	}
	cout << endl;
}

🚩 运行结果如下：

实际上这里从树根往下找了两次，第一次是 find 在找，第二次是 insert 再找，有点多余了。

这里实际上可以让 insert 来兼顾 “查找” 的工作，我们来看下 map 的 insert 接口的原型：

std::pair<iterator, bool>insert(const value_type& value);

我们可以看到 insert 的返回值是一个 pair<iterator, bool> 类型。

插入成功， second 就是 true；如果插入失败， second 就是 false。

既然如此，我们就可以这么去迭代：

for (auto& str : arr) {
	pair< map<string, int>::iterator, bool >ret
    = count_map.insert(make_pair(str, 1)); 
}

这个类型是相当的长，pair<map<string, int>::iterator, bool>，不用 auto 简化一下简直没法看：

for (auto& str : arr) {
	auto ret = count_map.insert(make_pair(str, 1)); 
}

• 插入成功的情况：说明这个 “水果” 第一次出现
• 插入失败的情况：说明这个 “水果” 已经有了，insert 又充当了 find 的作用

所以我们写一个判断，判断 second (bool) 是不是 false，如果是就让统计 次数++。

💬 代码演示：

map<string, int> count_map;
for (auto& str : arr) {
	auto ret = count_map.insert(make_pair(str, 1)); 
	if (ret.second == false) {
		ret.first->second++;
	}
}

🚩 运行结果如下：

• 🔑 解读：ret.first->second++ 不好理解？实际上这里是两个 pair 嵌套在一块的！一个 pair 是 insert 的返回值，一个 pair 是节点。insert 的返回值里是 pair<iterator, int>，其中第一个是迭代器，所以我们取 first。而迭代器里是节点 pair<string, int> ，我们要让次数 +1，所以我们节点里我们取 second。

这种方法相较于第一种 find + insert 的方法有一点点效率上的优势，但是属实是微乎其微：

实际运用中这两种方法我们几乎都不用，因为有更加🐂🍺的方式！非常恐怖的方式！

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

我嘞个豆！只需要用一个 operator[] 再 ++ 就搞定了？！

0x05 map::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 类

0x00 引入：不去重的 multi

一词多义的情况，比如 left 这个单词，我们同时想记录它的 “左边” 和 “剩余” 这两个意思。

这时我们就可以使用 multimap 类，和 multiset 一样，只排序不去重。

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

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

• multimap 允许在容器中存储多个具有相同键的元素，这使得它成为处理具有相同键的多个值的理想选择。每个元素是一个键-值对，键用于按顺序组织元素，而值则是与键关联的实际数据。

0x01 multimap 不支持 operator[]

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

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

 存在多个相同键对应的值，无法明确确定要返回哪个值：

int main(void) 
{
    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;
}

这样可以处理具有相同键的多个元素的情况了。

0x02 mutimap 的删除

使用 erase 函数可以删除指定键的元素，。比如下面这样就会删除所有键为 1 的元素。

mmap.erase(1);   // 删除所有键为1的元素

📌 [ 笔者 ]   王亦优
📃 [ 更新 ]   2023.12.20
❌ [ 勘误 ]   /* 暂无 */
📜 [ 声明 ]   由于作者水平有限，本文有错误和不准确之处在所难免，
              本人也很想知道这些错误，恳望读者批评指正！