CONTENTS
备注:
本读书笔记基于侯捷先生的《STL源码剖析》,截图和注释版权均属于原作者所有。
本读书笔记中的源码部分直接拷贝自SGI-STL,部分代码删除了头部的版权注释,但代码版权属于原作者。
小弟初看stl,很多代码都不是太懂,注释可能有很多错误,还请路过的各位大牛多多给予指导。
为了降低学习难度,作者这里换到了SGI-STL-2.91.57的源码来学习,代码下载地址为【 http://jjhou.boolan.com/jjwbooks-tass.htm 】
之前笔记了下【 维基百科中关于红黑树的介绍 】,这里笔记下STL中的代码实现,部分代码为了便于理解,使用了前面的图。
stl_tree.h:
//先定义了红黑树中颜色的类型和【红】【黑】的值,便于后面进行判断。 typedef bool __rb_tree_color_type; const __rb_tree_color_type __rb_tree_red = false; const __rb_tree_color_type __rb_tree_black = true; //红黑树的节点类基类 struct __rb_tree_node_base { typedef __rb_tree_color_type color_type; typedef __rb_tree_node_base* base_ptr; color_type color; //该节点的颜色 base_ptr parent;//指向父节点的指针 base_ptr left;//指向左子结点的指针 base_ptr right;//指向右子节点的指针 //获取当前红黑树的最小值,注意该函数为静态函数,需要入参。 //二叉搜索树的最小值很好找,最左边的节点为最小值。 static base_ptr minimum(base_ptr x) { while (x->left != 0) x = x->left; return x; } //获取当前红黑树的最大值,注意该函数为静态函数,需要入参。 //二叉搜索树的最大值很好找,最右边的节点为最大值。 static base_ptr maximum(base_ptr x) { while (x->right != 0) x = x->right; return x; } }; //红黑树的节点类 template <class Value> struct __rb_tree_node : public __rb_tree_node_base { typedef __rb_tree_node<Value>* link_type; Value value_field;//节点储存的值 }; //红黑树iterator基类 struct __rb_tree_base_iterator { typedef __rb_tree_node_base::base_ptr base_ptr; typedef bidirectional_iterator_tag iterator_category; typedef ptrdiff_t difference_type; base_ptr node;//iterator指向的节点 void increment()//iterator递增函数,找到大于它的下一个节点。 { if (node->right != 0) {//有右子树,那么就是右子树的最小值,即右子树的最左边的值 node = node->right; while (node->left != 0) node = node->left; } else {//没有右子树,就一直上溯,找到该节点所属的【整棵左子树】的父节点。 base_ptr y = node->parent; while (node == y->right) { node = y; y = y->parent; } if (node->right != y) //循环退出之后,如果是因为找到了父子树的话,就把iterator指向的node指向该父子树。 node = y; } } void decrement()//iterator递减函数,找到小于它的下一个节点。 { if (node->color == __rb_tree_red && node->parent->parent == node) node = node->right; else if (node->left != 0) {//有左子树,那么就是左子树的最大值,即左子树的最右边的值 base_ptr y = node->left; while (y->right != 0) y = y->right; node = y; } else {//没有左子树,就一直上溯,找到该节点所属的【整棵右子树】的父节点。 base_ptr y = node->parent; while (node == y->left) { node = y; y = y->parent; } node = y; } } };
increment和decrement的一些操作比较复杂,这里先画张图,将STL中的节点的关系标下,如下图:
//红黑树iterator类 template <class Value, class Ref, class Ptr> struct __rb_tree_iterator : public __rb_tree_base_iterator { typedef Value value_type; typedef Ref reference; typedef Ptr pointer; typedef __rb_tree_iterator<Value, Value&, Value*> iterator; typedef __rb_tree_iterator<Value, const Value&, const Value*> const_iterator; typedef __rb_tree_iterator<Value, Ref, Ptr> self; typedef __rb_tree_node<Value>* link_type; //各种构造函数。 __rb_tree_iterator() {} __rb_tree_iterator(link_type x) { node = x; } __rb_tree_iterator(const iterator& it) { node = it.node; } //对iterator进行解引用,返回的是iterator指向的节点的存储的值。 reference operator*() const { return link_type(node)->value_field; } #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator->() const { return &(operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ //递增运算符,实际上调用的是iterator的increment方法。 self& operator++() { increment(); return *this; } self operator++(int) { self tmp = *this; increment(); return tmp; } //递减运算符,实际上调用的是iterator的decrement方法。 self& operator--() { decrement(); return *this; } self operator--(int) { self tmp = *this; decrement(); return tmp; } }; //判断两个iterator是否相等 inline bool operator==(const __rb_tree_base_iterator& x, const __rb_tree_base_iterator& y) { return x.node == y.node; } //判断两个iterator是否不等 inline bool operator!=(const __rb_tree_base_iterator& x, const __rb_tree_base_iterator& y) { return x.node != y.node; } #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION //返回iterator的类型 inline bidirectional_iterator_tag iterator_category(const __rb_tree_base_iterator&) { return bidirectional_iterator_tag(); } inline __rb_tree_base_iterator::difference_type* distance_type(const __rb_tree_base_iterator&) { return (__rb_tree_base_iterator::difference_type*) 0; } template <class Value, class Ref, class Ptr> inline Value* value_type(const __rb_tree_iterator<Value, Ref, Ptr>&) { return (Value*) 0; } #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
左旋:
inline void __rb_tree_rotate_left(__rb_tree_node_base* x, __rb_tree_node_base*& root) { __rb_tree_node_base* y = x->right; x->right = y->left; if (y->left !=0) y->left->parent = x; y->parent = x->parent; if (x == root) root = y; else if (x == x->parent->left) x->parent->left = y; else x->parent->right = y; y->left = x; x->parent = y; }
如下图:
右旋:
inline void __rb_tree_rotate_right(__rb_tree_node_base* x, __rb_tree_node_base*& root) { __rb_tree_node_base* y = x->left; x->left = y->right; if (y->right != 0) y->right->parent = x; y->parent = x->parent; if (x == root) root = y; else if (x == x->parent->right) x->parent->right = y; else x->parent->left = y; y->right = x; x->parent = y; }
如下图:
//节点X插入树中之后,红黑树自平衡一次,参考插入操作部分笔记。 inline void __rb_tree_rebalance(__rb_tree_node_base* x, __rb_tree_node_base*& root) { //首先默认令插入的节点的颜色为红色 x->color = __rb_tree_red; //如果父节点为红色,参考情形3及之后情形 while (x != root && x->parent->color == __rb_tree_red) { //X的父节点P为G节点的左子结点。 if (x->parent == x->parent->parent->left) { //y为G节点的右子节点,即P的兄弟节点,X的叔父节点。 __rb_tree_node_base* y = x->parent->parent->right; if (y && y->color == __rb_tree_red) { //情形3: 父节点P和叔父节点U二者都是红色 x->parent->color = __rb_tree_black;//那么P,U均改为黑色 y->color = __rb_tree_black; x->parent->parent->color = __rb_tree_red;//G改为红色。 //将G认为是新加入的节点,重复判断。 x = x->parent->parent; } else { //情形4: 父节点P是红色而叔父节点U是黑色。 if (x == x->parent->right) { //新节点N是其父节点P的右子节点(右左情况),先左旋至左左情况。 x = x->parent; __rb_tree_rotate_left(x, root);//左旋 } //到了这里情况为:情形5: 父节点P是红色而叔父节点U是黑色,新节点N是其父节点的左子节点,而父节点P又是其父节点G的左子节点(左左情况)。 //直接使用情形5右旋一下即可。 x->parent->color = __rb_tree_black;//G节点变为黑色 x->parent->parent->color = __rb_tree_red;//A节点变为红色 __rb_tree_rotate_right(x->parent->parent, root);//右旋,注意这里的代码是先调整G,A节点颜色再右旋,作者自己画的图是先右旋在变颜色,实际效果是一样的。 } } else {//X的父节点P为G节点的右子结点。 //y为G节点的右子节点,即P的兄弟节点,X的叔父节点。 __rb_tree_node_base* y = x->parent->parent->left; if (y && y->color == __rb_tree_red) { //情形3: 父节点P和叔父节点U二者都是红色 x->parent->color = __rb_tree_black; y->color = __rb_tree_black; x->parent->parent->color = __rb_tree_red; x = x->parent->parent; } else { //情形4: 父节点P是红色而叔父节点U是黑色。 if (x == x->parent->left) { //新节点N是其父节点P的左子节点(左右情况),先右旋至右右情况。 x = x->parent; __rb_tree_rotate_right(x, root); } //到了这里情况为:情形5: 右右情况,直接使用情形5右旋一下即可。 x->parent->color = __rb_tree_black; x->parent->parent->color = __rb_tree_red; __rb_tree_rotate_left(x->parent->parent, root); } } } //while循环结束之后,只有两种情况:情形1(x == root)或者情形2(x->parent->color == __rb_tree_black),这里直接把root节点赋黑色即可。 root->color = __rb_tree_black; } //节点Z从树中删除之后,红黑树自平衡一次,参考删除操作部分笔记。 inline __rb_tree_node_base* __rb_tree_rebalance_for_erase(__rb_tree_node_base* z, __rb_tree_node_base*& root, __rb_tree_node_base*& leftmost, __rb_tree_node_base*& rightmost) { //如果要删除的节点Z没有子节点就把它删掉了,如果它有子节点,那么根据二叉树的规则,被删除的节点会被它的左子树中的最大元素【B】、或者在它的右子树中的最小元素【C】所替换。因此实际上删除的节点是它的左子树中的最大元素【B】、或者在它的右子树中的最小元素【C】。在本函数实现中,这里用的是右子树中的最小元素【C】所替换。 __rb_tree_node_base* y = z;//Y指向的是删除Z时实际要替换上去的节点。 __rb_tree_node_base* x = 0;//x指向的是删除Z时实际要替换上去的节点Y的子节点。 __rb_tree_node_base* x_parent = 0; if (y->left == 0) // z has at most one non-null child. y == z. x = y->right; // x might be null. else if (y->right == 0) // z has exactly one non-null child. y == z. x = y->left; // x is not null. else { // z has two non-null children. Set y to y = y->right; // z's successor. x might be null. while (y->left != 0) y = y->left; x = y->right; //Y是Z的右子树的最小值,经过循环之后,Y没有左子结点了,X是Y的子节点。 } // Y和Z不是同一个节点,那么二叉树删除的逻辑是用Y代替Z,用X代替Y,实际上删除的节点位置为Y位置而不是Z位置。 if (y != z) { // relink y in place of z. y is z's successor z->left->parent = y; y->left = z->left; if (y != z->right) { x_parent = y->parent; if (x) x->parent = y->parent; y->parent->left = x; // y must be a left child y->right = z->right; z->right->parent = y; } else x_parent = y; if (root == z) root = y; else if (z->parent->left == z) z->parent->left = y; else z->parent->right = y; y->parent = z->parent; __STD::swap(y->color, z->color); y = z; // y now points to node to be actually deleted } else { // y == z //Y和Z是同一个节点,说明Z只有一个子树X。直接用X替换掉Z即可,这里删除的位置是Z(Y)位置。 x_parent = y->parent; if (x) x->parent = y->parent; if (root == z) root = x; else if (z->parent->left == z) z->parent->left = x; else z->parent->right = x; if (leftmost == z) if (z->right == 0) // z->left must be null also leftmost = z->parent; // makes leftmost == header if z == root else leftmost = __rb_tree_node_base::minimum(x); if (rightmost == z) if (z->left == 0) // z->right must be null also rightmost = z->parent; // makes rightmost == header if z == root else // x == z->left rightmost = __rb_tree_node_base::maximum(x); } //由于删除的位置是Y位置,因此这里就要判断Y位置的颜色。 //注意这里的代码实现和维基百科的有些出入。 if (y->color != __rb_tree_red) { //Y:要删除的节点为黑色时,X:Y的子节点。x_parent:X的父节点。 while (x != root && (x == 0 || x->color == __rb_tree_black)) //x是左子结点 if (x == x_parent->left) { //w:Y的兄弟节点,x的叔父节点。 __rb_tree_node_base* w = x_parent->right; if (w->color == __rb_tree_red) { //情形2: S是红色,处理时包含了情形4。 w->color = __rb_tree_black;//S变为黑色 x_parent->color = __rb_tree_red;//P变为红色 __rb_tree_rotate_left(x_parent, root);//左旋,作者自己画的图是先左旋在变颜色,实际效果是一样的。 w = x_parent->right; } //情形3: P、S、SL、SR都是黑色的。 if ((w->left == 0 || w->left->color == __rb_tree_black) && (w->right == 0 || w->right->color == __rb_tree_black)) { w->color = __rb_tree_red; x = x_parent; x_parent = x_parent->parent; } else { //W的左子结点为红色,右子节点为黑色, //情形5: S是黑色,SL是红色,SR是黑色,P颜色无所谓,而N是P的左子节点。 if (w->right == 0 || w->right->color == __rb_tree_black) { if (w->left) w->left->color = __rb_tree_black; w->color = __rb_tree_red; __rb_tree_rotate_right(w, root);//右旋 w = x_parent->right; } //情形6: S是黑色,SR是红色,而N是P的左子节点,P颜色无所谓。 w->color = x_parent->color;//S和P颜色互换 x_parent->color = __rb_tree_black; if (w->right) w->right->color = __rb_tree_black;//SR变黑色 __rb_tree_rotate_left(x_parent, root);//左旋 break; } } else { // same as above, with right <-> left. __rb_tree_node_base* w = x_parent->left; if (w->color == __rb_tree_red) { w->color = __rb_tree_black; x_parent->color = __rb_tree_red; __rb_tree_rotate_right(x_parent, root); w = x_parent->left; } if ((w->right == 0 || w->right->color == __rb_tree_black) && (w->left == 0 || w->left->color == __rb_tree_black)) { w->color = __rb_tree_red; x = x_parent; x_parent = x_parent->parent; } else { if (w->left == 0 || w->left->color == __rb_tree_black) { if (w->right) w->right->color = __rb_tree_black; w->color = __rb_tree_red; __rb_tree_rotate_left(w, root); w = x_parent->left; } w->color = x_parent->color; x_parent->color = __rb_tree_black; if (w->left) w->left->color = __rb_tree_black; __rb_tree_rotate_right(x_parent, root); break; } } //情形B:如果删除一个黑色节点,且它的子节点是红色。 //此时直接删掉该节点,让其子节点X顶替自己,颜色变黑色即可。 if (x) x->color = __rb_tree_black; } //情形A:如果删除一个红色节点。直接返回,什么都不做。 return y; }
备注:以下代码只做了部分笔记,后续补全吧。
//红黑树的实现类 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc> class rb_tree { protected: typedef void* void_pointer; typedef __rb_tree_node_base* base_ptr; typedef __rb_tree_node<Value> rb_tree_node; typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator; typedef __rb_tree_color_type color_type; public: typedef Key key_type; typedef Value value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; typedef rb_tree_node* link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; protected: //申请一个新的节点 link_type get_node() { return rb_tree_node_allocator::allocate(); } //释放一个新的节点 void put_node(link_type p) { rb_tree_node_allocator::deallocate(p); } //创建一个新的节点,节点值为X link_type create_node(const value_type& x) { link_type tmp = get_node();//首先申请内存 __STL_TRY { construct(&tmp->value_field, x);//调用构造函数 } __STL_UNWIND(put_node(tmp)); return tmp; } //克隆一个节点。 link_type clone_node(link_type x) { link_type tmp = create_node(x->value_field);//先构造一个节点 tmp->color = x->color;//把颜色复制过来 tmp->left = 0;//左右子节点都为0 tmp->right = 0; return tmp; } //删除一个节点。 void destroy_node(link_type p) { destroy(&p->value_field);//先调用析构函数 put_node(p);//然后释放内存 } protected: size_type node_count; // keeps track of size of tree //树中节点的数量 link_type header; //特殊节点,指向树的最大,最小值,以及根节点。 Compare key_compare;//节点大小的比较方式 //返回树的根节点 link_type& root() const { return (link_type&) header->parent; } //返回树的最左节点 link_type& leftmost() const { return (link_type&) header->left; } //返回树的最右节点 link_type& rightmost() const { return (link_type&) header->right; } //返回某个节点的左子结点 static link_type& left(link_type x) { return (link_type&)(x->left); } //返回某个节点的右子结点 static link_type& right(link_type x) { return (link_type&)(x->right); } //返回某个节点的父节点 static link_type& parent(link_type x) { return (link_type&)(x->parent); } //返回某个节点的节点值的引用 static reference value(link_type x) { return x->value_field; } static const Key& key(link_type x) { return KeyOfValue()(value(x)); } //返回颜色的类型 static color_type& color(link_type x) { return (color_type&)(x->color); } //返回各种引用 static link_type& left(base_ptr x) { return (link_type&)(x->left); } static link_type& right(base_ptr x) { return (link_type&)(x->right); } static link_type& parent(base_ptr x) { return (link_type&)(x->parent); } static reference value(base_ptr x) { return ((link_type)x)->value_field; } static const Key& key(base_ptr x) { return KeyOfValue()(value(link_type(x)));} static color_type& color(base_ptr x) { return (color_type&)(link_type(x)->color); } //获取当前红黑树的最小值,注意该函数为静态函数,需要入参。 static link_type minimum(link_type x) { return (link_type) __rb_tree_node_base::minimum(x); } //获取当前红黑树的最大值,注意该函数为静态函数,需要入参。 static link_type maximum(link_type x) { return (link_type) __rb_tree_node_base::maximum(x); } public: //iterator的定义 typedef __rb_tree_iterator<value_type, reference, pointer> iterator; typedef __rb_tree_iterator<value_type, const_reference, const_pointer> const_iterator; #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION typedef reverse_iterator<const_iterator> const_reverse_iterator; typedef reverse_iterator<iterator> reverse_iterator; #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ typedef reverse_bidirectional_iterator<iterator, value_type, reference, difference_type> reverse_iterator; typedef reverse_bidirectional_iterator<const_iterator, value_type, const_reference, difference_type> const_reverse_iterator; #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ private: iterator __insert(base_ptr x, base_ptr y, const value_type& v); link_type __copy(link_type x, link_type p); void __erase(link_type x); //红黑树的初始化 void init() { //申请header的内存 header = get_node(); color(header) = __rb_tree_red; // used to distinguish header from // root, in iterator.operator++ root() = 0; leftmost() = header;//初始化时最左最右指向均为header rightmost() = header; } public: //构造函数 // allocation/deallocation rb_tree(const Compare& comp = Compare()) : node_count(0), key_compare(comp) { init(); } //拷贝构造函数 rb_tree(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x) : node_count(0), key_compare(x.key_compare) { header = get_node(); color(header) = __rb_tree_red; if (x.root() == 0) { root() = 0; leftmost() = header; rightmost() = header; } else { __STL_TRY { root() = __copy(x.root(), header); } __STL_UNWIND(put_node(header)); leftmost() = minimum(root()); rightmost() = maximum(root()); } node_count = x.node_count; } //析构函数 ~rb_tree() { clear();//释放树中所有节点 put_node(header);//释放header节点 } rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& operator=(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x); public: // accessors: Compare key_comp() const { return key_compare; } //返回起始节点。 iterator begin() { return leftmost(); } const_iterator begin() const { return leftmost(); } //返回最终节点,这里直接返回的header iterator end() { return header; } const_iterator end() const { return header; } reverse_iterator rbegin() { return reverse_iterator(end()); } const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } //判断树是否为空 bool empty() const { return node_count == 0; } //返回树的节点的数目 size_type size() const { return node_count; } //返回最大节点数目,由于树的节点时动态申请的,因此最大数量和内存有关。 size_type max_size() const { return size_type(-1); } void swap(rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& t) { __STD::swap(header, t.header); __STD::swap(node_count, t.node_count); __STD::swap(key_compare, t.key_compare); } public: // insert/erase pair<iterator,bool> insert_unique(const value_type& x); iterator insert_equal(const value_type& x); iterator insert_unique(iterator position, const value_type& x); iterator insert_equal(iterator position, const value_type& x); #ifdef __STL_MEMBER_TEMPLATES template <class InputIterator> void insert_unique(InputIterator first, InputIterator last); template <class InputIterator> void insert_equal(InputIterator first, InputIterator last); #else /* __STL_MEMBER_TEMPLATES */ void insert_unique(const_iterator first, const_iterator last); void insert_unique(const value_type* first, const value_type* last); void insert_equal(const_iterator first, const_iterator last); void insert_equal(const value_type* first, const value_type* last); #endif /* __STL_MEMBER_TEMPLATES */ void erase(iterator position); size_type erase(const key_type& x); void erase(iterator first, iterator last); void erase(const key_type* first, const key_type* last); //清除树中的所有数据。将Header的指向重置为初始状态。 void clear() { if (node_count != 0) { __erase(root()); leftmost() = header; root() = 0; rightmost() = header; node_count = 0; } } public: // set operations: iterator find(const key_type& x); const_iterator find(const key_type& x) const; size_type count(const key_type& x) const; iterator lower_bound(const key_type& x); const_iterator lower_bound(const key_type& x) const; iterator upper_bound(const key_type& x); const_iterator upper_bound(const key_type& x) const; pair<iterator,iterator> equal_range(const key_type& x); pair<const_iterator, const_iterator> equal_range(const key_type& x) const; public: // Debugging. bool __rb_verify() const; }; //判断两个树是否相等。通过判断其中的节点是否相等来判断 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> inline bool operator==(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x, const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& y) { return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); } template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> inline bool operator<(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x, const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& y) { return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> inline void swap(rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x, rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& y) { x.swap(y); } #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ //赋值构造函数,先将本地的节点清除掉,然后将传入的树复制一份,保存下来。 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& rb_tree<Key, Value, KeyOfValue, Compare, Alloc>:: operator=(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x) { if (this != &x) { // Note that Key may be a constant type. clear(); node_count = 0; key_compare = x.key_compare; if (x.root() == 0) { root() = 0; leftmost() = header; rightmost() = header; } else { root() = __copy(x.root(), header); leftmost() = minimum(root()); rightmost() = maximum(root()); node_count = x.node_count; } } return *this; } //插入一个节点 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator rb_tree<Key, Value, KeyOfValue, Compare, Alloc>:: __insert(base_ptr x_, base_ptr y_, const Value& v) { link_type x = (link_type) x_; link_type y = (link_type) y_; link_type z; if (y == header || x != 0 || key_compare(KeyOfValue()(v), key(y))) { z = create_node(v); left(y) = z; // also makes leftmost() = z when y == header if (y == header) { root() = z; rightmost() = z; } else if (y == leftmost()) leftmost() = z; // maintain leftmost() pointing to min node } else { z = create_node(v); right(y) = z; if (y == rightmost()) rightmost() = z; // maintain rightmost() pointing to max node } parent(z) = y; left(z) = 0; right(z) = 0; __rb_tree_rebalance(z, header->parent); ++node_count; return iterator(z); } //插入一个节点 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_equal(const Value& v) { link_type y = header; link_type x = root(); while (x != 0) { y = x; x = key_compare(KeyOfValue()(v), key(x)) ? left(x) : right(x); } return __insert(x, y, v); } //插入一个唯一的节点,如果之前已经插入过,就返回已经存在的节点(返回为pair,第二个参数表示是否是新申请的还是之前存在的) template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> pair<typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator, bool> rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(const Value& v) { link_type y = header; link_type x = root(); bool comp = true; //先在树中查找一下,看下之前有没有插入过。 while (x != 0) { y = x; comp = key_compare(KeyOfValue()(v), key(x)); x = comp ? left(x) : right(x); } iterator j = iterator(y); if (comp) if (j == begin()) return pair<iterator,bool>(__insert(x, y, v), true); else --j; if (key_compare(key(j.node), KeyOfValue()(v))) return pair<iterator,bool>(__insert(x, y, v), true); return pair<iterator,bool>(j, false); } template <class Key, class Val, class KeyOfValue, class Compare, class Alloc> typename rb_tree<Key, Val, KeyOfValue, Compare, Alloc>::iterator rb_tree<Key, Val, KeyOfValue, Compare, Alloc>::insert_unique(iterator position, const Val& v) { if (position.node == header->left) // begin() if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node))) return __insert(position.node, position.node, v); // first argument just needs to be non-null else return insert_unique(v).first; else if (position.node == header) // end() if (key_compare(key(rightmost()), KeyOfValue()(v))) return __insert(0, rightmost(), v); else return insert_unique(v).first; else { iterator before = position; --before; if (key_compare(key(before.node), KeyOfValue()(v)) && key_compare(KeyOfValue()(v), key(position.node))) if (right(before.node) == 0) return __insert(0, before.node, v); else return __insert(position.node, position.node, v); // first argument just needs to be non-null else return insert_unique(v).first; } } template <class Key, class Val, class KeyOfValue, class Compare, class Alloc> typename rb_tree<Key, Val, KeyOfValue, Compare, Alloc>::iterator rb_tree<Key, Val, KeyOfValue, Compare, Alloc>::insert_equal(iterator position, const Val& v) { if (position.node == header->left) // begin() if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node))) return __insert(position.node, position.node, v); // first argument just needs to be non-null else return insert_equal(v); else if (position.node == header) // end() if (!key_compare(KeyOfValue()(v), key(rightmost()))) return __insert(0, rightmost(), v); else return insert_equal(v); else { iterator before = position; --before; if (!key_compare(KeyOfValue()(v), key(before.node)) && !key_compare(key(position.node), KeyOfValue()(v))) if (right(before.node) == 0) return __insert(0, before.node, v); else return __insert(position.node, position.node, v); // first argument just needs to be non-null else return insert_equal(v); } } #ifdef __STL_MEMBER_TEMPLATES template <class K, class V, class KoV, class Cmp, class Al> template<class II> void rb_tree<K, V, KoV, Cmp, Al>::insert_equal(II first, II last) { for ( ; first != last; ++first) insert_equal(*first); } template <class K, class V, class KoV, class Cmp, class Al> template<class II> void rb_tree<K, V, KoV, Cmp, Al>::insert_unique(II first, II last) { for ( ; first != last; ++first) insert_unique(*first); } #else /* __STL_MEMBER_TEMPLATES */ template <class K, class V, class KoV, class Cmp, class Al> void rb_tree<K, V, KoV, Cmp, Al>::insert_equal(const V* first, const V* last) { for ( ; first != last; ++first) insert_equal(*first); } template <class K, class V, class KoV, class Cmp, class Al> void rb_tree<K, V, KoV, Cmp, Al>::insert_equal(const_iterator first, const_iterator last) { for ( ; first != last; ++first) insert_equal(*first); } template <class K, class V, class KoV, class Cmp, class A> void rb_tree<K, V, KoV, Cmp, A>::insert_unique(const V* first, const V* last) { for ( ; first != last; ++first) insert_unique(*first); } template <class K, class V, class KoV, class Cmp, class A> void rb_tree<K, V, KoV, Cmp, A>::insert_unique(const_iterator first, const_iterator last) { for ( ; first != last; ++first) insert_unique(*first); } #endif /* __STL_MEMBER_TEMPLATES */ template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> inline void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(iterator position) { link_type y = (link_type) __rb_tree_rebalance_for_erase(position.node, header->parent, header->left, header->right); destroy_node(y); --node_count; } template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::size_type rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(const Key& x) { pair<iterator,iterator> p = equal_range(x); size_type n = 0; distance(p.first, p.second, n); erase(p.first, p.second); return n; } template <class K, class V, class KeyOfValue, class Compare, class Alloc> typename rb_tree<K, V, KeyOfValue, Compare, Alloc>::link_type rb_tree<K, V, KeyOfValue, Compare, Alloc>::__copy(link_type x, link_type p) { // structural copy. x and p must be non-null. link_type top = clone_node(x); top->parent = p; __STL_TRY { if (x->right) top->right = __copy(right(x), top); p = top; x = left(x); while (x != 0) { link_type y = clone_node(x); p->left = y; y->parent = p; if (x->right) y->right = __copy(right(x), y); p = y; x = left(x); } } __STL_UNWIND(__erase(top)); return top; } //删除 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__erase(link_type x) { // erase without rebalancing while (x != 0) { __erase(right(x)); link_type y = left(x); destroy_node(x); x = y; } } //删除iterator指向从first到last间的节点。 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(iterator first, iterator last) { if (first == begin() && last == end()) clear(); else while (first != last) erase(first++); } //删除节点值在first到last间的节点 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(const Key* first, const Key* last) { while (first != last) erase(*first++); } //查找某个节点 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::find(const Key& k) { link_type y = header; // Last node which is not less than k. link_type x = root(); // Current node. while (x != 0) if (!key_compare(key(x), k)) y = x, x = left(x); else x = right(x); iterator j = iterator(y); return (j == end() || key_compare(k, key(j.node))) ? end() : j; } //查找某个节点 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::const_iterator rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::find(const Key& k) const { link_type y = header; /* Last node which is not less than k. */ link_type x = root(); /* Current node. */ while (x != 0) { if (!key_compare(key(x), k)) y = x, x = left(x); else x = right(x); } const_iterator j = const_iterator(y); return (j == end() || key_compare(k, key(j.node))) ? end() : j; } //返回返回小于K的最大节点和大于K的最小节点间的节点的数目 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::size_type rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::count(const Key& k) const { pair<const_iterator, const_iterator> p = equal_range(k); size_type n = 0; distance(p.first, p.second, n); return n; } //返回不大于K的最大的节点 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::lower_bound(const Key& k) { link_type y = header; /* Last node which is not less than k. */ link_type x = root(); /* Current node. */ while (x != 0) if (!key_compare(key(x), k)) y = x, x = left(x); else x = right(x); return iterator(y); } //返回不大于K的最大的节点 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::const_iterator rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::lower_bound(const Key& k) const { link_type y = header; /* Last node which is not less than k. */ link_type x = root(); /* Current node. */ while (x != 0) if (!key_compare(key(x), k)) y = x, x = left(x); else x = right(x); return const_iterator(y); } //返回大于K的最小的节点 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::upper_bound(const Key& k) { link_type y = header; /* Last node which is greater than k. */ link_type x = root(); /* Current node. */ while (x != 0) //一直找到树的最下面一层,才能找到大于K的【最小】的节点。 if (key_compare(k, key(x))) y = x, x = left(x);//如果K小于x,那么就调到左子树上找更小的x。 else x = right(x);//如果K大于x,那么转到右子树上继续找更大的x。 return iterator(y); } //返回大于K的最小的节点 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::const_iterator rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::upper_bound(const Key& k) const { link_type y = header; /* Last node which is greater than k. */ link_type x = root(); /* Current node. */ while (x != 0) if (key_compare(k, key(x))) y = x, x = left(x); else x = right(x); return const_iterator(y); } //返回小于K的最大节点对应的iterator和大于K的最小节点对应的iterator template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> inline pair<typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator, typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator> rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::equal_range(const Key& k) { return pair<iterator, iterator>(lower_bound(k), upper_bound(k)); } //返回小于K的最大节点对应的iterator和大于K的最小节点对应的iterator template <class Key, class Value, class KoV, class Compare, class Alloc> inline pair<typename rb_tree<Key, Value, KoV, Compare, Alloc>::const_iterator, typename rb_tree<Key, Value, KoV, Compare, Alloc>::const_iterator> rb_tree<Key, Value, KoV, Compare, Alloc>::equal_range(const Key& k) const { return pair<const_iterator,const_iterator>(lower_bound(k), upper_bound(k)); } //返回node到root间的黑色节点的数目 inline int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root) { if (node == 0) return 0; else { int bc = node->color == __rb_tree_black ? 1 : 0; if (node == root) return bc; else return bc + __black_count(node->parent, root); } } template <class Key, class Value, class KeyOfValue, class Compare, class Alloc> bool rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__rb_verify() const { if (node_count == 0 || begin() == end()) return node_count == 0 && begin() == end() && header->left == header && header->right == header; int len = __black_count(leftmost(), root()); for (const_iterator it = begin(); it != end(); ++it) { link_type x = (link_type) it.node; link_type L = left(x); link_type R = right(x); if (x->color == __rb_tree_red) if ((L && L->color == __rb_tree_red) || (R && R->color == __rb_tree_red)) return false; if (L && key_compare(key(x), key(L))) return false; if (R && key_compare(key(R), key(x))) return false; if (!L && !R && __black_count(x, root()) != len) return false; } if (leftmost() != __rb_tree_node_base::minimum(root())) return false; if (rightmost() != __rb_tree_node_base::maximum(root())) return false; return true; }
发表评论