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.
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.
* I think I'll scrap together a pull request to address both these
issues though.
--
Dmitry Olshansky
