Iterators for D

[Bill Baxter]

Walter Bright wrote:
> Bill Baxter 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
>>
>> 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);
> 
> It's simpler than that. Pointers can be converted to arrays:
>     auto array = some_numbers[0 .. theLength];
> and then you can get the iterator.

Nice!  Didn't know you could do that.


> I think the C++ like way will be a lot more efficient, and I think it 
> will work. Reference types are not needed.

The C++ way really embodies two design choices:
1) iterators are defined by 'concept'
    --> Means generic iteration functions all need to be templates
    --> The other alternative is define them by interfaces.
        --> these two aren't necessarily mutually exclusive though
2) an iterator is a pointer -- begin() and end() are kept separate.
    --> The other alternative is 'an iterator is a range'

Definitely 1) will be more efficient than using interfaces,
but I don't thing pointer semantics, 2), are required for 1) to work.

It may be possible for D iterators to have the speed of C++ while having 
the convenience and safety of Java's iterators that know their bounds.

>> 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.
> 
> Iterators can be any type, not just objects, that support [], ++, +=, 
> and =.

I think the iterator-as-range idea is at least worth discussing.  99% of 
the time you use an iterator you also need to know where to stop.  It's 
pretty similar to how arrays in D keep a length, because 99% of the time 
when you have an array you need to know how long it is too.  So it makes 
sense to keep those two bits of information together.  Similarly in C++, 
when you have an iterator, you almost always need the end() too.  And 
any time you want to pass around iterators you end up having to pass the 
two bits of information around separately.

--bb