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.
