cstriker1407的笔记本

好记性不如铅笔头

C && C++, C++ STL, 编程

C++ STL读书笔记：stl_tree.h

已发表 通过 cstriker1407 在 2014年7月21日 0 评论

阅读下个 →

CONTENTS [hide]

备注：

本读书笔记基于侯捷先生的《STL源码剖析》，截图和注释版权均属于原作者所有。
本读书笔记中的源码部分直接拷贝自SGI-STL，部分代码删除了头部的版权注释，但代码版权属于原作者。
小弟初看stl，很多代码都不是太懂，注释可能有很多错误，还请路过的各位大牛多多给予指导。
为了降低学习难度，作者这里换到了SGI-STL-2.91.57的源码来学习，代码下载地址为【 http://jjhou.boolan.com/jjwbooks-tass.htm 】

之前笔记了下【 维基百科中关于红黑树的介绍 】，这里笔记下STL中的代码实现，部分代码为了便于理解，使用了前面的图。

stl_tree.h:

view source
//先定义了红黑树中颜色的类型和【红】【黑】的值，便于后面进行判断。
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中的节点的关系标下，如下图：

view source
//红黑树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 */

 左旋：

view source
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;
}

如下图：

右旋：

view source
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;
}

如下图：

view source
//节点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;
}

 备注：以下代码只做了部分笔记，后续补全吧。

view source
//红黑树的实现类
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;
}

 

cstriker1407

阅读下个 →

发表评论

19 + 19 =

此站点使用 Akismet 来减少垃圾评论。了解我们如何处理您的评论数据。

2025 年 3 月
一 二 三 四 五 六 日
 12
3456789
10111213141516
17181920212223
24252627282930
31  

Contents