Как видите, после вставки значений 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 pr1ority 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 priority 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.begin().c.endC).comp):

void pope) {

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

bool emptyO const { return c.emptyO: }

s1ze 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 Containers cont)

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

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

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

Inputlterator end)

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

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

приоритетндя очврвдь: :\)nontyj\[j.eue (Inputlterator beg. Inputlterator end.

const CompFuncS op)

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

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

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

приоритетная очередь: :{>riorityj][ieue (Inputlterator beg. Inputlterator end.

const CompFuncS op. const Containers cont)

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

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

Другие операции

size type приоритетная очередь: .s-yze () const О Возвращает текущее количество элементов.

О Для проверки отсутствия элементов в приоритетной очереди рекомендуется использовать функцию empty(), поскольку она может работать быстрее.

bool приоритетная очередь:-.empty () const

О Проверяет, пуста ли приоритетная очередь. О Эквивалент (но может работать быстрее):

приоритетная очередь: :size()==0

void приоритетная очередь: -.pusb (const value type&. elem)

Вставляет копию elem в приоритетную очередь, const valuej:ype& приоритетная очередь: -.top О const

О Возвращает следующий элемент приоритетной очереди (то есть элемент с наибольшим значением среди всех элементов очереди). Если приоритетная очередь содержит сразу несколько элементов с таким значением, критерий выбора определяется реализацией.

О Перед вызовом необходимо убедиться в том, что приоритетная очередь содержит хотя бы один элемент (size()>0), иначе вызов приводит к непредсказуемым последствиям.