C++ RBTree封装mapset

2024-05-26 00:28
文章标签 c++ 封装 rbtree mapset

本文主要是介绍C++ RBTree封装mapset，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

RBTreeNode的声明

 RBTree结构

 map结构

 set结构

改造红黑树

迭代器类

迭代器成员函数

默认成员函数 

Insert

set

map

RBTreeNode的声明

template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;colour _col;RBTreeNode(const T& data): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};

 RBTree结构

template<class K, class T, class KeyOfType>
class RBTree
{typedef RBTreeNode<T> node;
public:typedef  __RBTreeIterator<T, T&, T*> Iterator;typedef  __RBTreeIterator<T, const T&, const T*> ConstIterator;
private:node* _root = nullptr;
};

 map结构

namespace nineone
{template<class K, class V>class map{struct keyofmap{const K& operator()(const pair<K, V>& kv) const{return kv.first;}};public:private:RBTree<K, pair<const K, V>, keyofmap> rbt;};
}

 set结构

namespace nineone
{template<class K>class set{struct keyofset{const K& operator()(const K& lhs)  const{return lhs;}};public:private:RBTree<K, const K, keyofset> rbt;//这里没有const find说类型不对};
}
  • mapset通过组合的方式复用RBTree
  • 第二个模板参数是用来决定RBTree数的类型
  • 第三个模板参数是为了拿出T里的键，是去实例化的对象的变量里，就是node里的_data
  • 那不是有T和KeyOfType，为什么还需要第一个模板参数呢？因为作为成员函数形参的时候没法从T里拿出K，比如Find就要传进K进去

解释const

