Вывод и удаление одного элемента 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>, в котором определяются обычные очереди"

linclude <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 шаблону всегда передавался тип контейнера и критерий сортировки, поэтому объявление приоритетной очереди с элементами Ti-nia float выглядело так:

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

Как и в остальных контейнерных адаптерах, функция рор() удаляет следующий элемент, но не возвращает его, тогда как функция top() возвращает следующий элемент без удаления. Следовательно, чтобы обработать и удалить следующий элемент очереди, всегда приходится вызывать обе функции. И, как обычно, если очередь не содержит ни одного элемента, поведение функций top() и рорО не определено. Наличие элементов в очереди проверяется фушсциями size() и empty().

Пример использования приоритетных очередей

пример использования класса priority queue<>:

cont/pqueuel.cpp #1nclude <1ostream> #1nclude <queue> using namespace std;

int ma1nC) {

priority queue<float> q;

Вставка трех элементов в приоритетную очередь q.pushC66.6) q.push(22.2) q.push(44.4)

Вывод и удаление двух элементов cout « q.topO « ; q.popO;

cout « q.topO « endl; q.popC);

Вставка еще трех элементов q.pushCU.O q.pushC55.5) q.pushC33.3)

Удаление одного элемента q.popC);

Извлечение и вывод оставшихся элементов while Oq.emptyC)) {

cout « q.topO « :

q.popC):

cout « endl;

Результат выполнения программы выглядит так:

66.6 44.4 33.3 22.2 11.1