c++ - bits/STL_tree.h中_Rb_tree_increment的定义是什么？

Question

想学习STL中红黑树的代码。并且在文件bits/STL_tree.h中找到了一个名为_Rb_tree_increment的函数

它写道:

 143   _GLIBCXX_PURE _Rb_tree_node_base*
 144   _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();

但是我找不到这个函数的定义。谁能帮忙？

非常感谢。

Answer 1

正如@Mike Seymour 所说，我在库的源路径中找到了定义，更准确地说是在 gcc-4.8.1/libstdc++-v3/src/c++98/tree.cc 中:

  static _Rb_tree_node_base*
  local_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
  {
    if (__x->_M_right != 0) 
      {
        __x = __x->_M_right;
        while (__x->_M_left != 0)
          __x = __x->_M_left;
      }
    else 
      {
        _Rb_tree_node_base* __y = __x->_M_parent;
        while (__x == __y->_M_right) 
          {
            __x = __y;
            __y = __y->_M_parent;
          }
        if (__x->_M_right != __y)
          __x = __y;
      }
    return __x;
  }

  _Rb_tree_node_base*
  _Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
  {
    return local_Rb_tree_increment(__x);
  }

  const _Rb_tree_node_base*
  _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ()
  {
    return local_Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x));
  }