Phobos 'collections' question

Marco Leise Marco.Leise at
Mon Oct 24 19:50:33 PDT 2011

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

More information about the Digitalmars-d mailing list