企业官网建设流程全解析

⭐️博主：此生决int-@CSDN博客

速胜派就是最大的投降派！！！

🔥热门专栏🔥

深入理解 C++ 系列｜算法系列

快速复习系列｜Java 速通系列

上期回顾

上一篇我们主要学习了红黑树的底层以及模拟实现，重点掌握了红黑树的四个规则，模拟实现了红黑树，。那么今天，我们就在红黑树的基础上，封装出我们自己的map和set，这一节呢会把我们在模版进阶里面学习到的一些新的C++特性运用起来，巩固理解记忆！同时也和后面封装哈希的思想一样！如果还有印象模糊的地方，建议先回顾对应内容，再继续阅读本文。

封装 map 和 set（一个红黑树复用出两个容器）

我们来对map和set进行一下封装，我们来学习一下库里面是怎么封装map和set的

一、库里 map 和 set 的源码及框架分析

本节的本质：就是用set和map继承红黑树！
但是呢，set只要一个key即可，map要key/value两个值，怎么办呢？即，我们要同时实现

set<int>s1;map<int,string>m1;

我们要让map和set都继承红黑树并且达到上面的效果，要怎么办呢？可以这样：即set和map的模版参数分别为1个和两个，但是，RBTree的结构要一致，

template<classK>classset{public:private:RBTree<K,constK,keyofset>_set;};}template<classK,classV>classmap{public:private:RBTree<K,std::pair<constK,V>,keyofmap>_map;};}

也就是，红黑树有三个参数，键值key，底层存储的什么（set就是一个key，map是pair类型的kv，以及第三个获取key的仿函数）
问题1：为什么要用仿函数来获取key而不是直接利用第一个参数？
首先我们要搞明白，什么函数我们需要使用key 键值？
其实就两个：一个是插入（insert）的函数，还有一个是查找（find）的。
你使用的时候都是传的T类型，即

s1.insert(2);//传的intm1.insert(2,"hello");//传的pair<int,string>

所以，我们可以看到，红黑树（RBTree）里面这两个函数(insert和find)，你使用的时候，传的参数都是 T 类型的。即对应红黑树模板的第二个参数 T

