STL Priority Queue

The STL on my Mac seems to have a "priority queue", but it's not quite what I want - it's just a wrapper around a heap.  What I want in a priority queue is:

1. log-time insertion of elements.
   
2. Constant time popping of the front.  (Actually, I can live with log-time here.)
   
3. The ability to reprioritize a single item in log time, based on the item itself.
   
4. Priorities stored with the elements (rather than calculated by a comparator).
   
5. Ability to put items into the queue without adding special "helper" fields.

Those last two points aren't critical, but they are very convenient.

Item 3 is what makes things interesting...for a lot of priority queue algorithms, the algorithm is only fast if you can reprioritize just a few affected other items without going over the entire queue.  (Doing an entire-queue operation will typically give you N-squared time, because you hit the entire queue to reprioritize every time you process a single item.)

There are two ways I've used to do this:

1. If I store the priority in the item itself (violates the last two points), I can just insert the items into an STL multi-map by priority.  To reprioritize an item, I find it by doing an equal_range query on its current priority, erase it, then reinsert it at the new priority.
2. To meet all the point, I use a map from priority to item, but then maintain a separate "back-link" map from items to iterators into the original map.  This gives me the ability to find an item by value and remove it from the priority queue and reinsert it.

The system can be made more efficient by using a hash map instead of a regular map for the back links, but it requires a hashing operator to be defined for the values, rather than just operator<.