We need to rethink remove in std.container

[Steven Schveighoffer]

On Mon, 21 Feb 2011 21:55:20 -0500, Jonathan M Davis <jmdavisProg at gmx.com>  
wrote:

> Okay, removing elements from a container sucks right now. You can do  
> stuff like
> removeAny (generally pretty useless IMHO) or removeFront just fine, but  
> removing
> an arbitrary range from a container just plain sucks.
>
> remove takes a range type which is the range type for the container that  
> it's
> on. That makes sense. It's obviously not going to be able to a take an  
> arbitrary
> range and remove that from itself. How would it know which elements in  
> that
> range corresponded to which elements in itself - especially when it  
> could be a
> range which skips elements or something similar? So, _that_ part makes  
> sense.
>
> But have you actually tried to get a range of the appropriate type to  
> remove
> from a container? It seems like almost ever function in std.range and
> std.algorithm returns a new range type, making them completely useless  
> for
> processing a range to be removed from a container.
>
> I was looking to remove a single element for a RedBlackTree. The best  
> function
> that I could think to get the proper range was findSplit. The middle  
> portion of
> the return value would be the portion that I was looking for. I'd take  
> that and
> pass it to RedBlackTree's remove. Wrong. It uses takeExactly in its
> implementation and the first two portions of the result of findSplit  
> aren't the
> right range type.

RedBlackTree supports the equalRange function, which gives you a range of  
elements equal to the value you give.

If your RedBlackTree does not support duplicate elements, then this should  
always be a 1 or zero element range, which you can then remove.

> That's disgusting. All that just to remove one element? And what if the  
> range
> isn't bidirectional (e.g. SList)? Well, then you have no popBack, and as  
> far as
> I can tell, you're screwed, since you can't use either take or  
> takeExactly,
> because both of them return new range types.

take is supported as a range type for SList.  It is not for RedBlackTree  
because there are usually better ways to get ranges from the container.   
However, I can see reasons that take could be used.  For example, in a  
RedBlackTree implementing a map, you may want to search for the first  
element that has a particular value (O(n) complexity find).  In that case,  
you should be able to remove just one element.  This should be added as a  
bugzilla report, and I'll add the ability to do take ranges to the red  
black tree.  RBT is overdue for some improvements anyways (bearophile  
found quite a few shortfalls with it).

But I see your point in that you should really be able to construct *any*  
type of range and have it work.

I wonder if there is a way we could generalize "give me the  
implementation-specific representation of the first item *reference*"

For example, in dcollections, we have the notion of cursors.  The remove  
functions take either a cursor or a range.  However, I could possibly  
extend the range removal function to allow any range type as long as the  
begin() member gives you the correct cursor type.

-Steve