std.container & ranges

[Dmitry Olshansky]

On 03.11.2011 21:13, Steven Schveighoffer wrote:
> 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?
>

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