Re: [boost] Re: boost::tree advice?

From: Dan Rosen (dan.rosen_at_[hidden])
Date: 2005-03-29 03:33:38

On Tue, 29 Mar 2005 01:53:44 -0600, David B. Held
<dheld_at_[hidden]> wrote:

> Also, I'm not familiar with any use-cases for a tree with an unbounded
> number of keys per node.

I'm getting the feeling we're talking about different things. I'm not
suggesting that the tree would have multiple keys per node -- I'm not
even sure what you mean by "keys" in this context -- I was saying that
a node in a tree may have an unbounded number of *children*.

> > 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];
> };

Well, a couple things:

1. There is no precedent for having an array of values at any given
node. In my experience, the precedent in container design is to let
clients fully specify the value type (and key type if appropriate). If
a client wants a node to contain an array of values, the code
indicates that by passing an array as the value type.

2. For the list of children, you've also specified array storage. But
what if I want to insert between two children? What if I don't want to
allocate K pointers for each node? What if I simply don't want the
number of children per node to be bounded? The implementation you
suggest here is decent for a k-ary tree, but it does have its inherent
restrictions. Simply put, I can't use it in any context where I don't
know how many children a given node might have, such as a parse tree
or a game tree, hence my "draconian" comment.

Anyway, I've posted a more complete document in response to João's
post, which I hope will better illustrate my intent. Have a look!

Thanks,
dr