Prioritized_Set<>

Hello All,

I have a problem that seems to be common. I need a Prioritized_Set<>.
Note that this is not the same as a prioritized queue. A prioritized
queue, as implemented in STL, allows replication of the elements in its
queue. By contrast, I need a data structure where every "queued"
element is unique. In particular, the Prioritized_Set<> that I have
in mind would have the following characteristics:

template <typename Element, typename Priority> class Prioritized_Set
{};

1. The structure must maintain elements with the same uniqueness as
would a set.
2. Each element must have a priority.
3. There must be a 1-to-1 mapping of elements to their corresponding
priorities.
4. There must be a 1-to-n mapping of priorities to their corresponding
elements.
5. It must be possible to delete any arbitrary element, and if
necessary, its corresponding priority.
6. It must be possible to extract the highest-priority element and its
priority.
7. It must be possible to redefine the priority of an arbitrary
element.
8. It must be possible to determine if there is containment of an
element.
9. Elements of identical priority become highest priority according to
a FIFO model.

I need all operations to run in O[log(n)], or better, actual time.

I am ready to implement a data structure that satisfies 1-8 and the O[]
constraint, but characteristic (9) is a problem. The data structure I
have in mind is already fat with pointers, and to do (9) would make it
even fatter.

I'd like to know:

a) Is there already a data structure that satisfies these constraints?
b) In your experience has (9) been so important as to be essential?

I've read some of Dietmar Kuhl's posts and comments, but have not had
time to look at Boost.

-Le Chaud Lapin-

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]