On Tuesday 22 February 2011 05:01:24 Andrei Alexandrescu wrote: > 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.
I've made several improvements to RedBlackTree and created a pull request for them: https://github.com/D-Programming-Language/phobos/pull/10 - Jonathan M Davis