dsimcha wrote:
== Quote from Michel Fortin (michel.for...@michelf.com)'s article
On 2009-04-26 11:21:54 -0400, dsimcha <dsim...@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
