foreach vs. iterators

Sean Kelly sean at f4.ca
Sat Nov 4 16:16:34 PST 2006


Oskar Linde wrote:
> Sean Kelly wrote:
> 
>>  From this it seems clear that foreach is not sufficiently adaptable 
>> to meet the needs of all sequential algorithms and opIndex is not a 
>> reasonable substitute for all cases where foreach may not be used.  
>> What alternatives do we have?  So far, iterator variants are all I've 
>> been able to come up with.
> 
> I agree, and I have been saying this countless times. :)
> 
> Why don't we come up with a standard iterator concept for D?
> For a forward iterator, C++ has:
> 
> *i
> i++ / ++i
> i != end
> 
> In the post "Iterators (Was: Re: Lazy eval -- an example issue)" in 
> digitalmars.D ( 
> news://news.digitalmars.com:119/ecmvec$ksl$1@digitaldaemon.com ) I 
> suggested a simple java-style variant:
> 
> *i.next()
> i.hasNext()

I think a Java style iterator is the way to go for D.  Personally, I 
basically never find a need for bidirectional iterators, and I only use 
random access iterators with vectors, which correspond to D's built-in 
dynamic arrays.  Also, a single iterator that knows when it's reached 
the end of the sequence better suits being used with foreach than the 
pointer-style iterators of C++.  About the only thing I don't like about 
Java iterators is how they work ;-)  Only being able to access the 
referenced data by calling next() is a bit irritating.  That said, it 
does eliminate the need for iterators to potentially cache the current 
value when iterating across sequences that don't inherently store data, 
such as an input stream.  Still, I think it's useful to have in an 
iterator, so perhaps something roughly like this:

interface Iterator(T)
{
     T val();
     T next();
     bool hasNext();
}

interface WriteIterator(T) : Iterator(T)
{
     T val( T n );
}

> A generic opApply could then be implemented as:
> 
> template opApplyMixin() {
>   int opApply(int delegate(inout ValueType v) dg) {
>     ValueType *t;
>     while(hasNext()) {
>       t = next();
>       if (auto status = dg(*t))
>         return status;
>     }
>     return 0;
>   }
> }
> 
> And a simple array iterator wrapper (Could of course be more efficiently 
> implemented):
> 
> struct ArrayForwardIterator(T) {
>   T[] arr;
>   alias T ValueType;
> 
>   T* next() { arr = arr[1..$]; return arr.ptr-1; }
>   bool hasNext() { return arr.length > 0; }
>   mixin opApplyMixin;
> }

Looks good.

> If pointers should be avoided, and since D doesn't have an opDeref, but 
> has lhs/rhs overloads for indexing, another iterator variant could be to 
> use
> 
> i[]
> i[]=
> 
> for rhs, and lhs iterator dereferencing.

I prefer the 'val' approach.  It seems a bit more meaningful than 
something with operators.

> i++ / ++i could be used instead of .next() if it is any clearer, and so 
> on...

I'm not sure how I feel about using structs for iterators (instead of 
classes).  With classes, we can retain some semblance of control over 
copy semantics, but we can't with structs.  And I'm not entirely sure I 
think we should be able to copy iterators at will--consider Walter's 
case of an iterator for a traditional binary tree, for example.  Also, 
using structs forces user code to either be hard-coded to work with a 
specific iterator type or to use templates.  And I'll admit I do sort of 
like the idea of:

     void myFunction( Iterator!(int) x ) {}

being possible.

> It doesn't really matter what convention we pick. For better rather than 
> worse, D doesn't allow us to do as C++ does, make iterators 
> interchangeable with pointers. We may as well pick anything we like as 
> long as the compiler is able to make reasonable efficient code out of it.

Agreed.

> As I said in the above referenced post, I have been toying with making a 
> template iterator/array algorithm library. I've got a quite substantial 
> proof of concept working, but have not had much time lately. I do love 
> discussions about this though. :)

I've been focusing on arrays thus far, but am getting to the point where 
I'd like to extend some algorithms to work for user-defined containers 
as well.  And that obviously requires a decent convention for how 
iterators should be implemented.  Also, I'll admit that I really enjoy 
algorithm talk as well :-)


Sean



More information about the Digitalmars-d-announce mailing list