[boost] Re: boost::tree advice?

From: Thorsten Ottosen (nesotto_at_[hidden])
Date: 2005-03-30 04:23:28

"David B. Held" <dheld_at_[hidden]> wrote in message 
news:d2cvju$lui$1_at_sea.gmane.org...
| 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,

then use the state children_.empty() instead.

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

if you need flexibility, you won't get it for free.

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

3 pointers (words) should be enough (first,last,capacity).

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

what do you mean? you can define allocators for everything in
a ptr_vector.

Speaking of design

| template <int K = 2, int N = 1>
| struct node
| {
|     node* parent_;
|     node* child_[K];
|     T value_[N];
| };

if you know it is a k-ary tree, then use ptr_array<T,N>. No overhead,
no flexibility, but a lot easier to make exception-safe. If you use
ptr_array<T,N> in the no-node design, I can't see how it
gives any overhead. It also seems to be simpler.

-Thorsten