C++ за 21 день седьмое издание

Функции-члены класса priority_queue

Функции-члены f r o n t () и b a c k (), доступные в классе q u eu e, не доступны в классе

p r io r i ty _ q u e u e . Функции-члены класса p r i o r i t y _ q u e u e приведены в табл. 24.3. ТАБЛИЦА 24 .3. Функции-члены класса std: :priority_queue

Функция	Описание
push	Вставляет элемент в приоритетную очередь
pop	pqlntegers.push (10);
	Извлекает элемент из начала очереди, т.е. наибольший элемент
top	pqlntegers.pop ();
	Возвращ ает ссылку на наибольший элемент в очереди, занимающ ий также
	верхнюю позицию
	cout «	"The	largest element in the priority queue is: "
empty	«	pqlntegers.top ();
	Проверяет, не пуста ли приоритетная очередь; возвращ ает значение типа bool
	if (pqlntegers.empty ())
size	cout «		"The queue is empty!";
	Возвращ ает количество элементов в приоритетной очереди

size_t nNumElements = pqlntegers.size ();

556 ЗАНЯТИЕ 24. Адаптивные контейнеры: стек и очередь

Как свидетельствует таблица, к членам приоритетной очереди можно обратиться, толь­ ко используя метод to p (), возвращающий элемент с самым высоким значением, согласно заданному пользователем предикату или предикату s t d : :le s s < > при его отсутствии.

Вставка в конец и извлечение из начала приоритетной очереди с использованием методов push () и pop ()

Для вставки элементов в приоритетную очередь используется метод p u sh ():

pqlntegers.push (5); // элементы помещаются в отсортированном порядке

Извлечение, напротив, осуществляется с начала при помощи метода pop ():

pqlntegers.pop (); // извлечь элемент из начала

Использование методов класса p r io r i t y _ q u e u e представлено в листинге 24.6.

0. 
   И С ТИ Н Г 2 4 .6 . Работа с приоритетной очередью при помощи методов push ( ) ,top () и pop ()
   

1. 
   #include
   

2. 
   #include
   
0. 
   :
   

1. 
   int main ()
   

2. 
   {
   

3. 
   using namespace std;
   

0. 
   :
   

0. 
   priority_queue pqlntegers;
   

8: cout « "Inserting {10, 5, -1, 20} into the priority_queue"

1. 
   endl;
   

0. 
   pqlntegers.push (10);
   

0. 
   pqlntegers.push (5); // помещаются в отсортированном порядке
   

0. 
   pqlntegers.push (-1);
   

0. 
   pqlntegers.push (20);
   

13:


14: cout « "Deleting the " « pqlntegers.size () « " elements"

1. 
   endl;
   

0. 
   while (!pqlntegers.empty ())
   

0. 
   {
   

17: cout « "Deleting topmost element: " « pqlntegers.top ()

1. 
   endl;
   

0. 
   pqlntegers.pop ();
   

0. 
   }
   

2 0 :

0. 
   return 0;
   

22: }


Результат


Inserting {10, 5, -1, 20} into the priority_queue


Deleting the 4 elements


Deleting topmost element: 20


Deleting topmost element: 10


Deleting topmost element: 5


Deleting topmost element: -1

Использование класса priority_queue библиотеки STL

557

Анализ

Сначала код листинга 24.6 вставляет примеры целых чисел в приоритетную очередь (строки 9 -12), а затем извлекает элементы из его вершины, используя метод pop (), как показано в строке 18. Вывод демонстрирует, что вверху очереди доступен элемент с са­ мым большим значением. Поэтому применение метода p r i o r i t y q u e u e : :р о р () факти­ чески удаляет элемент, значение которого считается самым большим среди всех элементов

0. 
   контейнере. Его же предоставляет метод to p () как значение, находящееся на самом верху (строка 17). Если предикат установки приоритетов не задан, очередь автоматически сортирует элементы в порядке убыванию (самое высокое значение вверху).
   

Следующий пример в листинге 24.7 демонстрирует создание экземпляра класса p r i - o r ity _ q u e u e с предикатом s t d : : g r e a t e r < i n t > . При этом предикате у очереди приори­ тет имеет наименьшее число, как элемент с самым высоким значением, которое и будет доступно при помощи метода f r o n t ().

Л И СТИ Н Г 24-7. Создание экземпляра приоритетной очереди,

хранящей наименьш ее значение вверху______________________________________________________

0.