std.container & ranges

[Steven Schveighoffer]

On Thu, 03 Nov 2011 12:32:06 -0400, Christophe  
<travert at phare.normalesup.org> wrote:

> "Steven Schveighoffer" , dans le message (digitalmars.D.learn:30402), a
>> The primitive for a container is remove(range).  Ranges are essential to
>> containers, and should be the major interface to them.
>
> Programmers have to learn ranges to use containers. Hiding ranges is not
> helping them.
>
> But here, it is more complicated than that, because range may be more
> powerful than iterators, they are less friendly to use when a single
> element reference has to be used.
>
> c.remove(find(c.all, E));
>
> will not remove the first occurence of E, but all elements beyond E.
> so instead we have to write:
>
> c.remove(take(find(c[], E), 1));
>
> Then it's too much.
>
> The problem is that range are not practical to refer to a single element
> in the container. We need to have single-element reference to manipulate
> the range. Then a function should be used to find such one-element
> reference. std.find is already taken, and can hardly be changed
> (although it should be name popUntil), but we can still use a find
> method of the container.
>
> auto r = take(find(c[], E), 1);
>
> should just be written:
>
> auto r = c.find(E);
>
> Then the syntax to remove a single element from c is acceptable:
> c.remove(c.find(E)).
>
> Now let us remove several consecutive elements from c, let us say, all
> elements between the value E and the next value F:
>
> | auto r = find(c[], E);
> | int i=0;
> | foreach(e, r)
> |   if (e == F) break;
> |   else ++i;
> | c.remove(take(r, i+1));
>
> That is not practical at all, and in addition, it is not efficient,
> since r is walked again from E to F.
>
> If we add little methods to single element reference to make them behave
> a little like iterators, we can recreate ranges from two single element
> references, and regain all the power of iterators. To remove all
> elements from E to the next F included:
>
> auto r = c.find( E);
> c.remove(r, r.find(F)++);
> // or c.remove(range(r, r.find(F)++));
>
> (I use the find method a bit like a joker in this exemple, it is just
> to get the idea).
>
> In conclusion, to refer to a single element of a container for simple
> operations, range looses against iterator. Ranges even loose to refer to
> a range of consecutive elements...
> Many alternatives are possible, but a simple iterator structure to refer
> to a single element, and that you can combine to recreate a range (and
> use all range algorithms) would be enough, and would complete the range
> interface to make them have no drawback against iterators.

Preaching to the choir sir :)

http://www.dsource.org/projects/dcollections/browser/branches/d2/concepts.txt

If you can convince Andrei that cursors are a good addition to  
std.container, you have my admiration.  I've tried and failed quite a few  
times.

To illustrate syntax:

auto cursor = c.elemAt(E);
c.remove(c[cursor..c.end]); // note, $ could be used here, but opDollar is  
broken.

Note, this only works if c supports elemAt.  For example, TreeSet supports  
this, LinkList does not.  But dcollections supports even other slicing  
abilities.  For example TreeSet can do this too:

c.remove(c[E..F]);

If you have a container that doesn't support elemAt, you can use  
std.algorithm.find, and the dcollections' range.begin method to get a  
valid cursor:

auto cursor = find(c[], E).begin;

I realize this isn't much better than take(find(c[], E), 1), but I don't  
know if you realize what a task/chore it would be to create a simple  
shortcut in a class for std.algorithm.find.

-Steve