Subject: Re: [boost] [tree] Reviving the tree library
From: Cromwell Enage (sponage_at_[hidden])
Date: 2011-05-06 17:14:12
--- 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
> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk