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
2) Doesn't need to work with associative arrays
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

Overloading * doesn't work with D. But, instead:

Overload opIndex for rvalue access
Overload opIndexAssign for lvalue access

Overloading opIndex also will work for random access

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

Walter Bright wrote:
> .being property returns an iterator that starts at the beginning

Make that .begin

Also, overloading += will be used to advance the iterator.

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
> 2) Doesn't need to work with associative arrays
> 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
> 
> Overloading * doesn't work with D. But, instead:
> 
> Overload opIndex for rvalue access
> Overload opIndexAssign for lvalue access
> 
> Overloading opIndex also will work for random access
> 
> foreach loops will not be able to have a 'key' parameter.

Would this mechanism work for, say, arrays of structs (not struct*[] 's) so that we could avoid the overhead of either a) copying the struct and/or b) the extra level of indirection in the loop? (In other words, could the iterator provide a reference to each element by default).

Thanks,

- Dave

Dave wrote:
> 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
>> 2) Doesn't need to work with associative arrays
>> 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
>>
>> Overloading * doesn't work with D. But, instead:
>>
>> Overload opIndex for rvalue access
>> Overload opIndexAssign for lvalue access
>>
>> Overloading opIndex also will work for random access
>>
>> foreach loops will not be able to have a 'key' parameter.
> 
> Would this mechanism work for, say, arrays of structs (not struct*[] 's) so that we could avoid the overhead of either a) copying the struct and/or b) the extra level of indirection in the loop? (In other words, could the iterator provide a reference to each element by default).
> 
> Thanks,
> 
> - Dave

I should add - will native arrays of structs (say) provide this by default w/o having to add specialized operators?

Thanks.

Walter Bright wrote:
> Overload opIndex for rvalue access
> Overload opIndexAssign for lvalue access

Could you elaborate on how this would look like ? E.g. a usage example of iterators with the proposed design.


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

What's the particular reason for that restriction ?


--
Tomasz Stachowiak

Walter Bright wrote:
> Walter Bright wrote:
>> .being property returns an iterator that starts at the beginning
> 
> Make that .begin
> 
> Also, overloading += will be used to advance the iterator.

that would give something like this?

import std.stdio;

void main()
{
	char[] s = "hello";
	// += for advancing an iterator, why not ++?
	for (iterator i = s.begin; i != s.end; i += 1)
		writefln(s[i]);

	// ??? i is an iterator or a char  ???
	foreach(i; s)
		// extend writefln to take iterators ?
		// but that would mean that it must be possible
		// to determine a value from an iterator
		writefln(i);
}

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
> 2) Doesn't need to work with associative arrays
> 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

Is it worth discussing whether the pointer-style C++ iterators are the best approach?  They certainly are if random access iterators are a requirement, but if we're just implementing forward and reverse iterators, the all-in-one Java approach may be better.  In that vein, I  assume alose that reverse iteration would work with reverse iterators and an .rbegin type method instead of .begin and foreach_reverse?


Sean

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

rm wrote:
> Walter Bright wrote:
>> Walter Bright wrote:
>>> .being property returns an iterator that starts at the beginning
>>
>> Make that .begin
>>
>> Also, overloading += will be used to advance the iterator.
> 
> that would give something like this?
> 
> import std.stdio;
> 
> void main()
> {
>     char[] s = "hello";
>     // += for advancing an iterator, why not ++?
>     for (iterator i = s.begin; i != s.end; i += 1)
>         writefln(s[i]);

Oh right, that's what doesn't seem to work with the C++ model--such an iterator wouldn't work in foreach:

    foreach( e; s.begin() ) // nowhere to supply s.end()

I think the Java style may be more appropriate:

    foreach( e; s.fwdIter() )
    foreach( e; s.revIter() )


Sean

> I think the Java style may be more appropriate:
> 
>     foreach( e; s.fwdIter() )
>     foreach( e; s.revIter() )
> 

I didn't read the discussion, but wasn't there a topic about foreach_reverse? Should that not cover s.revIter()?

Secondly, why must one give in the foreach statement the first iterator?
I'd say that there the iterable must be given?

roel