网站ping值,wordpress怎么迁移,中通建设计院网站,潍坊网站制作怎么做✨感谢您阅读本篇文章#xff0c;文章内容是个人学习笔记的整理#xff0c;如果哪里有误的话还请您指正噢✨ ✨ 个人主页#xff1a;余辉zmh–CSDN博客 ✨ 文章所属专栏#xff1a;c篇–CSDN博客 文章目录 前言一.set和map的初步封装1.树的节点封装修改2.Find()查找函数3.红… ✨感谢您阅读本篇文章文章内容是个人学习笔记的整理如果哪里有误的话还请您指正噢✨ ✨ 个人主页余辉zmh–CSDN博客 ✨ 文章所属专栏c篇–CSDN博客 文章目录 前言一.set和map的初步封装1.树的节点封装修改2.Find()查找函数3.红黑树的封装修改4.set和map的初步封装框架 二.红黑树的迭代器封装1.基本框架2.常用成员函数3.前置函数4.前置--函数5.红黑树封装中的迭代器函数6.红黑树封装中的插入函数修改 三.set封装完整实现1.set的迭代器函数2.set的插入函数3.测试 四.map封装完整实现1.map的迭代器函数2.map的插入函数3.map的operator[]函数4.测试 五.完整代码文件1.RBTree.h文件2.Set.h文件3.Map.h文件 前言 在之前的文章中我们知道set和map是两种常用的关联容器。他们内部通常使用红黑树来实现高效的查找插入和删除操作尽管它们提供了不同的接口函数但它们依然可以通过共享相同的底层数据结构也就是同一个红黑树来实现。下面将详细讲解如何通过改造我们之前的红黑树来实现我们自己的set和map容器。红黑树的实现在我上一篇文章中有详细讲解不清楚的可以看我之前的文章 一.set和map的初步封装
1.树的节点封装修改
首先我们来看一下我们之前的红黑树如何实现节点类的封装
//节点类封装
templateclass K,class V
class RBTreeNode{
public://构造函数RBTreeNode(const pairK,V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED) {}//成员变量RBTreeK,V* _left;RBTreeK,V* _right;RBTreeK,V* _parent;pairK,V _kv;Colour _col;
};我们学完set和map应该已经知道set存储的是一个key值而map存储的是一个键值对key-value在上面这段代码中如果通过这两个模板参数可以实现map但set却没办法使用因此这里节点类的两个模板参数需要使用一个泛型参数来修改这样就可以实现set和map能够共享一颗树。
修改如下
//RBTree.h文件templateclass T
class RBTreeNode {
public://构造函数RBTreeNode(const T data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}//成员变量RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;Colour _col;
};通过上面的修改为一个模板参数就可以实现共享效果
set存储的是一个键值key这里的模板参数T就是键值key的类型
map存储的是一个键值对key-value这里的模板参数T就是容器pairkeyvalue 类型
2.Find()查找函数
在上面对节点封装进行修改后这里又会产生新的问题如果我们要通过键值Key来查找对应的节点也就是Find()函数的参数是键值key对于set来说直接通过键值key就能找到但是map中的节点存储的是一个键值对key-value也就是一个pair(key,value)对象直接通过参数key并不能查找具体可以看下面函数
Node* Find(const K key){Node* cur_root;while(cur){//对于set来说_data就是key//对于map来说_data是一个piar(key,value)对象if(cur-_datakey){curcur-_right;}else if(cur-_datakey){curcur-_left;}else{return cur;}}return nullptr;
}因此为了解决这个问题这里需要借助一个仿函数来实现两个不同容器的查找 set的仿函数 struct SetKeyOfT{const K operator()(const K key){return key;}
};map的仿函数 struct MapKeyOfT{const K operator()(const pairK,V kv){return kv.first;}
};Find()函数 Node* Find(const K key){Node* cur_root;//对于set来说这里的KeyOfT就是SetKeyOfT//对于map来说这里的KeyOfT就是MapKeyOfTKeyOfT kot;while(cur){if(kot(cur-_data)){curcur-_right;}else if(kot(cur-_data)key){curcur-_left;}else{return cur;}}return nullptr;
}3.红黑树的封装修改
上面了解完如何实现两个不同容器之间的查找之后这里就需要开始对原本的红黑树进行封装修改从Find()函数中我们可以看到需要一个新的模板参数KeyOfT用来实现不同容器仿函数的查找功能。
修改如下:
//RBTree.h文件//增加一个新的模板参数KeyOfT
templateclass K,class V,class KeyOfT
class RBTree{typedef RBTreeNodeT Node;
public: //构造函数RBTree():_root(nullptr){}//Node* Find(const K key);//...其他成员函数private:Node* _root;
}4.set和map的初步封装框架
有了前面三个的基础这里就可以开始对set和map进行初步的封装set和map的底层都是借用同一个红黑树。 set的初步封装框架 //Set.h文件namesapce MySet{templateclass Kclass Set{//将仿函数设置为内部类struct SetKeyOfT{const K operator()(const K key){return key;}};public://...其他成员函数private://第一个模板参数K是set存储的数据类型RBTreeK,K,SetKeyOfT _t;};
};map的初步封装框架 //Map.h文件namesapce MyMap{templateclass K,class Vclass Map{//将仿函数设置为内部类struct MapKeyOfT{const K operator()(const pairK,V kv){return kv.first;}};public://...其他成员函数private://第一个模板参数K是set存储的数据类型RBTreeK,pairconst K,V,MapKeyOfT _t;};
};二.红黑树的迭代器封装
这里红黑树的迭代器封装其实和容器list比较类似不能像string和vector一样使用原生指针作为迭代器只能通过封装结点指针来实现迭代器。
1.基本框架
//迭代器封装
templateclass T,class Ptr,class Ref
class TreeIterator{//重命名定义typedef RBTreeNodeT Node;typedef TreeIteratorT,Ptr,Ref self;public://节点指针Node* _node;//构造函数TreeIterator(Node* node):_node(node){}//...成员函数}2.常用成员函数 operator*函数 //T operator*()
//const T operator*()
//用模板参数Ref来实现两个不同返回类型的替换
Ref opeartor*(){return _node-_data;
}operator-函数 //T* operator-()
//const T* operator-()
//用模板参数Ptr来实现两个不同返回类型的替换
Ptr operator-(){return _node-_data;
}operator!函数 bool operator!(const self s)const {return _node!s._node;
}operator函数 bool operator(const self s)const {return _nodes._node;
}3.前置函数 self operator(){//如果该节点右子节点不为空则到右子树中找最左节点if(_node-_right){Node* subleft_node-_right;while(subleft-_left){subleftsubleft-_left;}_nodesubleft;}//如果该节点右子节点为空则找到该节点父节点的左子节点的祖先节点else{Node* cur_node;Node* parentcur-_parent;while(parent){//如果cur节点是父节点的右子节点继续往上if(curparent-_right){curparent;parentparent-_parent;}//如果cur节点是父节点的左子节点停止else{break;}}_nodeparent;}return *this;
}4.前置--函数 self operator--(){if(_node-_left){Node* subright_node-_left;while(subright-_right){subrightsubright-_right;}_nodesubright;}else{Node* cur_node;Node* parentcur-_parent;while(parent){if(curparent-_left){curparent;parentparent-_parent;}else{break;}_nodeparent;}return *this;}
}5.红黑树封装中的迭代器函数
对于红黑树来说有普通对象迭代器和const对象迭代器。
templateclass ,class T,class KeyOfT
class RBTree{//....public://普通对象迭代器typedef TreeIteratorT,T*,T iterator;//const对象迭代器typedef TreeIteratorT,const T*,const T const_iterator;iterator begin(){Node* cur_root;while(curcur-_left){curcur-_left;}return cur;} iterator end(){return nullptr;}const_iterator begin()const {Node* cur_root;while(curcur-_left){curcur-_left;}return cur;}const_iterator end()const {return nullptr;}
}6.红黑树封装中的插入函数修改
有了前面红黑树封装的迭代器这里插入函数就可以进行修改从原本的bool类型变为pairiterator,bool类型其中iterator表示插入位置的迭代器如果差人成功返回插入位置的迭代器和true如果该值已经存在返回该值位置的迭代器和false。
//这里第三个模板参数KeyOfT就可以用到
pairiteraotr,bool insert(const T data){if(_rootnullptr){_rootnew Node(data);_root-_colBLACK;return make_pair(_root,true);}Node* parentnullptr;Node* cur_root;KeyOfT kot;while(cur){if(kot(cur-_data)kot(data)){parentcur;curcur-_right;}else if(kot(cur-_data)kot(data)){parentcur;curcur-_left;}else{return make_pair(cur,false);}}curnew Node(data);cur_colRED;if(kot(parent-_data)kot(data)){parent-_rightcur;}else{parent-_leftcur;}cur-_parentparent;//更新平衡因子旋转变色//...return make_pair(newnode,true);
}三.set封装完整实现
1.set的迭代器函数
在前面通过对红黑树的迭代器进行封装之后这里就可以直接实现set的迭代器函数
代码实现
namespace MySet{templateclass Kclass set{//内部类用来获取set存储对象中的key值struct SetKeyOfT{const K operator()(const K key){return key;}};public://这里的类模板还没有实例化对象所以要加上关键字typenametypedef typename RBTreeK,K,SetKeyOfT::const_iterator iterator;typedef typename RBTreeK,K,SetKeyOfT::const_iterator const_iterator;//set的begin()函数const_iterator begin()const {return _t.begin();}//set的end()函数const_iterator end()const {return _t.end();}private://第一个模板参数k是set存储的数据类型RBTreeK,K,SetKeyOfT _t;};
};实现原理 首先就是要将红黑树原本的迭代器类型进行命名重定义这里有一个注意点因为RBTreeK,K,SetKeyOfT是一个类模板现在还没有进行实例化所以直接加上作用域限定符::后面加上迭代器类型会报错因为编译器并不知道当前模板参数的具体类型因此要加上关键字typename。 其次set还有一个性质就是对于key值不能进行修改所以使用迭代器时如果对于当前迭代器解引用获取key值要求只能访问不能修改。因此我们这里可以将set的普通类型迭代器iterator和const类型迭代器const_iterator全都使用红黑树的const类型迭代器typename RBTreeK,K,SetKeyOfT::const_iterator。
2.set的插入函数
set的插入函数返回的是一个pairiterator,bool类型
pairiterator,bool insert(const K key){return _t.insert(key);
}注意set的返回类型pairiterator,bool表面上看起来是普通类型的迭代器但其实我们是将红黑树的const_iterator迭代器重命名定义成了iterator因此pairiterator,bool中的其实是const_iterator但是红黑树的插入函数返回的又是一个iterator所以这里直接写成上面的代码显然是错误的。
正确的写法是要进行一次类型转换
pairiterator,bool insert(const K key){pairtypename RBTreeK,K,SetKeyOfT::iterator ret_t.insert(key);return pairiterator,bool(ret.first,ret.second);
}为了实现从iterator类型转换为const_iterator我们要在红黑树的迭代器封装中添加一个构造函数
TreeIterator(Node* node)
:_node(node)
{}3.测试
测试代码
#includeSet.hint main(){MySet::setint s;s.insert(2);s.insert(10);s.insert(4);s.insert(7);MySet::setint::iterator sits.begin();while(sit!s.end()){//(*sit);//这里修改key值就会报错cout*sit ;sit;}coutendl;return 0;
}测试结果 四.map封装完整实现
1.map的迭代器函数
这里map的迭代器函数和set的有些不同因为set要求存储的key值不能被修改而map只限定了键值对中的key值不能修改而value值可以修改所以这里使用红黑树类模板做参数时有些不同通过pairconst K,V实现key值不能修改而value值可以修改。
namespace MyMap{templateclass K,class Vclass Map{struct MapKeyOfT{const K operator()(const pairconst K,V kv){return kv.first;}};public://map的普通迭代器iteratortypedef typename RBTreeK,pairconst K,V,MapKeyOfT::iterator iterator;//map的const类型迭代器const_iteratortypedef 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();}//其他成员函数//...private:RBTreeK,pairconst K,V,MapKeyOfT _t;};
};2.map的插入函数
相较于set的插入函数map的插入函数就比较简单直接调用函数即可
pairiterator,bool insert(const pairconst K,V kv){return _t.insert(kv);
}3.map的operator[]函数
map相比于set还有一个其他的使用方法就是[][]可以通过key值返回value值。如果参数key值不存在map中会将参数key值插入到map中然后返回value的对应类型的初始化值当然还可以通过[]修改对应key值的value值。
V operator[](const K key){//V()是模板参数V的默认构造pairiterator,bool ritinsert(make_pair(key,v()));return rit.first-second;
}4.测试
测试代码
#includeMap.hvoid test1(){MyMap::Mapint,int m;m.insert(make_pair(3,3));m.insert(make_pair(2,2));m.insert(make_pair(1,1));MyMap::Mapint,int::iterator itm.begin();while(it!m.end()){//(it-first);//这里对key值修改就会报错coutit-first it-secondendl;it;}coutendl;m[3]1;m[4];m[5]100;for(auto e : m){coute.first e.secondendl;}
}int main(){test1();return 0;
}测试结果 五.完整代码文件
1.RBTree.h文件
#includeiostream
#includeutility
#includevector
#includetime.h
using namespace std;enum Colour {RED,BLACK
};templateclass T
class RBTreeNode {
public://构造函数RBTreeNode(const T data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}//成员变量RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;Colour _col;
};//迭代器类封装
templateclass T,class Ptr,class Ref
class TreeIterator{//重命名定义typedef RBTreeNodeT Node; typedef TreeIteratorT,Ptr,Ref self;typedef TreeIteratorT,T*,T Iterator;public:Node* _node;TreeIterator(Node* node):_node(node){}TreeIterator(const Iterator it):_node(it._node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const self s)const {return _node !s._node;}bool operator(const self s)const {return _nodes._node;}self operator(){//如果该节点右子节点不为空则到右子树中找最左节点if(_node-_right){Node* subleft_node-_right;while(subleft-_left){subleftsubleft-_left;}_nodesubleft;}//如果该节点右子节点为空则找到该节点父节点的左子节点的祖先节点else{Node* cur_node;Node* parentcur-_parent;while(parent){//如果cur节点是父节点的右子节点继续往上if(curparent-_right){ curparent;parentparent-_parent;}//如果cur节点是父节点的左子节点停止else{break;}}_nodeparent;}return *this;}self operator--(){//如果当前节点左子节点不为空则到该节点的左子树中的最右节点if(_node-_left){Node* subright_node-_left;while(subright-_right){subrightsubright-_right;}_nodesubright;}//如果该节点左子节点为空就到该节点的祖先节点的右子节点else{Node* cur_node;Node* parentcur-_parent;while(parent){if(curparent-_left){curparent;parentparent-_parent;}else{break;}}_nodeparent;}return *this;}};templateclass K , class T, class KeyOfT
class RBTree {typedef RBTreeNodeT Node;
public://普通对象迭代器typedef TreeIteratorT ,T* ,T iterator;//const对象迭代器typedef TreeIteratorT ,const T* ,const T const_iterator;//构造函数RBTree():_root(nullptr){}iterator begin(){Node* cur_root;while(curcur-_left){curcur-_left;}return cur;}iterator end(){return nullptr;}const_iterator begin()const {Node* cur_root;while(curcur-_left){curcur-_left;}return cur;}const_iterator end()const {return nullptr;}Node* Find(const K key){Node* cur_root;KeyOfT kot;while(cur){//这里参数key已经是K类型的所以不用调用仿函数kot()if(kot(cur-_data)key){ curcur-_right;}else if(kot(cur-_data)key){curcur-_left;}else{return cur;}}return nullptr;}pairiterator,bool insert(const T data) {if(_rootnullptr){_rootnew Node(data);_root-_colBLACK;return make_pair(_root,true);}Node* parentnullptr;Node* cur_root;KeyOfT kot;while(cur) {//这里参数data是T类型的是容器里存储的对象不是K类型所以要调用仿函数kot()获取key值if(kot(cur-_data)kot(data)) { parentcur;curcur-_right;}else if(kot(cur-_data)kot(data)) {parentcur;curcur-_left;}else {return make_pair(cur,false);}}curnew Node(data);cur-_colRED;if(kot(parent-_data)kot(data)){parent-_rightcur;}else{parent-_leftcur;}cur-_parentparent;Node* newnodecur;while(parentparent-_colRED){Node* grandfatherparent-_parent;//如果parent节点在左子节点if(parentgrandfather-_left){Node* unclegrandfather-_right;//如果uncle节点存在且节点为红色if(uncleuncle-_colRED){//变色parent-_coluncle-_colBLACK;grandfather-_colRED;//继续往上curgrandfather;parentcur-_parent;}//如果uncle节点不存在 或者 节点为黑色else{//如果cur节点在左子节点if(curparent-_left){//右单旋RotateR(grandfather);//旋转后变色grandfather-_colRED;parent-_colBLACK;}//如果cur节点在右子节点else{//左双旋//先左单旋再右单旋RotateL(parent);RotateR(grandfather);//旋转后变色cur-_colBLACK;grandfather-_colRED;}break;}}//如果parent节点在右子节点else{Node* unclegrandfather-_left;//如果uncle节点存在且节点为红色if(uncleuncle-_colRED){//变色parent-_coluncle-_colBLACK;grandfather-_colRED;//继续往上curgrandfather;parentcur-_parent;}//如果uncle节点不存在 后者 节点为黑色else{//如果cur节点在右子节点if(curparent-_right){//左单旋RotateL(grandfather);//变色parent-_colBLACK;grandfather-_colRED;}//如果cur节点在左子节点else{//右双旋//先右单旋再左单旋RotateR(parent);RotateL(grandfather);//旋转后变色cur-_colBLACK;grandfather-_colRED;}break;}}}_root-_colBLACK;return make_pair(newnode,true);}int Height(){return _Height(_root);}bool IsBlance(){return _IsBlance(_root);}private:int _Height(Node* root){if(rootnullptr){return 0;}int leftheight_Height(root-_left);int rightheight_Height(root-_right);return leftheightrightheight ? leftheight1 : rightheight1;}bool CheckColour(Node* root,int blacknum,int benchmark){//如果节点是空判断黑色节点个数是否等于基准值if(rootnullptr){if(blacknum!benchmark){return false;}return true;}//如果节点是黑色黑色个数加加if(root-_colBLACK){blacknum;}//如果节点是红色判断父节点是否也是红色不能出现连续的红色节点if(root-_colREDroot-_parentroot-_parent-_colRED){coutroot-_kv.firstRED Falseendl;return false;}return CheckColour(root-_left,blacknum,benchmark)CheckColour(root-_right,blacknum,benchmark);}bool _IsBlance(Node* root){if(rootnullptr){return true;}//如果根节点不是黑色返回错误if(root-_col!BLACK){return false;}//设置一个基准值int benchmark0;Node* curroot;while(cur){if(cur-_colBLACK){benchmark;}curcur-_left;}return CheckColour(root,0,benchmark);}//左单旋void RotateL(Node* parent){Node* curparent-_right;Node* curleftcur-_left;Node* ppnodeparent-_parent;parent-_rightcurleft;if(curleft){curleft-_parentparent;}cur-_leftparent;parent-_parentcur;if(ppnode){if(ppnode-_leftparent){ppnode-_leftcur;cur-_parentppnode;}else{ppnode-_rightcur;cur-_parentppnode;}}else{cur-_parentnullptr;_rootcur;}}//右单旋void RotateR(Node* parent){Node* curparent-_left;Node* currightcur-_right;Node* ppnodeparent-_parent;parent-_leftcurright;if(curright){curright-_parentparent;}cur-_rightparent;parent-_parentcur;if(ppnode){if(ppnode-_leftparent){ppnode-_leftcur;cur-_parentppnode;}else{ppnode-_rightcur;cur-_parentppnode;}}else{cur-_parentnullptr;_rootcur;}}private:Node* _root;
};2.Set.h文件
#includeRBTree.hnamespace MySet{templateclass Kclass set{//内部类用来获取set存储对象中的key值struct SetKeyOfT{const K operator()(const K key){return key;}};public://这里的类模板还没有实例化对象所以要加上关键字typenametypedef typename RBTreeK,K,SetKeyOfT::const_iterator iterator;typedef typename RBTreeK,K,SetKeyOfT::const_iterator const_iterator;const_iterator begin()const {return _t.begin();}const_iterator end()const {return _t.end();}//这里返回的是const_iterator类型的迭代器pairiterator,bool insert(const K key){//插入返回的是iterator类型的迭代器pairtypename RBTreeK,K,SetKeyOfT::iterator,bool ret_t.insert(key);return pairiterator,bool(ret.first,ret.second);}private://第一个模板参数k是set存储的数据类型RBTreeK,K,SetKeyOfT _t;};
};3.Map.h文件
#includeRBTree.hnamespace MyMap{templateclass K,class Vclass 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::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();}//operator[],通过key值返回value值具备插入和修改V operator[](const K key){pairiterator,bool ritinsert(make_pair(key,V()));return rit.first-second;}pairiterator,bool insert(const pairconst K,V kv){return _t.insert(kv);}private:RBTreeK,pairconst K,V,MapKeyOfT _t;};
};以上就是关于set和map的封装讲解如果哪里有错的话可以在评论区指正也欢迎大家一起讨论学习如果对你的学习有帮助的话点点赞关注支持一下吧
