婚庆公司网站建设总结,网站下雪特效,电商网站建设制作,东莞常平镇最好的工厂#x1f680;个人主页#xff1a;小羊 #x1f680;所属专栏#xff1a;C 很荣幸您能阅读我的文章#xff0c;诚请评论指点#xff0c;欢迎欢迎 ~ 目录 前言一、更高维度的泛型二、模版参数三、比较逻辑的重写四、迭代器4.1 const迭代器4.2 重载4.3 - -重载 五、完整代… 个人主页小羊 所属专栏C 很荣幸您能阅读我的文章诚请评论指点欢迎欢迎 ~ 目录 前言一、更高维度的泛型二、模版参数三、比较逻辑的重写四、迭代器4.1 const迭代器4.2 重载4.3 - -重载 五、完整代码 前言
前面我们介绍了set和map的底层细节在上篇文章中也简单实现了红黑树而我们知道set和map的底层就是依靠红黑树实现的那么在本文我们将学习如何基于红黑树来封装出set和map。 本篇文章会带你深入理解C的三大特性之一——封装。 封装屏蔽底层细节提供统一访问方式。 一、更高维度的泛型
| 红黑树部分代码
#pragma once#include iostream
using namespace std;enum Colour
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Colour _col;RBTreeNode(const pairK, V kv, Colour col RED):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(col){}
};templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:RBTree() default;RBTree(const RBTreeK, V t){_root _copy(t._root);}~RBTree(){_Destroy(_root);_root nullptr;}RBTreeK, V operator(RBTreeK, V t){swap(_root, t._root);return *this;}void InOrder(){_InOrder(_root);cout endl;}bool Find(const pairK, V kv){Node* pcur _root;while (pcur){if (kv.first pcur-_kv.first){pcur pcur-_left;}else if (kv.first pcur-_kv.first){pcur pcur-_right;}else{return true;}}return false;}bool Insert(const pairK, V kv){Node* pcur _root;Node* parent nullptr;if (pcur nullptr)//当前还没有节点{_root new Node(kv);_root-_col BLACK;//根节点必须是黑色的return true;}while (pcur){if (kv.first pcur-_kv.first){parent pcur;pcur pcur-_left;}else if (kv.first pcur-_kv.first){parent pcur;pcur pcur-_right;}else{return false;}}pcur new Node(kv);if (kv.first parent-_kv.first){parent-_left pcur;}else{parent-_right pcur;}pcur-_parent parent;Node* grandfather parent-_parent;Node* uncle nullptr;//当父节点存在且颜色为红需要往上更新while (parent parent-_col RED){if (parent grandfather-_left){uncle grandfather-_right;}else{uncle grandfather-_left;}if (uncle uncle-_col RED)//情况一u存在且为红{parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;if (grandfather-_parent nullptr){grandfather-_col BLACK;return true;}pcur grandfather;parent pcur-_parent;grandfather parent-_parent;}else //情况二u存在且为黑 / 情况三u不存在{if (parent grandfather-_left pcur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_left pcur parent-_right){RotateL(parent);RotateR(grandfather);pcur-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_right pcur parent-_left){RotateR(parent);RotateL(grandfather);pcur-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_right pcur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}break;}}return true;}
private:void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;subL-_right parent;if (subLR){subLR-_parent parent;}Node* parentparent parent-_parent;parent-_parent subL;if (parentparent nullptr){_root subL;}else{if (parent parentparent-_left){parentparent-_left subL;}else{parentparent-_right subL;}}subL-_parent parentparent;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL){subRL-_parent parent;}subR-_left parent;Node* parentparent parent-_parent;parent-_parent subR;if (parentparent nullptr){_root subR;}else{if (parent parentparent-_left){parentparent-_left subR;}else{parentparent-_right subR;}}subR-_parent parentparent;}Node* _copy(Node* root){if (root nullptr){return nullptr;}Node* newnode new Node(root-_kv);newnode-_left copy(root-_left);newnode-_right copy(root-_right);return newnode;}void _Destroy(Node* root){if (root nullptr){return;}_Destroy(root-_left);_Destroy(root-_right);delete root;}void _InOrder(Node* root){if (root nullptr)//递归一定要有结束条件{return;}_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}
private:Node* _root nullptr;
};
前面我们实现的红黑树存储的数据是键值对pairK, V现在又需要基于红黑树封装出set和map而我们知道set中存的是Kmap中存的是pairK, V它们数据类型不一样那我们要拷贝两份红黑树的代码来分别封装set和map吗如果真是这样那也太挫了。
我们可以想办法只用一个红黑树封装set和map像这种使用不同类型在同一套代码中操作的需求我们很容易就想到了模版。值得一说的是我们实现的红黑树已经是一个类模版不过这个类模版还不是太灵活因为它存储类型是K还是pairK, V是写死的并不能够做到完全泛型。
说到这里相信我们都想到了一个解决办法把用于封装set和map的红黑树存储数据的类型也设计成一个模版参数在实例化具体的类时根据传过去的值来确定是存储K还是pairK, V而站在set和map层面它们肯定知道自己的数据类型。
RBTree.h:
templateclass T
struct RBTreeNode
{T _data;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Colour _col;RBTreeNode(const T data, Colour col RED): _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(col){}
};templateclass K, class T
class RBTree
{typedef RBTreeNodeT Node;
public:RBTree() default;RBTree(const RBTreeK, T t){_root _copy(t._root);}~RBTree(){_Destroy(_root);_root nullptr;}RBTreeK, T operator(RBTreeK, T t){swap(_root, t._root);return *this;}//...MySet.h:
namespace yjz
{templateclass Kclass set{public:private:RBTreeK, const K _t;};
}MyMap.h:
namespace yjz
{templateclass K, class Vclass map{public:private:RBTreeK, pairconst K, V _t;};
}上面我们使红黑树节点模版类的模版参数仅用T来表示当用set实例化红黑树类模版时红黑树节点类模版参数T是K类型当用map实例化红黑树类模版时红黑树节点类模版参数T是pairK, V类型。这里相当于实现了一个更高一点维度的泛型。 二、模版参数
有同学可能注意到了上面用红黑树封装set和map时传过去了两个参数。一个T类型不是就能确定是K还是pairK, V了嘛为什么还要传过去一个K呢而且像set传过去两个一模一样的K感觉很奇怪。其实这是为了满足红黑树一些接口的特点而不得不这样做。
bool Find(const K key)bool Insert(const T data)像上面的查找和插入操作仅通过一个参数T还解决不了问题。对于插入操作如果是set就插入K如果是map就插入pairK, V但是对于查找操作不管是set还是map我们只能通过key查找这是set和map的特点。 对于map来说是通过key找value不能说骑驴找驴。
另外这里的Find和Insert函数的返回值也需要改一改Find函数应该返回节点的迭代器Insert函数应该根据插入成功或失败返回相应的pairiterator, bool。
Iterator Find(const K key)
{KeyOfT kot;Node* pcur _root;while (pcur){if (key kot(pcur-_data)){pcur pcur-_left;}else if (key kot(pcur-_data)){pcur pcur-_right;}else{return Iterator(pcur, _root);}}return End();
}pairIterator, bool Insert(const T data)
{KeyOfT kot;Node* pcur _root;Node* parent nullptr;if (pcur nullptr)//当前还没有节点{_root new Node(data);_root-_col BLACK;//根节点必须是黑色的return make_pair(Iterator(_root, _root), true);}while (pcur){if (kot(data) kot(pcur-_data)){parent pcur;pcur pcur-_left;}else if (kot(data) kot(pcur-_data)){parent pcur;pcur pcur-_right;}else{return make_pair(Iterator(pcur, _root), false);}}pcur new Node(data);Node* newnode pcur;//记录新节点指针旋转可能会更新pcurif (kot(data) kot(parent-_data)){parent-_left pcur;}else{parent-_right pcur;}pcur-_parent parent;Node* grandfather parent-_parent;Node* uncle nullptr;//当父节点存在且颜色为红需要往上更新while (parent parent-_col RED){if (parent grandfather-_left){uncle grandfather-_right;}else{uncle grandfather-_left;}if (uncle uncle-_col RED)//情况一u存在且为红{parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;if (grandfather-_parent nullptr){grandfather-_col BLACK;return make_pair(Iterator(newnode, _root), true);}pcur grandfather;parent pcur-_parent;grandfather parent-_parent;}else //情况二u存在且为黑 / 情况三u不存在{if (parent grandfather-_left pcur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_left pcur parent-_right){RotateL(parent);RotateR(grandfather);pcur-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_right pcur parent-_left){RotateR(parent);RotateL(grandfather);pcur-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_right pcur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}break;}}return make_pair(Iterator(newnode, _root), true);
}三、比较逻辑的重写
当我们修改了红黑树的模版参数那它的底层实现也要做相应的修改。 例如插入操作的部分代码
//...while (pcur){if (data pcur-data){parent pcur;pcur pcur-_left;}else if (data pcur-data){parent pcur;pcur pcur-_right;}else{return false;}}
//...同学们想一下这里还能用data pcur-data这种直接比较的方式吗 当然是不可以的。如果是set还好说key和key比较没问题但是map就有问题了因为我们知道pairK, V不是单纯的依据first比较的来看下图中pairK, V的比较方式 从上图我们可以看到second也加入了比较逻辑这和我们期望的只依靠first比较是不符合的。 可能有同学想到了用仿函数但是这里普通的仿函数还解决不了问题因为仿函数的作用是让我们可以灵活的定制实际需求而这里的问题是不能知道到底是K还是pairK, V。
这里我们就要想我们期望的是如果是set就用key比较key如果是map就用first比较first。而站在红黑树的角度它是不知道接下来要实例化它的到底是set还是map的那谁知道呢当然是set和map他们自己知道嘛。 所以我们可以在set和map实例化红黑树时前用仿函数提前把key和first取出来这样在红黑树中比较时通过回调的方式就能拿到我们想要的值。 这里我们再来回顾一下之前学的回调函数回调函数不是由该函数的实现方直接调用而是在待定的事件或条件发生时由另外的一方调用的用于对该事件或条件进行响应。 MySet.h:
namespace yjz
{templateclass Kclass set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:private:RBTreeK, K, SetKeyOfT _t;};
}MyMap.h:
namespace yjz
{templateclass K, class Vclass map{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};public:private:RBTreeK, pairK, V, MapKeyOfT _t;};
}RBTree.h:
bool Insert(const T data)
{KeyOfT kot;Node* pcur _root;Node* parent nullptr;if (pcur nullptr)//当前还没有节点{_root new Node(data);_root-_col BLACK;//根节点必须是黑色的return true;}while (pcur){if (kot(data) kot(pcur-_data)){parent pcur;pcur pcur-_left;}else if (kot(data) kot(pcur-_data)){parent pcur;pcur pcur-_right;}else{return false;}}pcur new Node(data);//...四、迭代器 set和map的迭代器都是双向迭代器既可以通过操作符前进到下一个元素也可以通过- -操作符回退到前一个元素。因为set和map的底层红黑树是二叉树不能完成简单的和- -所以需要重载运算符。 这里我们先实现一下简单的构造、begin、end以及*、-、、!的重载最后再探讨和- -的重载如何实现。
templateclass T, class Ref, class Ptr
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT, Ref, Ptr Self;Node* _node;Node* _root;RBTreeIterator(Node* node, Node* root):_node(node),_root(root){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}
};begin和end分别返回红黑树最左边节点的迭代器和最右边节点下一个空节点的迭代器。这里我们就暂且让end返回nullptr。C标准库中是借助哨兵节点解决end的。
Iterator Begin()
{Node* leftMost _root;while (leftMost leftMost-_left){leftMost leftMost-_left;}return Iterator(leftMost, _root);
}Iterator End()
{return Iterator(nullptr, _root);
}4.1 const迭代器
除了普通迭代器还需要const迭代器const迭代器相较于普通迭代器主要是*和-的重载为了复用普通迭代器可以增加模版参数来提高泛型这个在实现list迭代器中也有使用。 另外还有set的key是不能修改的map的key也不能修改但value是可以修改的。既然如此我们在pairK, V中K前面加上const就能巧妙的解决这个问题。对于set也可以和map保持一致的做法。
MySet.h:
templateclass K
class set
{struct SetKeyOfT{const K operator()(const K key){return key;}};
public:typedef typename RBTreeK, const K, SetKeyOfT::Iterator iterator;typedef typename RBTreeK, const K, SetKeyOfT::ConstIterator 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();}private:RBTreeK, const K, SetKeyOfT _t;
};MyMap.h:
templateclass K, class V
struct map
{struct MapKeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};
public:typedef typename RBTreeK, pairconst K, V, MapKeyOfT::Iterator iterator;typedef typename RBTreeK, pairconst K, V, MapKeyOfT::ConstIterator 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();}private:RBTreeK, pairconst K, V, MapKeyOfT _t;
};RBTree.h:
templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
public:typedef RBTreeIteratorT, T, T* Iterator;typedef RBTreeIteratorT, const T, const T* ConstIterator;Iterator Begin(){Node* leftMost _root;while (leftMost leftMost-_left){leftMost leftMost-_left;}return Iterator(leftMost, _root);}Iterator End(){return Iterator(nullptr, _root);}ConstIterator Begin() const{Node* leftMost _root;while (leftMost leftMost-_left){leftMost leftMost-_left;}return ConstIterator(leftMost, _root);}ConstIterator End() const{return ConstIterator(nullptr, _root);}RBTree() default;RBTree(const RBTreeK, T, KeyOfT t){_root _copy(t._root);}~RBTree(){_Destroy(_root);_root nullptr;}//...4.2 重载
最后到了相对麻烦一点的和- -重载我们知道红黑树的遍历走的是中序中序遍历是左子树、根节点、右子树那如果通过走到中序的下一个节点呢 it当前指向8这个节点按照中序遍历应该指向11这个节点因为左、根、右所以我们应该找当前节点的右节点那么这时候就有两种情况即右节点为空和右节点不为空。
上图情况一是右节点不为空当右节点不为空时中序遍历的下一个节点并不一定就是当前节点的右孩子而是当前节点右子树的最左节点。 情况二是右节点为空右节点为空说明当前节点所在子树遍历完了那当前节点所在子树遍历完了中序遍历下一个节点就是它的父亲吗并不一定。接下来我们应该判断当前节点是它父亲的左孩子还是右孩子如果是它父亲的右孩子则说明它父亲所在子树也遍历完了需要继续往上更新再做判断如果是它父亲的左孩子则下一个节点就是它的父亲。
Self operator()
{//1.当前节点右子树不为空if (_node-_right){Node* leftMost _node-_right;while (leftMost leftMost-_left){leftMost leftMost-_left;}_node leftMost;}else//2.当前节点右子树为空当前节点所在子树访问完了{Node* pcur _node;Node* parent pcur-_parent;while (parent pcur parent-_right){pcur parent;parent pcur-_parent;}_node parent;}return *this;
}4.3 - -重载 重载- -运算符和类似就是反过来而已。 假设当前节点的迭代器it- -应该得到的是它的左孩子的迭代器那这个时候也有两种情况左孩子为空和左孩子不为空。 上图情况一是左孩子不为空那- -得到的应该是其左子树的最右节点的迭代器情况二是左孩子为空左孩子为空说明当前节点所在子树遍历完了如果当前节点是其父亲的左孩子那说明其父亲所在子树也遍历完了需要向上更新如果当前节点是其父亲的右孩子则- -得到的就是它的父亲。
值得注意的是前面我们实现的end返回的是nullptr而end返回的迭代器- -是要得到二叉树最右节点的迭代器的显然我们这里的- -并不能实现那我们就对这种情况做特殊处理。 如果当前指针为空我们就通过_root来找到红黑树的最右节点。这也是最开始在迭代器增加_root成员的原因。
Self operator--()
{//当迭代器是end()时特殊处理if (_node nullptr){Node* rightMost _root;while (rightMost rightMost-_right){rightMost rightMost-_right;}_node rightMost;}//1.左子树不为空找左子树最右节点else if (_node-_left){Node* rightMost _node-_left;while (rightMost rightMost-_right){rightMost rightMost-_right;}_node rightMost;}else//2.左子树为空当前节点所在子树访问完了{Node* pcur _node;Node* parent pcur-_parent;while (parent pcur parent-_left){pcur parent;parent parent-_parent;}_node parent;}return *this;
}五、完整代码
RBTree.h:
#pragma once#include iostream
using namespace std;enum Colour
{RED,BLACK
};templateclass T
struct RBTreeNode
{T _data;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Colour _col;RBTreeNode(const T data, Colour col RED): _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(col){}
};templateclass T, class Ref, class Ptr
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT, Ref, Ptr Self;Node* _node;Node* _root;RBTreeIterator(Node* node, Node* root):_node(node),_root(root){}Self operator(){//1.当前节点右子树不为空if (_node-_right){Node* leftMost _node-_right;while (leftMost leftMost-_left){leftMost leftMost-_left;}_node leftMost;}else//2.当前节点右子树为空当前节点所在子树访问完了{Node* pcur _node;Node* parent pcur-_parent;while (parent pcur parent-_right){pcur parent;parent pcur-_parent;}_node parent;}return *this;}Self operator--(){//当迭代器是end()时特殊处理if (_node nullptr){Node* rightMost _root;while (rightMost rightMost-_right){rightMost rightMost-_right;}_node rightMost;}//1.左子树不为空找左子树最右节点else if (_node-_left){Node* rightMost _node-_left;while (rightMost rightMost-_right){rightMost rightMost-_right;}_node rightMost;}else//2.左子树为空当前节点所在子树访问完了{Node* pcur _node;Node* parent pcur-_parent;while (parent pcur parent-_left){pcur parent;parent parent-_parent;}_node parent;}return *this;}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}
};templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
public:typedef RBTreeIteratorT, T, T* Iterator;typedef RBTreeIteratorT, const T, const T* ConstIterator;RBTree() default;RBTree(const RBTreeK, T, KeyOfT t){_root _copy(t._root);}~RBTree(){_Destroy(_root);_root nullptr;}RBTreeK, T, KeyOfT operator(RBTreeK, T, KeyOfT t){swap(_root, t._root);return *this;}void InOrder(){_InOrder(_root);cout endl;}Iterator Begin(){Node* leftMost _root;while (leftMost leftMost-_left){leftMost leftMost-_left;}return Iterator(leftMost, _root);}Iterator End(){return Iterator(nullptr, _root);}ConstIterator Begin() const{Node* leftMost _root;while (leftMost leftMost-_left){leftMost leftMost-_left;}return ConstIterator(leftMost, _root);}ConstIterator End() const{return ConstIterator(nullptr, _root);}Iterator Find(const K key){KeyOfT kot;Node* pcur _root;while (pcur){if (key kot(pcur-_data)){pcur pcur-_left;}else if (key kot(pcur-_data)){pcur pcur-_right;}else{return Iterator(pcur, _root);}}return End();}pairIterator, bool Insert(const T data){KeyOfT kot;Node* pcur _root;Node* parent nullptr;if (pcur nullptr)//当前还没有节点{_root new Node(data);_root-_col BLACK;//根节点必须是黑色的return make_pair(Iterator(_root, _root), true);}while (pcur){if (kot(data) kot(pcur-_data)){parent pcur;pcur pcur-_left;}else if (kot(data) kot(pcur-_data)){parent pcur;pcur pcur-_right;}else{return make_pair(Iterator(pcur, _root), false);}}pcur new Node(data);Node* newnode pcur;//记录新节点指针旋转可能会更新pcurif (kot(data) kot(parent-_data)){parent-_left pcur;}else{parent-_right pcur;}pcur-_parent parent;Node* grandfather parent-_parent;Node* uncle nullptr;//当父节点存在且颜色为红需要往上更新while (parent parent-_col RED){if (parent grandfather-_left){uncle grandfather-_right;}else{uncle grandfather-_left;}if (uncle uncle-_col RED)//情况一u存在且为红{parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;if (grandfather-_parent nullptr){grandfather-_col BLACK;return make_pair(Iterator(newnode, _root), true);}pcur grandfather;parent pcur-_parent;grandfather parent-_parent;}else //情况二u存在且为黑 / 情况三u不存在{if (parent grandfather-_left pcur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_left pcur parent-_right){RotateL(parent);RotateR(grandfather);pcur-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_right pcur parent-_left){RotateR(parent);RotateL(grandfather);pcur-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_right pcur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}break;}}return make_pair(Iterator(newnode, _root), true);}private:void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;subL-_right parent;if (subLR){subLR-_parent parent;}Node* parentparent parent-_parent;parent-_parent subL;if (parentparent nullptr){_root subL;}else{if (parent parentparent-_left){parentparent-_left subL;}else{parentparent-_right subL;}}subL-_parent parentparent;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL){subRL-_parent parent;}subR-_left parent;Node* parentparent parent-_parent;parent-_parent subR;if (parentparent nullptr){_root subR;}else{if (parent parentparent-_left){parentparent-_left subR;}else{parentparent-_right subR;}}subR-_parent parentparent;}Node* _copy(Node* root){if (root nullptr){return nullptr;}Node* newnode new Node(root-_kv);newnode-_left copy(root-_left);newnode-_right copy(root-_right);return newnode;}void _Destroy(Node* root){if (root nullptr){return;}_Destroy(root-_left);_Destroy(root-_right);delete root;}void _InOrder(Node* root){if (root nullptr)//递归一定要有结束条件{return;}_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}private:Node* _root nullptr;
};MySet.h:
#pragma once#include RBTree.hnamespace yjz
{templateclass Kclass set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename RBTreeK, const K, SetKeyOfT::Iterator iterator;typedef typename RBTreeK, const K, SetKeyOfT::ConstIterator 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 K key){return _t.Insert(key);}iterator find(const K key){return _t.Find(key);}private:RBTreeK, const K, SetKeyOfT _t;};void Print(const setint s){setint::iterator it s.end();while (it ! s.begin()){--it;cout *it ;}cout endl;}void test_set(){setint s;int a[] { 4,2,6,1,3,5,15,7,16,14 };for (auto e : a){s.insert(e);}for (auto e : s){cout e ;}cout endl;setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;setint::iterator It s.end();while (It ! s.begin()){--It;cout *It ;}cout endl;Print(s);}
}MyMap.h:
#pragma once#include RBTree.hnamespace yjz
{templateclass K, class Vstruct map{struct MapKeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};public:typedef typename RBTreeK, pairconst K, V, MapKeyOfT::Iterator iterator;typedef typename RBTreeK, pairconst K, V, MapKeyOfT::ConstIterator 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 pairconst K, V kv){return _t.Insert(kv);}iterator find(const K key){return _t.Find(key);}V operator[](const K key){pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;}private:RBTreeK, pairconst K, V, MapKeyOfT _t;};void test_map(){mapstring, string m;m.insert({ front, 前 });m.insert({ behind, 后 });m.insert({ left, 左 });m.insert({ right, 右 });mapstring, string::iterator it m.begin();m[it-first] 前面;m[sort] 排序;m[string];while (it ! m.end()){//it-first x;it-second x;cout it-first - it-second endl;it;}cout endl;}
}本篇文章的分享就到这里了如果您觉得在本文有所收获还请留下您的三连支持哦~
