I really REALLY miss a doubly-linked list. That's all i can think of right now, which is missing from D's containers :-)
On Tue, Oct 25, 2011 at 9:00 AM, Andrew Wiley <[email protected]> wrote: > > > 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) >>> 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?
