【C++】关联容器探秘：Map与Multimap详解

1.映射类 map

0. 引入 pair：

1.定义

2.插入

3. 遍历

4.❗operator[]的实现

5. 插入

运用

2.Multimap 类

0. 引入：不去重的 Multi

1. Multimap 不支持 Operator[]

2. Multimap 的删除

1.映射类 map

0. 引入 pair：

在C++中，std::pair是一个非常有用的容器适配器，它属于C++标准模板库(STL)的一部分，主要用于存储两个相关联的数据项。std::pair的设计目的是为了方便地处理需要成对出现的数据，比如坐标点(x, y)、键值对(key, value)等。

std::pair由<utility>头文件提供，它包含两个成员，分别是first和second，这两个成员可以是任意类型的组合。std::pair的声明语法如下：

#include <utility> // 包含std::pair的定义std::pair<Type1, Type2> myPair;

其中，Type1和Type2是你想要存储的两种类型。

创建pair实例

可以通过构造函数直接初始化std::pair：

std::pair<int, double> p1(1, 2.5);

也可以使用std::make_pair函数：

std::pair<int, double> p2 = std::make_pair(1, 2.5);

访问pair成员

std::pair的成员first和second可以直接访问：

std::pair<int, double> p(1, 2.5);
int x = p.first;
double y = p.second;

pair的比较

std::pair可以进行比较，比较规则首先比较first成员，如果first相等，则比较second成员。这使得std::pair可以用于std::map和std::set等容器中的键值对。

示例

下面是一个使用std::pair的简单示例：

#include <iostream>
#include <utility> // 包含std::pair的定义int main() {std::pair<std::string, int> studentGrade("Alice", 90);std::cout << "Student: " << studentGrade.first << ", Grade: " << studentGrade.second << std::endl;std::pair<std::string, int> studentGradeB("Student:Bob", 85);if (studentGradeA.second > studentGradeB.second) {std::cout << "Alice has a higher grade than Bob." << std::endl;
}return 0;
}

在这个示例中，我们创建了一个std::pair实例，存储了学生的名字和成绩，然后比较了两个学生的成绩。

1.定义

key 通常用于排序和唯一地标识元素，value 中存储与 key 关联的内容。

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

Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)

Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

2.插入

例如简单实现一个字典，我们可以有四种插入方法：

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

② 可以用匿名对象的方式来写

③ 调用神奇的 make_pair

④ 直接用 { }

std::map<std::string, std::string> dict;std::pair<std::string, std::string> kv1("insert", "插入");// 传参的四种实现dict.insert(std::pair<std::string, std::string>("sort", "排序")); // 方法一dict.insert(kv1); // 方法二// C++98dict.insert(std::make_pair("string", "字符串")); // 方法三// C++11 多参数的构造函数隐式类型转换// 最常用的dict.insert({ "erase", "删除" }); // 方法四// 输出字典的内容以验证是否插入成功for (const auto& item : dict) {std::cout << "Key: " << item.first << ", Value: " << item.second << std::endl;}

运行：

对于方法四中存在的隐式类型转化:

// 隐式类型的转换string str1 = "hello";A aa1 = { 1, 2 };pair<string, string> kv2 = { "string", "字符串" };
}

3. 遍历

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

map<string, string>::iterator it = dict.begin();
//有请auto
auto it=dict.begin();

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

有问题就有解决方法：使用 it-> 中分别提取 first 和 second

//map<string, string>::iterator it = dict.begin();//迭代器返回pair指针auto it = dict.begin();while (it != dict.end()){//it->first = "xxx";//it->second = "xxx";//cout << (*it).first << ":" << (*it).second << endl;cout << it->first << ":" << it->second << endl;//结构体指针调用++it;}cout << endl;

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

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

4.`❗operator[]`的实现

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

判断 pair 的 first 就是 map 的迭代器即指针类型 , map 指针->second 实现计数

key 已经在树里面，返回 pair<树里面 key 所在节点的 iterator, false>
key 不在树里面，返回 pair <新插入 key 所在节点的 iterator, true>

5. 插入

注意：

// 不插入，不覆盖；插入过程中，只比较key，value是相同无所谓// key已经有了就不插入了dict.insert(make_pair("insert", "xxxx"));

