Remove element from DList

[Jonathan M Davis]

On Sunday, October 07, 2012 04:14:58 cal wrote:
> On Sunday, 7 October 2012 at 01:14:48 UTC, Jonathan M Davis wrote:
> > The correct way is to use find combined with take (which is
> > what you're doing,
> > except that you're not using find). So, something like this
> > should work
> > 
> > void main()
> > {
> > 
> >     auto list = DList!int([1,2,3,4]);
> >     list.remove(find(list[], 3).take(1));
> > 
> > }
> > 
> > 
> > However, for some reason, this is indeed not working right now.
> > It's a bug.
> > Please report it.
> 
> SList doesn't implement remove, so perhaps DList can only
> guarantee the required complexity when given the range defined in
> DList, and for other types of ranges, it can only guarantee
> linear complexity?

singly-linked lists and doubly-linked lists are completely different beasts. A 
singly-linked list can't do it sanely, because it has to traverse the list to 
find the previous node so that it adjust the links. A node in a doubly-linked 
list has a link to the previous node in the list instead of just the next 
node, so it doesn't have that problem. You can add and remove elements from 
anywhere in a doubly-linked list in O(1). And if you're dealing with 
iterators, it won't affect any iterators except if they point at the element 
being removed (so it's a stable remove). With ranges, it would affect the 
elements in the range, but unless you're removing an element which is at the 
front or end of a range, it shouldn't invalidate the range at all. And that 
can be gotten around by letting that node continue to exist and point to what 
was the next node in the list (in which case, it would go away once no more 
ranges referred to it - the GC makes doing that fairly easy).

So, I don't see any reason why remove wouldn't be stable or non-linear. It's 
actually kind of hard to make it _un_stable in this case. And actually, 
looking at the code, stableLinearRemove (and linearRemove is an alias for 
stableLinearRemove in this case) calls remove, so overall, this is a bit 
bizarre. Regardless, it's a bug that normal remove doesn't work with the 
result of take.

- Jonathan M Davis