We need to rethink remove in std.container

[Lutger Blijdestijn]

Jonathan M Davis wrote:

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

It's a matter of range (in)validation right? I admit at this point I'm not 
sure how it is supposed to work. remove + popFront is a bad idea if the 
range is a view into the contained from where stuff is removed, but in c++ 
this works for map: some_map.erase(i++) where i is an iterator. So it 
depends on the type of container what is supported I think. But perhaps this 
falls under Walter's category of useless wankery, since it is easy to write 
yourself.

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

(stable)removeAny does not solve the problem of removing ranges, but there 
must be *something* that solves the problem of removing one element. You 
found one way to do it for RedBlackTree (i gave up), but if I am not 
mistaken it doesn't have the right complexity and efficient removal is a key 
property of this container.