在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));
  }

Answer 2

该定义取决于您拥有的标准库。不同的编译器供应商为其编译器提供了标准库的不同实现。看来您找到了一个非模板函数。它应该在某些 cpp 中定义，并且将在 lib 文件中随编译器一起提供，因此您无法直接访问代码，因为它不会随您的编译器一起提供 - 这根本没有必要。

如果您的编译器是专有编译器，例如来自 Microsoft 或 Borland 的编译器，那么您将得到的就是这些。然而，如果您有 gcc，那么您很幸运：gcc 是开源的，您可以在线找到标准库的 gcc 实现的源代码。