[libstdc++] PATCH: STL allocator cleanup, part 1

[Matt Austern <austern at apple dot com>]

I mentioned a few weeks ago that I was working on cleaning up the use 
of allocators in the STL part of libstdc++.  This is a patch for the 
first part of that work, to give people a better idea of where I'm 
planning to go.  This part is complete in itself, and I've tested it on 
Linux (I've verified that it doesn't break the libstdc++ or libjava 
build on Linux and that it doesn't introduce libstdc++ regressions), so 
first of all: OK to commit to mainline?

Read on for an explanation of what this patch is supposed to do and 
where I'm planning to go with it.

The goal is to get rid of some of the gross stuff in <memory> and in 
the various containers, which was introduced to work around compiler 
deficiencies in old SGI compilers and to accommodate an old 
pre-standard allocator interface that nobody cares about anymore.  From 
a maintainer's point of view this will make the containers more 
maintainable.  From a user's point of view the main effect is that 
we'll be instantiating fewer classes, so we ought to be making 
compilations a bit faster and object files a bit smaller.

Specifically, the various stages of this work:
 1. This patch: change vector<>, deque<>, list<>, and the four hash 
containers so that they no longer use _Alloc_traits and they no longer 
have alternative base classes depending on whether or not the allocator 
is instanceless.  Instead, just inherit from the allocators and rely on 
the empty base class optimization for instanceless allocators.  It's 
safe to rely on that optimization, because it's written into our ABI.  
Also fix previously hidden bugs in demangle.h (see below).
2. Do the same thing for the remaining containers: vector<bool>, the 
four standard associative containers, rope, and slist.  (If anyone 
would like to volunteer to do rope, I'd appreciate it.)
3. Remove _Alloc_traits, and remove all support for the old 
pre-standard SGI allocator interface.
4. Some of the internals of allocator<> should always have been 
declared out-of-line, in a .cc file.  The reason Hans and I didn't do 
that back at SGI was that we wanted it to be possible to install STL as 
headers only, so we artificially made some things templates just so 
they could go in headers.  This goal is now irrelevant.  So: get rid of 
the artificial templatization in stl_allocator.h, and put things that 
belong in a .cc file in one.

What I am *not* planning to do as part of this work: change the way 
containers use allocators so that it's possible to use alternative 
memory models.  That work is interesting and a little challenging (you 
have to be very disciplined about calling a.construct() and you 
suddenly find that you need a *lot* more allocator types than you had 
before), but the benefit-to-intrusiveness ratio seems pretty low right 
now.  If we ever do want to do it, though, the work I'm doing will make 
it easier.

Two possibly-controversial design choices that you'll see in my patch.

First, one of the reasons I did deque<> as part of the first batch is 
that it has an interesting property: internally, the container needs to 
allocator objects of two different types.  That means we have to deal 
with two different allocators.  You can get from one allocator type to 
the other using rebind, and from one object to the other using the 
converting constructor.  So the question: do we store both allocator 
objects in the container, or do we just store one of them and create an 
allocator of the other type on demand when we need it?  I chose the 
latter.  I think it was the right decision, but it's not a tremendously 
big deal.

Second, the old containers were tolerant of allocator type mismatches: 
they would let you write something like std::vector<int, 
std::allocator<double> >.  That tolerance was deliberate, but I now 
think it was a mistake; it lets bugs creep in by mistake, and lets 
people write nonportable code without knowing it. I've now taken that 
extension away, and I now require that the allocator's type match the 
container's value type.  (That's what I had to fix in the demangler, a 
few places where it was sloppy about using an allocator of the correct 
type.)  This does mean that some users will have to fix their code, but 
that doesn't bother me very much.  Explicit use of allocators is not 
for the naive user.  Anyone sophisticated enough to want to use 
allocators at all is sophisticated enough to use them correctly.

			--Matt

Attachment: stlpatch.txt
Description: Text document