序言：

在之前，我们已经对STL中的序列式容器进行了相关的学习。本期，我将给大家介绍的则是另外一类容器 —— 关联式容器！！！

（一）容器回顾

💨【顺序容器】

💨【关联式容器】

💨【容器适配器】

（二）键值对

（三）树形结构的关联式容器

1、set

1️⃣基本介绍

2️⃣set的使用

2、multiset

1️⃣ 基本介绍

2️⃣ multiset的使用

3、map

1️⃣基本介绍

2️⃣ map的使用

4、multimap

1️⃣基本介绍

2️⃣ multimap的使用

（四）在OJ中的使用

1、前k个高频单词

2、两个数组的交集

总结

（一）容器回顾

在初阶阶段，我们已经接触过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个高频单词

692. 前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、两个数组的交集

349. 两个数组的交集

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

输出结果：