We need to rethink remove in std.container

[Steven Schveighoffer]

On Wed, 23 Feb 2011 12:16:26 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> On 2/23/11 8:51 AM, Steven Schveighoffer wrote:
>>
>> I don't think this is possible. When passing a range to a container for
>> removal, the container needs to access the underlying implementation
>> (e.g. pointer to tree node) in order to immediately know what element is
>> being removed. The takeOne range you propose does not allow this, you
>> can't get at the underlying range.
>
> I agree that takeOne's source should be made public.

But what about takeOne(retro(myrange))?  If support for that was desired,  
one would need to do it explicitly.  As each new wrapper type is desired,  
one needs to add support for the specific configuration of wrappers.

>> Even if you could, only
>> takeOne!(myrangetype) would work, which leaves us right back at
>> supporting a small number of specific ranges.
>
> That's arguably correct and in any case better than supporting a range  
> plus a distinct cursor abstraction. You remove the cursor abstraction  
> and replace it with a specific realization of the range abstraction.

At the end of the day, a container needs a cursor (or something like it)  
in order to remove an element.  The cursor is the gateway between the safe  
range abstraction, and the unsafe internal representation (with nasty  
pointers).

In reality, supporting cursors and ranges vs. takeOne and ranges only  
differs in that you need to add a cursor type.  The number of functions  
required remains the same (the cursor handling functions replace the  
takeOne handling functions).

> Soon as we get to begin() and end() as primitives it all starts being  
> problematic. We may as well design with STL-style iterators then. One  
> good thing about ranges is that they _don't_ need to rely on lower-level  
> primitives.

Ranges for containers necessarily need to rely on lower level primitives  
as I stated above.  A cursor gives a safe abstraction of such a primitive.

Example, An SList range:


     struct Range
     {
         private Node * _head; // <------ this is the primitive
         private this(Node * p) { _head = p; }
         /// Forward range primitives.
         bool empty() const { return !_head; }
         /// ditto
         @property Range save() { return this; }
         /// ditto
         @property T front() { return _head._payload; }
         /// ditto
         @property void front(T value)
         {
             enforce(_head);
             _head._payload = value;
         }
         ...

Note that the range *hides* the unsafe primitive.  But so does a cursor.   
Essentially, a cursor is a way to refer to one of those primitives.   
Seeing as how the implementation needs to use one of those primitives,  
being able to pass around a safe version of that primitive is very  
advantageous.  Requiring passing around a range of them is problematic for  
many functions.

>> In addition, dcollections (and any collection that can verify its
>> endpoints and cursor membership, SList obviously cannot) allows slicing
>> based on cursors in a limited fashion. Therefore, this allows
>> constructing ranges from cursors if you have the original container.
>>
>> As an example of what this could allow (assuming retro and take forward
>> the begin(), end() and last() methods):
>>
>> container.remove(take(retro(container[]), 5)); // remove the last 5
>> elements from the container.
>
> I understand and I see the advantages. Still I believe that the  
> disadvantages of dealing with cursors overcome this potential  
> flexibility. I'd be more inclined to look for a design for which ranges  
> suffice for iteration.

Then I think we shall keep things the way they are.  Cursors are  
absolutely necessary in my model of collections, and to get rid of them  
would abandon the most fundamental reason I created dcollections.

-Steve