Jak korzystać z priorytetowej kolejki STL dla obiektów?

Question 1

class Person
{
public:
    int age;
};

Chcę przechowywać obiekty klasy Person w kolejce priorytetowej.

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

Myślę, że muszę zdefiniować klasę do porównania, ale nie jestem tego pewien.

Kiedy piszemy,

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

Jak działa większy?

Question 2

W tym przypadku musisz podać poprawne ścisłe porównanie słabej kolejności dla typu przechowywanego w kolejce Person. Wartością domyślną jest użycie std::less<T>, co jest odpowiednikiem operator<. Zależy to od tego, że jego własny przechowywany typ ma jeden. Więc jeśli miałbyś wdrożyć

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

powinien działać bez dalszych zmian. Realizacja mogłaby być

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

Jeśli typ nie ma naturalnego porównania „mniejsze niż”, bardziej sensowne byłoby podanie własnego predykatu zamiast domyślnego std::less<Person>. Na przykład,

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

następnie utwórz instancję kolejki w następujący sposób:

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

Jeśli chodzi o użycie std::greater<Person>jako komparatora, użyłoby to odpowiednika operator>i spowodowałoby utworzenie kolejki z odwróconym priorytetem WRT domyślnym przypadkiem. Wymagałoby to obecności, operator>które może działać w dwóch Personprzypadkach.

Question 3

Napisałbyś klasę porównawczą, na przykład:

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

i użyj tego jako argumentu porównawczego:

priority_queue<Person, vector<Person>, CompareAge>

Użycie greaterdaje odwrotną kolejność do domyślnej less, co oznacza, że kolejka poda najniższą wartość, a nie najwyższą.

Question 4

Kolejka priorytetowa to abstrakcyjny typ danych, który odzwierciedla pojęcie kontenera, którego elementy mają przypisane „priorytety”. Element o najwyższym priorytecie zawsze pojawia się na początku kolejki. Jeśli ten element zostanie usunięty, następny element o najwyższym priorytecie zostanie przeniesiony na pierwszy plan.

Biblioteka standardowa C ++ definiuje szablon klasy priority_queue, z następującymi operacjami:

push : Wstaw element do kolejki priorytetów.

top : Zwróć (bez usuwania) element o najwyższym priorytecie z kolejki priorytetowej.

pop : usuwa element o najwyższym priorytecie z kolejki priorytetów.

size : Zwraca liczbę elementów w kolejce priorytetowej.

empty : Zwraca wartość true lub false w zależności od tego, czy kolejka priorytetowa jest pusta, czy nie.

Poniższy fragment kodu pokazuje, jak utworzyć dwie kolejki priorytetowe, jedną, która może zawierać liczby całkowite, a drugą, która może zawierać ciągi znaków:

#include <queue>

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

Oto przykład użycia kolejki priorytetowej:

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

Wynik tego programu to:

the quick
the lazy dog
jumped over
fox

Ponieważ kolejka podlega dyscyplinie priorytetu, łańcuchy są drukowane od najwyższego do najniższego priorytetu.

Czasami trzeba utworzyć kolejkę priorytetową, aby zawierała obiekty zdefiniowane przez użytkownika. W takim przypadku kolejka priorytetów musi znać kryterium porównania używane do określenia, które obiekty mają najwyższy priorytet. Odbywa się to za pomocą obiektu funkcji należącego do klasy, która przeciąża operator (). Przeciążona () działa jako <na potrzeby określania priorytetów. Na przykład załóżmy, że chcemy utworzyć kolejkę priorytetową do przechowywania obiektów Time. Obiekt Czas ma trzy pola: godziny, minuty, sekundy:

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

Kolejka priorytetowa do zapisania czasów według powyższego kryterium porównania byłaby zdefiniowana w następujący sposób:

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

Program wypisuje czas od ostatniego do najwcześniejszego:

Gdybyśmy chcieli, aby najwcześniejsze czasy miały najwyższy priorytet, przedefiniowalibyśmy opcję CompareTime w następujący sposób:

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

Question 5

Ten fragment kodu może pomóc ...

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

Wynik:

22 prashantonly
22 prashant
23 prashantandsoon..

Question 6

Możemy zdefiniować komparator zdefiniowany przez użytkownika: Poniższy kod może być dla Ciebie pomocny.

Fragment kodu:

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

Wejście :

batman 2
goku 9
mario 4

Wynik

goku 9
mario 4
batman 2