cola de prioridad de pares en orden inverso

Question

Estoy con ganas de hacer algo como esto:

priority_queue< pair<int, int>, vector<int>, greater<int> > Q; 

Esto funciona bien si el tipo que estoy comparando es int, es decir:

priority_queue< int, vector<int>, greater<int> > Q; 

embargo

, obviamente con pair<int, int>, no hay forma de comparar los pares en la cola con el estándar >. Me preguntaba qué debería hacer? ¿Cómo implementaría un > sobrecargado o existe otra forma de crear una cola de pares de prioridad con el pair.second más pequeño en la parte superior de la cola?

Answer 1

¿Has probado esto?

typedef pair<int, int> P; 
priority_queue< P, vector<P>, greater<P> > Q; 

Esto dará la orden inverso de la operator< normal para pair<int, int>, que comenzará con el más pequeño first tie-roto con menor second.

Si desea ordenar más pequeño second primero y first segundos, entonces necesitará una nueva funtor de clasificación (!):

struct Order 
{ 
    bool operator()(P const& a, P const& b) const 
    { 
     return a.second < b.second || a.second == b.second && a.first < b.first; 
    } 
} 

A continuación, utilice:

priority_queue< P, vector<P>, Order > Q; 

Answer 2

Debe crear su propia clase de dominio en lugar de usar pair<int, int> aquí, hasta donde puedo ver. Entonces puede sobrecargar > como desee.