Dan Rosen wrote:
[...] In short, although I'd like my concepts for trees to allow users to specify and access the sequences representing the children of a node, my implementation of this is proving very clumsy. So I'm wondering two things:
1. Is this a good idea in the first place? Are there really any compelling use cases, where you'd want one tree to store its node structure in vectors and another in lists? Or is this a case where a policy-based approach is misplaced effort? [...]
My personal intuition, not at all tested on real experience, is that you want to make the nodes as thin as possible. Trees are already fat structures by design, and something like std::list as a node type would bloat them beyond all recognition. 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. But to recoup the cost, this variance would have to be rather significant (I'd say there would have to be a fairly even distribution of nodes having anywhere from 2 to 30 children). This seems to me to be a rather unusual tree that probably won't occur often in practice. The only exception I can think of offhand would be a trie, but that should probably be implemented on its own anyway. Even a vector is not appropriate in my mind, because a fixed-size node should be sufficient in the vast majority of cases. Thus, I would suggest making your node container be an array of fixed size determined by a template parameter. It would be very difficult to justify something more elaborate than this given the speed and simplicity advantages. I think in the cases where someone needs very specialized nodes, it shouldn't be much bother for them to go straight to boost::graph. Dave