Correctly implementing a bidirectional range on a linked list?

[anonymous via Digitalmars-d-learn]

On Monday, 6 July 2015 at 20:50:19 UTC, Gary Willoughby wrote:
> How do you correctly implement a bidirectional range on a 
> linked list?
>
> I have a linked list implementation and I've added a range 
> interface to it but after a while I've realized it not quite 
> right. The problem is when I call the save method of the 
> forward range interface I don't get a copy I only get another 
> view to the same state. So when i remove nodes from the 
> original list the range becomes invalid.
>
> How can you implement such a range over a type whose state is 
> accessed via pointers?
>
> Here's my implementation:
>
> https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection/linkedlist.d#L533

There's no requirement for a range to stay valid when the 
underlying container changes. std.container defines "stable" 
variants of the various insertion and removal operations. They 
promise not to invalidate any ranges. When the unstable variants 
are used, it's to be expected that ranges are invalidated.

To make your removal methods stable, it may be enough to not free 
the removed node. That is, don't do this:
https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection

There's a doubly linked list in phobos: std.container.dlist; 
maybe look how things are done there:
https://github.com/D-Programming-Language/phobos/blob/master/std/container/dlist.d

Off topic: I think `@trusted:` is horrible. It's easy to forget 
that you're in a @trusted environment when editing things later. 
And even worse, you're trusting everything that's passed through 
template parameters.