Removing from SList (std.container)...

[Timon Gehr]

On 06/27/2012 08:46 PM, Roman D. Boiko 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?

O(1) removal works quite ok for a singly linked list. eg:

1.
- Add a sentinel node to the start of your list.
- Represent an iterator into the list as a pointer to the predecessor
   of the respective node.
- Removal: trivial. rebind the 'next' reference of the pointed-to node.

2.
- Represent the empty list as a sentinel node with null 'next' field.
- For removal of a node you own a pointer to:
  -- case 1: the successor is an empty list:
     - destroy the value, set the 'next' reference to null.
  -- case 2: else:
     - move the successor's value into the node that holds the value to
       be removed, bind the 'next' reference to the successor of the
       successor.