On Iteration
Steven Schveighoffer
schveiguy at yahoo.com
Tue Nov 10 04:28:22 PST 2009
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
More information about the Digitalmars-d-announce
mailing list