std.container & ranges

[Steven Schveighoffer]

On Thu, 03 Nov 2011 14:50:31 -0400, Timon Gehr <timon.gehr at gmx.ch> wrote:

> On 11/03/2011 07:15 PM, Steven Schveighoffer wrote:
>> 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?
>
> I can do that, but it will have to wait a few days, as I am quite busy  
> at the moment.

No rush.  I just wanted to know if you would do it, and if not, I would do  
it.

>
>> If not, I
>> can see about doing it. One issue, you could not do this if the value is
>> immutable/const.
>
> That is true. But how to fix this? Resolving it by simply not exposing  
> the remove method if it is impossible to implement the straightforward  
> way would be an option, but I don't think that is satisfying. Probably  
> it could be made to work by creating some kind of head mutable  
> structure. I will think about it. It should even be possible to  
> generalize std.typecons.Rebindable for structs to help this idea.

Hm... rebindable doesn't help if the item is a struct.  You'd have to  
store an allocated struct on the heap.

-Steve