11

我想在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 ();

但是我找不到这个函数的定义。任何人都可以帮忙吗？

非常感谢。

4

3 回答 3

15

就像@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));
  }
于 2013-06-17T15:15:22.647 回答
3

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

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

于 2013-06-17T15:10:38.077 回答
2

它将在库的源代码中，您可能没有。

看起来您正在查看 GNU 库的标头，因此这里是开始寻找源代码的好地方。

于 2013-06-17T15:12:18.523 回答