GSoC-2011 project:: Containers

Daniel Gibson metalcaedes at gmail.com
Wed Mar 30 08:27:19 PDT 2011


Am 30.03.2011 16:15, schrieb spir:
> On 03/30/2011 10:41 AM, Daniel Gibson wrote:
>> Am 30.03.2011 10:27, schrieb KennyTM~:
>>> On Mar 30, 11 16:18, Daniel Gibson wrote:
>>>> Am 30.03.2011 01:55, schrieb Jonathan M Davis:
>>>>> On 2011-03-29 14:50, dsimcha wrote:
>>>>>> == Quote from Jonathan M Davis (jmdavisProg at gmx.com)'s article
>>>>>>
>>>>>>> The fancier stuff would be nice, but we don't even have a
>>>>>>> doubly-linked
>>>>>>> list yet. We should get the simpler stuff sorted out before we get
>>>>>>> particularly fancy, not to mention that it's usually the simple
>>>>>>> stuff
>>>>>>> that gets heavily used.
>>>>>>
>>>>>> For the most part I agree, but a doubly linked list might be **too**
>>>>>> simple. Linked lists are so trivial to implement that I'd tend to
>>>>>> roll my
>>>>>> own that does exactly what I need with regard additional behavior on
>>>>>> insertion, etc. rather than wrapping a library solution to get these
>>>>>> features.
>>>>>
>>>>> A doubly-linked list is on the list of containers that every standard
>>>>> library
>>>>> should have or it's likely to be considered lacking. I can understand
>>>>> rolling
>>>>> your own for specific uses, but _I_ sure don't want to be doing that
>>>>> if I
>>>>> don't have to. If I want a doubly-linked list, I want to be able to
>>>>> just
>>>>> create a standard one and use it. C++, C#, and Java all have
>>>>> doubly-linked
>>>>> lists in their standard libraries.
>>>>>
>>>>> If no one else ever implements a doubly-linked list for Phobos, I'll
>>>>> probably
>>>>> do it eventually simply because it's one of the containers that is on
>>>>> the
>>>>> short list of containers that pretty much every standard library has.
>>>>>
>>>>> - Jonathan M Davis
>>>>
>>>> It may be feasible to enhance the single-linked list to support both
>>>> single- and double linking, via an additional template-parameter "bool
>>>> doubly" or something like that and some static-ifs in the
>>>> implementation.
>>>> I once created a simple single/double-linked queue for D1 like that.
>>>>
>>>> Cheers,
>>>> - Daniel
>>>
>>> It is always possible to combine types together with 'static if', but
>>> the structure and interface is sufficiently different that doubly-linked
>>> list should better be a separate type.
>>
>> Is it? It's just a few additional functions and the functions do some
>> additional stuff (mostly handling prev-pointers) for double-linked
>> lists. Much
>> of the single-linked list code can (probably) be reused - so why
>> duplicate code?
>
> The internal mechanisms are different when one has 2-side pointers
> available (actually simpler, that's why I guess singly-linked lists are
> rare outside the cons-based functional realm).
>
> Denis

Deleting within the list is different, yes, at least if you want to 
support something else than "delete next element" - in that case you 
only have to care about the additional pointers.
Inserting (at least "insert after this element") is pretty similar, 
apart from some additional prev-pointers.
I mostly thought about the other stuff (insert/remove at front/back) 
because that were my usecases in my single/double linked queue.	

Cheers,
- Daniel


More information about the Digitalmars-d mailing list