std.container & ranges

[Timon Gehr]

On 11/03/2011 09:46 PM, Steven Schveighoffer wrote:
> 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

My point is, if you have a struct like this:

struct S{
     const int* x;
     immutable int y;
}

Then that could be stored in the list as

struct _S{
     const(int)* x;
     int y;

     S getS(){return S(x,y);}
}

Without putting the type system under pressure.
But on second thought, std.typecons.Rebindable can probably not 
meaningfully be generalized to structs because it could not deal with 
member functions.