std.container & ranges

[Steven Schveighoffer]

On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky  
<dmitry.olsh at gmail.com> wrote:

> 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.

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?

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...

> 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.

-Steve