Re: [boost] Proposal: Monotonic Containers - Comparison with boost::pool, boost::fast_pool and TBB

Subject: Re: [boost] Proposal: Monotonic Containers - Comparison with boost::pool, boost::fast_pool and TBB
From: Christian Schladetsch (christian.schladetsch_at_[hidden])
Date: 2009-06-23 18:14:09

>
>  Christian> The other thing I'd like is for map<> etc to ensure that new
>> containers
>> added to them use a rebound allocator. I do this for monotonic containers
>> via a trait is_monotonic<Container>;
>>
>
> Felipe> I don't think you should do that. It is unintuitive IMHO. Elements
> inside the map are different beasts. If the user wants to use the same
> allocator. Then he shouldn't use operator[]. Which default-constructs the
> object.

Irrespective of that issue, surely there is a case to be made for
normalising the use of allocator::construct?

The fact that it is only sometimes used by the STL containers renders it
practically useless. You currently can't do anything useful in
allocator::construct, which seems to me to be counter to its original
intended purpose.

By ensuring that it is always called before an object is used, we can start
to use it how it was first intended.

Back to the idea of nested containers using the same allocator. I agree that
there is a case to be made against automatically spreading an allocator down
into contained types. monotonic currently solves this by using regions:

    struct my_region{};
    std::map<int, std::list<int, monotonic::allocator<int, my_region>>,
std::less<int>, monotonic::allocator<int, my_region> > map;

and that works - both the map and the inner list will use the same storage
and both can be defalt constructed. But it doesn't allow for truly local
storage and doesnt use a stateful allocator.

So, consider the following, which purports to use a statefull allocator with
a container that norminally respects statefull allocators:

   boost::containers::list<int, my_custom_allocator<int> >
list(stateful_allocator);
   generate_n(back_inserter(list), 100, rand);
   list.sort();

In this case, without at least ensuring that allocator::construct is called
in list::sort when it creates temporary lists, the sort method will create
lists that do not use a correct allocator. This is useless and contradicts
the entire purpose of supporting statefull allocators in the first place.
There are other specific areas where this is a problem as well, but it truly
is a general problem.

monotonic::containers attempt to solve this by dealing with it at the
allocation level, which uses traits to determine when what is being
constucted is in turn a monotonic container that uses the same allocator
type and if so, passes itself as a construction parameter in
allocator::construct. This means that default-constructed temporaries
created by the parent container will indeed use a correct statefull
allocator.

But this can't work if the parent container simply calls allocator::allocate
then uses placement new, or if the parent container creates
default-constructed value_types on the stack. Ironically, if the container
used its allocator correctly, it would use both ::allocate and ::construct,
and the value_type may well be on the stack...

In summary, sometimes STL containers use allocator::construct, sometimes
they don't, which renders allocator::construct effectively and practically
pointless.

By not at least ensuring that allocator::construct is called before a
contained object is used, the nominal support for statefull allocators in
the proposed boost::containers is rendered useless, and I'm back to making
my own.

Regards,
Christian