用同一个树的类模板封装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;