_Rb_tree + allocator observations

[Paolo Carlini]

Chris Lattner wrote:

>I've noticed that libstdc++ goes through a lot of contortions to support
>allocators which are "stateless", but it doesn't bother to optimize lots
>of other obvious cases.
>
>For example, assume an implementation of a custom allocator does not
>implement _Alloc_traits: the allocator is probably stateless, but it will
>still have space allocated for it in the _Rb_tree structure.  Why not
>derive from the allocator object itself somehow to take advantage of the
>empty base class optimization?
>
Hi Chris. Just a naive observation: if I merge in my mind some obervations
Nathan made a few years ago:

    http://www.cantrip.org/emptyopt.html

with this comment from stl_tree.h

    // Base class to encapsulate the differences between old SGI-style
    // allocators and standard-conforming allocators.  In order to avoid
    // having an empty base class, we arbitrarily move one of rb_tree's
    // data members into the base class.

I strongly suspect that, as quite often happens, the root of the problem is
that some old parts of our STL should be updated to take advantage of the
features provided by the current g++ (or other modern compilers for that
matter ;)

Nathan, do you have somehing to add, out of the top of your head?

Paolo.