We need to rethink remove in std.container

[Steven Schveighoffer]

On Tue, 22 Feb 2011 03:43:25 -0500, Denis Koroskin <2korden at gmail.com>  
wrote:

>
> I believe remove operation is better expressed in terms of a Cursor  
> (iterator in C++). It also doesn't make much sense (at least of me) for  
> a find to return a subrange of the source range. While it does  
> generalize well, it's not really what most people expect.
>
> What I'd love to have instead is something like this:
>
> int[] arr = [1, 2, 3, 4, 5];
> auto cursor = arr.find(3); // either points to 3 or null
>
> int[] before = arr[0..cursor];
> int value = arr[cursor]; // for consistency, C++ uses *cursor
> int[] after = arr[arr.advance(cursor)..$];

This is exactly how dcollections works.

> Note that typeof(cursor) could/should actually be int*, but I don't use  
> arr[cursor+1..$] because cursor doesn't know about range bounds, and as  
> such it can't advance on it's own.

Here is how dcollections solves this.

A cursor in dcollections is actually a zero or one element range.  It can  
only reference exactly one element.  Since it has no references to other  
elements, it is immune to operations that use the surrounding elements.   
In contrast, a red black tree range contains references to the begin and  
the end node.  This means operations on these nodes (i.e. removing the end  
node, or inserting an element between the two) can affect the range.

So essentially, your code would look like this in dcollections:

auto arr = new ArrayList!int(1,2,3,4,5);

auto cursor = arr.find(3);

int[] before = arr[0..cursor];
int value = arr[cursor];
cursor.popFront();
int[] after = arr[cursor..arr.end]; // note, $ overrides don't currently  
work, so we can't get the sugar here...

> I think it's also worth noting that "find" for trees makes even less  
> sense (to me). You can't "slice" a tree arbitrarily, yet find tries to  
> do that:
>
>>     auto rbt = RedBlackTree!int([0, 2, 5, 12, 59, 22]);
>>     assert(to!string(rbt[]) == "[0, 2, 5, 12, 22, 59]");
>>
>>     auto found = find(rbt[], 5);
>>     assert(to!string(found) == "[5, 12, 22, 59]");
>
> What is the type of "found"? It's clearly not a tree anymore. Don't know  
> why, but it's still a range. How is it implemented? Without looking at  
> the source I can tell it's implemented as an original tree + a cursor.  
> And I believe the two are better be separated.

Actually, find is probably not the correct thing to use for this.  Use  
upperBound (or lowerBound, I can never remember which one does what) to  
get all the elements >= 5.

The range is not a tree, and this is intentional.  Containers are *not*  
ranges.  Think of a range as a 'view' into a container, but not a  
container itself.  You can't add/remove elements from the tree using a  
range, you can just traverse it.  If it helps, think of the range as a  
pair of iterators.

-Steve