std.container & ranges

[Dmitry Olshansky]

On 03.11.2011 19:34, Steven Schveighoffer wrote:
> On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath
> <tobias at 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