STL priority queue with duplicate keys - is it possible??

Question

Hi everybody,

I need to store my class A objects in some data structure. In addition, i would like them to be automatically sorted according to a key, which is in my case an embedded object of another class B.

Thus I decided to use a STL priority queue.

However it is possible that the 2 or more objects B to have the same key value.

My questions:

Does the STL priority queue allow duplicate keys??

If it does what should I consider and which predicate should I use?

I know I could use a multiset but its Big O notation performance is worse, that why I want to use the priority queue.

Answer 1

Does the STL priority queue allow duplicate keys??

Yes.

If it does what should I consider

That the order between equal elements may change arbitrarily.

and which predicate should I use?

That do you mean? That depends entirely on your semantics.

Answer 2

Yes, it supports duplicate keys.

From the doucumentation:

void push(const value_type& x) Inserts x into the priority_queue.
                               Postcondition: size() will be incremented by 1.

A simple test confirms it:

int main() {
  priority_queue<int> q;
  q.push(5);
  q.push(5);
  cout << q.top() << endl;
  q.pop();
  cout << q.top() << endl;
  q.pop();
}

Outputs:

5
5

As for the predicate, use whatever you would have used before - nothing guaranteed by the priority queue is broken by allowing equal elements, so your algorithm should work just fine.

Answer 3

Konrad has a great answer, to add to that. You should know that priority_queue doesn't necessarily have great performance. According to this page http://www.cs.brown.edu/~jwicks/libstdc++/html_user/classstd_1_1priority__queue.html, it looks like it is implemented by doing a make_heap, pop_heap, etc on all operations to get the highest priority.

The re-heapifying, can be expensive compared to other data structures, depending on your use case.