序言：
在之前，我们已经对STL中的 序列式容器 进行了相关的学习。本期，我将给大家介绍的则是另外一类容器 —— 关联式容器 ！！！
（一）容器回顾
在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list 等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？
接下来，我先带大家回顾一下有关容器的一些基本知识，帮助大家唤醒一些“远古”的记忆！
容器可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构，都是模板类：分为顺序容器、关联式容器、容器适配器三种类型，三种类型容器特性分别如下：
💨【顺序容器】
容器并非排序的，元素的插入位置同元素的值无关。包含 vector、deque、list，具体实现原理如下：
（1）vector 头文件
- 动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。
（2）deque 头文件
- 双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成（仅次于vector）。在两端增删元素具有较佳的性能（大部分情况下是常数时间）
（3）list 头文件
- 双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。
💨【关联式容器】
而本期将要介绍的 关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高
元素是排序的；插入任何元素，都按相应的排序规则来确定其位置；在查找时具有非常好的性能；
通常以平衡二叉树的方式实现。包含set、multiset、map、multimap，具体实现原理如下：
（1）set/multiset 头文件
- set 即集合。set中不允许相同元素，multiset中允许存在相同元素。
（2）map/multimap 头文件
- map与set的不同在于map中存放的元素有且仅有两个成员变量，一个名为first,另一个名为second；
- map根据first值对元素从小到大排序，并可快速地根据first来检索元素。
💨【容器适配器】
封装了一些基本的容器，使之具备了新的函数功能，比如把deque封装一下变为一个具有stack功
能的数据结构。这新得到的数据结构就叫适配器。包含stack,queue,priority_queue，具体实现原
理如下：
（1）stack 头文件
- 栈是项的有限序列，并满足序列中被删除、检索和修改的项只能是最进插入序列的项（栈顶的
- 项）；
- 后进先出
（2）queue 头文件
- 队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行；
- 先进先出
（3）priority_queue 头文件
- 优先级队列。内部维持某种有序，然后确保优先级最高的元素总是位于头部。最高优先级元素总是第一个出列
（二）键值对
在C++中，键值对是一种常见的数据结构，它将一个唯一的键与一个值相关联。提供了一种高效的方式来存储和检索数据。该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。
【场景】
比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该单词，在词典中就可以找到与其对应的中文含义.
键值对的定义可以采用不同的数据结构或语法表示，具体取决于所使用的编程语言或数据格式。
以下是一些常见的定义方式：
- C++关联容器示例：
std::map<std::string, int> myMap; myMap["apple"] = 10; myMap["banana"] = 5;
- JSON格式示例：
{ "name": "John", "age": 30, "city": "New York" }
- Python字典示例：
my_dict = {"key1": "value1", "key2": "value2", "key3": "value3"}
- JavaScript对象示例：
var myObject = { key1: "value1", key2: "value2", key3: "value3" };
【说明】
- 在以上示例中，“key1”、“key2"等都是键，对应的"value1”、"value2"等是对应的值；
- 你可以使用键值对来存储、访问和处理各种数据，根据具体编程语言和数据结构的不同，提供了丰富的函数和操作来操作和处理键值对。
而在SGI-STL中关于键值对的定义如下：
template <class T1, class T2> struct pair { typedef T1 first_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) {} };
（三）树形结构的关联式容器
- 根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构；
- 树型结构的关联式容器主要有四种：map、set、multimap、multiset；
- 这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。
下面一依次介绍每一个容器：
1、set
1️⃣基本介绍
- 官方链接如下：set文档介绍
简单点来说 set是按照一定次序存储元素的容器，且set中的元素不可以重复。具体的大家可以参照文档进行相应的学习。
2️⃣set的使用
set的模板参数列表：
【说明】
- T: set中存放元素的类型，实际在底层存储<value, value>的键值对。
- Compare：set中元素默认按照小于来比较
- Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理
接下来，我们简单的来使用下 set：
void test_set1() { set<int> s1; s1.insert(3); s1.insert(1); s1.insert(4); s1.insert(2); s1.insert(1); s1.insert(2); set<int>::iterator it1 = s1.begin(); while (it1 != s1.end()) { cout << *it1 << " "; ++it1; } cout << endl; }
输出展示：
【说明】
- 首先，我们可以使用迭代器对其进行操作；
- 其次，我们验证了上述所说的 set中的元素不可以重复，可以发现结果自动进行了去重的操作
紧接着，此时我们就会想，既然可以使用迭代器，那么我们就可以知道 范围for 也可以使用：
有的小伙伴可能不知道迭代器和范围for的联系，接下来我简单的描述一下：
迭代器 和 范围for循环 都是在 C++ 中用于遍历容器（如数组、向量、映射等）中的元素的工具。它们之间存在联系和互补关系。
- 迭代器：迭代器是一个对象，用于遍历容器中的元素序列。通过迭代器，可以逐个访问容器中的元素，并进行增加、删除、修改等操作。C++ 标准库提供了多种类型的迭代器，如
begin()和end()返回的迭代器可以表示容器的起始和结束位置。迭代器可以使用*运算符来访问当前位置的值，也可以使用++运算符来移动到下一个位置。 - 范围for循环：范围for循环是一种简洁的语法形式，用于遍历容器中的元素。它可以自动处理迭代器的创建和递增，并以一种更直观的方式对容器中的元素进行访问。范围for循环的语法是
for (element : container)，其中element是用于存储当前元素的变量，container是要遍历的容器。在每次循环迭代中，element会被赋值为容器中的下一个元素，直到遍历完所有元素。
迭代器和范围for循环的联系在于，范围for循环在内部使用迭代器来实现对容器的遍历。范围for循环抽象了迭代器的创建和递增过程，使得代码更加简洁和易读。范围for循环适用于大多数情况下对容器进行遍历，并且不需要修改容器中的元素。而当需要更精细的控制和操作时，迭代器提供了更灵活的功能。
紧接着，在文档中介绍了 set中的元素不能在容器中修改。举例来验证一下：
【说明】
- 从上述图片中不难发现在C++的
set容器中，元素不允许直接修改； - set是一个有序的集合容器，它通常基于红黑树实现。红黑树是一种平衡二叉搜索树，用于维护元素的有序性。为了保持树的平衡和有序，set 中的元素在插入时按照特定规则被插入到合适的位置，并且不允许直接修改。
- 具体而言，当你在set 中插入一个元素时，该元素会被自动插入到正确的位置，以保持集合的有序性。红黑树的平衡性是通过左旋、右旋以及颜色调整等操作来维护的。直接修改元素的值可能导致元素位置不再准确，破坏了红黑树的性质，进而影响整个集合的有序性。
- 因此，在set 中，如果你需要修改一个元素，你需要先将该元素从集合中删除，然后再重新插入修改后的值。
【注意】
- 如果你需要对集合中的元素进行频繁的修改操作，可能 set 并不是最适合的容器选择；
- 相应地，可以考虑使用
unordered_set容器，它基于哈希表实现，并提供了快速的查找和修改元素的能力； - 在
unordered_set中，元素的位置是根据哈希函数计算得到的，而不是通过有序性进行维护，因此允许直接修改元素的值。
接下来，再给大家介绍一下关于 查找元素是否存在的操作。
举例：
void test_set2() { set<int> s1; s1.insert(3); s1.insert(1); s1.insert(4); s1.insert(2); s1.insert(1); s1.insert(2); int x; while (cin >> x) { auto ret = s1.find(x); if (ret != s1.end()) { cout << "在" << endl; } else { cout << "不在" << endl; } } }
输出显示：
- 除了上述方法，我们还可以使用 count函数来进行操作。具体如下：
if (s1.count(x)) { cout << "在" << endl; } else { cout << "不在" << endl; }
输出显示：
2、multiset
- 链接如下：Multiple的文档介绍
1️⃣ 基本介绍
multiset 对比 set，multiset是按照特定顺序存储元素的容器，其中元素是可以重复的
2️⃣ multiset的使用
void test_set3() { multiset<int> s1; s1.insert(3); s1.insert(1); s1.insert(4); s1.insert(2); s1.insert(1); s1.insert(2); multiset<int>::iterator it1 = s1.begin(); while (it1 != s1.end()) { cout << *it1 << " "; ++it1; } cout << endl; }
输出显示：
此时，对于在 set中进行的查找操作，在multiset中该如何表现呢？（因此存在重复的情况）
void test_set3() { multiset<int> s1; s1.insert(3); s1.insert(1); s1.insert(4); s1.insert(1); s1.insert(2); s1.insert(1); s1.insert(2); s1.insert(1); multiset<int>::iterator it1 = s1.begin(); while (it1 != s1.end()) { cout << *it1 << " "; ++it1; } cout << endl; // 多个key，find中序的第一个key auto ret = s1.find(1); while (ret != s1.end() && *ret == 1) { cout << *ret << " "; ++ret; } cout << endl; }
输出显示：
【说明】
需要注意的是，multiset 中的元素是按键的自然顺序存储的。当存在多个相同的键时，它们按照插入的顺序存储在容器中。使用 find 方法仅返回指向中序遍历的第一个key，而不能一次性找到所有具有相同键的元素。
其次，除了上述的操作之外，multiset 还可以使用 count函数来统计元素出现的次数：
对于其他的操作，在这里就不做过多的介绍。大家结合文档我相信各位都可以看懂的！！！
3、map
1️⃣基本介绍
- 链接如下：map的使用
【说明】
- 在正式的学习之前，先要了解在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容；
- 键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:
2️⃣ map的使用
【说明】
- key: 键值对中key的类型
- T： 键值对中value的类型
- Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
- Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器
- 注意：在使用map时，需要包含头文件
接下来，我们简单的来使用下 map：
void test_map1() { map<string, string> dict; dict.insert(make_pair("insert", "排序")); dict.insert(make_pair("count", "计数")); dict.insert(make_pair("find", "查找")); dict.insert(make_pair("string", "字符串")); dict.insert(make_pair("swap", "交换")); map<string, string>::iterator dt1 = dict.begin(); while (dt1 != dict.end()) { cout << (*dt1).first << " "; ++dt1; } cout << endl; }
输出显示：
【说明】
请注意，指针形式的输出在实际编码中可能不常见。通常，可以直接访问 std::pair 对象的成员变量，并以合适的方式打印出所需的内容。例如，cout << dt1->first << " "; 与 cout << (*dt1).first << " "; 是等效的。
- 具体如下：
接下来，带大家看个例子，让大家更加深入的理解：
【说明】
- 在 C++ 的
map容器中，每个键（key）都是唯一的。当你尝试插入一个已经存在的键时，插入操作会失败； map是一个关联容器，它按照键的顺序对元素进行排序，并且保持唯一键的特性。当你插入一个新的键值对时，map会自动根据键的顺序将其插入到合适的位置，如果已经存在相同的键，则插入失败。
接下来，我给大家讲一下 operator[] 。首先我先用一下这个，让大家直观的感受：
void test_map2() { string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨" }; map<string, int> countMap; for (auto& e : arr) { countMap[e]++; } for (auto& kv : countMap) { cout << kv.first << ":" << kv.second << endl; } }
输出结果：
接下来，带大家详解这个operator[] ：
【解释】
在给定的代码中，this 是一个指向当前对象的指针（或引用），make_pair(k, mapped_type()) 创建一个键为 k，值为默认构造的 mapped_type 类型对象的 std::pair 对象。接下来，通过调用 insert 方法将这个 std::pair 对象插入到容器中，并获取插入结果的迭代器。
然后，通过解引用和成员访问操作符 .second，(*((this->insert(make_pair(k, mapped_type ()))).first)).second 表达式从插入结果的迭代器中获取对应元素的值。
其实文档给的有一点太复杂了，在这里我给出简化的版本，供大家参考：
V& operator[](const K& key) { pair<iterator, bool> ret = insert(make_pair(key, V())); return ret.first->second; }
接下来，有了上述operator[] 这样的功能，我们就可以使用其进行插入操作了。具体如下:
当我们有这样的代码时：
dict["left"]; // 插入 dict["right"] = "右边"; // 插入+修改 dict["string"] = "(字符串)"; // 修改 cout << dict["string"] << endl; // 查找 cout << dict["string"] << endl; // 查找
输出展示：
接下来，我们通过调试看看：
【总结】
- 1. map中的的元素是键值对
- 2. map中的key是唯一的，并且不能修改
- 3. 默认按照小于的方式对key进行比较
- 4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列
- 5. map的底层为平衡搜索树(红黑树)，查找效率比较高$O(log_2 N)$
- 6. 支持[]操作符，operator[]中实际进行插入查找
4、multimap
1️⃣基本介绍
- 链接如下：multimap的使用
注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以
重复的
2️⃣ multimap的使用
multimap中的接口可以参考map，功能都是类似的。
【注意】
- 1. multimap中的key是可以重复的。
- 2. multimap中的元素默认将key按照小于来比较
- 3. multimap中没有重载operator[]操作(同学们可思考下为什么?)。
- 4. 使用时与map包含的头文件相同：
（四）在OJ中的使用
1、前k个高频单词
class Solution { public: vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> num; for(auto e : words) num[e]++; //按照单词出现次数的逆序存储单词及其对应的出现次数 multimap<int, string, greater<int>> arry; for(auto e : num) { arry.insert(make_pair(e.second, e.first)); } vector<string> res; auto it = arry.begin(); for(int i = 0; i < k; i++) { res.push_back(it->second); it++; } return res; } };
输出结果：
2、两个数组的交集
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int> set1(nums1.begin(), nums1.end()); unordered_set<int> set2(nums2.begin(), nums2.end()); vector<int> intersection; for (auto num : set1) { if (set2.find(num) != set2.end()) { intersection.push_back(num); } } return intersection; } };
输出结果：
总结
以上便是关于 map和set 的全部知识。感谢大家的观看与支持！！！
