Iterators for D

[Bill Baxter]

Walter Bright wrote:
> Mike Capp wrote:
>>> Overload opIndex for rvalue access
>>> [...]
>>> Overloading opIndex also will work for random access
>>
>> Wouldn't this make iterators incompatible with e.g. linked lists? 
>> Seems to defeat
>> much of the purpose.
> 
> To work, all it has to do is support [0], and throw an exception if the 
> index is anything but 0.
> 
>> (It might be possible to implement random access for a list, but it's not
>> something you'd want to encourage.)
> 
> I agree.

This is one point where there's a huge divide between C++ iterators and 
Java iterators.

In C++ there is no such thing as *the* iterator type or interface.  What 
C++ (or STL, rather) has is collection of *iterator concepts*.  What 
that means is that if opIndex doesn't make sense for the the collection 
in question, you just leave it out.  A 'concept' is like an interface 
but for templates.  Here are the concepts in the STL:

Trivial Iterator - http://www.sgi.com/tech/stl/trivial.html
Input Iterator - http://www.sgi.com/tech/stl/InputIterator.html
Output Iterator - http://www.sgi.com/tech/stl/OutputIterator.html
Forward Iterator - http://www.sgi.com/tech/stl/ForwardIterator.html
Bidirectional Iterator - 
http://www.sgi.com/tech/stl/BidirectionalIterator.html
Random Access Iterator
http://www.sgi.com/tech/stl/RandomAccessIterator.html

If you want your container to support forward iteration, then your 
iterator can be of any type you wish, but it must support x++, ++x, and 
*x operations.


The Java/C# model is instead based on predefined interfaces which has 
pros and cons.
* Main pro is that functions that take generic iterators can be ordinary 
functions rather than templates.
* Main con is that such functions can't generally be as efficient as raw 
pointer manipulation, because you have to make a virtual method call 
through the interface pointer to get each next element.


D is in a very interesting place in that it is high level enough that 
the C++ model doesn't quite make sense, but low level enough that the 
Java model doesn't quite make sense either.

D may be able to have the best of both worlds.  Define *both* standard 
concepts *and* standard interfaces that implement those concepts, and 
then libraries can write either templatized algorithms for speed, or 
regular function based algorithms for code-size, use with inheritance, etc.

--bb