c++ - 这个结构的数据在内存中的什么位置？

Question

我正在查看 STL_tree.h 中 std::set 的 GCC 源代码，其中有:

  enum _Rb_tree_color { _S_red = false, _S_black = true };

  struct _Rb_tree_node_base
  {
    typedef _Rb_tree_node_base* _Base_ptr;
    typedef const _Rb_tree_node_base* _Const_Base_ptr;

    _Rb_tree_color  _M_color;
    _Base_ptr       _M_parent;
    _Base_ptr       _M_left;
    _Base_ptr       _M_right;

    static _Base_ptr
    _S_minimum(_Base_ptr __x)
    {
      while (__x->_M_left != 0) __x = __x->_M_left;
      return __x;
    }

    static _Const_Base_ptr
    _S_minimum(_Const_Base_ptr __x)
    {
      while (__x->_M_left != 0) __x = __x->_M_left;
      return __x;
    }

    static _Base_ptr
    _S_maximum(_Base_ptr __x)
    {
      while (__x->_M_right != 0) __x = __x->_M_right;
      return __x;
    }

    static _Const_Base_ptr
    _S_maximum(_Const_Base_ptr __x)
    {
      while (__x->_M_right != 0) __x = __x->_M_right;
      return __x;
    }
  };

三个指针数据成员:

    _Base_ptr       _M_parent;
    _Base_ptr       _M_left;
    _Base_ptr       _M_right;

假设默认分配器，这些指针指向的数据是否会随机分配到堆上？

更新:

@Jeff 我想弄明白，看看这段代码:

struct _Rb_tree_impl : public _Node_allocator
        {
      _Key_compare      _M_key_compare;
      _Rb_tree_node_base    _M_header;
      size_type         _M_node_count; // Keeps track of size of tree.
           .
           .
           .

_M_node_count 和 _M_header._M_left 会在单独的缓存行中吗？它们在此处引用:

const_iterator begin() const _GLIBCXX_NOEXCEPT
{ 
   return const_iterator(static_cast<_Const_Link_type>(this->_M_impl._M_header._M_left));
}

  size_type size() const _GLIBCXX_NOEXCEPT 
  { 
      return _M_impl._M_node_count; 
  }

Answer 1

g++ 库实际上将 _Rb_tree_node_base 类型用于两个不同的目的:

1. 红黑树的节点。从 _Rb_tree_node_base 派生的类型的一个对象被分配到容器中每个元素的堆上。

   一个。 _M_color 是一个枚举，声明红黑树算法的节点为红色或黑色。

   _M_parent 指向父节点，或者如果该节点是根节点，则指向树的“头部”(见下文)。

   _M_left 指向左子节点，如果没有则为null。

   _M_right 指向右子节点，如果没有则为null。

   派生类中的另一个成员包含实际的容器元素。

2. “ header ”，即实际容器对象中的子对象 _M_header。

   一个。 _M_color 始终为红色(这有助于某些迭代器算法)。

   _M_parent 指向根节点，如果容器为空则为null。

   _M_left 指向排序顺序中的第一个节点，如果容器为空，则指向 header 本身。

   _M_right 指向排序顺序中的最后一个节点，如果容器为空，则指向 header 本身。

“past-the-end”的迭代器也指向容器的头部。

因此(几乎)回答您的问题，c._M_node_count 和c._M_header._M_left 都是c 的子对象。但是如果c不为空，则c._M_header._M_left指向的数据在c之外，由c分配 的分配器。