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?

This SO answer may be helpful: http://stackoverflow.com/a/14148870/12711 — Michael Burr, Jun 07 '14 at 00:23

score 4 · Accepted Answer · edited Jun 07 '14 at 02:32

4

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.

edited Jun 07 '14 at 02:32

David Rodríguez - dribeas

204,818
23
294
489

answered Jun 07 '14 at 00:20

Kerrek SB

464,522
92
875
1,084

Ok I get what you are saying- I don't understand how the code achieves this though? "base class layout optimizations" – intrigued_66 Jun 07 '14 at 00:35
@mezamorphic: the size of a base subobject is allowed to be less than the size of a complete object of the same type. – Kerrek SB Jun 07 '14 at 00:47
and what part of the sub object is "removed"/sliced to achieve this? – intrigued_66 Jun 07 '14 at 00:51
2

*The allocator is stateless* is quite an overstatement, the allocator **may** be stateless (or not). Also, in the implementation the OP mentions, the type is not a *nested* type, although it does not matter much for the answer. – David Rodríguez - dribeas Jun 07 '14 at 02:30
1

@mezamorphic: I think the relevant base class layout optimization is the possibility that a base class not occupy any space. From [intro.object]/5: "Unless it is a bit-field (9.6), a most derived object shall have a non-zero size and shall occupy one or more bytes of storage. Base class subobjects may have zero size." – rici Jun 07 '14 at 03:01
@DavidRodríguez-dribeas: I believe that `std::allocator` is always stateless, non? – Kerrek SB Jun 07 '14 at 13:54
@KerrekSB: `std::allocator` is stateless (well, in most implementations). The the containers in the standard library must support stateful allocators since C++11. C++03 had some weirdness where the combination of requirements ended up implying that allocators could not have state, but that changed in C++11. Don't get me wrong, the answer is correct: the allocator is moved to a base because the most frequent allocator is stateless and you can take advantage of EBO. – David Rodríguez - dribeas Jun 07 '14 at 22:46

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

1 Answers1