Water lawn Feed dog Feed cat Feed bird Mow lawn Empty trash

Приоритетная очередь не поддерживает перебор элементов, однако ее поведение можно имитировать при помощи вектора (и получить полный доступ к функциональности вектора). Попробуйте разобраться в реализации приоритетной очереди, использующей функции mal<e heap(), push heap() и pop heap(). Эти функции являются сердцем приоритетной очереди. В сущности, можно сказать, что куча является приоритетной очередью, а priority queue - всего лишь ее интерфейсная оболочка. Имитация получается достаточно прямолинейной, хотя на первый взгляд может показаться, что существует более короткий путь. Поскольку базовый контейнер priority queue хранится в защищенной переменной класса (которой в соответствии со стандартом С++ назначается идентификатор с), можно объявить производный класс и получить доступ к базовой реализации:

: C07:PriorityQueue4.cpp

Получение доступа к базовой реализации

linclude <algorithm>

linclude <cstdlib>

linclude <ctime>

linclude <iostream>

linclude <iterator>

linclude <queue>

using namespace std:

class PQI : public priority queue<int> { public:

vector<int>& impK) { return c: }

int mainO { PQI pqi: srand(time(0)); for(int i = 0: i < 100: i++)

pqi.push(rand() % 25); copy(pqi .implO.beginO. pqi .implО.endO.

ostream iterator<int>(cout. )); cout endl: whileC!pqi .emptyO) {

cout pqi .topO ;

pqi .popO;

} /:-

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

Чтобы оператор < для вывода ToDoItem работал с шаблоном less<>, он должен быть оформлен в виде внешней функции (а не функции класса). Все остальное происходит автоматически. Результат выполнения программы выглядит так:

: C07:PriorityQueue5.cpp

Построение собственной приоритетной очереди

linclude <algorithm>

linclude <cstdlib>

linclude <ctinie>

linclude <iostream>

linclude <iterator>

linclude <queue>

using namespace std:

tempiate<class T. class Compare> class PQV : public vector<T> {

Compare comp: public:

PQV (Compare cmp - CompareO) : comp (cmp) { make heap(this->begin(). this->end(). comp):

const T& topO { return this->front(): } void push(const T& x) { this->push back(x):

push heap(this->begin(). this->end(). comp):

void popO { pop heap(this->begin(). this->end(). comp): pop back():

int mainO { PQ\/<int, less<int> > pqi: srand(time(0)): for(int i 0: i < 100: i++)

pqi.push(rand() % 25): copy(pqi .beginO, pqi.endO.

ostream iterator<int>(cout, )): cout endl: while( !pqi .emptyO) {

cout pqi .topO :

pqi .popO:

} /:-

Однако и эта программа ведет себя так же, как предыдущая! На самом деле в базовом векторе хранится не отсортированная последовательность элементов, а структура данных, называемая кучей. Она представляет дерево приоритетной очереди (хранящееся в виде линейной векторной структуры), но при последовательном переборе элементов кучи вы не получите ожидаемого порядка следования элементов приоритетной очереди. Вообще говоря, нужного результата можно добиться простым вызовом функции sort heap(), но это решение работает только один раз; после вызова куча превращается в отсортированный список. Чтобы снова использовать его как кучу, необходимо снова вызвать функцию make heap(). Мы можем инкапсулировать этот вызов в пользовательской реализации очереди:

: C07:PriorityQueue6.cpp linclude <algorithm> linclude <cstdlib> linclude <ctime> linclude <iostream>

linclude <iterator> linclude <queue> using namespace std:

tempiate<class T. class Compare> class PQV : public vector<T> { Compare comp: bool sorted: void assureHeapO { if(sorted) { Обратное преобразование списка в кучу: make heap(this->begin(). this->end(). comp): sorted = false:

public:

PQV (Compare cmp = CompareO) : comp(cmp) { make heap(this->begin(). this->end(). comp): sorted = false:

const T& topO { assureHeapO: return this->front():

void push(const T& x) { assureHeapO:

this->push back(x): Занести элемент в конец Внести изменения в кучу: push heap(this->begin(). this->end(). comp):

void popO { assureHeapO:

Перемещение верхнего элемента в последнюю позицию: pop heap(this->begin(). this->end(). comp): Удаление элемента: pop back():

void sortО { ifdsorted) { sort heap(this->begin(). this->end(). comp): reverse(this->begin(). this->end()): sorted = true:

int mainO { PQV<int. less<int> > pqi: srand(time(0)):

for(int i = 0: i < 100: i++) { pqi.push(rand() % 25): copy(pqi .beginO. pqi.endO,

ostream iterator<int>(cout. )): cout \n-----\n :

pqi.sortО:

copy(pqi .beginO. pqi.endO.

ostream iterator<int>(cout. )): cout \n.....\n :