Re: libstdc++/8230: Buggy allocator behaviour

[Matt Austern <austern at apple dot com>]

On Friday, November 15, 2002, at 09:24  AM, Benjamin Kosnik wrote:

> > There is a simpler way.  If the containers use their Allocator as a
> > private base class instead of a member, the code is a lot cleaner.
> >
> > I did a treatment of this and found, although the code looked cleaner
> > to my eye, there was no significant advantage in terms of time or 
> > space
> > (at least in 3.0, when I ran the tests).  I did not measure compile
> > time differences.
> >
> > I could try to dig up the treatment if you want an example of what I'm
> > talking about.
> Please, I'd like to see it.
I've done something similar, in an experimental cleanup of the
library that I did while at AT&T.  I'm not sure if I have
permission to distribute that code (we were just getting release
permission at the time I left), but I can certainly talk about it.

It's clean, it conserves space properly for empty allocators,
and it's pretty easy to adapt it to the case of allocators with
non-default pointer types and with state.  Two things you should
be aware of, though, for future evolution.

First, of course, you need to deal with allocators for multiple
types.  For a linked list, for example, if you really want to
be rigorous about allocator type correctness, you need three
different kinds of allocators.  (One for list nodes, one for
pointers, one for the container's value type.)  The way you
mention these allocator types, of course, is with rebind.  This
results in pretty cumbersome expressions.

This is a nuisance if you use the base class technique, because,
of course, there's no scope in which you can put a typedef.
So you end up with something like this:
 template <class T, class Allocator>
 struct List
   : private typename Allocator::template rebind<_Node<T> >::other,
     ...
and then, of course, you have to mention that type again inside
the class.  That time you can use a typedef, but you still have
to write it out twice.  (Actually it's worse than that if you're
trying to be rigorous about allocators with alternate pointer
types, because node has to be parameterized by a void pointer
type as well.)

An alternative is of course to keep just one allocator around as
a base class, and convert to other types on demand.  But this
might be slower, and, depending on how the standards committee
resolves issue 258, may or may not be correct.

The second issue you should be aware of deals with swap() and
allocators with state.  What happens when you have two
containers with allocators of the same type but different
values, and you write x.swap(y).   Three alternatives:
 (1) You can't do that: allocator equality is a precondition
     for swap, so this is an error and invokes undefined
     behavior.
 (2) The containers' contents get swapped, the allocators
     remain attached to their original containers.
 (3) The allocators get swapped.

I favor option (1), or possibly (2), but some people, notably
Howard Hinnant, favor option (3).  You should be aware that if
we go with the private-base-class design we'll be making
option (3) impossible.  In my opinion it's the right decision,
be we should make sure we're aware of the consequences.

				--Matt

P.S.  Note that a lot of the complexity of the existing way
of handling allocators is for reasons that are no longer
relevant.  Absolutely clear that there's scope here for major
cleanups.