"David B. Held" <dheld@codelogicconsulting.com> wrote in message news:d2cvju$lui$1@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