On Sat, 2012-10-06 at 19:42 -0700, Jonathan M Davis wrote: […] > 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
Not sure about the D implementation, but in other languages all the singly-linked list iterator has to do to allow for removal is to maintain a "front foot"/"back foot" state. This is needed for insert as well, so it is already there. > 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). Removal from a singly-linked list can be O(1) as well, it depends whether you are deleting using an iterator in progress. > 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 -- Russel. ============================================================================= Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.win...@ekiga.net 41 Buckmaster Road m: +44 7770 465 077 xmpp: rus...@winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
signature.asc
Description: This is a digitally signed message part
