On 2/21/11 8:55 PM, 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.
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.
It's good that positioned remove does not work with findSplit. It would
be inefficient to use the wonderfully structured tree for linear search.
The algorithm should be simple - find the key to delete in O(log n),
then remove it.
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.
[snip]
What we need to do is add to RedBlackTree a function that accepts the
result of take() - the same way SList does. It has only recently dawned
on me that certain generic ranges are pivotal to algorithms and
containers, and so far I identified take() and takeExactly() to be two
such important ranges.
One other thing that we can add to RedBlackTree is a simple removeKey()
convenience method that does the find-and-remove thing. Any Phobos
developer (including JMD of course :o)), please feel free to implement
all of the above and submit it for pulling. And thanks Jonathan for
using std.container - I am sure there are a few other wrinkles that will
be revealed and then ironed out following consistent usage.
Andrei
