Как использовать приоритетную очередь STL для объектов?

class Person
{
public:
    int age;
};

Я хочу хранить объекты класса Person в очереди с приоритетом.

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

Я думаю, мне нужно определить класс для сравнения, но я не уверен в этом.

Кроме того, когда мы пишем,

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

Как работает большее?

В этом случае вам необходимо предоставить допустимое строгое сравнение слабого порядка для типа, хранящегося в очереди Person. По умолчанию используется std::less<T>, что разрешает нечто эквивалентное operator<. Это зависит от его собственного сохраненного типа. Итак, если бы вы реализовали

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

он должен работать без дальнейших изменений. Реализация могла бы быть

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

Если тип не имеет естественного сравнения «меньше чем», было бы разумнее предоставить свой собственный предикат вместо предиката по умолчанию std::less<Person>. Например,

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

затем создайте экземпляр очереди следующим образом:

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

Что касается использования в std::greater<Person>качестве компаратора, это будет использовать эквивалент operator>и иметь эффект создания очереди с инвертированным приоритетом WRT в случае по умолчанию. Это потребует наличия объекта, operator>который может работать с двумя Personэкземплярами.

Вы бы написали класс компаратора, например:

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

и используйте это как аргумент компаратора:

priority_queue<Person, vector<Person>, CompareAge>

Использование greaterдает порядок, обратный порядку по умолчанию less, а это означает, что очередь будет давать вам самое низкое значение, а не самое высокое.

Очередь приоритетов - это абстрактный тип данных, который отражает идею контейнера, элементы которого имеют прикрепленные к ним «приоритеты». В начале очереди всегда появляется элемент с наивысшим приоритетом. Если этот элемент удален, следующий элемент с наивысшим приоритетом перемещается вперед.

Стандартная библиотека C ++ определяет шаблон класса priority_queue со следующими операциями:

push : вставить элемент в очередь приоритета.

top : вернуть (не удаляя) элемент с наивысшим приоритетом из очереди приоритетов.

pop : удалить элемент с наивысшим приоритетом из очереди приоритетов.

size : возвращает количество элементов в очереди с приоритетом.

empty : возвращает истину или ложь в зависимости от того, пуста ли очередь с приоритетами.

В следующем фрагменте кода показано, как создать две очереди с приоритетом, одна из которых может содержать целые числа, а другая - строки символов:

#include <queue>

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

Ниже приведен пример использования приоритетной очереди:

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

Результат этой программы:

the quick
the lazy dog
jumped over
fox

Поскольку очередь следует дисциплине приоритета, строки печатаются от наивысшего до самого низкого приоритета.

Иногда необходимо создать очередь с приоритетом, чтобы содержать определенные пользователем объекты. В этом случае приоритетной очереди необходимо знать критерий сравнения, используемый для определения того, какие объекты имеют наивысший приоритет. Это делается с помощью объекта функции, принадлежащего классу, который перегружает operator (). Перегруженный () действует как <с целью определения приоритетов. Например, предположим, что мы хотим создать приоритетную очередь для хранения объектов Time. У объекта Time есть три поля: часы, минуты, секунды:

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

Очередь с приоритетом для хранения времени в соответствии с вышеуказанным критерием сравнения будет определяться следующим образом:

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

Программа распечатывает время от самого раннего до самого раннего:

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

Если бы мы хотели, чтобы самые ранние времена имели наивысший приоритет, мы бы переопределили CompareTime следующим образом:

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

Этот фрагмент кода может помочь ..

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

Вывод:

22 prashantonly
22 prashant
23 prashantandsoon..

Мы можем определить определяемый пользователем компаратор:. Приведенный ниже код может быть вам полезен.

Фрагмент кода:

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

ввод:

бэтмен 2
гоку 9
марио 4

Вывод

гоку 9
марио 4
бэтмен 2