Removing from SList (std.container)...

[Roman D. Boiko]

On Wednesday, 27 June 2012 at 19:10:24 UTC, Steven Schveighoffer 
wrote:
> On Wed, 27 Jun 2012 14:46:36 -0400, Roman D. Boiko 
> <rb at d-coding.com> wrote:
>
>> On Wednesday, 27 June 2012 at 18:26:46 UTC, Steven 
>> Schveighoffer wrote:
>>> The thing that makes SList useless is the O(n) removal.  
>>> Nobody will ever use SList when they can write a replacement 
>>> that has O(1) removal in 10 minutes.
>> Do you mean something like indexed/sorted dictionary? It 
>> doesn't seem to be that easy to implement. Or some other data 
>> structure with O(1) removal?
>
> struct Link
> {
>   int val;
>   Link *next;
>   removeNext() {assert(next); next = next.next;}
> }
>
> O(1) removal, easy as that.
I thought you meant removal by index or value, not element 
reference.

> Look up SList docs, even with a reference to a *specific 
> element*, you cannot do O(1) removal.
Ha-ha, didn't know SList doesn't support that.