Boost logo

Boost :

From: Darren Cook (darren_at_[hidden])
Date: 2003-03-23 20:06:57


>> 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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk