We need to rethink remove in std.container

[Steven Schveighoffer]

On Tue, 22 Feb 2011 08:01:24 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> 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.

This should be possible with equalRange.

However, there can be needs to do a linear search on a RBT if you are not  
searching for keys.  I think we definitely need take as a supported range  
in RBT (I didn't think so originally).

>
>> 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 should be able to complete these improvements before the next release  
(excluding any quick-fix releases).  Still need to learn git though...

-Steve