Re: [boost] Proposal: Monotonic Containers

Subject: Re: [boost] Proposal: Monotonic Containers
From: Christian Schladetsch (christian.schladetsch_at_[hidden])
Date: 2009-06-10 04:32:08

I was wrong.

boost::monotonic::inline_storage<N> storage;
std::map<int, float, std::less<int>, boost::monotonic::allocator<int> >
v(storage);

Won't even work. Storage is not the allocator. Rather, to not use the
container overloads would require:

boost::monotonic::inline_storage<N> storage;
std::map<int, float, std::less<int>, boost::monotonic::allocator<int> >
v(boost::monotonic::allocator<int>(storage));

Which is dramatically even worse again.

On Wed, Jun 10, 2009 at 8:16 PM, Christian Schladetsch <
christian.schladetsch_at_[hidden]> wrote:

> Hi David,
>
> auto_buffer is, in fact, related, inasmuch as it also attempts to use the
>>> stack for storage.
>>>
>>
>> Ok, so you could use Thorsten's auto_buffer as your storage, which
>> actually would give you, potentially, the best of two worlds (allocation
>> speed and - you seem to push this angle - cache) and dynamic heap beyond
>> that initial segment.
>
>
> Cache coherency is King!
>
> auto_buffer<T> is not analogous to monotonic::inline_storage<N>
>
>  However, boost::monotonic provides an allocator that means that *all* STL
>> containers - and other ones - can use the stack for storage. Or the heap.
>>
>
> NOTE: your "storage_base" is not a base abstraction at all, but a
>> "heap_storage"; having a non-leaf having a concrete but totally different
>> behavior from its leaf child is less than beautiful.
>
>
> I agree that the current implementation is not ideal, but I don't follow
> what you mean here. storage_base may be ugly, but it is also required so
> that different containers can use the same storage.
>
> I agree that it could be improved. I had a lot of problems with the more
> fundamental problems of std::allocator
>
>
>> Why is the behavior of whether to pick the heap storage ("storage_base"...
>> ugh) or stack (if not embedded in a heap-allocated object...) decided at
>> runtime, via that polymorphic "storage_interface"? It is set at the creation
>> of the allocator, so why not make it a type parameter of the allocator, with
>> a default to, say, "inline_storage"? Do you think it is important to have
>> two containers sharing the exact same type even when one uses "storage_base"
>> and the other "inline_storage"?
>
>
> I agree that there are some ugly aspects to the current proposal. However,
> it also works as advertised which is very important.
>
> I hate the current implementation's basis of using a virtual base class. It
> is anathema to me. I only presented it as it stands because I was more
> concerned about adoption of the general idea, rather than the smaller and
> less-relevant details of the implementation. I think most of us could write
> this from scratch with no problem, and without virtuals.
>
> Point being, if the idea is adopted, then yes there are optimisations and
> beautifying to do.
>
> That said, you may have also missed the point that multiple containers can
> use the same storage - which may be on the heap or the stack.
>
>
>> In that respect, auto_buffer<T> is a subset of the proposed
>> boost::monotonic::vector<T>.
>>
>
> I still fail to see why you wrap all those containers, instead of providing
>> just that allocator. Is the only reason what I just mentioned, to keep the
>> storage mechanism variable ("storage_base" or "internal_storage") while the
>> container types equal? That is the only somewhat logical rationale for me.
>> Regarding injecting stuff, such as your allocator, in a template class
>> higher up the hierarchy (such as in std::vector), you should have a look at
>> my proposal at a "type injector":
>> http://blog.davber.com/2006/07/24/hierarchy-generation-in-c/
>
>
> I will consider dropping the idea of including the containers on top of the
> allocator.
>
> The 'wrapping of the containers' is very small, very straight-forward, only
> requires the passing-forward of construction parameters, and is completely
> safe as none of them have any state outside of their base classes.
>
> Inheriting from the std::containers also means that existing code that
> pattern-matches against the std::containers will also match against
> monotonic::containers. They are functionally equivalent, and in-memory
> equivalent. They are the same thing, except that monotonic::containers must
> be given either an allocator or storage from which to make one.
>
> The fact that STL containers do not have virtual dtors is not relevant.
> There is no state in the proposed monotonic containers that is not in
> std::containers.
>
> There is a case for:
>
> boost::monotonic::inline_storage<N> storage;
> std::vector<int, boost::monotonic::allocator<int> > v(storage); // (A)
>
> versus:
> boost::monotonic::inline_storage<N> storage;
> boost::monotonic::vector<int> v(storage); // (B)
>
> but what about:
> boost::monotonic::inline_storage<N> storage;
> boost::monotonic::map<int, float> v(storage);
>
> versus:
> boost::monotonic::inline_storage<N> storage;
> std::map<int, float, std::less<int>, boost::monotonic::allocator<int> >
> v(storage);
>
> My main concern would be that people just aren't comfortable with the idea
> of using custom allocator types, but they will accept the idea of needing to
> pass the storage in once they realised that they needed a monotonic
> container.
>
> There are other important issues, like having to give the predicate type
> for the associative containers first.
>
> If I didn't think it was important, I wouldn't have proposed the library in
> the first place. Given that I think that it's important, it is also
> important to me that the usage is clean. (A) above may be `better`,  but (B)
> is cleaner.
>
> Take care.
>>
>> /David
>
>
> Cheers,
> Christian
>
>