On Iteration

[Steven Schveighoffer]

On Mon, 09 Nov 2009 20:53:01 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> I consider changing a bit D's range model following the better  
> understanding reflected in this article:
>
> http://erdani.com/publications/on-iteration.html
>
> If you have any thoughts and if you can help with the implementation,  
> please let us know.

Very good article.

I think the idea of separating access from traversal is a very good one.   
I still don't like the idea of having a "save" method vs. just assignment  
but I don't have a better idea right now.

One note:  As you know I think iterators are still useful for keeping  
pointers to individual elements.  One other drawback from storing  
1-element ranges as a substitute is that they may not remain one-element  
ranges.

For instance, if you had a sorted map, stored as a RB-tree, a one element  
range would undoubtedly consist of a begin element and an end element,  
which would be the next largest element.  If you inserted an element that  
was between those two, suddenly your 1-element range becomes a 2-element  
range.  Although you can simply say that all ranges are invalidated when  
the underlying container is modified, an iterator-based solution can say  
that iterators always remain valid when the container is added to.  That  
allows certain types of logic that wouldn't be as efficient with ranges.

What about adding a "marker" type that has the ability to reference the  
data but not to traverse to another element (except by assignment)?  
Basically a rebindable reference.  You can always get a marker to a  
copyable range's front element, and then a container can use 2 markers to  
make a traversable range, or use it as the primitive for functions like  
remove or insert (as an insert location), and 3-legged functions that  
don't map easily into 2-range functions.

I'm thinking this is how I'm going to implement ranges in dcollections.   
Currently I support cursors, which are akin to C++ iterators (my Iterator  
objects are akin to Java iterators, and support only foreach).  But what I  
might do is change them into markers, and make ranges out of 2 of them.

-Steve