Дерево GCC stl.h красно-черное дерево исходный код для std:: set

Я смотрю на следующий файл исходного кода GCC stl_tree.h:

Https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.1/stl__tree_8h-source.html

И, в частности, эта часть: 

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.
Я пытаюсь выяснить, какие элементы данных есть у Объекта _Rb_tree_impl - под этим я подразумеваю элементы данных, которые он может наследовать от _Node_allocator.

В строке 330 он определяет _Node_allocator Как: 

typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other _Node_allocator;

Я не знаю, как найти определение для этого типа, чтобы проверить, что элементы данных, которые он содержит. Может кто-нибудь помочь? Где находится этот класс / структура?

1 3
c++ gcc red-black-tree

1 ответ:

Распределитель не имеет состояния, поэтому он не содержит никаких полей. Цель класса impl состоит в том, чтобы не стоить вам места для распределителя, используя оптимизацию компоновки базового класса.

Наивная реализация будет тратить пространство: 

template <typename T, typename Alloc>
class NaiveContainer
{
    Node<T*> root;     // just for exposition
    Alloc alloc;

public:
    NaiveContainer(Alloc const & a = Alloc()) : alloc(a) {}
    Alloc get_alloc() const { return alloc; }
    // ...
};

Этот класс является строго больше, чем он должен быть. Поэтому более разумное решение - с частным вложенным классом: 

template <typename T, typename Alloc>
class EboContainer
{
    struct Impl : Alloc
    {
        Impl(Alloc const & a) : Alloc(a) {}
        Node<T*> root;
    };
    Impl impl;

public:
    EboContainer(Alloc const & a = Alloc) : impl(a) {}
    Alloc get_alloc() const { return impl;  /* slicing */ }
    // ...
};

Теперь класс ровно настолько велик, насколько это необходимо для хранения соответствующих элементов данных. Кстати, это реализация является примером того, когда нарезка полезна.

4