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.
