Re: [boost] Container suggestions (was: Re: BOOST_NO_HASH)

From: Matthew Austern (austern_at_[hidden])
Date: 2001-01-10 17:43:22

deansturtevant_at_[hidden] wrote:

> Funny this topic should come up -- I was just thinking of posting a
> suggestion that rb-trees be made a part of boost, until I realized
> that the functionality I needed I could get from the standard set.

You've probably all noticed that every so often, on comp.lang.c++
or some such place, people ask if there is an STL tree class.  I've
never been completely sure whether this is really a request for a 
dictionary class with performance characteristics typical of a 
balanced tree (e.g. worst-case logarithmic find/insert/erase), or 
whether people really are interested in an interface with operations
like "give me the right child of the current node".  

If the former, then set, and things like set, are good enough.  If
the latter, then the question is: what should a tree interface look
like, and who would ever want to use it?

A few of us have been working on that latter problem, and we will 
probably submit our work to BOOST.  Essentially, it's a framework 
for balanced binary trees with parent pointers.  (The "with parent
pointers" part is in some sense an implementation detail, but binary
trees with and without parent pointers are so different that we see
no value in trying to fit them both into the same framework.)

The interface we've come up with looks nothing like an STL interface,
but the general idea is similar: there are many different kinds of 
balanced binary trees (red-black trees, treaps, splay trees,...),
and there are many different uses for balanced binary trees.  Search
trees are the most obvious use, but not the only one.  So what we'll
be providing is a number of different implementations, for several 
different kinds of balanced binary trees, and several different 
"user" classes that provide higher-level functionality in terms of
balanced binary search trees.  In principle, STL classes like set<> 
and map<> could be implemented in terms of this low-level interface.

One nice thing that this framework makes possible is performance
testing that compares different kinds of balanced binary trees.

                        --Matt