From: Darren Cook (darren_at_[hidden])
Date: 2005-02-24 23:02:00
>> I think this is not feasible in the general case. Consider a minimal
>> node containing only a pointer to the next sibling and to the first
>> child. Or a binary tree that keeps pointers to its left and right
>> children.
>
> yet so I will play the Devil's advocate for now. A useful tree iterator,
> in my view should provide access to the parent node from a given
> position in the tree.
Some applications never need to go up the tree, and the overhead can be
significant. E.g. if your application just needs a pointer to first child
and to next sibling, and you store one int at each node then you need 12
bytes; if you store a parent pointer it becomes 16 bytes/node. I.e. a 33%
increase in memory usage, which can be a lot if your application data is
basically just that tree and it has a few million nodes.
> Without that algorithms, etc. are harder to write,
> and the tree is much harder to manage.
I've been following this discussion but not the code: I hope a high-quality
boost tree library would have ways to choose which pointers each node
maintains; even if that means separate containers for each.
My own attempt at a generic tree container ended up as a mess of compromises
that failed to meet any of the design goals well. So I'd be very interested
to see what Boost can come up with.
Darren