Thanks Ross, I have come to the same conclusion. On Mon, Jun 15, 2009 at 5:04 PM, Ross Levine <ross.levine@uky.edu> 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@gmail.com> 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