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
> 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk