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

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?

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.

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.

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;
    }
};

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..

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