prioridad - metodos de queue c++
¿Cómo utilizar la cola de prioridad STL para objetos? (5)
class Person
{
public:
int age;
};
Quiero almacenar objetos de la clase Persona en una cola de prioridad.
priority_queue< Person, vector<Person>, ??? >
Creo que necesito definir una clase para la comparación, pero no estoy seguro de eso.
Además, cuando escribimos,
priority_queue< int, vector<int>, greater<int> >
¿Cómo funciona el mayor?
Debe proporcionar una comparación de ordenamiento débil estricta válida para el tipo almacenado en la cola, Person en este caso. El valor predeterminado es usar std::less<T> , que se resuelve en algo equivalente al operator< . Esto se basa en su propio tipo almacenado que tiene uno. Así que si fueras a 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 de "menos que", tendría más sentido proporcionar su propio predicado, en lugar del estándar 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 como esta:
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 invertida WRT en el caso predeterminado. Requeriría la presencia de un operator> que pueda operar en dos instancias de Person .
Escribirías una clase comparativa, 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 usar eso como el argumento comparador:
priority_queue<Person, vector<Person>, CompareAge>
Al utilizar greater da el orden contrario al predeterminado less , lo que significa que la cola le dará el valor más bajo en lugar del más alto.
Esta pieza 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
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 en la parte delantera de la cola. Si se elimina ese elemento, el siguiente elemento de prioridad más alta 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 prioity.
arriba : devuelve (sin eliminarlo) un elemento de prioridad más alta de la cola de prioridad.
pop : elimina un elemento de prioridad más alta 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 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;
}
La salida 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, uno necesita 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 prioridad más alta. Esto se hace por medio de un objeto de función que pertenece 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 Tiempo 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 los tiempos de acuerdo con el criterio de comparación anterior se definirá 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 los tiempos desde el más reciente hasta el más antiguo:
5 16 13
5 14 20
3 2 40
3 2 26
Si quisiéramos que los primeros tiempos tuvieran la más alta prioridad, redefiniríamos CompararTime 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;
}
};