Cola de prioridad STL con claves duplicadas: ¿es posible?

Question

Necesito almacenar mis objetos de clase A en alguna estructura de datos. Además, me gustaría que se clasifiquen automáticamente según una clave, que en mi caso es un objeto incrustado de otra clase B.

Por lo tanto, decidí usar una cola de prioridad STL.

Sin embargo, es posible que los 2 o más objetos B tengan el mismo valor de clave.

Mis preguntas:

¿La cola de prioridad STL permiten duplicados de las llaves ??

Si lo hace, ¿qué debería considerar y qué predicado debo usar?

Sé que podría usar un multiset pero su rendimiento de notación Big O es peor, por eso quiero usar la cola de prioridad.

Answer 1

¿La cola de prioridad STL permite llaves duplicadas?

Sí.

si hace lo que debería considerar

que el orden entre los elementos iguales puede cambiar de forma arbitraria.

y qué predicado debo usar?

¿A qué te refieres? Eso depende completamente de tu semántica.

Answer 2

Sí, admite claves duplicadas.

Desde el doucumentation:

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

Una simple prueba confirma:

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

Salidas:

5 
5 

En cuanto a la predicado, el uso de lo que habría usado antes - nada garantizado por la cola de prioridad se rompe permitiendo elementos iguales, por lo que su algoritmo debería funciona bien

Answer 3

Konrad tiene una gran respuesta, para agregar a eso. Debes saber que priority_queue no necesariamente tiene un gran rendimiento. De acuerdo con esta página http://www.cs.brown.edu/~jwicks/libstdc++/html_user/classstd_1_1priority__queue.html, parece que se implementa haciendo make_heap, pop_heap, etc. en todas las operaciones para obtener la más alta prioridad.

El re-heapifying, puede ser costoso en comparación con otras estructuras de datos, dependiendo de su caso de uso.