foreach vs. iterators

[Bill Baxter]

Sean Kelly wrote:
> Walter Bright wrote:
> 
>> Sean Kelly wrote:
>>
>>> I think I agree, but for the sake of argument, how would D handle 
>>> 'find'  operations on sequences that don't support opIndex?  At some 
>>> point, a generalizable bookmark is almost necessary for a faithful 
>>> implementation of some C++ algorithms.  Also, many of these 
>>> algorithms also require iteration across two sequences 
>>> simultaneously, which doesn't map very cleanly into foreach.  
>>> Consider a substring-style find operation (std::search), for example, 
>>> where both the pattern and target types do not support opIndex or 
>>> opSlice.  I might argue that it's a bit silly or unrealistic to 
>>> desire such an operation, but the C++ algorithm library does support it.
>>
>>
>> I think the target types will have to support opIndex or opSlice.
> 
> 
> Forgive me for resurrecting a horribly battered equine, but I was 
> thinking about this a bit tonight and I've decided that foreach, 
> foreach_reverse, and array operations are not a sufficient general 
> substitute for C++ iterators.
> 
> For example, let's say I want to compute the set union of two sorted 
> ranges, one of size M, the other of size N.  By iterating across the two 
> ranges simultaneously is is easy to see that the complexity for the 
> operation will be max(M,N).  In C++ this is easily accomplished using 
> forward iterators, and the ranges can be anything from arrays to SQL 
> result sets.
> 
> In D however, there is no way to iterate across multiple ranges 
> simultaneously using foreach, so opIndex must be used instead.  With 
> containers that have a constant-time lookup cost this isn't a big deal, 
> but what if these containers are binary trees?  The complexity for such 
> an operation would be M(log(M)) + N(log(N)).
> 
>  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.

It would be sufficient if D had coroutines and opApply were implemented 
using them.

The problem is that once you call an opApply function right now, it has 
to run to completion.  The only way I can see to have multiple opApply 
style iterators going simultaneously if you could truly suspend 
execution of one opApply temporarily and run another one for an iteration.

In other words, if you're going to use the stack and function state to 
store iterator state, then the only way to have multiple iterators in 
different states simultaneously is to be able to have multiple stacks 
active simultaneously, aka coroutines.

--bb