Re: [boost] Proposal: Monotonic Containers

Subject: Re: [boost] Proposal: Monotonic Containers
From: Ross Levine (ross.levine_at_[hidden])
Date: 2009-06-15 01:04:10

I can't really think of a good niche for this. A deque is probably close
enough for most people, and in general I don't think that most users'
performance bottlenecks are caused in STL containers. Moreover, for those
who *are* getting poor performance from STL containers probably will want to
roll their own container that works in a custom way. This "chain" seems like
a container that would rarely be used, because in order to use it, a user
would want something that was like a deque, but performed nominally better,
and would need to have profiled their code and discovered that it was the
deque that was causing the problem. I am of the serious opinion that hardly
anyone would have a legitimate use for it.

So if you are convinced that it would useful, I would suggest against trying
to submit it on its own. It's just a deque that you can choose the size of
the chunks.

On Sun, Jun 14, 2009 at 11:16 PM, Christian Schladetsch <
christian.schladetsch_at_[hidden]> wrote:

> Hello,
>
> Before I make a third proposal within a single week, I wanted to ask
> whatever crowd remains on this thread about the idea of a boost::chain.
>
> The basic interface is:
>
> template <class T, size_t C = 64, class Al = std::allocator<T> >
> struct chain;
>
> A `chain` (what I previously called a `rope`) is a random-access sequence.
> Internally, it is a sequence of array<T>'s, where each such 'link in the
> chain' has C elements.
>
> By default, it has O(1) access time. It is similar to a deque (with the
> same
> interface), except that it is nominally more efficient and the user can
> specify the trade-off on access time vs. granularity. Not incidentally, it
> also supports different links having their storage in different places.
>
> The complete interface is:
>
> template <class T
>   , size_t C = 64
>   , class Al = std::allocator<T>
>   , class Link = boost::uninitialised_array<T, C, Al>
>   , class Links = std::deque<Link, Al>
> >
> struct chain;
>
> I have made reference to boost::uninitialised_array<T, C, Al> here. I don't
> think such a beast exists at the moment, but the idea is pretty simple. It
> is a fixed-sized array of uninitialised T's using storage from the given
> allocator.
>
> In the general case, chain<> is a hard-sell over a std::deque<>. They are
> functionally equivalent, and have the same big-O qualities.
>
> However, because chain<> uses fixed-size, inline storage for the links, and
> because it can be user-tuned, it can be more efficient in time and space
> than a deque. How much would be hard to guess, is abusable by the user, and
> whether it would be even worth finding out is hard to tell.
>
> But of course it is abundantly clear that the motivation for such a
> structure is to create an ideal 'array-like sequence' for use with a
> monotonic allocator, and further, for the case where some of the links are
> on the stack, and others are on the heap.
>
> That said, it is also clear that it may have application outside of that.
>
> So, my question is: should I bother writing this generally and make a
> proposal to put it into boost::, or do I just make it specialised and put
> it
> into boost::monotonic::chain?
>
> Thanks in advance for your thoughts,
>
> Regards,
> Christian
>
> PS. The mere act of writing post this makes me think that chain<> would
> raise limited interest in the general case.
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>