Re: [boost] Proposal: Monotonic Containers

Subject: Re: [boost] Proposal: Monotonic Containers
From: Christian Schladetsch (christian.schladetsch_at_[hidden])
Date: 2009-06-15 01:10:11

Thanks Ross,

I have come to the same conclusion.

On Mon, Jun 15, 2009 at 5:04 PM, Ross Levine <ross.levine_at_[hidden]> wrote:

> 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
> >
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>