Boost logo

Boost :

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

Dan Rosen wrote:
> [...]
>>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.
> Well, the concepts I'm hoping to support, roughly speaking, are
> binary trees (a node contains at most 2 children), k-ary trees (a
> node contains at most k children), and trees with no limit on the
> number of children per node. To say that users who want the third
> type of tree should just use boost::graph, or that a trie shouldn't
> be implemented as a tree, seems draconic to me.

Well, we could implement a single container type with a massive number
of policies that implements all the containers in the STL, but is
that a good design decision? The points you are talking about are
{2, N, oo}. I agree with 2 and N. oo is a different type of beast
altogether, and trying to stuff it in a tree-sized box doesn't seem
like sound judgement to me. I guarantee that if you tried to
implement a trie as a generic tree with std::list nodes, or perhaps
even a std::vector, that I would probably not use it. The whole
point of a trie is to get super-fast access to strings, and fattening
it up with those containers is the antithesis of that goal. Also,
I'm not familiar with any use-cases for a tree with an unbounded
number of keys per node. Perhaps you could cite some? Just because
you can build in the kitchen sink doesn't mean it's a good idea. It's
often a better idea to build a component that does one thing well.

> I think the tree concept should be general-purpose enough to
> encompass these uses, even if it's embodied by multiple
> implementations with different space/time tradeoffs.

I'm not convinced that a trie necessarily has the same interface
as a generic tree. And if you have a beast with nodes having an
unbounded number of keys, I'm even more skeptical of the consistency
of that interface with a generic tree. I imagine such a container
would have very special needs that would best be served by a
specialized data structure. I can tell you right now that such a
tree, in the absence of any further constraints, would have almost
no relevant performance guarantees (except possibly that it would
be provably easy to find use cases where its performance is

> [...]
> And in a general-purpose tree, it would be:
> struct node {
> node* parent_;
> node* first_child_;
> node* last_child_;
> node* prev_sibling_;
> node* next_sibling_;
> T* value_;
> };
> Would you consider five pointers to be too much?

Yes. I don't see what's wrong with my original suggestion:

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


Boost list run by bdawes at, gregod at, cpdaniel at, john at