We need to rethink remove in std.container

[Steven Schveighoffer]

On Tue, 22 Feb 2011 09:23:00 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> On 2/22/11 7:58 AM, Steven Schveighoffer wrote:
>> A cursor in dcollections is actually a zero or one element range. It can
>> only reference exactly one element. Since it has no references to other
>> elements, it is immune to operations that use the surrounding elements.
>
> At this exact point I had what would be either a good idea or a  
> brainfart.
>
> I've been thinking for a good while to define a "singleton range", a  
> range that has at most one element. I had the intuition that a singleton  
> range is a useful concept, but I felt it was a bit tenuous to argue in  
> its favor (mostly because one could easily simulate it with repeat(x,  
> 1)), so I never put it in std.range.
>
> The definition would go like this:
>
> auto singletonRange(T)(T element)
> {
>      static struct Result
>      {
>          private T _element;
>          private bool _done;
>          @property bool empty() { return _done; }
>          @property auto front() { assert(!empty); return _element; }
>          void popFront() { assert(!empty); _done = true; }
>          auto save() { return this; }
>      }
>
>      return Result(element, false);
> }

This is almost the same as a dcollections cursor.  The only difference is,  
popFront in a cursor not only sets the '_done' member, but also moves to  
the next element.  This distinction is necessary with node-based  
containers that have an end marker node.  So the cursor that is returned  
 from 'end()' (or from find where the element was not found, etc.) is an  
already-empty cursor.

I hadn't thought of just setting the empty variable, but I think it  
wouldn't work properly.  You could possibly say "a cursor that points to  
an element but is empty is actually pointing *after* the element."  But  
then I'm not sure how to construct an end cursor.  It's advantageous to  
point at the end of a container, where there is no true node to point at.   
Is there another way to think about this?

> But now I realized that singleton ranges are your cursors, so I'll  
> definitely add them. And you also made me realize that a singleton range  
> is very different from other ranges in the same way 1 is different from  
> other numbers. Great.

Yes, that distinction is really important, I'm glad you see that!

> This may as well be The Great Unification that was needed to converge  
> std.container with dcollections in a harmonious whole.

I'm not sure what to think of this ;)  Is this a "oh what could have been"  
statement or a "let's reopen negotiations" statement?

Note, I would love for dcollections to be mainstream Phobos, but I have  
accepted the current reality and am fine with the way things are now too.

-Steve