GCC stl_tree.h red-black tree source code for std::set

Question

I am looking at the following GCC source code file stl_tree.h:

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

and in particular, this part:

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.

I am trying to work out what data members a _Rb_tree_impl object has- by this I mean the data members it may inherit from _Node_allocator.

On line 330 it defines _Node_allocator as:

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

I do not know how to find the definition for this type to check what data members it contains. Could someone please help? Where is this class/struct located?

Answer 1

The allocator is stateless, so it doesn't contain any fields. The purpose of the impl class is to not cost you any space for the allocator by employing base class layout optimizations.

The naive implementation would waste space:

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; }
    // ...
};

This class is strictly larger than it needs to be. So the cleverer solution is with a private nested class:

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 */ }
    // ...
};

Now the class is exactly as large as it needs to be to hold the relevant data members. Incidentally, this implementation is an example of when slicing is useful.