[boost] Re: boost::tree advice?

From: David B. Held (dheld_at_[hidden])
Date: 2005-03-29 20:40:02

Thorsten Ottosen wrote:

> [...]
> There is an alternative that doesn't really need a node concept.
> It goes like this
> 
> template< class T >
> class tree
> {
>     T data_;
>      boost::optional< boost::ptr_vector<tree<T> > > children_;
>     tree* parent_;
>     ...
> };
> 
> for n-ary trees, exchange ptr_vector<> with ptr_array<,N>.

This has "fat" written all over it.  First, you have overhead
with optional, and second, you have overhead with vector.  If
the vector conforms to the standard, the capacity will most
likely be larger than the size, wasting space, unless you
intentionally resize it every time, defeating the performance
guarantees.  On top of that, you need to store both the size
and the capacity in each vector, as well as a pointer to the
vector itself.  That's three words not counting any of the
pointer themselves.  Furthermore, the vector is stored on
the heap, so there is no possibility of creating a specialized
node heap.  I find this design to be, err..."less than optimal."

Dave