--- On Thu, 5/5/11, Erik Erlandson wrote:
A couple other observations:
Some common tree-related methods like parent(), depth(), ply() seem like they would be good additions. Maintaining them adds some overhead, but I found I was able to keep things logarithmic in complexity.
The functions are useful. But perhaps depth() and ply() are better suited to be free functions, so that new concept-conforming tree models don't need to re-implement them the same way.
I found that I wanted to support what I called 'storage models' for child nodes. I ended up with three of them:
1) a vector<>-like model, where node[j] gives the jth-child 2) a map<>-like model, where node[key] gives the child indexed by (key) 3) a multiset<>-like model where children are automatically maintained in a sorted order.
Do these storage models wrap around their respective STL containers? (From previous posts I gather that they weren't.) In my TreeNode library, I use the container_gen metafunction that's currently part of the BGL. I'd be happy to hear how users would like to select their underlying containers.
I'm not sure if that has a role in a Hierarchical Container concept definition -- such things might just be instantiations of such a concept.
In my TreeNode library, I currently distinguish between associative tree nodes and ones that provide random access to their child nodes because they lend themselves to somewhat different use cases (and therefore different interfaces). Otherwise, whatever storage model I use is left as an implementation detail. Cromwell D. Enage