Remove element from DList

[Andrei Alexandrescu]

On 10/7/12 5:15 AM, Jonathan M Davis wrote:
> On Sunday, October 07, 2012 10:09:06 Russel Winder wrote:
>> Removal from a singly-linked list can be O(1) as well, it depends
>> whether you are deleting using an iterator in progress.
>
> IIRC that dcollections' singly-linked list is like this, but
> std.container.SList definitely isn't. I'm not a big fan of singly-linked lists
> in the first place and tend to think that they're useless, but std.container's
> is particularly bad in that regard.

Singly-linked lists are limited in functionality as containers, but very 
fast for a few applications. It's quite likely someone would choose a 
singly-linked list primarily for performance.

Some more functionality could be implemented for SList if it used for 
its range a pointer pointing one before the first element. But that 
would have meant an extra indirection for each and every access, undoing 
a large fraction of performance benefits. That's why I chose the 
primitives the way I did.


Andrei