云深麋鹿专栏C | 用C语言学数据结构 | Java回顾上一篇我们结束了 红黑树 的相关介绍接下来这篇文章让我们尝试封装红黑树实现容器mymap跟myset体会新的设计思路吧~放个目录前言一 分析源码1.1 可以分别实现map和set的红黑树是怎样的1.2 函数怎么适配map的pair跟set的key1.3 源码怎么实现iterator1.4 源码怎么实现const_iterator1.5 Key二 模拟实现2.1 搭框架2.1.1 RBTreeNode结构2.1.2 RBTree结构1修改框架2修改Insert①_kv.first怎么修改②测试Insert3封装iterator①搭个框架②重载需要的操作符简单③重载需要的操作符稍难4封装const_iterator①加俩模板参数②在RBTree里5修改key①修改Insert返回值②MySet的Key不能修改③MyMap的Key不能修改6重载[]前言摘要本文基于红黑树实现mymap与myset容器通过模板参数设计统一底层结构以T存储节点数据K提取键值利用_KeyOfValue函数适配map的pair与set的key。通过迭代器封装、const迭代器机制及节点key不可修改特性模拟标准库源码思路实现高效、安全的键值对与集合管理深入理解STL容器底层设计逻辑。一 分析源码这里可以用Everything搜源码位置打开来看打开Everything输入相应文件名称查找要同时满足两个容器的特点底层上关键在于树结点存不同数据的同时函数接口能够取得所需数据。1.1 可以分别实现map和set的红黑树是怎样的源码的设计巧思从模板参数开始给个模板参数即_Val。树结点就是用这个_Val构造出来的。另外Key模板参数是给find/erase函数用的。1.2 函数怎么适配map的pair跟set的key关键在于模板参数_KeyOfValue我们代码实现部分再细讲。1.3 源码怎么实现iterator源码比较长直接拷贝templatetypename_Tpstruct_Rb_tree_iterator{typedef_Tp value_type;typedef_Tpreference;typedef_Tp*pointer;typedefbidirectional_iterator_tag iterator_category;typedefptrdiff_t difference_type;typedef_Rb_tree_iterator_Tp_Self;typedef_Rb_tree_node_base::_Base_ptr _Base_ptr;typedef_Rb_tree_node_Tp*_Link_type;_Rb_tree_iterator()_GLIBCXX_NOEXCEPT:_M_node(){}explicit_Rb_tree_iterator(_Link_type __x)_GLIBCXX_NOEXCEPT:_M_node(__x){}referenceoperator*()const_GLIBCXX_NOEXCEPT{return*static_cast_Link_type(_M_node)-_M_valptr();}pointeroperator-()const_GLIBCXX_NOEXCEPT{returnstatic_cast_Link_type(_M_node)-_M_valptr();}_Selfoperator()_GLIBCXX_NOEXCEPT{_M_node_Rb_tree_increment(_M_node);return*this;}_Selfoperator(int)_GLIBCXX_NOEXCEPT{_Self __tmp*this;_M_node_Rb_tree_increment(_M_node);return__tmp;}_Selfoperator--()_GLIBCXX_NOEXCEPT{_M_node_Rb_tree_decrement(_M_node);return*this;}_Selfoperator--(int)_GLIBCXX_NOEXCEPT{_Self __tmp*this;_M_node_Rb_tree_decrement(_M_node);return__tmp;}booloperator(const_Self__x)const_GLIBCXX_NOEXCEPT{return_M_node__x._M_node;}booloperator!(const_Self__x)const_GLIBCXX_NOEXCEPT{return_M_node!__x._M_node;}_Base_ptr _M_node;};后面模拟实现部分细讲。1.4 源码怎么实现const_iterator普通迭代器const迭代器可以看到const迭代器直接在typedef的时候加上了const。我们可以使用模板参数实现类似效果。1.5 Keymap中的结点要求key不能修改值可以修改set结点只有值也不能修改。源码中map这里typedef的时候加上了const。set则是普通迭代器也使用了const迭代器以此限制Key的修改。二 模拟实现2.1 搭框架原来的RBTree头文件需要改下。2.1.1 RBTreeNode结构templateclassTstructRBTreeNode{T _t;RBTreeNodeT*_left;RBTreeNodeT*_right;RBTreeNodeT*_parent;Colour _col;RBTreeNode(constTt):_t(t),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}};只留下TT具体是什么由底层map/set决定。2.1.2 RBTree结构1修改框架templateclassK,classTclassRBTree{typedefRBTreeNodeTNode;public://...private:Node*_rootnullptr;};2修改InsertboolInsert(constTt){if(_rootnullptr){_rootnewNode(t);_root-_colBLACK;returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){//...}修改到一半卡住了。①_kv.first怎么修改源码给出了解决方案加上模板参数KeyOfValue。templateclassK,classT,classKeyOfValue再加上MyMap跟MySet对应代码MyMaptemplatetypenameKclassMySet{public:structSetKeyOfT{constKoperator()(constKk)const{returnk;}};private:RedBlackTreeK,K,SetKeyOfT_mySet;};MySettemplatetypenameKclassMySet{public:structSetKeyOfT{constKoperator()(constKk)const{returnk;}};private:RedBlackTreeK,K,SetKeyOfT_mySet;};重载操作符。改函数KeyOfT kot;while(cur){if(kot(cur-_t)kot(t)){parentcur;curcur-_right;}elseif(kot(cur-_t)kot(t)){parentcur;curcur-_left;}else{returnfalse;}}②测试Insert分别给MyMap跟MySet写个Print方便输出观察templateclassK,classVvoidPrint(constMyMapK,Vm){for(autoe:m){coute.first e.second;coutendl;}coutendl;}templateclassKvoidPrint(constMySetKs){for(autoe:s){coute ;}coutendl;}测试函数voidTestMyMap01(void){coutTestMyMap:endl;MyMapstring,stringm;m.insert(make_pair(1,one));m.insert(make_pair(2,two));m.insert(make_pair(3,three));Print(m);}voidTestMySet01(void){coutTestMySet:endl;MySetstrings;s.insert(one);s.insert(two);s.insert(three);Print(s);}在main函数里调用运行符合预期。3封装iterator①搭个框架templateclassTstructRBTreeIterator{typedefRBTreeNodeTNode;Node*_node;RBTreeIterator(Node*node):_node(node){}}提供模板参数方便适配不同node类型的Iterator。给结点类型起一个简短别名Node。RBTreeIterator初始化带一个参数node给_node赋值。②重载需要的操作符简单structRBTreeIterator{// ...Toperator*()const{return_node-_t;}T*operator-()const{return_node-_t;}booloperator(constSelfit)const{return_nodeit._node;}booloperator!(constSelfit)const{return_node!it._node;}}对一个Iterator解引用*为_node的_t内容把Node定义找出来瞅一眼templateclassTstructRBTreeNode{T _t;RBTreeNodeT*_left;RBTreeNodeT*_right;RBTreeNodeT*_parent;Colour _col;// ...}重载成员访问符-结果返回_node的_t地址。重载成员访问符跟!就是比较两个_node。③重载需要的操作符稍难这里就不区分前后置了。重载自增遵循左根右原则。Selfoperator(){if(_node-_right){Node*minLeft_node-_right;while(minLeft-_left){minLeftminLeft-_left;}_nodeminLeft;}else{Node*cur_node;Node*parentcur-_parent;while(parentcurparent-_right){curparent;parentcur-_parent;}_nodeparent;}return*this;}为了更好演示假设当前遍历到了A结点。第一种情况右子树不为空则到右子树的最左结点。如图后遍历到B结点。第二种情况右子树为空则向上找祖先。图中向上找到B当前结点A是B的左孩子则遍历到B结点。第三种情况右子树为空向上找不到祖先。图中A结点不属于任何一个祖先的左孩子则已遍历完整棵树再就是nullptr即End()。重载自减- -- -遵循右根左原则Selfoperator--(){if(!_node){Node*maxRight_root;while(maxRight-_right){maxRightmaxRight-_right;}_nodemaxRight;}elseif(_node-_left){Node*maxRight_node-_left;while(maxRight-_right){maxRightmaxRight-_right;}_nodemaxRight;}else{Node*cur_node;Node*parentcur-_parent;while(parentcurparent-_left){curparent;parentcur-_parent;}_nodeparent;}return*this;}同样假设当前遍历到了A结点。第一种情况当前结点为空结点。找到当前子树的最右结点该结点为当前空结点–后下一个结点。第二种情况当前结点不为空且有左孩子当前结点的左孩子就是下一个结点。第三种情况当前结点不为空且没有左孩子向上找祖先直到自己为祖先的右孩子该祖先即为下一个结点。第四种情况当前结点不为空且没有左孩子且遍历不到下一个祖先。一般不会有这种情况当前代码下–后变为空结点。4封装const_iterator①加俩模板参数templateclassT,classRef,classPtr②在RBTree里根据模板参数不同构造Iterator跟ConstIterator。typedefRBTreeIteratorT,T,T*Iterator;typedefRBTreeIteratorT,constT,constT*ConstIterator;加一个ConstIterator的Begin和End。ConstIteratorBegin()const{Node*minLeft_root;while(minLeftminLeft-_left){minLeftminLeft-_left;}returnConstIterator(minLeft,_root);}ConstIteratorEnd()const{returnConstIterator(nullptr,_root);}5修改key①修改Insert返回值我们写的Insert返回值是bool但是库里的返回值是一个pair我们也改成这样方便获取插入位置。修改底层RedBlackTree里的InsertpairIterator,boolInsert(constTt){//...// traverse to find the right position for the node to insert:while(cur){if//...else{returnmake_pair(Iterator(cur,_root),false);}}// create a new node and assign it to cur...pairIterator,boolretmake_pair(Iterator(cur,_root),true);// change colour...returnret;}同步修改MyMap跟MySetclassMySet{//...pairiterator,boolinsert(constKkey){return_mySet.Insert(key);}}classMyMap{//...pairiterator,boolinsert(constpairK,Vkv){return_myMap.Insert(kv);}}以上代码仅为展示修改部分。②MySet的Key不能修改现在MySet的Key是可以修改的。测试代码如下voidTestMySet02(void){coutTestMySet:endl;MySetstrings;pairMySetstring::iterator,boolrets.insert(one);MySetstring::iterator itret.first;*ittwo;Print(s);}运行修改代码。直接在定义类成员变量以及typedef迭代器时给模板参数加上constpublic:typedeftypenameRBTreeK,constK,SetKeyOfT::Iterator iterator;typedeftypenameRBTreeK,constK,SetKeyOfT::ConstIterator const_iterator;private:RBTreeK,constK,SetKeyOfT_mySet;之前的测试代码现在就报错了③MyMap的Key不能修改现在MyMap的Key同样是可以修改的。测试代码如下voidTestMyMap02(void){coutTestMyMap:endl;MyMapstring,stringm;pairMyMapstring,string::iterator,boolretm.insert(make_pair(1,one));MyMapstring,string::iterator itret.first;it-first2;Print(m);}代码注释声明一个MyMap容器对象 m向m中插入键值对1:one再修改该键值对的键为2。运行修改代码。同样直接在定义类成员变量以及typedef迭代器时给模板参数加上constpublic:typedeftypenameRBTreeK,pairconstK,V,MapKeyOfT::Iterator iterator;typedeftypenameRBTreeK,pairconstK,V,MapKeyOfT::ConstIterator const_iterator;private:RBTreeK,pairconstK,V,MapKeyOfT_myMap;回到之前的测试代码实现不能修改键但是可以修改值。6重载[]借助insert函数直接返回值本身Voperator[](constKkey){pairiterator,boolretinsert(make_pair(key,V()));iterator itret.first;returnit-second;}V()返回的是V类型的临时对象。简单测试测试代码如下voidTestMyMap03(void){MyMapstring,intm;m[one]1;m[one];Print(m);}运行符合预期。封装红黑树的学习就到这里下一篇我们要介绍两个不太一样的容器很快会更出来~