I'm very interested in having tree container concepts in Boost.
The tree_node_map class provides an implementation to a basic tree node of variable branching size. The implementation here uses the std::map to implement the children, but this could equally be a std::list, std::vector or any suitable container; it could even be a low-level implementation (for performance) or a fixed-size array (for n-ary nodes).
I've been implementing a tree class recently where each node has: Node* first_child; Node* next_sibling;
I'm using new/delete currently, but was planning to use boost.Pool once my design has settled down.
A std::map would be too much overhead for my particular application (which tends to have deep trees with few branches).
I briefly played with one block of memory per branch and doing away with the first_child pointer, but decided to come back to that idea later. It has a problem with identifying the last node; either you need to store "branch length", or a flag to mark the end (in which case you've saved no memory; still may have a speed advantage however).
Finding the previous sibling or parent in my tree requires starting from the root node (or keeping a stack of nodes visited).
The tree class is just a wrapper around a tree node that provides access to a root element. This would need some major work and additional support (e.g. post/pre/in-order traversal iterators) if it were to be useful.
Do you have any example usage?
I wonder if it would be better to approach this from the algorithms/iterators side and come to the containers later? I.e. what operations do you need to do on the trees?
As a couple of examples I need: 1. for_each() of first child at each node. 2. display all node values in the tree on stdout.
I'm not yet clear what I want from the second option there. Some kind of indenting I guess.
BTW, I'm new to Boost. Is it normal to include all the Allocator stuff early on when discussing designs? I thought it would be grafted on at the end.
Darren
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
