We need to rethink remove in std.container

[Jonathan M Davis]

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