std.container & ranges

[Steven Schveighoffer]

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

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

Yes, this looks like a viable solution.  Not sure how it would be done in  
a generic way.  I think what is best is to have getS be like this:

S *getS(){ return cast(S*)&this;}

And never provide access to this

As long as S.opCmp, S.opEquals, and S.toHash are all const, this should be  
no issue (this needs to be a requirement).

I wonder if we really have to go through such trouble...

-Steve