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

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

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

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

int mainC) {

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.l) q.pushC55.5) q.pushC33.3)

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

Извлечение и вывод оставшихся элементов while (!q.emptyO) {

cout q.topO :

q.popC):

cout endl:

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

66.6 44.4 33.3 22.2 11.1

Как видите, после вставки значений 66.6, 22.2 и 44.4 программа считает старшими элементами 66.6 и 44.4. После вставки еще трех элементов приоритетная очередь содержит значения 22.2, 11.1, 55.5 и 33.3 (в порядке вставки). Следующий элемент просто удаляется вызовом рор(), поэтому итоговый цикл выводит значения 33,3, 22.2 и 11.1 именно в этом порядке.

;троение класса priority queue

Типичная реализация класса priority queue<>, как и реализации классов stacko и queueo, понятна без комментариев:

namespace std {

template <cla5s Т. class Container = vector<T>.

class Compare = less<typename Container:-.value type> > class pr1or1ty queue { public:

typedef typename Container::value type value type:

typedef typename Container:;size type size type;

typedef Container container type;

protected:

Compare comp: Критерий сортировки

Container c: Контейнер public:

Конструкторы

explicit pr1or1ty queue(con5t Compares cmp CompareO,

const Containers = ContainerO)

: comp(cmp), cCcont) {

make heap(c.begin().с.end().comp);

void pushCconst value type& x) { c.push backCx):

push heap(c.beg1n().C.endO.comp):

void pope) {

pop heap(c.beginO.c.end().comp): c.pop backO:

bool emptyO const { return c.emptyO: }

size type sizeO const { return c.sizeO: )

const value type& topC) const { return c.frontO: )

Как видно из приведенного листинга, приоритетная очередь использует алгоритмы STL для работы с кучей, описанные на с. 396. В отличие от других контейнерных адаптеров для приоритетной очереди не определены операторы сравнения.

Ниже приводятся более подробные описания членов класса priority queue<>.

Определения типов

приоритетная очередь val ue type

О Тип элементов. О Эквивалент:

ноитейиер::value type

приоритетнаяочередь::size type

О Беззнаковый целый тип для значений размера. О Эквивалент:

контейнер: :size type

приоритетная очередь::container type Тип контейнера.

Конструкторы

приоритетная очередь: :priority queue С)

О Конструктор но умолчанию,

О Создает пустую приоритетную очередь.

explicit приоритетная очередь: :\)nority queue Cconst CompFuncS op)

О Создает пустую приоритетную очередь с критерием сортировки ор.

О Примеры передачи критерия сортировки в аргументах конструктора приведены на с. 198 и 218.

приоритетная очередь: :pnonty queue (const CorfipFunc& op.

const Container& cont)

О Создает приоритетную очередь с критерием сортировки ор и инициализирует ее элементами cont

О Данная функция объявлена как шаблонная (см. с. 28), поэтому элементы исходного интервала могут относиться к любому типу, который преобразуется к типу элементов контейнера.

приоритетиая очередь\ :pnonty q\jieue (Inputlterator beg.

Inputlterator end)

О Создаст приоритетную очередь с критерием сортировки ор и инициализирует ее элементами интервала [beg,end).

О Данная функция объявлена как шаблонная (см. с. 28), поэтому элементы исходного интервала могут относиться к любому типу, который преобразуется к типу элементов контейнера.