On Mon, 21 Feb 2011 21:55:20 -0500, Jonathan M Davis <jmdavisp...@gmx.com>
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.
RedBlackTree supports the equalRange function, which gives you a range of
elements equal to the value you give.
If your RedBlackTree does not support duplicate elements, then this should
always be a 1 or zero element range, which you can then remove.
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.
take is supported as a range type for SList. It is not for RedBlackTree
because there are usually better ways to get ranges from the container.
However, I can see reasons that take could be used. For example, in a
RedBlackTree implementing a map, you may want to search for the first
element that has a particular value (O(n) complexity find). In that case,
you should be able to remove just one element. This should be added as a
bugzilla report, and I'll add the ability to do take ranges to the red
black tree. RBT is overdue for some improvements anyways (bearophile
found quite a few shortfalls with it).
But I see your point in that you should really be able to construct *any*
type of range and have it work.
I wonder if there is a way we could generalize "give me the
implementation-specific representation of the first item *reference*"
For example, in dcollections, we have the notion of cursors. The remove
functions take either a cursor or a range. However, I could possibly
extend the range removal function to allow any range type as long as the
begin() member gives you the correct cursor type.
-Steve
