Remove element from DList

[cal]

On Sunday, 7 October 2012 at 02:54:44 UTC, Jonathan M Davis wrote:
> 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

Righto, i'll put in a ticket, thanks for the help.