On Mon, Oct 24, 2011 at 9:50 PM, Marco Leise <[email protected]> wrote:
> Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer < > [email protected]>: > > > On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <[email protected]> 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 (www.dsource.org/projects/** >> dcollections <http://www.dsource.org/projects/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?
