std.container & ranges

[Steven Schveighoffer]

On Thu, 03 Nov 2011 13:47:28 -0400, Timon Gehr <timon.gehr at gmx.ch> wrote:

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

It does, actually.  A range is a reference to a Node struct.  But I still  
think the following approach will work.

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

This would be a good addition to the type.  It could not be a  
stableRemove, however, because it would invalidate any ranges pointing at  
the node you removed.  Can you put together a pull request?  If not, I can  
see about doing it.  One issue, you could not do this if the value is  
immutable/const.

I could use this idea, I think, to implement a singly linked list in  
dcollections as well (the prospect of not having O(1) removal is what has  
stopped me).  Thanks for the idea!

-Steve