波奇学C++：用红黑树模拟实现map和set

本文主要是介绍波奇学C++：用红黑树模拟实现map和set，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

用同一个树的类模板封装map(key/value)和set(key)

红黑树的Node

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(BLACK){}
};

用只有一个data变量来代替map的pair<key,value> 和set的key

template<class key,class T,class KeyOfT>
struct RBTree

看红黑树的模板的我们依然保留key模板，对于Set来说key和T都是value的，对于map来说key 是 key,T是pair<key,value>。

RBTree<K, pair<K, V>,MapKeyOfT> _t;
RBTree<K, K,SetKeyOfT> _t;

由此相当于适配器模式，对于set来说第二个模板参数不是必要的。

由此我们可以思考，我们对两个对象的封装可以先统一起来某种形式，比如都提供两个模板参数。

红黑树的insert返回值由原来的bool变成了pair<iterator,bool>

pair<iterator,bool> Insert(const T& data)
//......
return make_pair(iterator(newnode), true);
//

注意实际上map和set的迭代器属性不一样，但我们返回权限大的普通迭代器，后面再分别进行const限制来适配

typedef __TreeIterator<T,T*,T&> iterator;

写红黑树的迭代器

template<class T, class Ptr, class Ref>
struct __TreeIterator
{typedef RBTreeNode Node;typedef __TreeIterator< T, Ptr, Ref> Self;// Iterator只可能是普通迭代器typedef __TreeIterator< T, T*, T&> Iterator;Node* _node;__TreeIterator(const Iterator& It):_node(It._node){}__TreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){//右边不为空if (_node->right){Node* leftmin = _node->_right;while (leftmin->_left){leftmin = leftmin->_left;}_node = leftmin;return *this;}else{// 右树为空Node* parent = _node->_parent;while (parent&&_node == parent->right){_node = parent;parent = _node->_parent;}_node = parent;return *this;}}bool operator!=(const Iterator it)const{return _node != it._node;}bool operator==(const Iterator)const{return _node == it._node;}Self& operator--(){//左不为空if (_node->_left){Node* rightmax = _node->_left;while (rightmax->_right){rightmax = rightmax->_right;}_node = rightmax;return *this;}else{Node* parent = _node->_parent;while (parent && parent->_right == _node){_node = parent;parent = _node->_parent;}_node = parent;return *this;}}};

比较重要的点是拷贝构造函数

__TreeIterator(const Iterator& It):_node(It._node){}

对于普通迭代器，是拷贝构造，同时它也可以接收普通迭代器来构造const 修饰的迭代器。

operate()++的分析

当右树存在时，再右子树的最大值，当右树不存在，找到parent节点向上处理，当cur是parentd1左节点时，parent就是下一个节点。

红黑树的begin()，end()方法 

typedef __TreeIterator<T,T*,T&> iterator;typedef __TreeIterator<T, const T*, const T&> const_iterator;iterator begin(){Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin=leftMin->_left;}return iterator(leftMin);}iterator end(){return iterator(nullptr);}const_iterator begin()const{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return const_iterator(leftMin);}const_iterator end()const{return const_iterator(nullptr);}

这里用了没有直接返回Node*指针而是返回迭代器对象，调用拷贝构造函数。

map和set的迭代器有不同的需求，对于set而言，iterator就是const_iterator。

typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

set的begin() 

iterator begin()
{return _t.begin();
}

当begin()调用时 _t.begin()返回的是iterator这是就是可以通过__TreeIterator的拷贝构造实现转换成Iterator，（其实可以直接调用const的begin()修饰的函数）

insert封装

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);}

注意此时的问题，insert规定返回值必须是pair<iterator, bool>，RBTree返回的值实际是iterator,myset返回的iterator实际是const_iterator。不能直接返回会导致权限的缩小，所以要再构造。

而map的迭代器要确保pair<key,value>的key不会改变。方法是给模板参数上const

typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;

这篇关于波奇学C++：用红黑树模拟实现map和set的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---