免费网站一级域名注册,个人简历网站模板下载,天津wordpress开发,学校网站建设计入哪个会计科目一.map/set的封装 在实现了红黑树的部分功能后#xff0c;我们可以便可以将红黑树作为底层结构来封装map 和 set #xff0c;但是问题也随之而来。我们都知道map是k-v的数据模型#xff0c;而set是k的数据模型#xff0c;我们难道要去使用两棵红黑树来封装吗#xff1f;显…一.map/set的封装 在实现了红黑树的部分功能后我们可以便可以将红黑树作为底层结构来封装map 和 set 但是问题也随之而来。我们都知道map是k-v的数据模型而set是k的数据模型我们难道要去使用两棵红黑树来封装吗显然不是这样的。 接下来我们将使用同一棵红黑树实现 map和set。
1.1 封装的基本思路 因为我们是用一棵红黑树去封装两种容器使用我们的这棵红黑树使用我们的这棵树就不能像以前一样写死成k-v模型的数据结构需要稍作修改。 因为红黑树不能自己判断其是否是map/set类型我们能做的努力就是提高其适应性对红黑树的要求为 既能适配 K-V模型的map又能适配出K 模型的set。
对map和set的要求为 需要准确的传入数据传入时让红黑树只能适配出一个类型的容器对不需要的部分进行切割。
1.2 红黑树节点的调整 这是我们之前写出的红黑树节点现在来看显然不太合适因为我们已经把K-V模型写死了不太好适配出K模型的set。 在这里我们建议让pair类型变成 一个模糊的 T类型至于是pair 类型还是 k类型我们希望让map和set来准确的传入。 1.3 map 和 set 的定义 我们该如何适配map和set的底层来让其匹配红黑树呢 在这里我建议让其内部的模板暂时先有两个数据类型第一个为 K 模型第二个为 T模型也就是说 当为map时传入mapK,K时底层实际传入RBTreek,pairk,k,传入setk时底层实际传入RBTreeK,K。 这样有什么好处呢 为因为我们的底层实现是红黑树那么我们为了适应map又适应set实际传入的代表数据参数至少得是两个可能会有些人问“map可以直接传入pair啊那么为什么不直接传入一个RBTreepairK,V呢。 因为有find的存在map的find是按照k来进行查找的如果直接传入pair类型那么红黑树里面的实际类型只有一个pair当我们查找时根本无法按照key类型来查找所以我们的红黑树至少得有两个模板参数。 因此即使set是k模型但是在这里的底层结构上我们仍然需要传入两个k类型。
map和set基本定义如下
#pragma once
#includeRBTree.husing namespace MyRBTree;namespace MySet
{templateclass Kclass Set{private:RBTreeK, K _set;};
}
#pragma once
#includeRBTree.husing namespace MyRBTree;namespace MyMap
{templateclass K,class Vclass Map{private:RBTreeK, pairK,V _map;};
}
1.4 仿函数 KeyOfValue 在insert中我们经常会用到data进行一些比较但是我们现在data的类型不固定如果是map中的pair类型我们就应该用其first进行比较如果是k类型我们就应该直接比较。 最好的解决办法是在map和set内部分别定义一个KetOfValue 仿函数然后将其传入红黑树模板中因为其传入的内容不同所以我们用来分别处理不同的数据。 如果是map中的data因为是kv结构所以我们取出其data.first;如果是set中的k模型那么我们直接返回仿函数定义如下
#pragma once
#includeRBTree.h
using namespace MyRBTree;namespace MyMap
{templateclass K,class Vclass Map{public:struct MapKeyOfvalue{const K operator()(const pairK, V kv){return kv.first;}};private:RBTreeK, pairK,V, MapKeyOfvalue _map;};
}
#pragma once
#includeRBTree.husing namespace MyRBTree;namespace MySet
{templateclass Kclass Set{public:struct SetKeyOfvalue{const K operator()(const K key){return key;}};private:RBTreeK, K, SetKeyOfvalue _set;};
}
同时我们因为要多传入一个仿函数所以我们的模板和mapset内部的红黑树模板参数也要进行修改
同时我们在红黑树内部也需要对进行数据比对的函数进行修改比如说insert和find等等。 bool Insert(const pairK, V data){//因为需要使用仿函数的机会不多我们在需要用到的地方局部创建一下就可以了//如何大多数函数都需要用到建议定义为全局变量KeyOfValue kot;if (!_root){_root new Node(data);_root-_co Black;return true;}Node* cur _root;Node* parent nullptr;while (cur){//if (cur-_data.first data.first)if (kot(cur-_data) kot(data)){parent cur;cur cur-_right;}//else if (cur-_data.first data.first)else if (kot(cur-_data) kot(data.first)){parent cur;cur cur-_left;}else{return false;}}cur new Node(data);cur-_co Red;//if (parent-_data.first cur-_data.first)if (kot(parent-_data) kot(cur-_data)){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;//开始判断是否需要变色while (parent parent-_co Red){Node* grand parent-_parent;if (parent grand-_left){Node* uncle grand-_right;if (uncle uncle-_co Red){//这里只变色就好parent-_co uncle-_co Black;grand-_co Red;cur grand;parent cur-_parent;}else{if (cur parent-_left){_RotateR(grand);grand-_co Red;parent-_co Black;}else{_RotateL(parent);_RotateR(grand);cur-_co Black;grand-_co Red;}break;}}else{Node* uncle grand-_left;if (uncle uncle-_co Red){//这里只变色就好parent-_co uncle-_co Black;grand-_co Red;cur grand;parent cur-_parent;}else{if (cur parent-_right){_RotateL(grand);grand-_co Red;parent-_co Black;}else{_RotateR(parent);_RotateL(grand);cur-_co Black;grand-_co Red;}break;}}}_root-_co Black;return true;} Node* Find(const K key){KeyOfValue kot;Node* cur _root;while (cur){//if (cur-_data.first key)if (kot(cur-_data) key){cur cur-_right;}//else if (cur-_data.first key)else if (kot(cur-_data) key){cur cur-_left;}else{return cur;}}return nullptr;}
1.5 map/set的插入 现在在其内部直接套用红黑树的插入即可。
namespace MySet
{templateclass Kclass Set{public:struct SetKeyOfvalue{const K operator()(const K key){return key;}};bool insert(const K k){return _set.Insert(k);}private:RBTreeK, K, SetKeyOfvalue _set;};
}
namespace MyMap
{templateclass K,class Vclass Map{public:struct MapKeyOfvalue{const K operator()(const pairK, V kv){return kv.first;}};bool insert(const pairK,V kv){return _map.Insert(kv);}private:RBTreeK, pairK,V, MapKeyOfvalue _map;};
} 在map和set中先插入一些数据来看一下有没有更改错误
这里建议在map和set内部封装进去红黑树的Inorder打印一下检查一下错误。
void Inorder()
{_map.Inorder();
}//判断一下是否平衡void IsBalance()
{_map.IsBalance();
}
同时我们的Inorder函数也需要更改
void _Inorder(Node* root)
{if (!root){return;}//这里我们也要更改一下_Inorder(root-_left);//cout root-_data.first : endl;cout kot(root-_data) ;_Inorder(root-_right);
}
验证一下map和set的准确性
#includeMyMap.h
#includeMySet.hvoid testmap()
{MyMap::Mapint, int _m;_m.insert(make_pair(1, 1));_m.insert(make_pair(2, 1));_m.insert(make_pair(3, 1));_m.insert(make_pair(4, 1));_m.insert(make_pair(5, 1));_m.Inorder();_m.IsBalance();cout endl endl;
}void testset()
{MySet::Setint _s;_s.insert(1);_s.insert(2);_s.insert(3);_s.insert(4);_s.insert(5);_s.Inorder();_s.IsBalance();cout endlendl;
}int main()
{testmap();testset();return 0;
}
结果为
二. map和set迭代器的实现 首先我们要明白map/set只是相当于一层壳子真正的底层实现永远都在红黑树的部分迭代器也是同理我们撰写的迭代器应该书写在红黑树部分。 迭代器的基本定义 // 节点数据 引用/const引用 指针/const指针template class T, class Ref, class Ptrstruct _RBTreeIterator{typedef RBTreeNodeT Node;typedef _RBTreeIteratorT, Ref, Ptr self;Node* _node;_RBTreeIterator(Node* node):_node(node){}};
2.1 解引用运算符重载 一般用来取出其节点中存储的数据直接返回data即可并且一般而言是是可以修改的因此这里我们返回其引用。
Ref operator*()
{return _node-_data;
}
2.2 成员访问运算符重载 - 运算符一般用来返回该节点的地址主要还是适用于map中用来访问pair里面的first和second成员。
Ptr operator-()
{return (_node-_data);
}
2.3 和 ! 运算符重载
这个就比较简单了 bool operator(const self s){return _node s._node;}bool operator!(const self s){return _node ! s._node;} 2.4 begin()和end() 迭代器常用成员函数begin()与end()其中begin()对应红黑树的最左节点end()对应最后一个节点的下一个节点即nullptr(这里我们并没有设置哨兵位感兴趣的同学可以自己研究一下 iterator begin()
{Node* left _root;while (left left-_left){left left-_left;}return iterator(left);
}iterator end()
{return iterator(nullptr);
} 2.6 运算符重载 首先我们要知道红黑树也是一个二叉搜索树我们对其的遍历顺序也是按照中序遍历因此运算符在这里指的是中序遍历的下一个节点。 那我们该如何找寻中序遍历的下一个节点呢。 我们先来观察一部分红黑树的遍历情况 当it指向17 时实际上是去访问18这个节点17有右子树 当it访问18时实际上是去访问33这个节点18无右子树故向上遍历 当it访问33时实际上是去访问37这个节点33有右子树 当it访问37时实际上是去访问42这个节点37无右子树向上遍历 我们可以看出实际上始终围绕着右子树进行移动 1.当所在节点有右子树时访问右子树的最左节点 2.当所在节点没有右子树时 找孩子不是父亲右节点的祖先这里需要进行遍历 故得到代码
self operator() //迭代器依旧返回迭代器
{//如果右子树存在if (_node-_right){Node* left _node-_right;//则寻找右子树的最左节点while (left-_left){left left-_left;}_node left;}//如果右子树不存在else{//找孩子不是父亲右节点的节点Node* parent _node-_parent;Node* cur _node; //一定要先判断parent是否存在以此来避免越界while (parentcur parent-_right){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;
}
//迭代器后置self operator(int){self it(_node);(*this);return it;}2.7 --运算符重载 --就是 代码思路反过来。 左子树不为空进行 -- 则是指向左子树(最右节点)。左子树为空-- 找孩子不是父亲左节点的祖先循环查找 得到代码如下 self operator--(){//如果左子树存在if (_node-left){//找左子树的最右节点Node* right _node-_left;while (right-_right){right right-_right;}_node rihgt;}//如果左子树不存在else{//找孩子不是父亲左节点的节点Node* parent _node-parent;Node* cur _node;while (parentparent-_left cur){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}//后置--self operator--(int){self it(_node);--(*this);return it;}
迭代器在map和set中的封装如下 三 map的[] 下标访问运算符重载 我们可以看到其返回为mapped_type类型这是什么呢
map文档中有如下声明
翻译一下我们得知在map中定义为其第二个模板参数T我们这里为V的别名
在官方库里面对这个【】是这样实现的 太迷茫了我们拆解来看一下
里面的第一层为 可见就是一层简单的插入 第一个传入的是k的值第二个是我们map中第二个模板参数V的默认构造。 第二步将this指针指向insert返回的这个内容。
第三步 取出this指向的内容中的first内容那么问题来了我们自己定义的insert返回的内容是bool类型我们该取这个的first吗显然不是的让我们看看库中的insert函数。 库中的返回值是一个pair类型其内部分别是一个i迭代器和bool类型那么这样的作法我们也就理解了现在我们要修改一下insert。 set中虽然用不到【】但其内部和set是一样定义的。 更改结果如下(RBTree内
typedef _RBTreeIteratorT, T, T* iterator;
typedef _RBTreeIteratorT, const T, const T* const_iterator;iterator begin()
{Node* left _root;while (left left-_left){left left-_left;}return iterator(left);
}iterator end()
{return iterator(nullptr);
}//bool Insert(const T data)
pairiterator, bool Insert(const T data)
{if (!_root){_root new Node(data);_root-_co Black;//如果成功返回成功节点的迭代器和truereturn make_pair(iterator(_root), true);}Node* cur _root;Node* parent nullptr;while (cur){//if (cur-_data.first data.first)if (kot(cur-_data) kot(data)){parent cur;cur cur-_right;}//else if (cur-_data.first data.first)else if (kot(cur-_data) kot(data)){parent cur;cur cur-_left;}else{//return false;return make_pair(iterator(cur), false);}}cur new Node(data);cur-_co Red;//注意这里cur可能因为旋转改变了原来的位置所以需要提前记录一下Node* newnode cur;//if (parent-_data.first cur-_data.first)if (kot(parent-_data) kot(cur-_data)){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;//开始判断是否需要变色while (parent parent-_co Red){Node* grand parent-_parent;if (parent grand-_left){Node* uncle grand-_right;if (uncle uncle-_co Red){//这里只变色就好parent-_co uncle-_co Black;grand-_co Red;cur grand;parent cur-_parent;}else{if (cur parent-_left){_RotateR(grand);grand-_co Red;parent-_co Black;}else{_RotateL(parent);_RotateR(grand);cur-_co Black;grand-_co Red;}break;}}else{Node* uncle grand-_left;if (uncle uncle-_co Red){//这里只变色就好parent-_co uncle-_co Black;grand-_co Red;cur grand;parent cur-_parent;}else{if (cur parent-_right){_RotateL(grand);grand-_co Red;parent-_co Black;}else{_RotateR(parent);_RotateL(grand);cur-_co Black;grand-_co Red;}break;}}}_root-_co Black;//return true;return make_pair(iterator(newnode), true);
} map和set内
第四步解引用返回因为first是个迭代器类型对其解引用返回data值 但是我们自己实现时应该返回其data值里面的second因为map的特性只有second可以被修改。
故可以得出以下代码 注意这是定义在map里面的并非定义在迭代器里面 V operator[](const K key){pairiterator, bool result insert(make_pair(key, V()));//如果存在则插入失败//如果不存在则插入数据//无论是否存在,都返回 second;return result.first-second;} 四.源代码 测试用例
其实map和set还有很多可以值得封装的地方这里我们给出一个比较完整的源代码
map
#pragma once
#includeRBTree.h
using namespace MyRBTree;namespace MyMap
{templateclass K,class Vclass Map{public:struct MapKeyOfvalue{const K operator()(const pairK, V kv){return kv.first;}};//注意声明迭代器//如果想取一个类模板中的一个类型要使用 typedname 进行声明。//告诉编译器这是一个类型并不是一个静态变量typedef typename RBTreeK, pairK, V, MapKeyOfvalue::iterator iterator;typedef typename RBTreeK, pairK, V, MapKeyOfvalue::const_iterator const_iterator;pairiterator,bool insert(const pairK,V kv){return _map.Insert(kv);}void Inorder(){_map.Inorder();}void IsBalance(){_map.IsBalance();}V operator[](const K key){pairiterator, bool result insert(make_pair(key, V()));//如果存在则插入失败//如果不存在则插入数据//无论是否存在,都返回 second;return result.first-second;}iterator begin(){return _map.begin();}iterator end(){return _map.end();}{return _map.begin();}iterator end(){return _map.end();}private:RBTreeK, pairK,V, MapKeyOfvalue _map;};
}
set
#pragma once
#includeRBTree.husing namespace MyRBTree;namespace MySet
{templateclass Kclass Set{public:struct SetKeyOfvalue{const K operator()(const K key){return key;}};//注意声明迭代器//如果想取一个类模板中的一个类型要使用 typedname 进行声明。//告诉编译器这是一个类型并不是一个静态变量typedef typename RBTreeK, K, SetKeyOfvalue::const_iterator iterator;typedef typename RBTreeK, K, SetKeyOfvalue::const_iterator const_iterator;pairiterator,bool insert(const K k){return _set.Insert(k);}void Inorder(){_set.Inorder();}void IsBalance(){_set.IsBalance();}private:RBTreeK, K, SetKeyOfvalue _set;};
}
红黑树
#pragma once
#includeiostream
using namespace std;namespace MyRBTree
{enum Color{Red,Black};//直接实现kv模型的红黑树templateclass Tstruct RBTreeNode{RBTreeNode(const T data):_co(Red), _left(nullptr), _right(nullptr), _parent(nullptr), _data(data){}Color _co;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;};// 节点数据 引用/const引用 指针/const指针template class T, class Ref, class Ptrstruct _RBTreeIterator{typedef RBTreeNodeT Node;typedef _RBTreeIteratorT, Ref, Ptr self;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;}self operator() //迭代器依旧返回迭代器{//如果右子树存在if (_node-_right){Node* left _node-_right;//则寻找右子树的最左节点while (left-_left){left left-_left;}_node left;}//如果右子树不存在else{//找孩子不是父亲右节点的节点Node* parent _node-_parent;Node* cur _node; //一定要先判断parent是否存在以此来避免越界while (parentcur parent-_right){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}//迭代器后置self operator(int){self it(_node);(*this);return it;}self operator--(){//如果左子树存在if (_node-left){//找左子树的最右节点Node* right _node-_left;while (right-_right){right right-_right;}_node right;}//如果左子树不存在else{//找孩子不是父亲左节点的节点Node* parent _node-parent;Node* cur _node;while (parentparent-_left cur){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}//后置--self operator--(int){self it(_node);--(*this);return it;}_RBTreeIterator(Node* node):_node(node){}Node* _node;};templateclass K, class T, class KeyOfValueclass RBTree{public:typedef RBTreeNodeT Node;typedef _RBTreeIteratorT, T, T* iterator;typedef _RBTreeIteratorT, const T, const T* const_iterator;iterator begin(){Node* left _root;while (left left-_left){left left-_left;}return iterator(left);}iterator end(){return iterator(nullptr);}const_iterator cbegin() const{Node* left _root;while (left left-_left){left left-_left;}return const_iterator(left);}const_iterator cend() const {return const_iterator(nullptr);}//bool Insert(const T data)//pairiterator,bool Insert(const T data) pairNode*, bool Insert(const T data) //因为set中的iterator是 const迭代器不可以转化为iterator类型变成node在返回时可以构造出iterator和const迭代器{if (!_root){_root new Node(data);_root-_co Black;//如果成功返回成功节点的迭代器和truereturn make_pair(_root, true);}Node* cur _root;Node* parent nullptr;while (cur){//if (cur-_data.first data.first)if (kot(cur-_data) kot(data)){parent cur;cur cur-_right;}//else if (cur-_data.first data.first)else if (kot(cur-_data) kot(data)){parent cur;cur cur-_left;}else{//return false;return make_pair(cur, false);}}cur new Node(data);cur-_co Red;//注意这里cur可能因为旋转改变了原来的位置所以需要提前记录一下Node* newnode cur;//if (parent-_data.first cur-_data.first)if (kot(parent-_data) kot(cur-_data)){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;//开始判断是否需要变色while (parent parent-_co Red){Node* grand parent-_parent;if (parent grand-_left){Node* uncle grand-_right;if (uncle uncle-_co Red){//这里只变色就好parent-_co uncle-_co Black;grand-_co Red;cur grand;parent cur-_parent;}else{if (cur parent-_left){_RotateR(grand);grand-_co Red;parent-_co Black;}else{_RotateL(parent);_RotateR(grand);cur-_co Black;grand-_co Red;}break;}}else{Node* uncle grand-_left;if (uncle uncle-_co Red){//这里只变色就好parent-_co uncle-_co Black;grand-_co Red;cur grand;parent cur-_parent;}else{if (cur parent-_right){_RotateL(grand);grand-_co Red;parent-_co Black;}else{_RotateR(parent);_RotateL(grand);cur-_co Black;grand-_co Red;}break;}}}_root-_co Black;//return true;return make_pair(newnode, true);}void Inorder(){_Inorder(_root);}bool IsBalance(){return _IsBalance();}Node* Find(const K key){//KeyOfValue kot;Node* cur _root;while (cur){//if (cur-_data.first key)if (kot(cur-_data) key){cur cur-_right;}//else if (cur-_data.first key)else if (kot(cur-_data) key){cur cur-_left;}else{return cur;}}return nullptr;}//求最左节点Node* LeftMost(){Node* cur _root;while (cur cur-_left){cur cur-_left;}return cur;}//求最右节点Node* RightMost(){Node* cur _root;while (cur cur-_right){cur cur-_right;}return cur;}private:bool _IsBalance(){if (!_root) return true;if (_root-_co Red){cout 根节点为红色 endl;return false;}int BlackSum 0;Node* cur _root;while (cur){if (cur-_co Black) BlackSum;cur cur-_left;}return _Check(_root, 0, BlackSum);}bool _Check(Node* root, int Blacknum, int BlackSum){if (!root){if (Blacknum ! BlackSum){cout 某条路径黑色节点的数量不相等 endl;return false;}return true;}if (root-_co Black){Blacknum;}if (root-_co Red root-_parent root-_parent-_co Red){cout 存在连续的红色节点 endl;return false;}return _Check(root-_left, Blacknum, BlackSum) _Check(root-_right, Blacknum, BlackSum);}//直接创建一个全局变量递归遍历的话消耗太高//注意把前面我们更改的删除//KeyOfValue kot;void _Inorder(Node* root){if (!root){return;}//这里我们也要更改一下_Inorder(root-_left);//cout root-_data.first : endl;cout kot(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;Node* pparent parent-_parent;SubL-_right parent;parent-_parent SubL;if (_root parent){_root SubL;SubL-_parent nullptr;}else{if (pparent-_left parent){pparent-_left SubL;}else{pparent-_right SubL;}SubL-_parent pparent;}}void _RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;subR-_left parent; //将subR的左指针指向parentNode* pparent parent-_parent;parent-_parent subR;//将parent的父指针指向subRif (subRL)subRL-_parent parent;if (_root parent) //判断parent是否是头节点{_root subR;subR-_parent nullptr;}else{if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}subR-_parent pparent;}}KeyOfValue kot;Node* _root nullptr;};
}
