【C++进阶】四、使用红黑树对set和map进行封装(四)

news/2024/10/30 19:32:25/

目录

前言

一、改造红黑树

1.1 红黑树迭代器相关

1.2 红黑树接口相关

二、set代码

三、map代码


前言

        set 是 K模型的容器,map 是 KV模型的容器,但是它们的底层实现都是红黑树实现,即用红黑树可以封装出 set和 map,之前的篇章已经讲过红黑树了,这里就不解释了。

        接下来对红黑树进行改造,用改造后的红黑树封装出 set 和 map

一、改造红黑树

使用的代码是之前篇章红黑树实现的代码,改造后红黑树的框架如下:

#pragma onceenum Colour
{RED,BLACK,
};template<class T>
struct RBTreeNode
{//构造函数RBTreeNode(const T& data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}//成员变量T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;
};template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ref, Ptr> Self;typedef __RBTreeIterator<T, T&, T*> iterator;//构造__RBTreeIterator(Node* node):_node(node){}// 普通迭代器的时候,他是拷贝构造// const迭代器的时候,他是构造,支持用普通迭代器构造const迭代器__RBTreeIterator(const iterator& s):_node(s._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 _node == s._node;}Self& operator++(){if (_node->_right){Node* min = _node->_right;while (min->_left){min = min->_left;}_node = min;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node->_left){Node* max = _node->_left;while (max->_right){max = max->_right;}_node = max;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}//成员变量Node* _node;
};template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __RBTreeIterator<T, T&, T*> iterator;typedef __RBTreeIterator<T, const T&, const T*> const_iterator;iterator begin(){Node* left = _root;while (left->_left){left = left->_left;}return iterator(left);// 使用匿名对象构造返回}const_iterator begin()const{Node* left = _root;while (left->_left){left = left->_left;}return const_iterator(left);}iterator end(){return iterator(nullptr);}const_iterator end()const{return const_iterator(nullptr);}//插入pair<iterator, bool> Insert(const T& data){}//中序遍历void InOrder(){_InOrder(_root);}//检查红黑树特性bool IsBalance(){}
private://检查每条路径的黑色节点是否相等 && 是否出现连续红色节点bool Check(Node* root, int blackNum, int ref){}void _InOrder(Node* root){}//左单旋void RotateL(Node* parent){}//右单旋void RotateR(Node* parent){}
private:Node* _root = nullptr;//缺省值
};

代码过多就不贴完了,完整代码链接:code_c++/Set_and_Map/Set_and_Map/RBTree.h · Maple_fylqh/code - 码云 - 开源中国 (gitee.com)https://gitee.com/Maple_fylqh/code/blob/master/code_c++/Set_and_Map/Set_and_Map/RBTree.h

改造红黑树就是给红黑树增加迭代器相关的,这棵泛型的红黑树可以同时封装出set 和 map

1.1 红黑树迭代器相关

迭代器模板参数在 list 模拟实现已经有过解释,这里不解释了,模板参数 T 是红黑树存放数据的类型,下面解释

template<class T, class Ref, class Ptr>

        上面迭代器类只需提供构造函数即可, 拷贝构造和赋值不需要自己实现,默认生成的即可,当前迭代器赋值给另一个迭代器是不需要深拷贝的,浅拷贝就可以,拷贝构造也是;析构释放空间的事情不归迭代器类管理,迭代器类只需构建迭代器对象即可

上面红黑树迭代器实现的接口有:

    //构造__RBTreeIterator(Node* node):_node(node){}// 普通迭代器的时候,他是拷贝构造// const迭代器的时候,他是构造,支持用普通迭代器构造const迭代器__RBTreeIterator(const iterator& s):_node(s._node){}//解引用,获取数据Ref operator*(){}//返回数据的地址Ptr operator->(){}//比较两个迭代器是否不相等bool operator!=(const Self& s)const{}//比较两个迭代器是否相等bool operator==(const Self& s)const{}//前置++Self& operator++(){}//前置--Self& operator--(){}

