We need to rethink remove in std.container

[Andrei Alexandrescu]

On 2/23/11 8:51 AM, Steven Schveighoffer wrote:
> On Wed, 23 Feb 2011 08:33:03 -0500, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org> wrote:
>
>> On 2/22/11 8:41 AM, Steven Schveighoffer wrote:
>>> On Tue, 22 Feb 2011 09:23:00 -0500, Andrei Alexandrescu
>>> <SeeWebsiteForEmail at erdani.org> wrote:
>
>>>> 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.
>>
>> Absolutely, and your collaboration on e.g. RedBlackTree and others is
>> very much appreciated.
>>
>> The way I was thinking is, there would a lot of convergence if
>> dcollections wiped the notion of "cursor" and replaced it with takeOne
>> throughout. One obvious objection to the range/cursor design is there
>> are two abstractions to deal with instead of one. I had the intuition
>> that ranges should be enough, but was not quite able to substantiate
>> it fully until just about now. With take, takeExactly, and takeOne, it
>> seems that indeed there is only need for the range interface, and that
>> particular range types can replace cursors.
>
> 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.

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

> In addition, a cursor points to one element, a range points to multiple
> elements. *conceptually* takeOne is the same, but it still stores the
> range internally, so it's actually more expensive than a range to pass
> around (additional _empty member).

I agree. There are a number of ways around this if important, but I need 
first to be clear of the projected uses of takeOne.

> I was thinking more along the lines of ranges being able to generate
> cursors if it makes sense (i.e. base range is a range of the container).
> Dcollections already supports this with the two accessors begin() and
> end(). We might also need a last() which gets the last valid element in
> the range. This would be akin to back().
>
> Here is what I was thinking that can help with unifying interface. I'll
> just show you as a code snippet:
>
> void remove(C)(C c) if (is(C == mycursortype))
> {
> // since we know the structure of c, we can use it to remove the element
> from the container
> }
>
> void remove(R)(R r) if (is(R == myrangetype))
> {
> // possibly can be optimized
> }
>
> void remove(R)(R r) if (!is(R == myrangetype) && isInputRange!R &&
> is(typeof(r.begin) == mycursortype))
> {
> while(!r.empty)
> {
> auto c = r.begin;
> r.popFront();
> remove(c);
> }
> }
>
> If wrapper ranges can "forward" the begin and end functions through
> their API, then you can construct arbitrary ranges that will be accepted
> as parameters to remove. We could potentially add forwarding functions
> to all wrapper ranges, or we could pick ones that make the most sense
> (like take).

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.

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


Andrei