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
