Yet another strike against the current AA implementation

[Andrei Alexandrescu]

dsimcha wrote:
> == Quote from Michel Fortin (michel.fortin at michelf.com)'s article
>> On 2009-04-26 11:21:54 -0400, dsimcha <dsimcha at yahoo.com> said:
>>> 2.  You can't iterate over a binary tree in O(1) auxiliary space, at least not
>>> in any way I'm aware of.  This means that a lazy range to iterate over the
>>> keys or values is relatively useless because it would generate heap activity
>>> anyhow to store the stack or queue necessary to iterate over the tree, so you
>>> may as well just use the current .keys or .values properties, which just
>>> return an array.  (Because of the way that ranges are designed, you can't just
>>> use the call stack, unless you use fibers or something, which is obviously not
>>> a win from an efficiency point of view.)
>> Hum, are you saying opApply superior when it comes to iterating in a
>> tree? It seems that with opApply you could use the stack by recursively
>> calling opApply with the given delegate on each one of the branches.
> 
> Exactly.  On the other hand, you lose a lot of flexibility with opApply.  If you
> tried to port most of std.range to operate on the opApply interface instead fo the
> forward range interface, I doubt you'd get very far.
> 
> IMHO, though, opApply should *not* be deprecated.  opApply and ranges attempt to
> solve similar problems, but not the same problem.  Ranges attempt to solve the
> problem of iterating over some object with maximum flexibility from the point of
> view of the user of the object.  opApply attempts to solve the problem of
> iterating with maximum flexibility from the point of view of the implementer of
> the object.  In some cases, like the one you just described, the latter can be
> better.  However, it might make sense to document and give examples of this
> tradeoff somewhere.

1. Depth of iteration is low, so a short vector optimization will most 
of the time solve the problem without allocating extra memory.

2. I haven't measured, but the cost of the indirect call is large enough 
to make me suspect that opApply is not as efficient as it's cracked to 
be, even when compared with an iterator.


Andrei