foreach vs. iterators

[Sean Kelly]

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.


Sean