std.container & ranges

[Timon Gehr]

On 11/03/2011 06:13 PM, 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?
>

The container interface does not expose references to the 'Node' struct, 
therefore the following approach would be practical:

0. Have a sentinel for end of list. (O(1) additional memory for the 
entire list). It is the only node in the list that has a null 'next' 
pointer.

example, for removing just the current node:
1. if the following node is not the sentinel
1.1. Move value from following node into the current node.
1.2. Remove following node.
2. if the following node is the sentinel
2.1. erase the contents of the current node (iff it has indirections)
2.2. set it's 'next' field to null


Removing an entire range is just erasing the contents of the current 
node and setting the 'next' field of the associated Node to zero. 
Removing a Take!Range is a simple generalization of the algorithm above.