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 terrible).
[...] 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]; }; Dave