Removing from SList (std.container)...

[Steven Schveighoffer]

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.

Look up SList docs, even with a reference to a *specific element*, you  
cannot do O(1) removal.

Only recently did it add O(1) insertion, but only after a specific  
element.  Good luck implementing a way to do insert *before* that element  
in O(1), it will be possible, but really obtuse.

-Steve