Re: [boost] Re: Boost library inclusion: generic tree containers?

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