map和set的封装

容器的分类

在C++标准模板库（STL）中，容器是用于存储和管理数据的类模板，它们可以分为两大类：序列式容器和关联式容器。
序列式容器：底层为线性序列的数据结构，里面存储的是元素本身。

1. vector：动态数组，支持随机访问，尾部插入和删除效率高，但中间插入和删除效率低。
2. deque：双端队列，支持在两端快速插入和删除，内部由多个数组片段组成，不连续。
3. list：双向链表，支持在任意位置快速插入和删除，不支持随机访问。
4. forward_list：单链表，只支持向前遍历，用于只需要单向遍历的场景。
5. array：固定大小的数组，支持随机访问，大小在编译时确定。
   容器适配器：它不是一种独立的容器，而是一种对容器的封装，使其表现出优先级队列的特性，并不是一个新的容器而是对deque容器的封装。
   C++的容器适配器有三个，有priority_queue、queue、stack,分别对应数据结构汇总的堆、队列、和栈
   堆的定义：父结点大于两个孩子结点就是大堆，父节点小于两个孩子结点就是小堆，每一个子树都满足该定义，通过向下调整算法或向上调整算法实现。
   队列的定义：队列中的数据要符合先进先出的逻辑
   栈的定义：栈的数据要符合后进先出的定义，可以用于模拟递归堆栈实现用循环去代替递归。
   关联式容器：关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。
6. set：存储唯一元素的集合，元素自动排序。 内部使用红黑树实现。
7. map：存储键值对的容器，键唯一，自动根据键排序。
8. multiset：允许存储重复元素的集合。
9. multimap：允许键重复的映射。

set的概念：

1. 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。
2. set中插入元素时，只需要插入value即可，不需要构造键值对。
3. set中的元素不可以重复(因此可以使用set进行去重)。
4. 使用set的迭代器遍历set中的元素，可以得到有序序列
5. set中的元素默认按照小于来比较
6. set中查找某个元素，时间复杂度为：$Olo{g}_{2}n$
7. set中的元素不允许修改(为什么?) 因为底层是红黑树，如果对任意结点进行修改就会破坏整个红黑树的结构
8. set中的底层使用二叉搜索树(红黑树)来实现。

map的概念：

1. map中的的元素是键值对
2. map中的key是唯一的，并且不能修改
3. 默认按照小于的方式对key进行比较
4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列
5. map的底层为平衡搜索树(红黑树)，查找效率比较高$O(lo{g}_{2}n)$
6. 支持[]操作符，operator[]中实际进行插入查找。

严格弱序

在内部，set和map中的key总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。

什么是严格弱序？

简单的来说就是 a<b 而不能 a<=b,就是在小于的旁边不能带等号。
三个要求：

1. a<b和b<a不可能同时成立
2. a<b, b<c 则a<c
3. a<b不成立，b<a不成立，则 a = b

作用：用于表示两个元素的 <、> 、=的关系

pair类：

是一个有两个值的类，而且这个类有两个模版参数为的就是让这两个值能够有不同的类型。

make_pair：

顾名思义：制作一个pair类

mulimap和muliset

与上面map和set没有多大区别：只是多了能够存放重复的key而已
PS:相关详细的接口，可以去官方文档看一下C++文档

模拟源码根据红黑树去封装map和set

源码逻辑图示：

在上图中，我们得到结论：红黑树存储什么值是由第二个模版参数Value决定的，而set在内部封装红黑树的时候，传入的Value其实是Key，红黑树是key结构还是key/value使用模板是由第二个模版参数决定的
所以我们要修改之前的红黑树模版类型
如图：

insert

如何让两个不同模版类型的值去比较大小进行搜索树的插入逻辑？

在之前的代码中:

就不能这样直接的去写比较了，因为set的模版参数是key,而map的模版参数是pair,而且map的比较大小也只是key之间的比较。
解决方式是在set和map里面写一个仿函数（函数对象）,然后作为模版参数传过去，再用该仿函数构造一个对象用于做key值的比较。
这样就实现了我是map,我就传map的比较方式。我是set，我就传set的比较方式。


修改后的代码：

迭代器类的封装

这里的迭代器本质是封装结点，让结点具有指针行为，所以迭代器的成员函数就是结点。

operator*和operator->

operator==和operator!=

operator++

迭代器的begin()是那个节点，++后又是那个节点，end()又是那个节点。
经过测试：

我们可以得出，begin=1而且++输出的序列都是有序，这个循环按照红黑树中序遍历打印出来的，所以begin就是中序遍历中的第一个节点，而++就是让结点以中序遍历的形式往后走。而end就是中序遍历的最后一个结点的后一位。
二叉树的中序遍历第一个就是最左结点，所以begin就是如下图：

1、it指向的节点，右子树不为空，下一个就是右子树的最左节点
2、it指向的节点，右子树为空，it中的节点所在的子树访问完了，往上找父遍历，直到找到遍历节点是左孩子的父节点，然后把父节点返回。

operator–

1、左不为空，左子树的最右节点
2、左为空，沿着到根的路径找孩子是父亲的右孩子的那个祖先

map的迭代器封装

我们把红黑树的迭代器写完，就可以在map和set中封装迭代器、begin、end。

set的迭代器封装

问：为什么这里要加上typename？
因为对于编译器来说，模版实例化在编译器之后，所以这里的RBTree<K,K,SetKeyOfT>::const_iterator,中的const_iterator并不知道是静态变量还是一个成员变量，如果是成员变量，这个成员变量的类型是不确定的，因为模版还没有实例化，所以要用typename关键字去修饰来告诉编译器这是一个类型。

map的operator[ ]解析

operator[ ]的使用

使用示例：

string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

现在有一个string的数组，要求使用map来统计数据。
第一种实现方式：

	map<string, int> countMap;for (auto& str : arr){auto ret = countMap.find(str);if (ret == countMap.end()){// 没有表示第一次出现，插入countMap.insert(make_pair(str, 1));}else{// 次数++ret->second++;}}

定义一个map<string, int>, 让arr中的元素做key值，用一个int的value去统计的出现的数据。
然后遍历一遍arr，如果找到了str就对value++，没有找到就插入。

第二种实现方式：

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

直接用operator【】代替,为什么呢?

关键去看最后的一句：A call to this function is equivalent to:(*((this->insert(make_pair(k,mapped_type()))).first)).second

operator[ ]的实现

		V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}

如何实现key值不被修改和set不被修改

使用const迭代器
map:

set：

从这里可以看到set的iterator其实是const_iterator迭代器封装的，所以他insert返回，还是调用begin返回都是const不能被修改，再去看一下我们的红黑树内部是如何实现const迭代器类的

和list的迭代器一样都是使用多两个模版参数，RBTree类决定RBTree_iterator类，根据传的是const还是非const来决定迭代器是const还是非const

为什么会报这个错误？如何解决？

首先，这个错误是说，非const内容的pair无法转换到const的pair，在返回的时候，所以我们的首先思路是写一个可以转换的构造出来给他，
在源码中是用这样的方式去写的如图：

实现了这样的功能：
1、这个类模板被实例化为iterator，他就是拷贝构造
2、这个类模板被实例化为const iterator，他不再是拷贝构造，他是一个支持用iterator去构造初始化const iterator的构造函数。