Phobos 'collections' question

Andrew Wiley wiley.andrew.j at
Mon Oct 24 22:00:51 PDT 2011

On Mon, Oct 24, 2011 at 9:50 PM, Marco Leise <Marco.Leise at> wrote:

> Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer <
> schveiguy at>:
>  On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr at> wrote:
>>  On 09/14/2011 04:08 PM, Robert McGinley wrote:
>>>> Hey all,
>>>> Mostly as an exercise I'm considering writing an ArrayList, AVL tree,
>>>> and possible other standard data structures in D.  I have two questions.
>>>> 1.) If completed should I send these around for review and inclusion or
>>>> do they not belong in phobos?
>>>> 2.) If I'm working on including these in phobos should I put them in
>>>> container.d (that has RedBlack Trees and a Singlelinked List) or is there a
>>>> better location?
>>>> Rob
>>> As far as I know, the reason why std.container is not under active
>>> development, is that phobos does not have an allocator abstraction yet. As
>>> soon as there is one, the module will probably undergo some breaking
>>> changes. But I think the more well implemented standard data structures
>>> there are in Phobos, the better. I think as soon as the standard allocator
>>> interface is settled on, your efforts will be welcome. Steve can probably
>>> answer your question better though.
>> Certainly more containers are welcome.
>> The review for getting things into phobos is done via github.  You do not
>> need write permission to generate a pull request.  Yes, they should all be
>> put into std.container for now.
>> I'd recommend doing one pull request per container, that way one container
>> type does not detract from the inclusion of another.
>> I don't think that lack of allocators should prevent implementing
>> containers.  My collection package (**
>> dcollections <>) uses
>> allocators, and they're pretty orthogonal to the operation of the container.
>> BTW, feel free to use any ideas/code from dcollections, it's also boost
>> licensed.  Note that the red black tree implementation in phobos is copied
>> verbatim from dcollections.  If you implement a good AVL tree, I might even
>> steal it for dcollections ;)  (with attribution, of course!)
>> -Steve
> I recently had the need for a priority queue and your library was the
> obvious choice. But it did the same that my code did when I ported it from
> 32-bit to 64-bit: array.length is no longer a uint, but a ulong, so the code
> breaks. So my advice is to use size_t when you deal with a natural number
> that can be up to the amount of addressable memory.

Wait, dcollections has a PriorityQueue?
You could use a tree for that, but my understanding is that a heap is much
more efficient?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Digitalmars-d mailing list