From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-09-08 04:44:01
Dear tree expert,
As you might know, Boost.Intrusive implements an intrusive red-black
tree and also a class offering red-black tree algorithms. Those
algorithms were taken from the SGI STL code and optimized a bit.
One of the goals of Boost.Intrusive is avoiding recursive calls to make
those algorithms suitable for very big trees and/or embedded systems.
The SGI STL uses two recursive algoritms:
* Recursive destruction with no rebalancing
* Recursive structural copy (which needs a erasing function in case a
copy throws an exception).
All STL implementations I'm aware of use recursive cloning and
destruction. Boost.Intrusive changed the recursive tree destruction
algorithm to a non-recursive one thanks to a step by step tree
destruction function (unlink_leftmost_without_rebalance) that is also
very useful to implement advanced tree cloning functions that might
reuse old allocated nodes. However, I haven't found a non-recursive
structural copy algorithm anywhere.
So if you are a tree expert, I need your help to get a tree cloning
function, that:
* Does not use the comparison predicate or calls any function that uses
it (e.g.: insert())
* Can destroy all constructed nodes in a non-recursive form if
node-copying throws an exception.
* It's pretty efficient ;-)
Willing to help?
Ion