Класс priority_queue: очередь с приоритетами

Класс priority_queue реализует очередь с приоритетами на основе последовательного контейнера. По умолчанию в качестве контейнера используется класс vector. При получении значения возвращается элемент с наивысшим приоритетом (наибольшим значением). По умолчанию для сравнения элементов используется функтор less. Объявление класса priority_queue выглядит следующим образом:

template<typename _Tp, typename _Sequence = vector<_Tp>,
         typename _Compare = less<typename _Sequence::value_type> >
   class priority_queue;

Прежде чем использовать класс, необходимо в начало программы добавить инструкцию:

#include <queue>

Создать экземпляр класса priority_queue можно следующими способами (полный список конструкторов смотрите в документации):

  • объявить переменную без инициализации. Для этого перед названием переменной указывается название класса, а после названия внутри угловых скобок задается тип данных. В этом случае очередь не содержит элементов. Пример объявления без инициализации, добавления элементов, получения и удаления элементов:
std::priority_queue<int> q;
q.push(4);                          // Добавляем элементы
q.push(2);
q.push(3);
while (!q.empty()) {
   std::cout << q.top() << ' ';     // Получаем значение
   q.pop();                         // Удаляем элемент
}
std::cout << std::endl;             // 4 3 2

Внутри угловых скобок после типа данных можно дополнительно указать тип контейнера и функцию сравнения. По умолчанию в качестве контейнера используется класс vector, а сравнение производится с помощью функтора less. Вместо класса vector можно использовать класс deque. Пример указания класса deque и функтора greater:

std::priority_queue<int, std::deque<int>,
                         std::greater<int> > q;
q.push(4);                          // Добавляем элементы
q.push(2);
q.push(3);
while (!q.empty()) {
   std::cout << q.top() << ' ';     // Получаем значение
   q.pop();                         // Удаляем элемент
}
std::cout << std::endl;             // 2 3 4
  • указать объект класса priority_queue внутри круглых скобок или после оператора = (можно создать копию объекта или переместить элементы):
std::priority_queue<int> q1;
q1.push(1); q1.push(2);
std::priority_queue<int> q2(q1);            // Копирование
std::cout << q1.size() << std::endl;        // 2
std::cout << q2.size() << std::endl;        // 2
std::priority_queue<int> q3(std::move(q1)); // Перемещение
std::cout << q3.size() << std::endl;        // 2
std::cout << q1.size() << std::endl;        // 0
  • указать диапазон внутри контейнера с помощью итераторов. В первом параметре передается итератор, указывающий на начало диапазона, а во втором параметре — итератор, указывающий на конец диапазона. Пример:
std::vector<int> arr = {1, 2, 3};
std::priority_queue<int> q(arr.begin(), arr.end());
while (!q.empty()) {
   std::cout << q.top() << ' ';
   q.pop();
}
std::cout << std::endl; // 3 2 1

Вместо итератора можно передать указатель. Создадим очередь на основе обычного массива:

const int ARR_SIZE = 3;
int arr[ARR_SIZE] = {1, 2, 3};
std::priority_queue<int> q(arr, arr + ARR_SIZE);
while (!q.empty()) {
   std::cout << q.top() << ' ';
   q.pop();
}
std::cout << std::endl; // 3 2 1

С помощью оператора = можно создать копию или переместить элементы:

std::vector<int> arr = {1, 2, 3};
std::priority_queue<int> q1(arr.begin(), arr.end()), q2;
q2 = q1;                             // Копирование
std::cout << q1.size() << std::endl; // 3
std::cout << q2.size() << std::endl; // 3
q2 = std::move(q1);                  // Перемещение
std::cout << q2.size() << std::endl; // 3
std::cout << q1.size() << std::endl; // 0

Класс priority_queue содержит следующие методы:

  • size() — возвращает количество элементов в очереди. Прототип метода:
size_type size() const;

Пример:

std::vector<int> arr = {1, 2, 3};
std::priority_queue<int> q(arr.begin(), arr.end());
std::cout << q.size() << std::endl; // 3
  • empty() — возвращает значение true, если очередь не содержит элементов, и false — в противном случае. Прототип метода:
bool empty() const;

Пример:

std::vector<int> arr = {1, 2, 3};
std::priority_queue<int> q1(arr.begin(), arr.end()), q2;
std::cout << std::boolalpha;
std::cout << q1.empty() << std::endl; // false
std::cout << q2.empty() << std::endl; // true
  • push() — добавляет элемент. Прототипы метода:
void push(const value_type &x);
void push(value_type &&x);

Пример:

std::priority_queue<int> q;
q.push(1); q.push(2); q.push(3);
while (!q.empty()) {
   std::cout << q.top() << ' ';
   q.pop();
}
std::cout << std::endl; // 3 2 1
  • emplace() — создает объект, передавая конструктору указанные через запятую значения, а затем добавляет объект в очередь:
class C {
public:
   int x, y;
   C(int a, int b) : x(a), y(b) { }
   bool operator<(const C &obj) const {
      return x < obj.x;
   }
};
// ... Фрагмент опущен ...
std::priority_queue<C> q;
q.emplace(10, 20); q.emplace(30, 40); q.emplace(50, 60);
while (!q.empty()) {
   std::cout << q.top().x << ' ';
   q.pop();
}
std::cout << std::endl; // 50 30 10
  • top() — возвращает константную ссылку на элемент с наивысшим приоритетом. Элемент из очереди не удаляется. Прототип метода:
const_reference top() const;
  • pop() — удаляет элемент с наивысшим приоритетом. Прототип метода:
void pop();

Пример:

std::priority_queue<int> q;
q.push(1); q.push(2); q.push(3);
std::cout << q.top() << std::endl; // 3
q.pop();
std::cout << q.top() << std::endl; // 2
  • swap() — меняет элементы двух контейнеров местами. Прототип метода:
void swap(priority_queue &q);

Пример:

std::priority_queue<int> q1, q2;
q1.push(1); q1.push(2); q1.push(3);
q2.push(4);
q1.swap(q2);
std::cout << q1.size() << std::endl;  // 1
std::cout << q2.size() << std::endl;  // 3

Учебник C++ (MinGW-W64)
Учебник C++ (MinGW-W64) в формате PDF

Помощь сайту

ЮMoney (Yandex-деньги): 410011140483022

ПАО Сбербанк:
Счет: 40817810855006152256
Реквизиты банка:
Наименование: СЕВЕРО-ЗАПАДНЫЙ БАНК ПАО СБЕРБАНК
Корреспондентский счет: 30101810500000000653
БИК: 044030653
КПП: 784243001
ОКПО: 09171401
ОКОНХ: 96130
Скриншот реквизитов