网站导航设计法则,国外做问卷网站好,天津塘沽网站建设,申请自媒体账号如果不知道红黑树是什么的时候可以去看看这个红黑树
思路
首先我们可以把封装分为两个层面理解#xff0c;上层代码就是set,和map#xff0c;底层就是红黑树 就相当于根据红黑树上面套了两个map,set的壳子#xff0c;像下面这张图一样 对于map和set#xff0c;map里面存…如果不知道红黑树是什么的时候可以去看看这个红黑树
思路
首先我们可以把封装分为两个层面理解上层代码就是set,和map底层就是红黑树 就相当于根据红黑树上面套了两个map,set的壳子像下面这张图一样 对于map和setmap里面存放的是pair一个键值对而set就只是一个key一般的想法是实现两个红黑树一个里面的节点放key一个放pair那么这样就太冗余了那么我们只用实现一个红黑树就行了我们利用模板就可以很轻松的解决冗余的问题 下面就来看看怎么具体的实现的
创建set,map
这里的set和map我们统称为myset,mymap 我们首先根据红黑树的基础把set,和map的架子搭起来 先来实现基本的插入功能
# includeRBtree.h
namespace mymap
{templateclass key, class valueclass mymap{public:struct k_of_t_map{const key operator()(const pairkey,value input_map){return input_map.first;}};bool Insert(const pairkey, value input_map){return _t.insert(input_map);}private:RBtreekey, pair const key, value, k_of_t_map _t;};
}
我们在插入的时候是根据搜索树的规则进行插入的搜索树肯定是要比较大小的我们的pair他原生是支持比较大小的但是库里面的比较大小是根据first和second来进行比较的我们这里肯定不是这样的我们是想两个pair不同的first进行比较大小的所以库里面的比较无法满足我们的需求 这里我们的解决方法是利用仿函数
struct k_of_t_map{const key operator()(const pairkey,value input_map){return input_map.first;}};我们通过实现一个内部类对operator()的重载实现类似于函数()的功能就能像函数一样使用去实现我们想要的功能这里我们通过operator()我们直接返回input_map.first,就得到了我们想要的pair的first也就是用来比较大小的key
同样set也是一样的道理 这里的set其实有点冗余了是为了配合map而创建的他本身就不需要都行
# includeRBtree.h
namespace myset
{templateclass keyclass myset{public:struct k_of_t_set{const key operator()(const key input_key){return input_key;}};bool Insert(const key input_key){return _t.insert(input_key);}private:RBtree key,const key,k_of_t_set _t;};
}有了上面的架子之后我们红黑树的插入功能里面的比较大小的方法也需要改一下改成在比较大小的时候去调用mymap,myset里面的内部类里面的成员函数。
所以我们在创建mymap,myset的成员变量时就要根据RBtree在加上自身的性质来创建这里mymap和myset最核心的差别就是一个数据类型另一个是比较大小的逻辑不同所以我们在RBtree的模板参数就要变成
templateclass key, class T, class k_of_t多提供一个k_of_t的模板参数 这个就是用来设置比较大小的方法用的 所以我们对于的mymap,myset就要变成
RBtreekey, pair const key, value, k_of_t_map _t;
RBtree key,const key,k_of_t_set _t;然后再插入的比较大小的逻辑也要套用这个内部类的成员函数 首先通过k_of_t来创建一个 kot的对象 然后再根据这个对象去调用相应的成员函数 关于mymap,myset的成员变量的初始化 其实我们根据代码我们就可以发现mymap,myset的成员函数的初始化其实就是去复用RBtree的初始化 就像一个映射一样**假设初始化mymap把mymap里面的模板参数传过去然后再去初始化RBtree的_root。**把相应的数据类型比较大小的方法替换的mymap的比较方法 myset也是同理。 有了以上的步骤之后我们就可以实现mymap和myset的插入了
map set的迭代器
下面我们讲讲迭代器的实现 我们先来看看迭代器的构造
templateclass T,class ref,class ptr
//迭代器就相当于一个节点的指针
struct RBtreeIterator//默认公有
{typedef RBtreenodeT Node;typedef RBtreeIteratorT, ref, ptr self;Node* _it_node;RBtreeIterator (Node* input_node, Node* root):_it_node(input_node){}这里我们传了三个模板参数一个是数据类型一个是引用最后一个是指针 这样的目的是为了方便我们想要引用的时候用引用想要指针的时候用指针 这里我们的成员变量是一个RBtreenode类型我们需要构造一个节点把他当作一个指针做为我们迭代器遍历容器的一个媒介迭代器就相当于一个节点的指针 了解了上面的结构之后 下面我们来看看迭代器的operator和–这个是迭代器的核心也是比较难的
operator
先来看看代码
self operator()
{if (_it_node-_right ! nullptr)//找右最小节点{Node* right_min this-_it_node-_right;while (right_min-_left ! nullptr){right_min right_min-_left;}_it_node right_min;}else//右边访问完代表以他为基本的左子树右子树都完了,就要向上走{Node* cur _it_node;Node* parent cur-_pre_node;//这里要找的是相对于儿子的父亲父亲的右节点不是孩子的节点//如果一直是右节点就代表当前节点的左右子树都完了//如果找到父亲的左节点是孩子就代表父亲还有右节点没访问完。while (parent ! nullptr parent-_right cur){cur parent;parent cur-_pre_node;}_it_node parent;}return *this;
}这里我们需要和红黑树的性质一起来说一下我们知道红黑树的中序遍历出来是一个从小到大的有序序列 我们的也是利用这个思想来的但是中序遍历是一个看全局思想来的但我们这里是要看局部只考虑当前中序局部要访问的下⼀个结点。可以看成一个局部的左根右 为什么不能直接用中序遍历来写红黑树的迭代器 那是因为 随机访问需求 迭代器通常需要支持随机访问操作这意味着可以在常数时间内访问任意一个元素。而中序遍历是线性的不支持随机访问。 也不能更加灵活的访问容器每次都要从根开始 我们现在来具体说一下代码
if (_it_node-_right ! nullptr)//找右最小节点{Node* right_min this-_it_node-_right;while (right_min-_left ! nullptr){right_min right_min-_left;}_it_node right_min;}这里是找除开当前节点如果当前节点的右边不为空我们就要一直找右边的最小节点也就是最左节点) 为什么要这样找我们可以联系下面的这个beign()这个函数来看看
typedef RBtreenodeT node;
typedef RBtreeIteratorT, T, T* Iterator;
typedef RBtreeIteratorT, const T, const T* ConstIterator;
Iterator begin()
{node* cur _root;while (cur ! nullptr cur-_left ! nullptr){cur cur-_left;}return Iterator(cur);
}这个begin()返回的是一个迭代器类型他是一直找红黑树的最小节点找到之后用最小节点去构造一个迭代器类型当找到最小节点的时候就代表以这个节点为基准他的左子树已经访问完了然后要去看看右子树我们可以画图看看 然后我们来看看下面的代码 else//右边访问完代表以他为基本的左子树右子树都完了,就要向上走{Node* cur _it_node;Node* parent cur-_pre_node;//这里要找的是相对于儿子的父亲父亲的右节点不是孩子的节点//如果一直是右节点就代表当前节点的左右子树都完了//如果找到父亲的左节点是孩子就代表父亲还有右节点没访问完。while (parent ! nullptr parent-_right cur){cur parent;parent cur-_pre_node;}_it_node parent;}return *this;
}当到15之后我们的第一个if进不去就要进else走到else说明15的左右子树都访问完了右边为空了就要向上返回去看看15的父亲也就是10的左右子树访问完没有15是10的右子树代表以10为基础的左右子树都访问完了又让10去找他的父亲18看看18的右子树是不是指向10的但通过图片来看18的左子树的指向10的说明18的右子树还没有访问然后就需要去访问18和18的右子树 总的来说就一句话就要去找不是自己父亲的右边是指向自己的节点 下面来说说operator–
operator- -
–的逻辑正好相反可以看成一个局部的右根左 我们先来看看end()
Iterator end()
{return Iterator(nullptr,_root);
}首先end()代表末尾我们这里直接用空表示的库里面是有一个哨兵位节点 就像这样 当然用空也可以实现这个功能 我们只需要特殊处理一下end我们就想表示红黑树里面的最右节点所以我们多再operator–里面多添加一种情况就行了去找他的最右节点但我们需要多传一个_root的参数进来 self operator--()
{//处理特殊情况if (this-_it_node nullptr){Node* rightmost _it_root;while (rightmost ! nullptr rightmost-_right ! nullptr){rightmost rightmost-_right;}_it_node rightmost;}//这里和begin()类似//右根左else if (this-_it_node-_left ! nullptr)//找左节点的最大节点{Node* left_max _it_node-_left;while (left_max ! nullptr left_max-_right ! nullptr){left_max left_max-_right;}this-_it_node left_max;}else//左边为空代表当前节点为基本的左右子树都访问完了{//就要往上面寻找不是父亲节点指向左边的孩子节点要找父亲节点指向右边是孩子节点的父亲节点Node* cur _it_node;Node* parent cur-_pre_node;while (parent ! nullptr parent-_left cur){cur parent;parent cur-_pre_node;}_it_node parent;}return *this;
}–就相当于反过来这里就不作过多说明了
迭代器整体代码
还有一些小的函数就不作过多说明了
templateclass T,class ref,class ptr
//迭代器就相当于一个节点的指针
struct RBtreeIterator//默认公有
{typedef RBtreenodeT Node;typedef RBtreeIteratorT, ref, ptr self;Node* _it_node;Node* _it_root;RBtreeIterator (Node* input_node, Node* root):_it_node(input_node), _it_root(root){}self operator(){if (_it_node-_right ! nullptr)//找右最小节点{Node* right_min this-_it_node-_right;while (right_min-_left ! nullptr){right_min right_min-_left;}_it_node right_min;}else//右边访问完代表以他为基本的左子树右子树都完了,就要向上走{Node* cur _it_node;Node* parent cur-_pre_node;//这里要找的是相对于儿子的父亲父亲的右节点不是孩子的节点//如果一直是右节点就代表当前节点的左右子树都完了//如果找到父亲的左节点是孩子就代表父亲还有右节点没访问完。while (parent ! nullptr parent-_right cur){cur parent;parent cur-_pre_node;}_it_node parent;}return *this;}self operator--(){//处理特殊情况if (this-_it_node nullptr){Node* rightmost _it_root;while (rightmost ! nullptr rightmost-_right ! nullptr){rightmost rightmost-_right;}_it_node rightmost;}//右根左else if (this-_it_node-_left ! nullptr)//找左节点的最大节点{Node* left_max _it_node-_left;while (left_max ! nullptr left_max-_right ! nullptr){left_max left_max-_right;}this-_it_node left_max;}else//左边为空代表当前节点为基本的左右子树都访问完了{//就要往上面寻找不是父亲节点指向左边的孩子节点要找父亲节点指向右边是孩子节点的父亲节点Node* cur _it_node;Node* parent cur-_pre_node;while (parent ! nullptr parent-_left cur){cur parent;parent cur-_pre_node;}_it_node parent;}return *this;}bool operator(const self input) const{return input._it_node _it_node;}bool operator!(const self input) const{return input._it_node ! _it_node;}ref operator*(){return this-_it_node-_data;}ptr operator-(){return this-_it_node-_data;}
};
operator[]
这个是map比较有特色的一个功能他支持插入查询和修改我们来看看是怎么实现的 来看看代码
value operator[](const key input_key) // int 1 0
{ //key valuepairiterator, bool ret Insert({ input_key,value() });iterator it ret.first;return it-second;
}首先要实现这个功能我们的插入的返回值需要修改一下 需要返回一个键值对 然后我们再来分析一下 首先我们用一个键值对ret来接受插入的返回值假设插入10红黑树里面没有10然后再插入一个value()的一个缺省值相当于一个默认构造int的就是0我把这个插入的默认值理解成一个占位符 插入成功返回true然后我们取这个返回值的first也就是一个迭代器然后这个迭代器也是pair类型的我们再返回他的second也就是返回里面存放的数据然后就可以插入了也就相当于it-second “123” 那是怎么支持查找和修改的呢 当我们再次插入10时insert就会返回一个false然后同样返回一个迭代器
然后去取他的first再取second就可以完成修改了 这样就实现了operator[]的功能 以上就是利用红黑树封装map和set实现主要功能有什么问题欢迎指正
