foreach vs. iterators

[Georg Wrede]

Walter Bright wrote:
> Georg Wrede wrote:
> 
>> Walter Bright wrote:
>>
>>> On the other hand, C++ iterators aren't a general substitute for 
>>> opApply. For example, it is not at all easy to turn a recursive data 
>>> structure (i.e. binary tree) into a linearized iterator.
>>
>>
>> If I'm not missing the essence here, there are several kinds of 
>> iterators, and not every data structure should try to provide all of 
>> these. For example, an iterator into a tree structure might be 
>> breadth-first or depth-first, but one wouldn't expect a linearized (if 
>> I understand the term in this context at all) iterator to exist. 
>> Conversely, an array is hardly thinkable without a linear iterator.
> 
> 
> Given the structure:
> 
> class Node
> {    Node left;
>     Node right;
>     ...data...
> }
> 
> how do you iterate that with an iterator? This is what I mean by 
> 'linearizing' it. The STL sidesteps the problem by avoiding providing 
> such a container.

You're right. This pointer-to-array semantics kept the iterators 
primitive, I'd almost forgotten how primitive.

So, to traverse the example, one obviously needs an iterator with more 
state than just the current node. In practice this state would be stored 
in a private, persistent LIFO.