dcollections version 0.02

[Bill Baxter]

On Wed, Aug 6, 2008 at 11:04 PM, Steven Schveighoffer
<schveiguy at yahoo.com> wrote:
> "Steven Schveighoffer"
>> "bearophile" wrote
>>> Steven Schveighoffer:
>>>> The only thing is that just because
>>>> the library 'builds' doesn't mean it all works :)  The classes/structs
>>>> are
>>>> all templates and so won't really 'compile' until you use them.
>>>
>>> But D unittests exists to test all templates too!
>>>
>>> Is an efficient deque too included? I often find the need for it (or just
>>> a stack). I have partially written a deque data structure (implemented as
>>> dynamic array of pointers to fixed size arrays, it's not an unrolled
>>> linked list), I may finish it to add it to your collections...
>>
>> I'm assuming you are talking about STL's deque?  I don't have anything
>> exactly.  You can implement a stack with the LinkList class.  If you end
>> up finishing your deque, I'll gladly take a look at adding it to
>> dcollections.
>>
>> The ArrayMultiset is implemented as a linked list of dynamic arrays, a
>> similar approach would probably work for a deque.
>
> Actually, it wouldn't work to provide O(1) lookup.  I think you need
> probably 2 arrays of arrays to provide the O(1) prepend, one that goes
> 'down' instead of 'up'.
>
> I'll think about how this could be implemented.  Maybe I'll take a look at
> the design of gcc's deque.

I think the wikipedia article on deque implementations is actually pretty good.
One way to implement is to use a circular buffer internally.  You can
tack on elements at either end of the empty space.  It also works very
efficiently for the case where you are hovering around a constant
number of elements.   No re-allocs needed in that case.  And all your
extra capacity can always be used for either end of the queue.   When
you are forced to realloc you can shift elements at the same time so
they're all at the front or back end of the new buffer.

Anyway there are various ways to do it, but that was the
implementation that sounded coolest to me.  Most of the others don't
do well with the case of stead flow in and steady flow out.  They
force either copying or reallocations.

--bb