Приоритетные очереди
Наконец, последний из рассматриваемых здесь контейнеров стандартной библиотеки — это приоритетная очередь. Она строится на основе вектора или deque. От обычной очереди она отличается тем, что вне зависимости от порядка размещения элементов первым будет извлекаться наиболее “критический” из них. Критичность, или приоритет, элемента определяется заданным функциональным объектом отношения (по умолчанию — “меньше”). Наиболее приоритетный (наибольший) элемент помещается на вершину очереди (его значение доступно посредством функции top ()) и удаляется первым (функция pop ()).
Создание и действия с приоритетной очередью
При конструировании очереди в общем случае указывается тип элементов, тип контейнера-основы и функциональный объект, определяющий приоритеты. Контейнером-основой для приоритетной очереди может быть вектор или deque.
Нужно сказать, что шаблоны стеков и очередей имеют аргументы по умолчанию. Тип контейнера и отношение (для приоритетной очереди) указывать, вообще говоря, не обязательно. Так, для стека и очереди тип контейнера по умолчанию — deque, для приоритетной очереди — vector, а операция отношения — “меньше”.
Вот маленький пример, моделирующий составление списка неотложных дел в порядке их важности:
////////////////////////////////////////////////////
// Priority.срр: Демонстрация приоритетной очереди.
//
#include <iostream>
#include <string>
#include <queue>
#include <deque>
#pragma hdrstop
using namespace std;
class ToDo {
int priority;
string doit;
public:
ToDo(int p = 0, string d = ""): priority(p), doit(d) {}
bool operator<(const ToDo &arg) const { return priority < arg.priority; }
friend ostream &operator<<(ostreams, const ToDo&);
};
ostream &operator<<(ostream &os, const ToDo &t) {
os << t.priority << " - " << t.doit;
return os;
}
int main() {
priority_queue<ToDo, deque<ToDo>, less<ToDo> > todo;
// Разместим некоторые неотложные дела... todo.push(ToDo(3, "Finish the program you started yesterday."));
todo.push(ToDo(7, "Write a letter to X."));
todo.push(ToDo(4, "Buy some food for dinner."));
todo.push(ToDo(1, "Call your publisher."));
// Распечатать список в порядке срочности. while (!todo.empty()) {
cout << todo.top() << endl;
todo-pop() ;
)
return 0;
)
Программа выводит:
7 - Write a letter to X.
4 - Buy some food for dinner.
3 - Finish the program you started yesterday.
1 - Call your publisher.
