深入理解C++系列（17）——封装map和set

⭐️博主此生决int-CSDN博客速胜派就是最大的投降派热门专栏深入理解 C 系列算法系列快速复习系列Java 速通系列文章目录上期回顾封装 map 和 set一个红黑树复用出两个容器一、库里 map 和 set 的源码及框架分析仿函数 KeyOfT⭐️⭐️⭐️红黑树节点的改动红黑树的结构迭代器的实现⭐️⭐️⭐️迭代器的结构operator⭐️⭐️代码operator--代码:operator*、、-、!begin和endmap支持的operator[]库里面的实现下期预告哈希结语上期回顾上一篇我们主要学习了红黑树的底层以及模拟实现重点掌握了红黑树的四个规则模拟实现了红黑树。那么今天我们就在红黑树的基础上封装出我们自己的map和set这一节呢会把我们在模版进阶里面学习到的一些新的C特性运用起来巩固理解记忆同时也和后面封装哈希的思想一样如果还有印象模糊的地方建议先回顾对应内容再继续阅读本文。封装 map 和 set一个红黑树复用出两个容器我们来对map和set进行一下封装我们来学习一下库里面是怎么封装map和set的一、库里 map 和 set 的源码及框架分析本节的本质就是用set和map继承红黑树但是呢set只要一个key即可map要key/value两个值怎么办呢即我们要同时实现setints1;mapint,stringm1;我们要让map和set都继承红黑树并且达到上面的效果要怎么办呢可以这样即set和map的模版参数分别为1个和两个但是RBTree的结构要一致templateclassKclassset{public:private:RBTreeK,constK,keyofset_set;};}templateclassK,classVclassmap{public:private:RBTreeK,std::pairconstK,V,keyofmap_map;};}也就是红黑树有三个参数键值key底层存储的什么set就是一个keymap是pair类型的kv以及第三个获取key的仿函数问题1为什么要用仿函数来获取key而不是直接利用第一个参数首先我们要搞明白什么函数我们需要使用key 键值其实就两个一个是插入insert的函数还有一个是查找find的。你使用的时候都是传的T类型即s1.insert(2);//传的intm1.insert(2,hello);//传的pairint,string所以我们可以看到红黑树RBTree里面这两个函数(insert和find)你使用的时候传的参数都是 T 类型的。即对应红黑树模板的第二个参数 TtemplateclassK,classT,classkeyoftreeclassRBTree{// 插入pairIterator,boolInsert(constTdata)//都是参数T我们要提供一个从T里获得key的仿函数所以现在问题就变成了我们要从你传的 T 类型中来获得这个键值 Key为什么要从你传的 T 类型来获取这个键值 key注释1注释1因为红黑树RBTree不知道外面是 set 在调用还是 map 在调用它不知道 T 是一个参数的 key 类型还是两个参数的 pair 类型所以我们就需要提供一个仿函数 KeyOfT仿函数 KeyOfT⭐️⭐️⭐️templateclassKclassset{public:structkeyofset//因为要和map保持一致所以也要写一个仿函数{constKoperator()(constKk){returnk;}};templateclassK,classVclassmap{public:classkeyofmap//仿函数{public:constKoperator()(constpairK,Vkv){returnkv.first;}};红黑树的底层实现中利用 KeyOfValue 这个仿函数来调用并得到键值 Key其实也很简单 keyoftree kof;然后kof(data)即可// 插入pairIterator,boolInsert(constTdata){......keyoftree kof;while(cur){if(kof(data)kof(cur-_data))那么现在Map 和 Set 与底层红黑树的关系已经搭建好了。后面我们只需要再来看底层的红黑树需要改动哪些地方即可。红黑树节点的改动节点全部存 T即 map 和 set 底层存的都是 T 类型也就是第二个参数。templateclassTstructRBTreeNode{T _data;RBTreeNodeT*_left;RBTreeNodeT*_right;RBTreeNodeT*_parent;Colour _col;RBTreeNode(constTdata):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}}那我们改正完树的节点就可以写树的结构了红黑树的结构templateclassK,classT,classkeyoftreeclassRBTree{//typedef RBTreeNodeK,T Node;当然可以这么设计但是STL 选择存 T是为了让底层 RBTree 更通用。typedefRBTreeNodeTNode;private:Node*_rootnullptr;};那么我们就可以对相应的函数进行改写即引入仿函数把key换为kof(data)即例如原来if(keycur-_key)换成keyoftree kof;......if(kof(data)kof(cur-_data))等等迭代器的实现⭐️⭐️⭐️迭代器的结构与之前的学习一样我们要支持 const 迭代器也要支持普通迭代器所以我们要利用模板另外相较于原来只存储一个节点的指针我们在这里增加了一个根节点的指针_root原因是--end()时要从根出发找整棵树的最右节点中序最后一个templateclassT,classRef,classPtrstructRBTreeIterator//struct 因为你这个肯定要给外面的用就是比较公有{typedefRBTreeNodeTNode;typedefRBTreeIteratorT,Ref,PtrSelf;//成员两个指针,Node*_node;Node*_root;operator⭐️⭐️我们要清楚这里的 是按照中序遍历来走的我们在这里实现 operator 看似很复杂其实很简单当我们走到某个节点时我们要可以分为以下几种情况1右孩子为空向上找祖先直到当前节点是父亲的左孩子那个父亲就是下一个节点2右孩子不为空——找到右孩子里面的最左孩子最小孩子代码Selfoperator(){assert(_node);Node*cur_node;Node*parentcur-_parent;if(cur-_right)//如果右孩子不为空访问右孩子的最小节点即最左孩子{curcur-_right;while(cur-_left){curcur-_left;}_nodecur;}else//找到/访问孩子是父亲的左孩子的父亲{while(parentparent-_rightcur){curcur-_parent;parentparent-_parent;}_nodeparent;}return*this;}operator–和operator类似当我们走到某个节点时我们要–可以分为以下几种情况1左孩子为空向上找祖先直到当前节点是父亲的右孩子那个父亲就是下一个节点即中序前驱2左孩子不为空——找到左孩子里面的最右孩子最大孩子代码:Selfoperator--(){Node*cur_node;if(curnullptr){Node*ccur_root;while(ccurccur-_right){ccurccur-_right;}_nodeccur;}else{Node*parentcur-_parent;if(cur-_left)//左边不为空左边找最右节点{curcur-_left;while(cur-_right){curcur-_right;}_nodecur;}else{//如果孩子是父亲的右孩子那就是访问完了的,要找的就是这个while(parentparent-_leftcur){curparent;parentparent-_parent;}_nodeparent;}}return*this;}operator*、、-、!Ptroperator-(){return_node-_data;//it-要达到的效果就是it-可以访问到data里面的东西那就要返回_node-_data;的地址}booloperator(constRBTreeIteratorit)const//一般只读属性的就要加const{return_nodeit._node;}booloperator!(constRBTreeIteratorit)const{return_node!it._node;}那么我们现在就可以实现红黑树的迭代器相关函数begin和end了begin和endbegin最左节点end最右节点的下一个节点——nullptrIteratorbegin(){Node*cur_root;if(_rootnullptr)returnIterator(nullptr,_root);while(curcur-_left){curcur-_left;}returnIterator(cur,_root);}Iteratorend(){returnIterator(nullptr,_root);}map支持的operator[]operator[]仅仅是map支持所以我们只需要在map里面实现operator[]底层调用的函数是insert函数但是我们要改一下insert函数的返回值由bool改为pairiterator,boolpairIterator,boolInsert(constTdata)这里的insert函数插入T返回值pairIterator,bool第二个bool对应的就是是否插入成功第一个为T对应的迭代器所以我们的operator[]可以这样实现Voperator[](constKkey){pairiterator,boolretinsert(make_pair(key,V()));returnret.first-second;}库里面的实现库里面对RBTree的结构与我们这里设计的有一点区别库里面加入了一个哨兵节点。完整代码可见博主的Gitee财哥的Gitee仓库下期预告哈希结语本文到此结束感谢大家的阅读如果觉得本文对你有所帮助欢迎点赞、收藏、关注也欢迎在评论区一起交流讨论。也欢迎订阅我的深入理解 C系列从语法入门到底层原理系统掌握现代 C算法系列从入门到精通蓝桥杯、ACM、LeetCode 与面试算法全路线快速复习系列知识梳理、查漏补缺考前冲刺必备Java 速通系列已学 C 语言快速上手 Java轻松备战期末考试愿每一次敲下键盘都比昨天更进一步愿每一行代码落下都让未来多一种可能