From: David Abrahams (abrahams_at_[hidden])
Date: 2001-01-07 01:15:20
----- Original Message -----
> 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.
> Still, it would be more natural to work with an interface to the tree
> itself, since what I wanted was a data structure which efficiently
> supported the following operations on a container of elements with a
> comparison defined:
> (I wanted to implement a 'priority deque', which is a double-ended
> priority queue. These are very useful in search algorithms where you
> want to bound the number of active hypotheses by tossing the least
> likely ones).
For that, I would say std::set<> fits the bill exactly (and I've used set<>
for exactly that in the past). How would it be more natural to have anything
> David Abrahams has provided a compelling reason for providing
> mechanisms for accessing internal tree structure.
> But I don't understand why it's inappropriate to use something like
> the interfaces underlying standard set implementations. David?
because, for example, there's no way to say "insert X right here". Insertion
is always tied to the container's comparison function. Suppose you wanted to
insert something at a particular place in a range of otherwise equal
elements. Once you've found the position, you shouldn't have to pay for
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk