From: Herve Bronnimann (hbr_at_[hidden])
Date: 2002-10-10 12:02:59
On Thu, Oct 10, 2002 at 04:09:32PM +0100, Craig Henderson wrote:
> Tree structures would be a welcome addition, IMO. Do you have (or plan to
> have) any "special case" tree structures, such as generic binary tree, AVL
> tree or red/black trees. Binary Trees are a very useful data structure that
> is lacking in the STL.
I have all these variants (more) in a STL-like library which I can
boostify. This was mentioned in a discussion involving Dietmar Kuehl's
priority queues structure a while ago on this list.
If anyone's interested in R/B trees, Randomized trees, Splay Trees, Treaps,
augmented or not, compact nodes (bools packed into pointers, for
instance), all in the STL style and ready to provide a set or a map
through an adapter which I provide, ask me.
What I'd expect from a generic tree library:
- a unified interface by concepts (BinaryTree, NAryTree, SearchTree,
RedBlackTree perhaps, etc.) Concepts are important because they lay
the ground for the interface with generic algorithms
- iterators for traversal, not as member functions (although a begin()
is certainly useful, there are many ways to traverse a tree)
- generic algorithms, with interface decoupled from the tree class
(much like algorithms/containers in the STL interact by iterators).
I think the right interface is algorithmic visitors, much like in
the BGL. For example, we'd want rotations that work on any tree
that provides left/right.
- policies, or traits (do you maintain the tree size? is it possible
to add fields/derive from node/add property, and have the generic
algorithm also maintain that property?)
It's really challenging to come up with the right mixture. I've tried,
and am nowhere near. I'll take a close look at the proposal though, as
I'm sure there will be more good ideas in there.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk