We need to rethink remove in std.container

[Jonathan M Davis]

On Monday 21 February 2011 21:04:47 %u wrote:
> > 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'm wondering, what was the reason for making a "remove range X from
> Y" method in the first place? To me, that's not a "remove"
> operation; if anything, it's the "removeAll" operation, but I'd
> actually call it "subtract" (because it's the set subtraction
> operation... although there can be duplicates).
> 
> If we change remove to only take in a single element, wouldn't its
> implementation then be trivial? (For a range, just return a filter
> that removes the element. For a container, actually remove the
> element. For ranges that also behave like containers -- like arrays
> -- I have no idea.)
> 
> Does this sound like a good idea?

Removing a range is not necessarily related to removing an element with a 
particular value. Sure, a method could be added to the various container types 
which takes a value and removes the first instance of that value from the 
container, but that's not what remove is necessarily trying to do. It's like 
erase in C++'s standard library which takes two iterators. There are plenty of 
situations where removing a range makes sense. The odd bit with remove in Phobos 
vs erase in the STL is that with iterators, you can give a single iterator to 
indicate a single element whereas you can't do that with a range. So, remove 
takes a range, and if you want to remove a single element, that range only has 
one element in it. It's a bit weird, but that's fine.

The typical way to remove an element in the STL is to use find to find an element 
and then erase to remove it. remove in std.container is doing the same thing. 
The problem is that you can't give the result of find to remove, because instead 
of a single iterator, find gives you a whole range, and you probably don't want 
to remove that whole range. You generally either want to remove the first element 
or some set of elements at the front of the range. So, you need to able to 
remove the other elements from the range so that you can give that range to the 
remove method on the container. That's fine in principle, but since so many of 
the range-based algorithms give you a new type back and you need the exact type 
that that container uses for its ranges, it's very hard to get a range of the 
correct type with the correct elements in it.

So, while find will give you the beginning of the range you want, there's not an 
easy way to remove the end of that range. Functions like take and takeExactly 
return new types, so they don't work. The more I look at it, the more I'm 
convinced that we really need to add a primitive to forward ranges that returns 
the first n elements of that range. Without that, I don't see how you can get a 
range of the correct type with only those elements in it unless it's also a 
bidirectional range, which some ranges (like SList's range) aren't.

- Jonathan M Davis