Yet another strike against the current AA implementation

Michel Fortin michel.fortin at michelf.com
Sun Apr 26 08:38:37 PDT 2009


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.

-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/




More information about the Digitalmars-d mailing list