Iterators for D

[Sean Kelly]

Bill Baxter wrote:
> 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.

For what it's worth, C++98 style iterator traits won't work in D because 
of D's simpler template lookup rules.  I think we'll have to go with 
something much closer to C++0x concept checking if we want to overload 
algorithms for different iterator categories.

> 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.

Hrm... you could still use a Java design without the base class and have 
everyone just use templates though.

> 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.

That's kind of what I was thinking, though if iterators all inherit from 
a common base class then the calls will be virtual regardless, unless 
the DMD optimizer gets a bit fancier.


Sean