_Rb_tree + allocator observations

[Chris Lattner]

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?

This could also be applied to the comparison predicate, which today does
require space in the various _Rb_tree users, even when it is a trivial
std::less instance.

Thoughts?

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/