We need to rethink remove in std.container

[Jonathan M Davis]

On Tuesday, February 22, 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.

Well, if RedBlackTree's remove gets changed to take the return values from take 
and takeExactly as you suggest below, then it _will_ work. Regardless, I don't 
think that findSplit is the best choice for this situation. It's just the best 
that I could think of given that take and takeExactly didn't work. I was then 
frustrated to discover that findSplit used takeExactly (though thinking about it 
now, given how forward ranges work, it's not like it could really do otherwise). 
removeKey is really what RedBlackTree needs for the most part, however. Removing 
a range from a RedBlackTree definitely makes sense in some cases, but usually 
you're looking to remove a particular element or set of elements which aren't 
necessarily in any specific order or adjacent in the tree (which implies that 
perhaps we need a removeKey(s) which takes a range of values - though not 
necessarily a range from RedBlackTree).

> > 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.

In this case, it probably makes sense to let Steve take care of it, since he's 
already working on it, though I may just add removeKey and submit a pull request 
which Steven can deal with as he sees appropriate, so that I can use it for what 
I'm doing.

However, having found a fundamental flaw in how remove currently works with 
RedBlackTree, I thought it best to discuss how to solve the problem before 
making any changes to it anyway. Regardless, RedBlackTree is the container that 
I've been most missing in what I've been doing in D, so I'll definitely be using 
it in code now that I have it.

By the way, are we looking at changing the containers to be classes by the next 
release (since, as I recall, you decided that we're definitely making that 
change)? That's one change that RedBlackTree could definitely benefit from (since 
you have to run one of its destructors for it to be set up correctly and it 
can't have a default constructor as a struct), and it's probably the sort of 
change that we should make sooner rather than later, since the longer that the 
types in std.container are structs, the more code it will break when they become 
classes.

- Jonathan M Davis