说明一下,迭代器都是支持普通迭代器构造const迭代器

实现如下,这里它利用了构造函数和拷贝构造函数的特性,当传入的迭代器是普通迭代器时:参数类型与拷贝构造参数要求一致,它就是拷贝构造;当传入的的迭代器是 const迭代器,参数类型与拷贝构造函数不匹配,类型有差异,它就变成了构造函数

typedef __RBTreeIterator<T, T&, T*> iterator;// 普通迭代器的时候,他是拷贝构造
// const迭代器的时候,他是构造,支持用普通迭代器构造const迭代器
__RBTreeIterator(const iterator& s):_node(s._node)
{}

前置++ 和前置-- 是红黑树迭代器实现的重点

前置++

一个结点的正向迭代器进行 ++ 操作后,应该根据红黑树中序遍历的序列找到当前结点的下一个结点

如下图,传入第一个节点是1,迭代器++ 下一个节点是6,再次++ 节点为8,迭代器要达到这种效果才可以满足需求

思路:

  1. 传入一个节点,如果节点右不为空就先往右边走,找到右边节点最小的节点,该节点就是 ++ 的下一个节点
  2. 传入一个节点,如果节点的右子树为空,去找祖先,迭代依次往上走,找到孩子是父亲左的那个祖先节点 

代码如下: 

Self& operator++()
{if (_node->_right)//传入节点右不为空,找右边最小节点{Node* min = _node->_right;while (min->_left){min = min->_left;}_node = min;}else)//传入节点为空{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;
}

前置--

一个结点的迭代器进行 -- 操作后,就是红黑树中序遍历找到的结点的前一个结点 

如下图,比如传入第一个节点是27,迭代器-- 下一个节点是25,再次 -- 节点为22,迭代器要达到这种效果才可以满足需求

--的思路和 ++ 的思路类似,只不过是反过来找

思路:

  1. 传入一个节点,如果节点左不为空就先往左边走,找到左边节点最大的节点,该节点就是 -- 的下一个节点
  2. 传入一个节点,如果节点的左子树为空,去找祖先,迭代依次往上走,找到孩子是父亲右的那个祖先节点

代码如下:

Self& operator--()
{if (_node->_left)//传入节点左不为空就先往左边走,{Node* max = _node->_left;while (max->_right){max = max->_right;}_node = max;}else//传入节点左为空{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;
}

其他就不介绍了

1.2 红黑树接口相关

template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __RBTreeIterator<T, T&, T*> iterator;typedef __RBTreeIterator<T, const T&, const T*> const_iterator;private:Node* _root = nullptr;//缺省值
};

说明一下模板参数,为了实现泛型RBTree:

  1. 红黑树第一个参数是 K(Key),主要用于查找数据;
  2. 红黑树第二个模板参数 T ,可以识别是 map 还是 set,因为 set和 map传给 T的参数不一样,set 传的是 Key,map 传的是键值对 pair<K, V>;
  3. 红黑树第三个参数是 KeyOfT,这是一个仿函数,由于红黑树中 T 存的可能是K,也可能是pair<K, V>。那我们插入的时候该怎么比较结点的大小呢,对于set是没有问题的,直接可以用T比较,但是map就不行了,我们要取出pair<K, V>的 first来进行比较

二、set代码

#include "RBTree.h"namespace fy
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;iterator begin()const{return _t.begin();}iterator end()const{return _t.end();}pair<iterator, bool> insert(const K& key){pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);return pair<iterator, bool>(ret.first, ret.second);}private:RBTree<K, K, SetKeyOfT> _t;};void TestSet(){int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };set<int> s;for (auto& e : arr){s.insert(e);}set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;for (auto& e : s){cout << e << " ";}cout << endl;}
}

三、map代码

