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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---