Т elem(c.frontO): c.popfrontC): return elem:

Получение значения следующего элемента Т& front о {

if (C.emptyO) {

throw ReadEmptyQueueC);

return C.frontO:

lendif /* QUEUE HPP */

При использовании этой очереди предыдущий пример можно записать в следующем виде:

cont/queue2.cpp #1nclude <105tream> #include <str1ng>

#include Queue.hpp Использование нестандартного класса очереди using namespace std:

int mainO {

try {

Queue<string> q:

Вставка трех элементов в очередь q.push( These ): q.pushCare ): q.push( more than ):

Вывод и удаление двух элементов иэ очереди cout q.popO: cout q.popO:

Вставка двух новых элементов q.pushc four ); q.pushCwords! ):

Удаление одного элемента q.popO:

Вывод и удаление двух элементов из очереди

cout q.popO:

cout q.popO endl:

Вывод количества оставшихся элементов cout number of elements in the queue: q.sizeC) endl:

Вывод и удаление одного элемента cout q.popC) endl:

catch (const exceptions e) {

cerr EXCEPTION: e.whatC) endl:

При последнем вызове pop() намеренно допущена ошибка. В отличие от стандартного класса очереди с неопределенным поведением наш класс генерирует исключение. Результат выполнения программы выглядит так:

These are four words!

number of elements in the queue: 0

EXCEPTION: read empty queue

Приоритетные очереди

Класс priority queue<> реализует очередь, в которой последовательность чтения элементов определяется их приоритетами. По своему интерфейсу приоритетные очереди близки к обычным очередям: функция push() заносит элемент в очередь, а функции top() и рор() читают и удаляют следующий элемент (рис. 10,5). Однако в приоритетных очередях следующим элементом является не первый вставленный элемент, а элемент с максимальным приоритетом. Таким образом, можно считать, что порядок сортировки элементов частично определяется их значениями. Как обычно, критерий сортировки может передаваться в параметре шаблона. По умолчанию элементы сортируются оператором < в порядке убывания; при этом следующим элементом всегда является элемент с максимальным приоритетом. Если существует несколько элементов с максимальными приоритетами, критерий выбора определяется реализацией.

Рис. 10.5. Интерфейс приоритетной очереди

Приоритетные очереди определяются в том же заголовочном файле <queue>, в котором определяются обычные очереди

Iinclude <queue>

В файле <queue> класс priority queue определяется следующим образом: namespace std {

template <class Т.

class Container = vector<T>.

class Compare = less<typename Container::value type > > class priority queue;

Первый параметр шаблона определяет тип элементов. Необязательный второй параметр шаблона определяет контейнер, который будет использоваться внутренней реализацией приоритетной очереди для хранения элементов. По умолчанию это вектор. Необязательный третий параметр шаблона определяет критерий сортировки, который требуется для поиска следующего элемента с высшим приоритетом. По умолчанию элементы сравниваются оператором <.

Например, следующее объявление определяет приоритетную очередь с элементами типа float:

std:;priority queue<float> pbuffer: Приоритетная очередь для типа float

Реализация приоритетной очереди просто отображает операции с очередью на соответствующие операции с используемым контейнером (см. рис. 10.4). Допускается использование любого класса последовательного контейнера с поддержкой функций итераторов произвольного доступа и функций front(), back(), push back() и pop back(). Произвольный доступ необходим для сортировки элементов, выполняемой алгоритмами STL для работы с кучей (см. с. 396). Например, элементы приоритетной очереди могут храниться в деке:

std::priority queue<float.std::deque<float> > pbuffer:

Чтобы определить собственный критерий сортировки, необходимо передать бинарный предикат в виде функции или объекта функции; предикат используется алгоритмами сортировки для сравнения двух элементов (за информацией о критериях сортировки обращайтесь на с. 186 и 296). Например, следующее объявление определяет приоритетную очередь с обратным порядком сортировки:

std::pri ori ty queue<f1 oat.std::vector<f1oat>.

std::greater<float> > pbuffer;

В такой приоритетной очереди следующим элементом всегда является один из элементов с наименьшим значением.

Основной интерфейс

Основной интерфейс приоритетных очередей состоит из функций push(), top() и рор():

О функция push() вставляет элемент в приоритетную очередь;

О функция top() возвращает следующий элемент приоритетной очереди;

О функция рор() удаляет элемент из приоритетной очереди.

В предыдущих версиях STL шаблону всегда передавался тип контейнера и критерий сортировки, поэтому объявление приоритетной очереди с элементами Tiina float выглядело так:

priority queue<vector<float>.less<float> > buffer: