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