On 03.11.2011 21:13, Steven Schveighoffer wrote:
On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky
<dmitry.o...@gmail.com> wrote:
On 03.11.2011 19:34, Steven Schveighoffer wrote:
On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath
<tob...@pankrath.net> wrote:
Dmitry Olshansky wrote:
And more importantly, it still would be horribly slow O(N^2).
Personally, because of that I'd prefer hand-rolled intrusive
singly-linked list any time of day.
To be honest, I don't understand this.
A "remove_if" for non-intrusive single-linked lists should be doable in
O(N).
Yeah, poor wording going to kill me one day :) And looking at how
SList works with "checked" remove does O(N^2) turned out to be a
context for reference for intrusive singly-linked list, just my bad.
As for why I'd rather go with intrusive lists, it's because of it
usually uses less memory due to node structures being more padding-free.
Anyway the point should have been focused on _hand-rolled_ part,
mostly because SList is plain not ready for prime time*. And btw
singly-linked list it's not hard to implement and you can fine tune it
how you like it e.g. they do play nice with free list allocation
strategy. Not to say of circular lists and/or using sentinels.
SList is a poor singly linked list implementation. It does not support
O(1) removal.
-Steve
Aye, looking at SList implementation I can say that it sort of tries
to verify that this is a correct list. Otherwise it would be O(1).
Indeed passing wrong range/iterator is quite bad in linked lists and
could lead to all manner of funky bugs, but the cost is horrific.
Especially since insert doesn't do this extra check.
No, it's necessarily doing O(n) search for current node because it has
no reference to the previous node.
The range type for a SList has a single pointer to the currently
iterated node. How do you remove that node without having access to the
head/previous pointer?
removeAfter ? ;) Hm though it does hit as strange. Looking at my code, I
usually keep previous node but only when I remove elements during iteration.
I suggested to Andrei having the range keep track of the *previous*
node/head, but he did not like that idea (too many dereferences for
front()). Another option is to have a removeAllButFirst method, but
that's kind of awkward...
And then using a sentinel as in Timon's idea doesn't look half bad.
Actually, it opens up a question of "Checked ranges" akin to "Checked
iterators" used in many STL implementations. Any ideas what they can
carry around as an "ID" of list? Root pointer won't cut it, as it can
be easily removed during iteration. If SList was a class it's
reference probably would do.
dcollections stipulates that all ranges/cursors can be verified in
O(lgn) time or better to belong to a specific container. In some cases,
this adds an extra word to the range/cursor, and in others, it's easy to
determine or the owner-reference was already needed. Since everything is
a class, the fallback is to just stick an owner class instance in the
range.
This stipulation is necessary to allow safe slicing.
Seems reasonable, I'd expect checks to go away in release, right(?).
--
Dmitry Olshansky
