[boost] Re: boost::tree advice?

From: David B. Held (dheld_at_[hidden])
Date: 2005-03-28 19:23:18

Dan Rosen wrote:

> [...]
> In short, although I'd like my concepts for trees to allow users to
> specify and access the sequences representing the children of a node,
> my implementation of this is proving very clumsy. So I'm wondering two
> things:
> 
> 1. Is this a good idea in the first place? Are there really any
> compelling use cases, where you'd want one tree to store its node
> structure in vectors and another in lists? Or is this a case where a
> policy-based approach is misplaced effort?
> [...]

My personal intuition, not at all tested on real experience, is that
you want to make the nodes as thin as possible.  Trees are already
fat structures by design, and something like std::list as a node
type would bloat them beyond all recognition.  The only reason I
can think of to justify a dynamically sized node is to construct a
tree where the size of the nodes varies considerably.  But to recoup
the cost, this variance would have to be rather significant (I'd say
there would have to be a fairly even distribution of nodes having
anywhere from 2 to 30 children).  This seems to me to be a rather
unusual tree that probably won't occur often in practice.  The only
exception I can think of offhand would be a trie, but that should
probably be implemented on its own anyway.

Even a vector is not appropriate in my mind, because a fixed-size
node should be sufficient in the vast majority of cases.  Thus, I
would suggest making your node container be an array of fixed size
determined by a template parameter.  It would be very difficult to
justify something more elaborate than this given the speed and
simplicity advantages.  I think in the cases where someone needs
very specialized nodes, it shouldn't be much bother for them to go
straight to boost::graph.

Dave