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, что означает, что очередь будет давать вам самое низкое значение, а не самое высокое.
Очередь приоритетов - это абстрактный тип данных, который отражает идею контейнера, чьи элементы имеют "приоритеты", прикрепленные к ним. Элемент наивысшего приоритета всегда появляется в передней части очереди. Если этот элемент удален, следующий элемент с наивысшим приоритетом продвигается вперед.
Стандартная библиотека С++ определяет шаблон priority_queue шаблона со следующими операциями:
push. Вставьте элемент в очередь приоритетов.
top: возвращает (не удаляя) элемент с наивысшим приоритетом из очереди приоритетов.
pop. Удалите элемент с наивысшим приоритетом из очереди приоритетов.
размер. Возвращает количество элементов в очереди приоритетов.
empty: вернуть true или false в зависимости от того, пуста ли очередь приоритетов или нет.
В следующем фрагменте кода показано, как создать две очереди приоритетов: одну, которая может содержать целые числа и другую, которая может содержать символьные строки:
#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.front() << endl; // Print highest priority string
pq.pop(); // Remmove highest priority string
}
return 0;
}
Выход этой программы:
the quick
the lazy dog
jumped over
fox
Поскольку очередь соответствует приоритетной дисциплине, строки печатаются от наивысшего до самого низкого приоритета.
Иногда нужно создать очередь приоритетов, чтобы содержать определенные пользователем объекты. В этом случае очередь приоритетов должна знать критерий сравнения, используемый для определения того, какие объекты имеют наивысший приоритет. Это делается с помощью объекта функции, несущего вид класса, который перегружает оператор(). Перегруженный() действует как < с целью определения приоритетов. Например, предположим, что мы хотим создать очередь приоритетов для хранения объектов 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;
}
:
batman 2
goku 9
mario 4
Выход
goku 9
mario 4
бэтмен 2