We need to rethink remove in std.container

[Jonathan M Davis]

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.

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.

======
import std.algorithm, std.container, std.conv,
       std.range, std.stdio;

void main()
{
    auto rbt = RedBlackTree!int([0, 2, 5, 12, 59, 22]);
    assert(to!string(rbt[]) == "[0, 2, 5, 12, 22, 59]");

    auto found = find(rbt[], 5);
    assert(to!string(found) == "[5, 12, 22, 59]");

    popBackN(found, walkLength(found) - 1);
    assert(to!string(found) == "[5]");

    rbt.remove(found);
    assert(to!string(rbt[]) == "[0, 2, 12, 22, 59]");
}
======

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.

In particular, the fact that you can't take a range and create a new one of the 
same type from its first n elements is highly problematic. Maybe we need to add a 
function to ForwardRange which returns a new range with the first n elements (it 
certainly looks like that's the key element that's missing here). I don't know 
if that would be reasonable, but the fact that you can't create a range of the 
same type as the original range when taking just its first n elements seems 
crippling in this situation.

I don't know what the proper solution to this is, but the current situation 
strikes me as untenable. I had to think through this problem for a while before 
I came to a solution that came even close to working, let alone get one that 
actually works. Removing elements from a container should _not_ be this hard. 
The situation with remove _needs_ to be improved.

- Jonathan M Davis