We need to rethink remove in std.container

[Andrei Alexandrescu]

On 2/21/11 8:55 PM, Jonathan M Davis 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.

It's good that positioned remove does not work with findSplit. It would 
be inefficient to use the wonderfully structured tree for linear search. 
The algorithm should be simple - find the key to delete in O(log n), 
then remove it.

> So, what do I do? The _only_ thing that I can think of at the moment is to use
> find to locate the beginning of the range that I want, take the length of the
> range with walkLength and then use popBackN to pop of the elements I don't want.
[snip]

What we need to do is add to RedBlackTree a function that accepts the 
result of take() - the same way SList does. It has only recently dawned 
on me that certain generic ranges are pivotal to algorithms and 
containers, and so far I identified take() and takeExactly() to be two 
such important ranges.

One other thing that we can add to RedBlackTree is a simple removeKey() 
convenience method that does the find-and-remove thing. Any Phobos 
developer (including JMD of course :o)), please feel free to implement 
all of the above and submit it for pulling. And thanks Jonathan for 
using std.container - I am sure there are a few other wrinkles that will 
be revealed and then ironed out following consistent usage.


Andrei