¿Cómo usar la cola de prioridad STL para objetos?

80 
class Person
{
public:
    int age;
};

Quiero almacenar objetos de la clase Person en una cola de prioridad.

priority_queue< Person, vector<Person>, ??? >

Creo que necesito definir una clase para la comparación, pero no estoy seguro.

Además, cuando escribimos,

priority_queue< int, vector<int>, greater<int> >

¿Cómo funciona el mayor?

c++ stl usuario2441151
fuente
Publicación similar aquí
Rick Smith

Respuestas:

110

Debe proporcionar una comparación de orden débil estricta válida para el tipo almacenado en la cola, Personen este caso. El valor predeterminado es usar std::less<T>, que se resuelve en algo equivalente a operator<. Esto depende de que su propio tipo almacenado tenga uno. Entonces, si tuviera que implementar

bool operator<(const Person& lhs, const Person& rhs);

debería funcionar sin más cambios. La implementación podría ser

bool operator<(const Person& lhs, const Person& rhs)
{
  return lhs.age < rhs.age;
}

Si el tipo no tiene una comparación natural "menor que", tendría más sentido proporcionar su propio predicado, en lugar del predeterminado std::less<Person>. Por ejemplo,

struct LessThanByAge
{
  bool operator()(const Person& lhs, const Person& rhs) const
  {
    return lhs.age < rhs.age;
  }
};

luego instancia la cola de esta manera:

std::priority_queue<Person, std::vector<Person>, LessThanByAge> pq;

Con respecto al uso de std::greater<Person>como comparador, esto usaría el equivalente de operator>y tendría el efecto de crear una cola con la prioridad WRT invertida como caso predeterminado. Requeriría la presencia de un operator>que pueda operar en dos Personinstancias.

juanchopanza
fuente
7
Si bien esta respuesta es correcta, no me gusta el uso de operator<aquí. operator<implementa la comparación predeterminada para un tipo que, en mi experiencia, rara vez es lo que desea. Creo que el enfoque que Mike describe en su respuesta es casi siempre preferible.
Björn Pollex
1
@ BjörnPollex De acuerdo. Estaba agregando algo sobre eso. En una clase con un solo miembro de datos, el operador podría haber tenido sentido.
juanchopanza
Digno de nota: la aplicación bool YourClass::operator <(const YourClass&) consttambién permitirá el uso transparente del comparador por defecto, std::less<T>. No tan flexible, pero funcional cuando eso es todo lo que necesita. (y +1).
WhozCraig
Gracias por la respuesta. Puedo sobrecargar el operador '<' incluso si la clase tiene varios miembros, ¿verdad?
user2441151
@ user2441151 Sí, puedes, pero debes tener cuidado con la lógica. Debe implementar un estricto orden débil. Cuantos más miembros de datos, más fácil es equivocarse. Eso es a menos que lo use std::tie, en cuyo caso es bastante trivial.
juanchopanza
50

Escribiría una clase de comparación, por ejemplo:

struct CompareAge {
    bool operator()(Person const & p1, Person const & p2) {
        // return "true" if "p1" is ordered before "p2", for example:
        return p1.age < p2.age;
    }
};

y utilícelo como argumento de comparación:

priority_queue<Person, vector<Person>, CompareAge>

El uso greaterda el orden opuesto al predeterminado less, lo que significa que la cola le dará el valor más bajo en lugar del más alto.

Mike Seymour
fuente
1
¿Es posible pasar "objetos de comparación" en lugar de clases de comparación? (para parametrizarlo y obtener más flexibilidad)
castarco
1
@castarco sí, puede pasar un objeto comparador específico como argumento de constructor.
Mike Seymour
Este es un método más preferible a la respuesta principal. No solo porque logra una comparación de nivel superior (que se puede transferir fácilmente a otros idiomas, nivel inferior y superior), sino también porque da como resultado un código más reutilizable.
Furkan Toprak
20

Una cola de prioridad es un tipo de datos abstracto que captura la idea de un contenedor cuyos elementos tienen "prioridades" adjuntas. Un elemento de máxima prioridad siempre aparece al principio de la cola. Si se elimina ese elemento, el siguiente elemento de mayor prioridad avanza al frente.

La biblioteca estándar de C ++ define una plantilla de clase priority_queue, con las siguientes operaciones:

push : inserta un elemento en la cola de prioridad.

top : Devuelve (sin eliminarlo) un elemento de mayor prioridad de la cola de prioridad.

pop : Elimina un elemento de mayor prioridad de la cola de prioridad.

tamaño : Devuelve el número de elementos en la cola de prioridad.

vacío : Devuelve verdadero o falso según si la cola de prioridad está vacía o no.

El siguiente fragmento de código muestra cómo construir dos colas de prioridad, una que puede contener números enteros y otra que puede contener cadenas de caracteres:

#include <queue>

priority_queue<int> q1;
priority_queue<string> q2;

El siguiente es un ejemplo de uso de la cola de prioridad:

#include <string>
#include <queue>
#include <iostream>

using namespace std;  // This is to make available the names of things defined in the standard library.

int main()
{
    piority_queue<string> pq; // Creates a priority queue pq to store strings, and initializes the queue to be empty.

    pq.push("the quick");
    pq.push("fox");
    pq.push("jumped over");
    pq.push("the lazy dog");

    // The strings are ordered inside the priority queue in lexicographic (dictionary) order:
    // "fox", "jumped over", "the lazy dog", "the quick"
    //  The lowest priority string is "fox", and the highest priority string is "the quick"

    while (!pq.empty()) {
       cout << pq.top() << endl;  // Print highest priority string
       pq.pop();                    // Remmove highest priority string
    }

    return 0;
}

