We need to rethink remove in std.container

[Jonathan M Davis]

On Tuesday 22 February 2011 01:04:48 Lutger Blijdestijn wrote:
> 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.
> 
> I don't understand why not. Given, as you said, that a lot of functions
> return a new type it would make sense. My answer as to how would be
> something like:
> 
> while range not empty
>     container.remove range.front
>     range.popFront
> 
> Is there a problem with that?

It's horribly inefficient for one. Also, I'm not sure that the range is valid any 
more after the remove, since it's front was removed. popFront may not work 
correctly.

> > 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.
> > 
> > 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. e.g.
> 
> The table in the docs mention stableRemoveAny(v) which says "Same as
> c.removeAny(v), but is guaranteed to not invalidate any iterators."
> 
> Though c.removeAny(v) itself is not listed in the table nor implemented in
> RedBlackTree, isn't this the right function for the job? (I take it v
> stands for a value of the container, rather than a range). builtin aa's
> also implement this function.

removeAny doesn't solve the problem. For starters, the table appears to be wrong 
in that stableRemoveAny takes a value and removeAny doesn't. So, either 
stableRemoveAny is supposed to not take a value or there's supposed to be 
another version of removeAny which takes a value, and it's missing. So, I don't 
know what exactly is intended with stableRemoveAny.

Regardless of that, however, remove still needs to work. It's perfectly valid to 
want to remove a range of elements rather than just one.

- Jonathan M Davis