Re: [boost] Proposal: Monotonic Containers

Subject: Re: [boost] Proposal: Monotonic Containers
From: Christian Schladetsch (christian.schladetsch_at_[hidden])
Date: 2009-06-14 23:16:55

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.