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

From: David Abrahams (abrahams_at_[hidden])
Date: 2001-01-07 01:15:20

----- Original Message -----
From: <deansturtevant_at_[hidden]>

> 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:
> insert
> minimum
> maximum
> remove_minimum
> remove_maximum
> empty
> count
>
> (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
else?

> 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
another comparison.

-Dave