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
❌ [ 勘误 ] /* 暂无 */
📜 [ 声明 ] 由于作者水平有限，本文有错误和不准确之处在所难免，
本人也很想知道这些错误，恳望读者批评指正！| 📜 参考资料 C++reference[EB/OL]. []. http://www.cplusplus.com/reference/. Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. . 百度百科[EB/OL]. []. https://baike.baidu.com/. 比特科技. C++[EB/OL]. 2021[2021.8.31]. |
文章出处登录后可见！
