dcollections version 0.02

Steven Schveighoffer schveiguy at yahoo.com
Wed Aug 6 07:04:42 PDT 2008


"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.

-Steve 




More information about the Digitalmars-d-announce mailing list