El resultado de este programa es:

the quick
the lazy dog
jumped over
fox

Dado que una cola sigue una disciplina de prioridad, las cadenas se imprimen de mayor a menor prioridad.

A veces es necesario crear una cola de prioridad para contener objetos definidos por el usuario. En este caso, la cola de prioridad necesita conocer el criterio de comparación utilizado para determinar qué objetos tienen la mayor prioridad. Esto se hace mediante un objeto función perteneciente a una clase que sobrecarga al operador (). El sobrecargado () actúa como <con el propósito de determinar prioridades. Por ejemplo, supongamos que queremos crear una cola de prioridad para almacenar objetos de tiempo. Un objeto Time tiene tres campos: horas, minutos, segundos:

struct Time {
    int h; 
    int m; 
    int s;
};

class CompareTime {
    public:
    bool operator()(Time& t1, Time& t2) // Returns true if t1 is earlier than t2
    {
       if (t1.h < t2.h) return true;
       if (t1.h == t2.h && t1.m < t2.m) return true;
       if (t1.h == t2.h && t1.m == t2.m && t1.s < t2.s) return true;
       return false;
    }
}

Una cola de prioridad para almacenar tiempos de acuerdo con el criterio de comparación anterior se definiría de la siguiente manera:

priority_queue<Time, vector<Time>, CompareTime> pq;

Here is a complete program:

#include <iostream>
#include <queue>
#include <iomanip>

using namespace std;

struct Time {
    int h; // >= 0
    int m; // 0-59
    int s; // 0-59
};

class CompareTime {
public:
    bool operator()(Time& t1, Time& t2)
    {
       if (t1.h < t2.h) return true;
       if (t1.h == t2.h && t1.m < t2.m) return true;
       if (t1.h == t2.h && t1.m == t2.m && t1.s < t2.s) return true;
       return false;
    }
};

int main()
{
    priority_queue<Time, vector<Time>, CompareTime> pq;

    // Array of 4 time objects:

    Time t[4] = { {3, 2, 40}, {3, 2, 26}, {5, 16, 13}, {5, 14, 20}};

    for (int i = 0; i < 4; ++i)
       pq.push(t[i]);

    while (! pq.empty()) {
       Time t2 = pq.top();
       cout << setw(3) << t2.h << " " << setw(3) << t2.m << " " <<
       setw(3) << t2.s << endl;
       pq.pop();
    }

    return 0;
}

El programa imprime las horas de la última a la más antigua:

5  16  13
5  14  20
3   2  40
3   2  26

Si quisiéramos que los primeros tiempos tuvieran la máxima prioridad, redefiniríamos CompareTime de esta manera:

class CompareTime {
public:
    bool operator()(Time& t1, Time& t2) // t2 has highest prio than t1 if t2 is earlier than t1
    {
       if (t2.h < t1.h) return true;
       if (t2.h == t1.h && t2.m < t1.m) return true;
       if (t2.h == t1.h && t2.m == t1.m && t2.s < t1.s) return true;
       return false;
    }
};
Siddharth Kumar
fuente
1
Tengo una pregunta, si se me permite. Priority_queue <Hora, vector <Time>, CompareTime> pq; . ¿Por qué es necesario el segundo parámetro, vector <Time>? Lo he visto en numerosos fragmentos de código, pero no pude entenderlo.
BarbuDorel
Oh noo ... el zorro no es marrón y el zorro no marrón saltó (salta) sobre el perro perezoso. :-(
cyber_raj
3
¿No debería pq.front () ser pq.top () en el primer fragmento?
codewing
4

Este fragmento de código puede ayudar ...

#include <bits/stdc++.h>
using namespace std;    

class node{
public:
    int age;
    string name;
    node(int a, string b){
        age = a;
        name = b;
    }
};

bool operator<(const node& a, const node& b) {

    node temp1=a,temp2=b;
    if(a.age != b.age)
        return a.age > b.age;
    else{
        return temp1.name.append(temp2.name) > temp2.name.append(temp1.name);
    }
}

int main(){
    priority_queue<node> pq;
    node b(23,"prashantandsoon..");
    node a(22,"prashant");
    node c(22,"prashantonly");
    pq.push(b);
    pq.push(a);
    pq.push(c);

    int size = pq.size();
    for (int i = 0; i < size; ++i)
    {
        cout<<pq.top().age<<" "<<pq.top().name<<"\n";
        pq.pop();
    }
}

Salida: 

22 prashantonly
22 prashant
23 prashantandsoon..
bitbyter
fuente
0

Podemos definir un comparador definido por el usuario:. El siguiente código puede ser útil para usted.

Fragmento de código :

#include<bits/stdc++.h>
using namespace std;

struct man
{
  string name;
  int priority; 
};

class comparator
{
 public:
   bool operator()(const man& a, const man& b)
   {
        return a.priority<b.priority;
   }
};

int main()
{
   man arr[5];
   priority_queue<man, vector<man>, comparator> pq;

   for(int i=0; i<3; i++)
   {
     cin>>arr[i].name>>arr[i].priority;
     pq.push(arr[i]);
   }

   while (!pq.empty())
   {
     cout<<pq.top().name<<" "<<pq.top().priority;
     pq.pop();
     cout<<endl;
   }
   return 0;
}

entrada:

batman 2
goku 9
mario 4

Salida

goku 9
mario 4
batman 2

rashedcs
fuente