个人作品网站,一 网站开发背景,西部数码网站备案核验单,最有性价比的网站建设前言 在前面#xff0c;我们学习了红黑树。#xff08;没学过红黑树直接看会很吃力#xff09;set和map的底层就是红黑树#xff0c;现在我们要用这棵树来封装STL里面的容器#xff1a;set和map。 下面是之前讲过的红黑树#xff0c;他只是普通的“Key”模型,适合封装set…前言 在前面我们学习了红黑树。没学过红黑树直接看会很吃力set和map的底层就是红黑树现在我们要用这棵树来封装STL里面的容器set和map。 下面是之前讲过的红黑树他只是普通的“Key”模型,适合封装set容器 RBTree.h代码如下这是之前的还没封装好后续会给上总代码
#pragma onceenum color
{RED,BLACK
};templateclass K
struct RBTreeNode
{RBTreeNodeK* _parent;RBTreeNodeK* _left;RBTreeNodeK* _right;K _key;color _col;RBTreeNode(const K key):_key(key),_parent(nullptr),_left(nullptr),_right(nullptr),_col(RED){}
};templateclass K
class RBTree
{typedef RBTreeNodeK Node;
public:bool Insert(const K key){Node* cur _root;Node* parent _root;if (_root nullptr){_root new Node(key);_root-_col BLACK;return true;}while (cur){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else{return false;}}if (parent-_key key){parent-_left new Node(key);cur parent-_left;}else{parent-_right new Node(key);cur parent-_right;}cur-_parent parent;while (parent parent-_col RED){Node* grandparent parent-_parent;if (grandparent-_left parent){// g// p u// cNode* uncle grandparent-_right;if (uncle uncle-_col RED){//变颜色parent-_col BLACK;uncle-_col BLACK;grandparent-_col RED;//往上更新cur grandparent;parent grandparent-_parent;}else{// g// p u// cif(cur parent-_left){RotateR(grandparent);grandparent-_col RED;parent-_col BLACK;break;}// g// p u// celse{RotateL(parent);RotateR(grandparent);cur-_col BLACK;grandparent-_col RED;break;}}}else //grandparent-_right parent{// g// u p// cNode* uncle grandparent-_left;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;parent grandparent-_parent;}else{// g// u p// cif (parent-_right cur){RotateL(grandparent);parent-_col BLACK;grandparent-_col RED;break;}else{// g// u p// cRotateR(parent);RotateL(grandparent);cur-_col BLACK;grandparent-_col RED;break;}}}}_root-_col BLACK;return true;}void InOrder(){_InOrder(_root);cout endl;}bool Check(Node* root,int BlackNum,int valRef){if (root nullptr){if(BlackNum valRef){return true;}else{cout 每条路径黑色结点个数不等 endl;return false;}}if (root-_col RED root-_parent-_col RED){cout 有连续的红色节点 endl;return false;}if (root-_col BLACK){BlackNum;}return Check(root-_left,BlackNum,valRef) Check(root-_right, BlackNum, valRef);}bool IsBalance(){if (_root nullptr)return true;if (_root-_col RED)return false;int valRef 0;Node* cur _root;while (cur){if (cur-_col BLACK)valRef;cur cur-_left;}int BlackNum 0;return Check(_root,BlackNum,valRef);}private:void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* grandparent parent-_parent;parent-_parent subL;if (grandparent nullptr){_root subL;subL-_parent nullptr;return;}if (grandparent-_left parent){grandparent-_left subL;}else{grandparent-_right subL;}subL-_parent grandparent;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;Node* grandparent parent-_parent;parent-_parent subR;if (grandparent nullptr){_root subR;_root-_parent nullptr;return;}if (grandparent-_left parent){grandparent-_left subR;}else{grandparent-_right subR;}subR-_parent grandparent;}Node* _root nullptr;
};
一、修改模型
如果要封装map的“KeyValue” 容器那么我们需要重新copy一份红黑树改成“KeyValue” 模型去封装map这样似乎也太笨了一点我们看看写库函数的大佬是如何处理的。如何用一棵树封装map和set
这里提出了库里面的关键信息其他内容看不懂没关系只需要知道红黑树结点类型只有Value通过类型Value来判断是“Key”还是“KeyValue” 1.set传递的第二个参数
我们再看一下set容器所传递的内容是什么可以看到对Key typedef了一下给到红黑树的第二个参数value_type就是Key。这个value_type会传递给上面的Value。注意看这里的私有成员是rb_tree类型的 t调用的是上面图片的rb_tree 2.map传递的第二个参数
map容器 typedef 的value_type是pairconst Key,T类型因此map传递给红黑树的第二个参数为pairconst Key,T类型。 如此一来可以通过一颗红黑树来实现“Key”和“KeyValue”模型。 那么他具体是怎么实现的我们还需要进一步分析
3.修改RBTree.h与添加map.h和set.h
根据库里面的内容我们也对自己的RBTree.h代码进行修改
RBTreeNode结点根据库里面的将模板类型K改成了TK _key改成T _data更容易理解_data是什么我们不知道要看你具体传什么内容可能是单个key可能是pair。
templateclass T
struct RBTreeNode
{RBTreeNodeT* _parent;RBTreeNodeT* _left;RBTreeNodeT* _right;T _data;color _col;RBTreeNode(const T data):_data(data),_parent(nullptr),_left(nullptr),_right(nullptr),_col(RED){}
};
对于RBTree也要进行改造模板参数添加上T类型 插入具体的我只改了一点点防止文章过与冗余后面都要弄成data。后续会给上总代码大家先理解就好
templateclass K,class T //添加了T
class RBTree
{typedef RBTreeNodeT Node;bool Insert(const T data) //修改部分{Node* cur _root;Node* parent _root;if (_root nullptr){_root new Node(data); //修改部分_root-_col BLACK;return true;}.........//后续还有很多内容这里就不多改造了}
}
写出set.h 仿函数不添加防止混乱跟库里面的一样传递的第二个参数为K类型
#pragma once
#includeRBTree.h
namespace kky
{templateclass Kclass set{private:RBTreeK, K _t;};
}
写出map.h 跟库里面的一样传递的第二个参数为pair类型
#pragma once
#includeRBTree.h
namespace kky
{templateclass K,class Vclass map{private:RBTreeK, pairconst K, V _t;};
} 这里有点绕现在我们再来捋一捋。 你是map那么你传递的第二个参数T是pair通过T构建出来的结点也是pair类型里面存放的_data自然是pair类型。 你是set你传递的第二个参数T是K通过T构建出来的结点也是K类型里面存放的_data自然是K类型。 4.仿函数取出set中的key和map中的key 那么现在问题又来了这样就可以构建出来了吗我们代码逻辑部分会不会有点问题 大家看下面的代码这是一个插入时的比较代码看存放的数据比当前结点大还是小如果大往右走如果小往左走后面就是找到合适的地方再进行插入。 对于set来说这句代码没有问题可以这样比较。
对于map呢map中的pair支不支持比较呢我们去C文档里面查一下如下发现pair支持比较大小但是他是first小就小first如果相等那么second小就小这里代码使用了复用仔细分析一下就是这个意思 但是我们需要的不是这样啊map我们只比较key不比较value如果key相等就不要处理了返回falseset和map的key不能重复。库函数的比较我们用不上我们需要自己写仿函数去判断。
现在的重点是将_data里面的key取出来比较。库里面是选择添加一个类型KeyOfValue。如下 那么具体是如何做到添加一个类模板对象就做到可以如此比较的呢 这里不懂没关系下面我们还有图
首先在set和map创建上KeyofValue类目的是通过仿函数取出Key
set.h 添加上SetKeyofT函数内部就是走个过场直接取出key。并传递给RBTree当做第三个参数。
public:struct SetKeyofT{const K operator()(const K key){return key;}};
private:RBTreeK, K,SetKeyofT _t;
map.h 添加上MapKeyofT目的是取出pair里面的first也就是key并将MapKeyofT传递给RBTree当做第三个参数。
public:struct MapKeyofT{const K operator()(const pairconst K, V kv){return kv.first;}};
private:RBTreeK, pairconst K, V,MapKeyofT _t;
RBTree.h 修改 添加了第三个模板参数KeyofT并使用KeyofT构建对象koft对需要进行_data比较的地方都是用koft仿函数处理。
templateclass K,class T,class KeyOfT
class RBTree
{KeyOfT koft; //构建对象typedef RBTreeNodeT Node;
public:pairNode*,bool Insert(const T data){Node* cur _root;Node* parent _root;if (_root nullptr){_root new Node(data);_root-_col BLACK;return make_pair(_root,true) ;}while (cur){if (koft(cur-_data) koft(data)){parent cur;cur cur-_right;}else if (koft(cur-_data) koft(data)){parent cur;cur cur-_left;}else{return make_pair(cur, false);}}if (koft(parent-_data) koft(data)){parent-_left new Node(data);cur parent-_left;}//后续内容没有比较无需修改}
}; 那么现在我们再画图捋一捋 你是map构建出的树第三个参数就是MapKeyofT因此使用koft去调用_data数据你获取的就是_data里面的first。 你是set构建出的树第三个参数就是SetKeyofT因此使用koft去调用_data数据你获取的就是_data本身这里的_data就是key。 相当于set是陪太子读书因为太子map需要使用koft去取出第一个数据那么你set也得去这样取就算你本身就是key也这样跟这太子取谁让他map是太子呢 这里逻辑其实并不复杂只是有点点绕大家不懂可以发评论问我 注意图片中的Insert函数返回类型大家看不懂可以忽略,当做bool就好这是为了后续实现operator[]使用的后面会讲 到了现在我们只需在set和map里面添加上insert函数就行因为我们现在已经有了_t这颗树因此调用_t树的Insert函数就好。
set.h 添加
bool Insert(const K key)
{return _t.Insert(key);
}
map.h 添加
bool Insert(const pairconst K, V kv)
{return _t.Insert(kv);
}
现在就可以插入运行一下看看我们封装得咋样了iterator也不用管后续会讲解这里只做打印 二、迭代器
1.迭代器基础
那么插入的基本逻辑我们已经实现了现在开搞迭代器家人们又是大坑来了我们耐下性子慢慢来。 首先map和set的迭代器只需要第二个参数------T 就可以了。他的成员函数只有红黑树结点_node通过结点_node来进行构造迭代器operator* 、 operator-、!、都很简单这里我们不多赘述代码如下 templateclass T
struct __TreeIterator
{typedef RBTreeNodeT Node;typedef __TreeIteratorT Self;__TreeIterator(Node* node):_node(node){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}bool operator!(const Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}Node* _node;
}
2.迭代器 那么迭代器中很重要的呢 大家知道在之前我们学习string、vector、list的时候他们都是线性表往后面走就可以了现在学到的set和map是树形结构他的应该如何走 如图it 在1的位置那么it应该到6的地方去那么我们可以知道当前节点的右子树不为空我们需要到右子树的最左结点去。那么如果我们现在在6的地方再应该去到8的地方那么我们又可以知道当parent-rightcur时我们需要再往上面走一直走到parent-left cur的时候才停止再去遍历parent节点。不理解没关系我们后面画图分析 为什么会这样因为中序是左根右当前结点已经遍历完了证明左和根已经遍历完毕需要遍历右边当右边遍历完毕证明该树遍历完毕也就是遍历完了父亲的左子树该树就是左子树应该去遍历父亲节点 关键点是如果当前节点右为空看当前节点是父亲的左还是右是左就遍历父亲是右就往上面走知道当前节点是父亲的左。 根据我们的分析代码如下 _node为迭代器成员变量
Self operator()
{if (_node-_right) //右树存在 找右树最左节点{Node* cur _node-_right;while (cur-_left){cur cur-_left;}_node cur;}else //右树不存在 往上迭代{Node* cur _node;Node* parent _node-_parent;while (parent parent-_right cur){cur parent;parent parent-_parent;}_node parent;}return *this;
}
3.迭代器--
迭代器--跟不能说一模一样只能说毫无差距他们是相反的直接上代码
Self operator--()
{if (_node-_left){Node* cur _node-_left;while (cur-_right){cur cur-_right;}_node cur;}else{Node* cur _node;Node* parent _node-_parent;while (parent parent-_left cur){cur parent;parent parent-_parent;}_node parent;}return *this;
}
4.添加begin()、end()
RBTree.h添加迭代器和begin()、end()
typedef __TreeIteratorT iterator;
iterator begin()
{Node* cur _root;while (cur cur-_left){cur cur-_left;}return iterator(cur);
}iterator end()
{return iterator(nullptr);
}
set.h
typedef RBTreeT::iterator iterator;
iterator begin()
{return _t.begin();
}iterator end()
{return _t.end();
} map.h
typedef RBTreepairconst K, V::iterator iterator;
iterator begin()
{return _t.begin();
}iterator end()
{return _t.end();
} 但是当我们编译时却报错了这是为什么呢 首先这个iterator是RBTree里面的而RBTree里面的iterator也是typedef过的是__TreeIterator里面的。 因此在set里面的RBTreeK, K, SetKeyofT::iterator是内嵌类型还没有实例化编译器在编译时不知道他是什么类型根本就不认识他我们需要给set里面的RBTreeK, K, SetKeyofT::iterator给添加上typename告诉编译器这里是类型你现在先不急着去找他等到对象实例化的时候你再去取出他的类型。如下 typedef typename RBTreeK,K,SetKeyofT::iterator iterator; 现在迭代器才算构建好set和map可以运行了。 三、map的operator[]
再把operator[]给实现一下C文档里面的operator[]如下 这里有点绕看不懂很正常我们拆分一下 如下 根据我们的分析operator[]首先会执行插入无论成功还是失败会取到该树的迭代器的Value。还有一点就是insert的返回类型为pairiterator,bool之前为了代码简单我们写的insert返回类型是bool。 因此我们需要修改insert的返回类型同时修改函数内部return 后接上的内容如下下面还有的return也需要修改这里不过多展开不多赘述。 set.h也修改 map.h也修改 并在map.h里面添加上我们写绕一点更容易理解库里面的大佬写法学不会。 V operator[](const K key)
{pairiterator, bool ret Insert(make_pair(key, V()));return ret.first-second;
} 测试一下结果nice完成啦 四、const迭代器
1.set的const迭代器
我们的代码还有一点点问题如下set的key竟然可以修改这并不是我们想要的。 库里面set是如下处理的首先在RBTree里添加了const迭代器然后set里面的普通迭代器和const迭代器都是调用的RBTree里的const迭代器目的就是不要修改key值。
至于为什么需要const迭代器这是STL的规定因为之前的容器都有const迭代器。 map是的处理如下普通的就是普通的const就是const的普通的key不可以修改value可以修改const迭代器key和value都不可以修改 那么现在我们的目的是要把const迭代器搞出来。
在红黑树的迭代器中我们只有T 和T*要去取出节点里面的值那么为了防止修改只需要给这两个地方添加上const就可以了。但是如果仅仅给T传参的时候传const T那么肯定是不符合要求的因为这样我们创建的结点Node的类型也是const T那岂不是会让Node里面的_data或者其他内容无法修改这肯定不行我们想要的。 因此我们可以借鉴库里的方法类模板传递三个参数修改方法如下普通的就传递T,T*,Tconst的就传递T,const T*,const T这样就符合我们的要求了是普通迭代器里面的内容就可以修改const的无法修改 同时还得在RBTree里添加const版本的begin()和end()。 如下
const_iterator begin() const
{Node* cur _root;while (cur cur-_left){cur cur-_left;}return const_iterator(cur);
}const_iterator end() const
{return const_iterator(nullptr);
} 同时在set里面修改一下将iterator和const_iterator都typedef为RBTree里的const_iterator这样就都没办法修改了还有一点我们并不需要再重写const_iterator的const版本的begin()和const版本的end()因为虽然看着返回值是iterator实际上被我们typedef成了const_iterator。只需要在结尾添加上const即可 现在我们就不能修改了。 但是现在我们取消了修改代码还是报错了 报错内容为insert的时候类型匹配不上注意这里返回类型K写出了应该为bool 为什么会报这种错误呢 看下面分析set里的iterator被我们typedef了他的本质是const_iterator 模板类型为T,const T*,const T而RBTree里面的iterator就是iterator模板类型为T, T*,T他们类型不一样。这里并不是权限缩小的问题是类模板参数不一样 有点难理解没关系我们再看下面这样看是不是就更清楚了他们类型不一样 2.解决方案1解决了set建议直接看解决方案2 那么对于这个报错我们可以如何修改呢 其实很简单只需要将RBTree里面的返回类型和返回结果修改一下就好如下 虽然看起来有那么一点点非主流但是这确实是一个可行方案并且很容易理解 。 那么为什么这样修改就可以运行了呢 这就要提到pair的构造了下面我们将pair的构造展开 现在分析一下为什么pairNode*,bool能够初始化pairconst_iterator,bool第一个参数表面上是iterator本质是const_iterator 因为const_iterator也是可以通过Node*来构造。这是我们迭代器的构造函数啊,如下 下面我们再捋一捋流程图看看是怎么构造的首先set调用了插入会调用RBTree的插入返回回来类型发现pair的类型不同不能拷贝构造于是他会尝试看能不能进行构造发现__TreeIterator有这么一个类并且可以构造于是就完成了iterator的构造了。 3.map的const迭代器
map的普通迭代器是key不能修改而value可以修改const迭代器是key和value都不可以修改因此他不能像set一样普通是constconst也是const。
我们在map里面添加上如下方框框起来的代码。 4.解决方案2解决map和set
再去看一看能不能运行map的const迭代器并且查看map的second是否可以修改 那我们再仔细看看为何报错 他们的区别是多了两个const 也就是这一句 我们翻译一下他的意思就是不能从普通迭代器变成const迭代器所针对的就是如下代码从iterator到const_iterator这条路行不通 那么我们应该如何修改呢 首先我们应该要想到构造函数我们写出一个从iterator到const_iterator的构造函数就好了。具体如何写我们还是可以参考一下库里面的内容。 库里面是如何操作的 首先用类模板的第一个参数构造typedef一个iterator。这代表着无论你传递的Ref和Ptr是普通的还是const版本的经过我只取第一个参数typedef的操作我都能保证他是普通的那么我用普通迭代器来进行构造。 1.如果你传递的Ref和Ptr是普通的我就相当于拷贝构造。 2.如果你传递的Ref和Ptr是const的我就相当于从普通版本构造成了const版本。 这样就符合我们的条件了。 那我们跟着库里面进行编写代码 写出如下代码。 再查看就不报错了只有不能修改的错误我们代码删除就好了 测试运行大功告成 五、总结 回到之前的问题为什么map和set的封装第一个参数需要K能不能不要K 先说答案不能。虽然我们在insert插入函数里面并没有用到K类型但如果是Find函数呢你肯定是德通过Key类型去传递参数查找吧我们所传递的第三个参数KeyOfT他仅仅能取出第二参数T里面的内容他不能推断T里面的参数类型因此第一个参数K不能省略 map和set的封装并不比红黑树简单需要肚兜理解并且我们实现的还仅仅是简单版本还有反向迭代器和除插入之外的函数都没有完成但这一部分也是足够我们学习红黑树和map、set的性质了。希望与大家共勉
最后附上总代码
RBTree.h
#pragma onceenum color
{RED,BLACK
};templateclass T
struct RBTreeNode
{RBTreeNodeT* _parent;RBTreeNodeT* _left;RBTreeNodeT* _right;T _data;color _col;RBTreeNode(const T data):_data(data),_parent(nullptr),_left(nullptr),_right(nullptr),_col(RED){}
};templateclass T,class Ptr,class Ref
struct __TreeIterator
{typedef RBTreeNodeT Node;typedef __TreeIteratorT, T*, T iterator;typedef __TreeIteratorT,Ptr,Ref Self;__TreeIterator(Node* node):_node(node){}//iterator为普通迭代器如果传入的Ptr和Ref是const版本//那么我们现在就是在用普通迭代器去构造const迭代器__TreeIterator(const iterator it) :_node(it._node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}Self operator(){if (_node-_right){Node* cur _node-_right;while (cur-_left){cur cur-_left;}_node cur;}else{Node* cur _node;Node* parent _node-_parent;while (parent parent-_right cur){cur parent;parent parent-_parent;}_node parent;}return *this;}Self operator--(){if (_node-_left){Node* cur _node-_left;while (cur-_right){cur cur-_right;}_node cur;}else{Node* cur _node;Node* parent _node-_parent;while (parent parent-_left cur){cur parent;parent parent-_parent;}_node parent;}return *this;}bool operator!(const Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}Node* _node;
};// set-RBTreeK,K,SetKeyOfT _t;
// map-RBTreeK.pairK,T,MapKeyOfT _t;
templateclass K,class T,class KeyOfT
class RBTree
{KeyOfT koft;typedef RBTreeNodeT Node;
public:typedef __TreeIterator T,const T*,const T const_iterator;typedef __TreeIteratorT,T*,T iterator;iterator begin(){Node* cur _root;while (cur cur-_left){cur cur-_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}const_iterator begin() const {Node* cur _root;while (cur cur-_left){cur cur-_left;}return const_iterator(cur);}const_iterator end() const{return const_iterator(nullptr);}pairiterator,bool Insert(const T data){Node* cur _root;Node* parent _root;if (_root nullptr){_root new Node(data);_root-_col BLACK;return make_pair(_root,true) ;}while (cur){if (koft(cur-_data) koft(data)){parent cur;cur cur-_right;}else if (koft(cur-_data) koft(data)){parent cur;cur cur-_left;}else{return make_pair(cur, false);}}if (koft(parent-_data) koft(data)){parent-_left new Node(data);cur parent-_left;}else{parent-_right new Node(data);cur parent-_right;}cur-_parent parent;while (parent parent-_col RED){Node* grandparent parent-_parent;if (grandparent-_left parent){// g// p u// cNode* uncle grandparent-_right;if (uncle uncle-_col RED){//变颜色parent-_col BLACK;uncle-_col BLACK;grandparent-_col RED;//往上更新cur grandparent;parent grandparent-_parent;}else{// g// p u// cif(cur parent-_left){RotateR(grandparent);grandparent-_col RED;parent-_col BLACK;break;}// g// p u// celse{RotateL(parent);RotateR(grandparent);cur-_col BLACK;grandparent-_col RED;break;}}}else //grandparent-_right parent{// g// u p// cNode* uncle grandparent-_left;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;parent grandparent-_parent;}else{// g// u p// cif (parent-_right cur){RotateL(grandparent);parent-_col BLACK;grandparent-_col RED;break;}else{// g// u p// cRotateR(parent);RotateL(grandparent);cur-_col BLACK;grandparent-_col RED;break;}}}}_root-_col BLACK;return make_pair(cur, false);}void InOrder(){_InOrder(_root);cout endl;}bool Check(Node* root,int BlackNum,int valRef){if (root nullptr){if(BlackNum valRef){return true;}else{cout 每条路径黑色结点个数不等 endl;return false;}}if (root-_col RED root-_parent-_col RED){cout 有连续的红色节点 endl;return false;}if (root-_col BLACK){BlackNum;}return Check(root-_left,BlackNum,valRef) Check(root-_right, BlackNum, valRef);}bool IsBalance(){if (_root nullptr)return true;if (_root-_col RED)return false;int valRef 0;Node* cur _root;while (cur){if (cur-_col BLACK)valRef;cur cur-_left;}int BlackNum 0;return Check(_root,BlackNum,valRef);}private:void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_data ;_InOrder(root-_right);}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* grandparent parent-_parent;parent-_parent subL;if (grandparent nullptr){_root subL;subL-_parent nullptr;return;}if (grandparent-_left parent){grandparent-_left subL;}else{grandparent-_right subL;}subL-_parent grandparent;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;Node* grandparent parent-_parent;parent-_parent subR;if (grandparent nullptr){_root subR;_root-_parent nullptr;return;}if (grandparent-_left parent){grandparent-_left subR;}else{grandparent-_right subR;}subR-_parent grandparent;}Node* _root nullptr;
}; set.h
#pragma once
#includeRBTree.h
namespace kky
{templateclass Kclass set{public:struct SetKeyofT{const K operator()(const K key){return key;}};//对类模板取内嵌类型需要加typename告诉编译器这是类型,等对象实例化typedef typename RBTreeK,K,SetKeyofT::const_iterator iterator;typedef typename RBTreeK,K,SetKeyofT::const_iterator const_iterator;iterator begin() const{return _t.begin();}iterator end() const{return _t.end();}pairiterator, bool Insert(const K key){return _t.Insert(key);}bool IsBalance(){return _t.IsBalance();}void InOrder(){_t.InOrder();}private:RBTreeK, K,SetKeyofT _t;};
}
map.h
#pragma once
#includeRBTree.h
namespace kky
{templateclass K,class Vclass map{public:struct MapKeyofT{const K operator()(const pairconst K, V kv){return kv.first;}};typedef typename RBTreeK, pairconst K, V, MapKeyofT::iterator iterator;typedef typename RBTreeK, pairconst K, V, MapKeyofT::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}pairiterator, bool Insert(const pairK, V kv){return _t.Insert(kv);}bool IsBalance(){return _t.IsBalance();}void InOrder(){_t.InOrder();}V operator[](const K key){pairiterator, bool ret Insert(make_pair(key, V()));return ret.first-second;}private:RBTreeK, pairconst K, V,MapKeyofT _t;};
}
Test.cpp
#includeiostream
#includevector
#includectime
using namespace std;
#includeRBTree.h
#includemap.h
#includeset.hvoid set_test()
{//const int N 10;//vectorint v;//v.reserve(N);//srand(time(0));//for (size_t i 0; i N; i)//{// v.push_back(rand() i);//}//kky::setint rbt;//for (auto e : v)//{// if (e 24473)// {// int i 0;// }// rbt.Insert(e);// rbt.IsBalance();//}//rbt.InOrder();//cout rbt.IsBalance() endl;kky::setint rbt;rbt.Insert(4);rbt.Insert(6);rbt.Insert(5);rbt.Insert(3);kky::setint::const_iterator it rbt.begin();while (it ! rbt.end()){cout *it endl;it;}
}void map_test()
{string arr[] {香蕉,苹果,橘子,香蕉,苹果 ,香蕉,苹果 ,香蕉 };kky::mapstring,int rbt;for (auto e : arr){rbt[e];}kky::mapstring,int::const_iterator it rbt.begin();while (it ! rbt.end()){cout it-first it-second endl;it;}//kky::mapstring, string dict;//dict.Insert(make_pair(sort, 排序));//dict.Insert(make_pair(sort, xx));//dict.Insert(make_pair(left, 左));//dict.Insert(make_pair(right, 右));//kky::mapstring,string::iterator it dict.begin();//while (it ! dict.end())//{// cout it-first it-second endl;// it;//}
}int main()
{set_test();map_test();
}
最后感谢大家的观看
