如果是it在15结点这个位置，往上走没有遇到符合祖先的位置，并且已经走到空了，那就代表已经结束了。
Self& operator++() { if (_node->_right)//右子树不为空 { Node* cur = _node->_right; while (cur->_left) { cur = cur->_left; } _node = cur; } else//左子树为空 { Node* parent = _node->_parent; Node* cur = _node; while (parent && parent->_left != cur) { cur = parent; parent = parent->_parent; } _node = parent; } return *this; }
然后来实现- -逻辑：
Self& operator--() { if (_node->_left)//左子树不为空 { Node* cur = _node->_left; while (cur && cur->_right) { cur = cur->_right; } _node = cur; } else { Node* cur = _node; Node* parent = cur->_parent; while (parent && cur != parent->_right) { cur = parent; parent = parent->_parent; } _node = parent; } return *this; }
补全set与map的实现
set当中的值是不允许被修改的。
这里我们就要实现const版本的迭代器：
template<class T,class Ref, class Ptr> struct RBTreeIterator//红黑树的迭代器 { typedef RBTreeNode<T> Node; typedef RBTreeIterator<T, Ref, Ptr> Self; Node* _node; RBTreeIterator(Node* node) :_node(node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; }
先将这两个函数变成能兼容const和非const版本。
看一下set源码是怎么定义迭代器的：
那么set当中就算是非const版本的迭代器也不能修改值：
template<class K> class set { struct setKeyOFV { const K& operator()(const K& key) { return key; } }; public: typedef typename RBTree<K, K, setKeyOFV>::const_iterator iterator;//这里无论是非const迭代器也不能修改set的值，所以要变成const版本 typedef typename RBTree<K, K, setKeyOFV>::const_iterator const_iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } bool insert(const K& key) { return _t.Insert(key); } private: RBTree<K, K, setKeyOFV> _t; };
但是我们的begin函数和end函数的返回值和重命名的迭代器类型已经不相同了。
所以看看set源码是如何做到的：
后面加了一个const就解决了问题，因为权限可以缩小，传入的就算是非const版本也可以。
在set的begin与end中加了个const就说明要去调用const版本的begin与end，所以在树那里也要实现const版本的begin与end。
template<class K, class T, class KeyOFV> 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* cur = _root; while (cur && cur->_left) { cur = cur->_left; } return iterator(cur); } iterator end() { return iterator(nullptr); } const_iterator begin()const { Node* cur = _root; while (cur && cur->_left) { cur = cur->_left; } return const_iterator(cur); } const_iterator end()const { return const_iterator(nullptr); }
然后来实现map的const版本的迭代器：
先看看源码：
template<class K, class V> class map { struct mapKeyOFV { const K& operator()(const pair<const K, V>& kv) { return kv.first; } }; public: typedef typename RBTree<K, pair<const K, V>, mapKeyOFV>::iterator iterator; typedef typename RBTree<K, pair<const K, V>, mapKeyOFV>::const_iterator const_iterator; iterator begin() { return _p.begin(); } iterator end() { return _p.end(); } const_iterator begin()const { return _p.begin(); } const_iterator end()const { return _p.end(); } bool insert(const pair<const K, V>& kv) { return _p.Insert(kv); } private: RBTree<K, pair<const K, V>, mapKeyOFV> _p; };
然后就是[]重载了：
这里首先要改插入的返回值和返回类型。
pair<iterator, bool> Insert(const T& data) { if (_root == nullptr) { _root = new Node(data); _root->_color = BLACK; return make_pair(iterator(_root), true); } Node* cur = _root; Node* parent = nullptr; KeyOFV kot;//仿函数对象 while (cur) { if (kot(cur->_data) > kot(data)) { parent = cur; cur = cur->_left; } else if (kot(cur->_data) < kot(data)) { parent = cur; cur = cur->_right; } else { return make_pair(iterator(cur), false); } } cur = new Node(data);//这里默认是红色结点 Node* newnode = cur;//因为cur会变位置，所以储存一下新节点 if (kot(parent->_data) > kot(data)) { cur->_parent = parent; parent->_left = cur; } else if (kot(parent->_data) < kot(data)) { cur->_parent = parent; parent->_right = cur; } //如果父节点为空就代表cur是根节点，没必要调整了 //还要判断cur结点是否与父节点的颜色均为红色 while (parent && parent->_color == RED) { Node* grandfather = parent->_parent;//祖父结点 if (parent == grandfather->_left)//新增结点在祖父左 { Node* uncle = grandfather->_right; //情况一 if (uncle && uncle->_color == RED)//这里不要忘记验证uncle的存在 { parent->_color = BLACK; uncle->_color = BLACK; grandfather->_color = RED; cur = grandfather;//最后让cur等于祖父结点的位置 parent = cur->_parent; } else { if (parent->_left == cur)//情况二 { RotateR(grandfather);//右单旋 grandfather->_color = RED; parent->_color = BLACK; } else if (parent->_right == cur)//情况三 { RotateL(parent);//左单旋 RotateR(grandfather);//右单旋 cur->_color = BLACK; grandfather->_color = RED; } break;//第二种和第三种情况变完之后因为最上面的组节点变为黑，所以这里跳出循环 } } else//新增结点在祖父右 { Node* uncle = grandfather->_left; if (uncle && uncle->_color == RED)//情况一 { uncle->_color = BLACK; parent->_color = BLACK; grandfather->_color = RED; cur = grandfather; parent = cur->_parent; } else { if (cur == parent->_right)//情况二 { RotateL(grandfather); grandfather->_color = RED; parent->_color = BLACK; } else if (cur == parent->_left)//情况三 { RotateR(parent); RotateL(grandfather); cur->_color = BLACK; grandfather->_color = RED; } break; } } } _root->_color = BLACK; return make_pair(iterator(newnode), true); }
[]在map中重载即可：
V& operator[](const K& key) { pair<iterator, bool> it = insert(make_pair(key, V())); return it.first->second; }
因为树种插入的函数改变了返回值，所以set与map的插入调用函数也要改变返回值，但是set当中插入的返回值是非const类型：
这里看看源码是如何解决的：
这里使用了rep_type类型去接收，然后再用p去重新构造一个pair<iterator, bool>类型。
这是构造，为了解决非const的迭代器不能拷贝给const迭代器的问题。