  • keyofmap是一个仿函数，用对象去调用，核心部分是operator()操作符的重载
  • 第一个const，为了防止返回的值被改变，从而对一个调用这个仿函数的函数，出现不被预期的结果
  • 第二个const，为了可以使const对象也可以调用
  • 第三个const，是为了防止 keyofmap 类成员函数的改变，那这类现在不是没有吗？这个仿函数的目的就是为了取出对应的K，建议看effectivC++

改造红黑树

迭代器类

template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{typedef RBTreeNode<T> node;typedef  __RBTreeIterator<T, Ref, Ptr> Self;node* _node;__RBTreeIterator( node *const n) :_node(n){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& self){return _node != self._node;}Self operator++(int){Self ret = *this;++*this;return ret;}Self operator++(){if (_node && _node->_right != nullptr){node* minright = _node->_right;while (minright->_left){minright = minright->_left; //果然，这里写错成_right了}_node = minright;}else{node* cur = _node;node* parent = cur->_parent;while (parent && parent->_right == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};
  • Ref对应的是T& 或者const T&；Ptr对应的是T* 或者const T*
  • 这是用一个类来封装node*指针，用类对象来使用迭代器
  • 构造里的const；指针是有两部分，第一是指针自身，第二是自己所指向的内容，★也就是说读写的有两部★；一个总结，const往左边找，左边没有往右边找，靠近哪个，哪个就是常量；node* const n这样写是为了防止传进来的指针被改变；如果是const node* n或node const * n那么是指针所指向的内容不能被改变，关键点是：这个指针所指向的内容是常量；而_node是一个读写指针指针，_node所指的内容和指针自身是可以改变的

operator++

  • 走到中序的下一个位置
  • 中序是左子树 根 右子树 ；过当前节点右不为空，就要去找右树的最左节点；如果为空，就说明这个节点走完了，回去看父亲，如果父亲的左指向他，那么父亲这个节点还没走，如果父亲的右指向他，说明父亲节点走完，要向上找，知道找到一个节点，使得parent的left等于cur
  • 注意 对指针的解引用之前，最好提前判空

迭代器成员函数

public:Iterator Begin(){node* minleft = _root;while (minleft && minleft->_left){minleft = minleft->_left;}return Iterator(minleft);}Iterator End(){return Iterator(nullptr); //要有构造}ConstIterator Begin() const{node* minleft = _root;while (minleft && minleft->_left){minleft = minleft->_left;}return ConstIterator(minleft);}ConstIterator End() const{return ConstIterator(nullptr); //要有构造}

默认成员函数 

public:RBTree() = default;RBTree(const RBTree<K, T, KeyOfType>& copy){_root = Copy(copy._root);}RBTree& operator=(RBTree<K, T, KeyOfType> rbt){swap(_root, rbt._root);return *this;}~RBTree(){Destory(_root);_root = nullptr;}
private:void Destory(node* root){if (root == nullptr)return;Destory(root->_left);Destory(root->_right);delete root;}	node* Copy(node* root){if (root == nullptr){return nullptr;}node* newnode = new node(root->_data);newnode->_col = root->_col;newnode->_left = Copy(root->_left);if (newnode->_left)newnode->_left->_parent = newnode;newnode->_right = Copy(root->_right);if (newnode->_right)newnode->_right->_parent = newnode;return newnode;}

类和对象 

  • 这里必须要提供默认构造，因为成员变量声明的时候不能使用()来初始化；为了提供更清晰的内存管理和初始化顺序，成员变量的初始化必须在初始化列表或者构造函数体内，
  • 构造函数一定不能是const函数，因为他就是为了初始化用的
  • 赋值重载 这里一定要是swap(_root, rbt._root);不能是 _root = rbt._root；因为这个rbt是一个传值传参，出了这个函数就会被调析构；一定要传引用返回，不然又会调拷贝构造；一定要有返回值，目的是为了可以连续赋值

代码

  • 析构的时候用后序析构
  • 拷贝的时候，不要忘记子连接回父

Insert

pair<Iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new node(data);_root->_col = BLACK;return make_pair(Iterator(_root), true);}KeyOfType keyoftype;node* cur = _root;node* parent = cur;while (cur){if (keyoftype(cur->_data) < keyoftype(data)){parent = cur;cur = cur->_right;}else if (keyoftype(cur->_data) > keyoftype(data)){parent = cur;cur = cur->_left;}else{return make_pair(Iterator(cur), false);}}cur = new node(data);node* newnode = cur;if (keyoftype(parent->_data) < keyoftype(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){node* pparent = parent->_parent;if (pparent->_left == parent){node* uncle = pparent->_right;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;pparent->_col = RED;cur = pparent;parent = pparent->_parent;}else{if (parent->_left == cur){rotateR(pparent);//cur->_col = RED;parent->_col = BLACK;pparent->_col = RED; //这个之前一定是黑}else{rotateL(parent);rotateR(pparent);cur->_col = BLACK;//这竟然写错了pparent->_col = RED;}break;}}else{node* uncle = pparent->_left;if (uncle && uncle->_col == RED){uncle->_col = BLACK;parent->_col = BLACK;pparent->_col = RED;}else{if (parent->_right == cur){rotateL(pparent);parent->_col = BLACK;pparent->_col = RED;}else{rotateR(parent);rotateL(pparent);cur->_col = BLACK;pparent->_col = RED;}break;}}_root->_col = BLACK;}return { Iterator(newnode), true };}
  • 返回值的变化，和取值的变化
  • 取值可以用  KeyOfType  的匿名对象来取

代码

  • return 也可以：pair<Iterator, bool>(newnode, true);  or  make_pair(Iterator(newnode), true)  or make_pair(newnode, true)，不建议最后一种写法；effectiv C++建议：应该尽量避免隐式类型转换，以防止潜在的错误和难以维护的代码；回过来看，第三种因为 iterator是一个node*的封装，而不是node* 
  • 列表初始化：一个重要特性是防止窄化转换，比如 防止double 变成 int ；防止隐式类型转换还是要使用explicit
  • explicit只能用于修饰构造函数或转换运算符；explicit operator int() const{}这是转换运算符（隐式转换运算符）
  • 不能传引用返回，因为return的是一个临时对象，出作用域会被销毁，导致悬空引用；make_pair也是传值返回，因为他是返回的是pair的匿名对象

set

namespace nineone
{template<class K>class set{struct keyofset{const K& operator()(const K& lhs)  const{return lhs;}};public:typedef typename RBTree<K, const K, keyofset>::Iterator iterator;typedef typename RBTree<K, const K, keyofset>::ConstIterator const_iterator;iterator begin(){return rbt.Begin();}iterator end(){return rbt.End();}const_iterator begin() const{return rbt.Begin();}const_iterator end() const{return rbt.End();}pair<iterator, bool> insert(const K& k){return rbt.Insert(k);}iterator find(const K& key){return rbt.Find(key);}private:RBTree<K, const K, keyofset> rbt;};
}

 解释

  • 通过组合的方式，用RBTree来封装set，隐藏RBTree类实现细节，提供用户简洁的接口
  • typedef前面一定要加 typename；没有实例化的类模板去取内嵌类型，是有异议的，编译器不知道这是成员函数名还是成员变量；iterator一定要是public，因为要在类外使用，对于RBTree里的别名同理

解释：两个别名和成员变量的第二个模板参数必须一样★

  • 前提要点，不同类型参数实例化的类模板被视为不同类型，所以不能直接转换（编译器不提供隐式类型转换）；
  • 这三个只要有一个不一样就会报类型无法转换的错误；报错的地方在insert或者find return的地方
  • 我写文章的时候再次调试，报错的地方是对的，在const_iterator end() const这里报错，就是这里，返回语句的地方；因为这个rbt对象构建的树节点的K，是const K类型；但是const_iterator的树节点类型是K，导致返回类型与返回语句的类型不一样，且类型不兼容★
  • 如果函数的返回类型与声明里的返回类型无法隐式类型转换（类型不兼容），编译器就会报错

解释：第二个模板参数

  • 这个模板参数作用到的是节点和迭代器
  • 但是在ConstIterator里后面两个模板参数不是有const了；编译器会自动去掉多余的const，但是你自己多加会编译报错
  • 第二个参数是const，那么迭代器里，_node的类型是RBTreeNode<const T>*，这是一个普通指针；于指针而言，可以指向不同的RBTreeNode<const T>对象；与对象而言，对象里有部分是可以改变的，只有_data是const；const RBTreeNode<const T>*这样才是一个常量指针
  • 所以_node不会因为T为const导致++不能使用

map

namespace nineone
{template<class K, class V>class map{struct keyofmap{const K& operator()(const pair<K, V>& kv) const{return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, V>::Iterator iterator;typedef typename RBTree<K, pair<const K, V>, V>::ConstIterator const_iterator;pair<iterator, bool> insert(const pair<K, V>& kv){return rbt.Insert(kv);}iterator find(const K& key){return rbt.Find(key);}V& operator[](const K& key){pair<iterator, bool> ret = rbt.Insert(make_pair(key, V()));return ret.first->second;}iterator begin(){return rbt.Begin();}iterator end(){return rbt.End();}const_iterator begin() const{return rbt.Begin();}const_iterator end() const{return rbt.End();}private:RBTree<K, pair<const K, V>, keyofmap> rbt;};
}

 解释insert

这篇关于C++ RBTree封装mapset的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

原文地址:
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.chinasem.cn/article/1003045。

相关文章

C++类和对象之初始化列表的使用方式

C++类和对象之初始化列表的使用方式

《C++类和对象之初始化列表的使用方式》：本文主要介绍C++类和对象之初始化列表的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C++初始化列表详解：性能优化与正确实践什么是初始化列表？初始化列表的三大核心作用1. 性能优化：避免不必要的赋值操作2. 强
阅读更多...
C++迭代器失效的避坑指南

C++迭代器失效的避坑指南

《C++迭代器失效的避坑指南》在C++中,迭代器（iterator）是一种类似指针的对象,用于遍历STL容器（如vector、list、map等）,迭代器失效是指在对容器进行某些操作后... 目录1. 什么是迭代器失效？2. 哪些操作会导致迭代器失效？2.1 vector 的插入操作（push_back,
阅读更多...
一文详解如何在Vue3中封装API请求

一文详解如何在Vue3中封装API请求

《一文详解如何在Vue3中封装API请求》在现代前端开发中,API请求是不可避免的一部分,尤其是与后端交互时,下面我们来看看如何在Vue3项目中封装API请求,让你在实现功能时更加高效吧... 目录为什么要封装API请求1. vue 3项目结构2. 安装axIOS3. 创建API封装模块4. 封装API请求
阅读更多...
C#如何调用C++库

C#如何调用C++库

《C#如何调用C++库》：本文主要介绍C#如何调用C++库方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录方法一：使用P/Invoke1. 导出C++函数2. 定义P/Invoke签名3. 调用C++函数方法二：使用C++/CLI作为桥接1. 创建C++/CL
阅读更多...
C++如何通过Qt反射机制实现数据类序列化

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类，并对数据类进行存储、打印、调试等操作。由于数据类
阅读更多...
Linux下如何使用C++获取硬件信息

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息：读取"/proc/cpuinfo"文件获取磁盘信息：读取"/proc/diskstats"文
阅读更多...
C++使用printf语句实现进制转换的示例代码

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符（formatspecifier）快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指
阅读更多...
C++中初始化二维数组的几种常见方法

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a
阅读更多...
C++ vector的常见用法超详细讲解

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》：本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve
阅读更多...
鸿蒙中Axios数据请求的封装和配置方法

鸿蒙中Axios数据请求的封装和配置方法

《鸿蒙中Axios数据请求的封装和配置方法》：本文主要介绍鸿蒙中Axios数据请求的封装和配置方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.配置权限 应用级权限和系统级权限2.配置网络请求的代码3.下载在Entry中 下载AxIOS4.封装Htt
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2