Wie verwende ich die Prioritätswarteschlange STL für Objekte?

class Person
{
public:
    int age;
};

Ich möchte Objekte der Klasse Person in einer Prioritätswarteschlange speichern.

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

Ich denke, ich muss eine Klasse für die Vergleichssache definieren, bin mir aber nicht sicher.

Auch wenn wir schreiben,

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

Wie funktioniert das Größere?

PersonIn diesem Fall müssen Sie einen gültigen strengen Vergleich der schwachen Reihenfolge für den in der Warteschlange gespeicherten Typ angeben . Standardmäßig wird verwendet std::less<T>, was in etwas aufgelöst wird, das äquivalent zu ist operator<. Dies hängt davon ab, dass ein eigener gespeicherter Typ einen hat. Also, wenn Sie implementieren würden

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

es sollte ohne weitere Änderungen funktionieren. Die Implementierung könnte sein

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

Wenn der Typ keinen natürlichen "weniger als" -Vergleich hat, ist es sinnvoller, anstelle des Standardprädikats ein eigenes Prädikat anzugeben std::less<Person>. Zum Beispiel,

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

Instanziieren Sie dann die Warteschlange wie folgt:

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

In Bezug auf die Verwendung std::greater<Person>als Komparator würde dies das Äquivalent von verwenden operator>und den Effekt haben, dass eine Warteschlange mit der Priorität invertierter WRT im Standardfall erstellt wird. Es würde das Vorhandensein eines erfordern, das operator>auf zwei PersonInstanzen arbeiten kann.

Sie würden eine Vergleichsklasse schreiben, zum Beispiel:

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

und benutze das als Vergleichsargument:

priority_queue<Person, vector<Person>, CompareAge>

Die Verwendung greatergibt die entgegengesetzte Reihenfolge zur Standardreihenfolge an less, was bedeutet, dass die Warteschlange Ihnen den niedrigsten und nicht den höchsten Wert gibt.

Eine Prioritätswarteschlange ist ein abstrakter Datentyp, der die Idee eines Containers erfasst, an dessen Elemente "Prioritäten" angehängt sind. Ein Element mit der höchsten Priorität wird immer vorne in der Warteschlange angezeigt. Wenn dieses Element entfernt wird, rückt das Element mit der nächsthöheren Priorität nach vorne vor.

Die C ++ - Standardbibliothek definiert eine Klassenvorlage priority_queue mit den folgenden Operationen:

push : Fügen Sie ein Element in die Prioity-Warteschlange ein.

top : Gibt ein Element mit der höchsten Priorität aus der Prioritätswarteschlange zurück (ohne es zu entfernen).

pop : Entfernen Sie ein Element mit der höchsten Priorität aus der Prioritätswarteschlange.

Größe : Gibt die Anzahl der Elemente in der Prioritätswarteschlange zurück.

leer : Gibt true oder false zurück, je nachdem, ob die Prioritätswarteschlange leer ist oder nicht.

Das folgende Codefragment zeigt, wie zwei Prioritätswarteschlangen erstellt werden, eine mit Ganzzahlen und eine mit Zeichenfolgen:

#include <queue>

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

Das folgende Beispiel zeigt die Verwendung der Prioritätswarteschlange:

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

Die Ausgabe dieses Programms ist:

the quick
the lazy dog
jumped over
fox

Da eine Warteschlange einer Prioritätsdisziplin folgt, werden die Zeichenfolgen von der höchsten zur niedrigsten Priorität gedruckt.

Manchmal muss eine Prioritätswarteschlange erstellt werden, die benutzerdefinierte Objekte enthält. In diesem Fall muss die Prioritätswarteschlange das Vergleichskriterium kennen, anhand dessen bestimmt wird, welche Objekte die höchste Priorität haben. Dies geschieht mit Hilfe eines Funktionsobjekts, das zu einer Klasse gehört, die den Operator () überlastet. Das überladene () fungiert als <, um Prioritäten zu bestimmen. Angenommen, wir möchten eine Prioritätswarteschlange zum Speichern von Zeitobjekten erstellen. Ein Zeitobjekt hat drei Felder: Stunden, Minuten, Sekunden:

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

Eine Prioritätswarteschlange zum Speichern von Zeiten gemäß dem obigen Vergleichskriterium würde wie folgt definiert:

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

Das Programm druckt die Zeiten von spätestens bis frühestens:

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

Wenn wir möchten, dass früheste Zeiten die höchste Priorität haben, würden wir CompareTime folgendermaßen neu definieren:

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

Dieser Code kann helfen ..

#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();
    }
}

Ausgabe:

22 prashantonly
22 prashant
23 prashantandsoon..

Wir können einen benutzerdefinierten Komparator definieren: Der folgende Code kann für Sie hilfreich sein.

Code-Auszug :

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

Eingabe:

batman 2 goku 9
mario 4

Ausgabe

goku 9
mario 4 batman
2