#include "RBTree.h"namespace fy
{template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<const K, V>& kv){return kv.first;}};public:typedef typename RBTree<const K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<const K, pair<const 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();}pair<iterator, bool> insert(const pair<const K, V>& kv){return _t.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};void TestMap(){int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };map<int, int> m;for (auto& e : arr){m.insert(make_pair(e, e));}map<int, int>::iterator it = m.begin();while(it != m.end()){it->second++;cout << it->first << "->" << it->second << endl;++it;}map<string, int> countMap;string str[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };for (auto& e : str){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}}
}

这篇文章写起来逻辑有点不通(难写)dog,主要是用来复习的

----------------我是分割线---------------

文章到这里就结束了,下一篇即将更新


http://www.ppmy.cn/news/32548.html

相关文章

【Linux学习】进程间通信——system V(共享内存 | 消息队列 | 信号量)

&#x1f431;作者&#xff1a;一只大喵咪1201 &#x1f431;专栏&#xff1a;《Linux学习》 &#x1f525;格言&#xff1a;你只管努力&#xff0c;剩下的交给时间&#xff01; 进程间通信——共享内存 | 消息队列 | 信号量&#x1f3c0;共享内存⚽系统调用shmgetkey值⚽系统…

DBA 日常:规模用户数据库访问权限管理

前言 研发、数据分析师及运维内部人员有数据查询、数据订正等需求。若无管控平台&#xff0c;则只能通过授予账号的形式来授权这些用户直接访问数据库。一般会按类型建几个不同级别权限的账号给对应的同学使用&#xff0c;这会导致以下问题&#xff1a; 因为一个账号对应的使…

3.系统学习JavaEE:多线程

作者&#xff1a;爱塔居 专栏&#xff1a;JavaEE 作者介绍&#xff1a;大三学生&#xff0c;希望跟大家一起进步 文章目录 目录 文章目录 上章节回顾 一、中断线程 1.1 给线程中设定一个结束标志位。 1.2 interrupt() 1.3为什么sleep要清空标志位呢&#xff1f; 二、等待一个线…

【前端】深入浅出缓存原理

缓存的基本原理 对于前端来说&#xff0c;缓存主要分为浏览器缓存&#xff08;比如 localStorage、sessionStorage、cookie等等&#xff09;以及http缓存&#xff0c;也是本文主要讲述的。 当然叫法也不一样&#xff0c;比如客户端缓存大概包括浏览器缓存和http缓存 所谓htt…

C语言进阶-数据的存储【详解】

一、类型的基本归类 &#xff08;1&#xff09;整型家族 字符存储和表示的时候本质上使用的是 ASCII 值&#xff0c;ASCII 值是整数&#xff0c;字符类型也归类到整型家族char 是不是 signed char 取决于编译器 &#xff08;2&#xff09;浮点数家族 浮点数家族包括&#xff1…

【Redis】高可用架构之哨兵模式 - Sentinel

Redis 高可用架构之哨兵模式 - Sentinel1. 前言2. Redis Sentinel 哨兵集群搭建2.1 一主两从2.2 三个哨兵3. Redis Sentinel 原理剖析3.1 什么哨兵模式3.2 哨兵机制的主要任务3.2.1 监控&#xff08;1&#xff09;每1s发送一次 PING 命令&#xff08;2&#xff09;PING 命令的回…

即时通讯系列-N-客户端如何在推拉结合的模式下保证消息的可靠性展示

结论先行 原则&#xff1a; server拉取的消息一定是连续的原则&#xff1a; 端侧记录的消息的连续段有两个作用&#xff1a; 1. 记录消息的连续性&#xff0c; 即起始中间没有断层&#xff0c; 2. 消息连续&#xff0c; 同时意味着消息是最新的&#xff0c;消息不是过期的。同…

排序算法汇总(数组+链表)

冒泡排序算法核心&#xff1a;相邻节点两两交换&#xff0c;重复进行&#xff08;n-1&#xff09;轮。时间复杂度为空间复杂度为是否稳定&#xff1a;稳定1.1 数组排序图1 冒泡排序算法&#xff08;数组&#xff09;public class BubbleSortArray {public static void main(Str…