Iterators for D

Bill Baxter wbaxter at gmail.com
Mon Nov 6 13:21:07 PST 2006


Walter Bright wrote:
> It's becoming increasingly obvious that D needs iterators. While opApply 
>  is far better for some kinds of iteration (such as recursively 
> traversing a directory), iterators are more efficient in some cases, and 
> allow for things that opApply makes difficult.
> 
> So hear are the design goals:
> 
> 1) Works with dynamic and stat arrays

How about pointers (unknown length arrays)?
   int *some_numbers;

Is it required that a pointer be a valid iterator?
I.e. should it be possible to have this template function:

    print_all(some_numbers, some_numbers+theLength);

Or will that case require a wrapper object that contains theLength?

    auto iter = PointerIterator(some_numbers, theLength);
    print_all(iter);

> 2) Doesn't need to work with associative arrays

Why not?  Do you mean it doesn't need to because you can just iterate 
over keys or values?

> 3) Should be possible to achieve "pointer efficiency" with it
> 4) Needs to be able to restrict lvalue access (what C++ does with const 
> iterators)
> 5) Needs to work seamlessly with foreach
> 6) Iterators need to be copyable

> So here's one design:
> 
> .being property returns an iterator that starts at the beginning
> 
> .end returns an iterator that is at the end

That's like C++'s way.  Iterator is basically a generalized pointer.
The other proposal is more like Java/Python/C#'s way, where the iterator 
  is like a pointer that knows it's own limits.
The Java/Python/C# way would definitely work in D.   I'm not sure about 
the C++ way working for D because, in practice, references and 
dereferencing get used pretty heavily there.  On the other hand 
Java/Python/C# were designed without real templates.

One of the major design goals for C++ was that for a basic array a 
regular pointer should be a valid iterator.  Thus the iterator cannot 
know where it's own end() is, because a pointer does not have such 
knowledge.  But aside from cute demos on SGI's STL web page where 
algorithms are applied to plain arrays using pointers,  I've never seen 
that sort of thing used in the real world.  You almost always use a 
std::vector or std::list or something besides a raw array.  So pointer 
equivalence seems to be pretty useless to me.  Even moreso with D.  In 
the rare case you need to work with raw pointers, you can always make an 
iterator wrapper.

On the plus side for C++ style:
* iterators are lightweight (just one size_t/pointer in most cases)
* algorithms and methods all take begin/end pairs making things uniform.
Minuses
* Iterators are dumb and error prone and easily go out of bounds
* algorithms all require begin/end pairs making things cumbersome

I think the minuses outweigh the plusses.
But maybe it's useful to take one concrete example:  A generic mergesort 
or quicksort algorithm.

In C++ recursive calls just pass the limits of the range to the children
mergesort(begin, end)
{
     ...
     mergesort(begin, (end-begin)/2);
     mergesort((end-begin)/2, end);
}
It's very efficient.

In the iterator-is-object approach I'm not sure how that works.
If all you've got is .next() or .hasNext() I'm not sure what you're 
supposed to do to create an iterator over half the range represented by 
the original iterator.


> foreach loops will not be able to have a 'key' parameter.

Don't understand that one.


--bb



More information about the Digitalmars-d mailing list