STL priority queue with duplicate keys - is this possible?

Question

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

So I decided to use the STL priority queue.

However, it is possible that two or more objects B have the same key value.

My questions:

STL queue queue allows duplicate keys

If he does what I should consider and what predicate should I use?

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

Answer 1

STL queue queue allows duplicate keys

Yes.

If he does what I should consider

So that the order between equal elements can be changed arbitrarily.

and which predicate should I use?

Do you mean this? It completely depends on your semantics.

Answer 2

Yes, it supports duplicate keys.

Based on:

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

A simple test confirms this:

 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 what you used before - nothing guaranteed by the priority queue is broken, allowing equal elements, so your algorithm should work fine.

Answer 3

Conrad has a great answer to add to this. You should know that priority_queue does not necessarily have excellent 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 creating make_heap, pop_heap, etc. For all operations, to get the highest priority.

Replicating can be expensive compared to other data structures depending on your use case.