На этом шаге мы приведдем общие сведения о приоритетных очередях.
Класс priority_queue<> реализует очередь, в которой последовательность чтения элементов определяется их приоритетами. По своему интерфейсу приоритетные очереди близки к обычным очередям: функция push() заносит элемент в очередь, а функции top() и рор() читают и удаляют следующий элемент (рисунок 1).
Рис.1. Интерфейс приоритетной очереди
Однако в приоритетных очередях следующим элементом является не первый вставленный элемент, а элемент с максимальным приоритетом. Таким образом, можно считать, что порядок сортировки элементов частично определяется их значениями. Как обычно, критерий сортировки может передаваться в параметре шаблона. По умолчанию элементы сортируются оператором < в порядке убывания; при этом следующим элементом всегда является элемент с максимальным приоритетом. Если существует несколько элементов с "максимальными" приоритетами, критерий выбора определяется реализацией.
Приоритетные очереди определяются в том же заголовочном файле <queue>, в котором определяются обычные очереди:
#include <queue>
В файле <queue> класс priority_queue определяется следующим образом:
namespace std {
template <class T,
class Container = vector<T>,
class Compare = less<typename Container::value_type > >
class priority_queue;
}
Первый параметр шаблона определяет тип элементов. Необязательный второй параметр шаблона определяет контейнер, который будет использоваться внутренней реализацией приоритетной очереди для хранения элементов. По умолчанию это вектор. Необязательный третий параметр шаблона определяет критерий сортировки, который требуется для поиска следующего элемента с высшим приоритетом. По умолчанию элементы сравниваются оператором <.
Например, следующее объявление определяет приоритетную очередь с элементами типа float:
std:.priority_queue<float> pbuffer; // Приоритетная очередь для типа float
Реализация приоритетной очереди просто отображает операции с очередью на соответствующие операции с используемым контейнером (рисунок 2).
Рис.2. Внутренний интерфейс очереди
Допускается использование любого класса последовательного контейнера с поддержкой функций итераторов произвольного доступа и функций front(), back(), push_back() и pop_back(). Произвольный доступ необходим для сортировки элементов, выполняемой алгоритмами STL для работы с кучей (смотри 307 шаг). Например, элементы приоритетной очереди могут храниться в деке:
std::priority_queue<float,std::deque<float> > pbuffer;
Чтобы определить собственный критерий сортировки, необходимо передать бинарный предикат в виде функции или объекта функции; предикат используется алгоритмами сортировки для сравнения двух элементов. Например, следующее объявление определяет приоритетную очередь с обратным порядком сортировки:
std::priority_queue<float,std::vector<f1oat>,
std::greater<float> > pbuffer;
В такой приоритетной очереди следующим элементом всегда является один из элементов с наименьшим значением.
На следующем шаге мы рассмотрим основной интерфейс такой очереди.
