Removing from SList (std.container)...

[Roman D. Boiko]

On Wednesday, 27 June 2012 at 19:06:46 UTC, Timon Gehr wrote:
> 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.
Nice. But forces to use iterators everywhere.