测试：

void test_map4()
{map<string, string> dict;dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("insert", "插入"));cout << dict["sort"] << endl; // 查找和读dict["map"];                  // 插入,返回1dict["map"] = "映射,地图";     // 修改dict["insert"] = "xxx";       // 修改dict["set"] = "集合";         // 插入+修改
}

运用

统计次数：例如说我们要计数如下动物：

"兔子", "大象", "兔子", "长颈鹿", "狮子", "猴子",
"大象", "兔子", "猴子", "猴子", "大象", "斑马",
"狮子", "猴子", "长颈鹿", "兔子", "斑马", "猴子"

我们可以这么写

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

这里实际上可以让 insert 来优化一下

我们可以看到 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)); 
}

所以我们写一个判断，判断 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++;}
}

实际运用中这两种方法我们几乎都不用，因为会有更好的方法，语言之父已经帮我们迭代过啦

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

根据上面我们可以知道，底层返回的实现

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

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

然后这个地方的使用不仅联想到了 hash ，讲个题外的知识点，将两者做个比较：

std::map和std::unordered_map（通常称为hash map）是C++标准库中提供的两种关联容器，它们的主要区别在于内部实现和性能特征上。

`std::map`

内部实现：std::map使用红黑树（一种自平衡的二叉搜索树）作为底层数据结构。这意味着它的键值对是有序的，按照键的自然顺序或由比较器定义的顺序排列。
查找、插入和删除的时间复杂度：对于std::map，这些操作的时间复杂度为O(log n)，其中n是容器中的元素数量。这是因为每次操作都需要在树中移动log n的距离。
迭代：由于std::map保持了键的排序，因此迭代访问元素时可以按照键的顺序进行，这对于需要排序访问的场景非常有用。

`std::unordered_map`

内部实现：std::unordered_map使用哈希表作为底层数据结构。它将键映射到哈希表中的位置，理想情况下，不同的键将映射到不同的位置，从而允许快速查找。
查找、插入和删除的时间复杂度：平均而言，std::unordered_map的查找、插入和删除操作的时间复杂度为O(1)，即常数时间。但在最坏的情况下，如果哈希冲突频繁发生，这些操作可能退化到线性时间复杂度O(n)。
迭代：std::unordered_map不保证元素的顺序，因此迭代访问元素时，元素的顺序可能是任意的，这取决于哈希函数和哈希表的实现。

总结

当你需要键值对保持排序时，使用std::map。
当你需要快速查找而不关心键值对的顺序时，使用std::unordered_map。
std::map在查找、插入和删除操作上的性能随着容器大小的增长而增长（对数时间复杂度），而std::unordered_map在平均情况下的性能通常是常数时间，但对于特定的输入数据可能会退化。

选择使用哪种容器应基于你的具体需求：是否需要排序、预期的性能、以及对最坏情况性能的考虑。

2.Multimap 类

0. 引入：不去重的 Multi

背景：对于一词多义的情况，例如单词 "left" 可以表示 "左边" 和 "剩余"，需要存储同一个键的多个值。
解决方案：使用 multimap 类，类似于 multiset，它允许存储具有相同键的多个值，但仍然保持排序。

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

特性：在 map 中，重复插入相同键的元素会导致失败，而在 multimap 中，相同键的多次插入均会成功。

1. Multimap 不支持 Operator[]

原因：multimap 允许多个键值对拥有相同的键，因此它不支持通过 operator[] 直接访问元素，因为该操作符假定键是唯一的。

int main() {multimap<int, std::string> myMultimap;myMultimap.insert(make_pair(1, "apple"));myMultimap.insert(make_pair(1, "apricot"));// myMultimap[1]; // 错误，因为无法确定返回哪个值
}

替代方案：使用迭代器遍历或 equal_range 函数来获取相同键的值范围。

equal_range 是 C++ 标准库中的一个函数模板，主要用于在有序容器（如 set, map, vector 等）中查找一个值的范围。它返回一对迭代器，表示要查找值在容器中第一次出现的位置所在指针（迭代器）和最后一次出现的位置指针。

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

2. Multimap 的删除

方法：使用 erase 函数可以删除指定键的元素，例如删除所有键为 1 的元素。

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