--- On Fri, 5/6/11, Erik Erlandson wrote:
ply() could easily be a free function, and would have O(depth) complexity. The problem I saw with depth() as a stateless function is that its complexity would be linear on the size of the (sub)tree, unless I'm missing something. (I mitigated that problem by maintaining some depth-histogram structures that can be updated in O(depth) time for various operations.)
Ah, I see now. In that case, storing the depth variable as part of the tree node would make the depth() member function most efficient...for those applications that actually need it. This leads to the question of whether or not applications that don't need depth() can live with the memory overhead. I suspect so, but that's just a guess. BTW, I've started a new discussion on container_gen, archived here: <http://article.gmane.org/gmane.comp.lib.boost.devel/219238> Cromwell D. Enage