Phobos 'collections' question
Steven Schveighoffer
schveiguy at yahoo.com
Wed Oct 26 07:02:11 PDT 2011
On Tue, 25 Oct 2011 01:00:51 -0400, Andrew Wiley
<wiley.andrew.j at gmail.com> wrote:
> On Mon, Oct 24, 2011 at 9:50 PM, Marco Leise <Marco.Leise at gmx.de> wrote:
>
>> Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer <
>> schveiguy at yahoo.com>:
>>
>>
>> On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr at gmx.ch>
>> 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?
No. Not yet.
> You could use a tree for that, but my understanding is that a heap is
> much
> more efficient?
Yes. I have a feeling dcollections will use heap from phobos (to avoid
duplication) for a full priority queue.
-Steve
More information about the Digitalmars-d
mailing list