template<classK,classT,classkeyoftree>classRBTree{// 插入pair<Iterator,bool>Insert(constT&data)//都是参数T，我们要提供一个从T里获得key的仿函数

所以现在问题就变成了：我们要从你传的 T 类型中，来获得这个键值 Key（为什么要从你传的 T 类型来获取这个键值 key？注释1）
注释1：
因为红黑树（RBTree）不知道外面是 set 在调用还是 map 在调用，它不知道 T 是一个参数的 key 类型，还是两个参数的 pair 类型，所以，我们就需要提供一个仿函数 KeyOfT！

仿函数 KeyOfT⭐️⭐️⭐️

template<classK>classset{public:structkeyofset//因为要和map保持一致，所以，也要写一个仿函数{constK&operator()(constK&k){returnk;}};template<classK,classV>classmap{public:classkeyofmap//仿函数{public:constK&operator()(constpair<K,V>&kv){returnkv.first;}};

红黑树的底层实现中，利用 KeyOfValue 这个仿函数来调用并得到键值 Key，其实也很简单： keyoftree kof;然后kof(data)即可

// 插入pair<Iterator,bool>Insert(constT&data){......keyoftree kof;while(cur){if(kof(data)<kof(cur->_data))

那么现在，Map 和 Set 与底层红黑树的关系已经搭建好了。后面我们只需要再来看底层的红黑树需要改动哪些地方即可。

红黑树节点的改动

节点：全部存 T（即 map 和 set 底层存的都是 T 类型，也就是第二个参数。

template<classT>structRBTreeNode{T _data;RBTreeNode<T>*_left;RBTreeNode<T>*_right;RBTreeNode<T>*_parent;Colour _col;RBTreeNode(constT&data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}}

那我们改正完树的节点，就可以写树的结构了

红黑树的结构

template<classK,classT,classkeyoftree>classRBTree{//typedef RBTreeNode<K,T> Node;当然可以这么设计，但是STL 选择存 T，是为了让底层 RBTree 更通用。typedefRBTreeNode<T>Node;private:Node*_root=nullptr;};

那么，我们就可以对相应的函数进行改写，即引入仿函数，把key换为：kof(data)
即，例如原来：

if(key<cur->_key)

换成：

keyoftree kof;......if(kof(data)<kof(cur->_data))

等等

迭代器的实现⭐️⭐️⭐️

迭代器的结构

与之前的学习一样，我们要支持 const 迭代器也要支持普通迭代器，所以我们要利用模板；另外，相较于原来只存储一个节点的指针，我们在这里增加了一个根节点的指针_root，原因是：--end()时要从根出发找整棵树的最右节点（中序最后一个）

template<classT,classRef,classPtr>structRBTreeIterator//struct 因为你这个肯定要给外面的用，就是，比较公有，{typedefRBTreeNode<T>Node;typedefRBTreeIterator<T,Ref,Ptr>Self;//成员：两个指针,Node*_node;Node*_root;

operator++⭐️⭐️

我们要清楚，这里的 ++ 是按照中序遍历来走的，我们在这里实现 operator++ 看似很复杂，其实很简单
当我们走到某个节点时，我们要++，可以分为以下几种情况：
1，右孩子为空：向上找祖先，直到当前节点是父亲的左孩子，那个父亲就是下一个节点

2，右孩子不为空——找到右孩子里面的最左孩子（最小孩子）

代码：

Self&operator++(){assert(_node);Node*cur=_node;Node*parent=cur->_parent;if(cur->_right)//如果右孩子不为空，访问右孩子的最小节点，即最左孩子{cur=cur->_right;while(cur->_left){cur=cur->_left;}_node=cur;}else//找到/访问孩子是父亲的左孩子的父亲{while(parent&&parent->_right==cur){cur=cur->_parent;parent=parent->_parent;}_node=parent;}return*this;}

operator–

和operator++类似，
当我们走到某个节点时，我们要–，可以分为以下几种情况：
1，左孩子为空：向上找祖先，直到当前节点是父亲的右孩子，那个父亲就是下一个节点（即中序前驱）

2，左孩子不为空——找到左孩子里面的最右孩子（最大孩子）

代码:

Self&operator--(){Node*cur=_node;if(cur==nullptr){Node*ccur=_root;while(ccur&&ccur->_right){ccur=ccur->_right;}_node=ccur;}else{Node*parent=cur->_parent;if(cur->_left)//左边不为空，左边找最右节点{cur=cur->_left;while(cur->_right){cur=cur->_right;}_node=cur;}else{//如果孩子是父亲的右孩子，那就是访问完了的,要找的就是这个while(parent&&parent->_left==cur){cur=parent;parent=parent->_parent;}_node=parent;}}return*this;}

operator*、==、->、!=

Ptroperator->(){return&_node->_data;//it->要达到的效果就是，it->可以访问到data里面的东西，那就要返回_node->_data;的地址}booloperator==(constRBTreeIterator&it)const//一般只读属性的就要加const{return_node==it._node;}booloperator!=(constRBTreeIterator&it)const{return_node!=it._node;}

那么，我们现在就可以实现红黑树的迭代器相关函数：begin和end了

begin和end

begin：最左节点
end：最右节点的下一个节点——nullptr

Iteratorbegin(){Node*cur=_root;if(_root==nullptr)returnIterator(nullptr,_root);while(cur&&cur->_left){cur=cur->_left;}returnIterator(cur,_root);}Iteratorend(){returnIterator(nullptr,_root);}

map支持的operator[]

operator[]仅仅是map支持，所以，我们只需要在map里面实现，operator[]底层调用的函数是insert函数，但是，我们要改一下insert函数的返回值，由bool改为：pair<iterator,bool>

pair<Iterator,bool>Insert(constT&data)

这里的insert函数，插入T，返回值pair<Iterator,bool>，第二个bool对应的就是是否插入成功，第一个为T对应的迭代器，
所以，我们的operator[]可以这样实现

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

库里面的实现

库里面对RBTree的结构与我们这里设计的有一点区别：库里面加入了一个哨兵节点。

完整代码可见：博主的Gitee：财哥的Gitee仓库

下期预告

哈希

结语

本文到此结束，感谢大家的阅读！如果觉得本文对你有所帮助，欢迎点赞、收藏、关注，也欢迎在评论区一起交流讨论。
也欢迎订阅我的
深入理解 C++系列：从语法入门到底层原理，系统掌握现代 C++
算法系列：从入门到精通，蓝桥杯、ACM、LeetCode 与面试算法全路线
快速复习系列：知识梳理、查漏补缺，考前冲刺必备
Java 速通系列：已学 C 语言，快速上手 Java，轻松备战期末考试