std::priority_queue

 

C++

Поддержка компилятором

Автономные и размещённые реализации

Язык

Стандартная библиотека

Заголовки стандартной библиотеки

Требования к именованию

Макросы тестирования функциональности (C++20)

Поддержка языка

Библиотека концептов (C++20)

Библиотека метапрограммирования (C++11)

Библиотека диагностики

Библиотека общих утилит

Библиотека строк

Библиотека контейнеров

Библиотека итераторов

Библиотека диапазонов (C++20)

Библиотека алгоритмов

Библиотека численных данных

Библиотека ввода/вывода

Библиотека локализаций

Регулярные выражения (C++11)

Атомарные операции (C++11)

Библиотека поддержки конкуренции (C++11)

Библиотека файловой системы (C++17)

Технические спецификации

Указатель символов

Внешние библиотеки

 

Библиотека контейнеров

Последовательные

array (C++11)

vector

vector<bool>

deque

forward_list (C++11)

list

Ассоциативные

set

multiset

map

multimap

Неупорядоченные ассоциативные

unordered_set (C++11)

unordered_multiset (C++11)

unordered_map (C++11)

unordered_multimap (C++11)

Адаптеры

stack

queue

priority_queue

flat_set (C++23)

flat_multiset (C++23)

flat_map (C++23)

flat_multimap (C++23)

Представления

span (C++20)

mdspan (C++23)

Недействительные итераторы

Таблица функций-элементов

Таблица функций, не являющихся элементами

 

std::priority_queue

Функции-элементы

priority_queue::priority_queue

priority_queue::~priority_queue

priority_queue::operator=

Доступ к элементам

priority_queue::top

Ёмкость

priority_queue::empty

priority_queue::size

Модификаторы

priority_queue::push

priority_queue::push_range (C++23)

priority_queue::emplace (C++11)

priority_queue::pop

priority_queue::swap (C++11)

Функции, не являющиеся элементами

std::swap (C++11)

Принципы вывода (C++17)

Вспомогательные классы

std::uses_allocator (C++11)

 

Определено в заголовочном файле <queue>
template<     class T,     class Container = std::vector<T>,     class Compare = std::less<typename Container::value_type> > class priority_queue;

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

Может быть предоставлен пользовательский Compare для изменения порядка, например использование std::greater<T> приведёт к тому, что наименьший элемент будет отображаться как top().

Работа с priority_queue аналогична управлению кучей в некотором контейнере с произвольным доступом, с тем преимуществом, что невозможно случайно повредить кучу.

Параметры шаблона

T	—	Тип хранимых элементов. Поведение неопределено, если T не того же типа, что и Container::value_type.
Container	—	Тип базового контейнера, используемого для хранения элементов. Контейнер должен соответствовать требованиям SequenceContainer, а его итераторы должны соответствовать требованиям LegacyRandomAccessIterator. Кроме того, он должен предоставлять следующие функции с обычной семантикой: front() push_back() pop_back() Стандартные контейнеры std::vector (включая std::vector<bool>) и std::deque соответствуют этим требованиям.
Compare	—	Тип Compare задающий строгий слабый порядок. Обратите внимание, что параметр Compare определён таким образом, что он возвращает true если его первый аргумент идёт перед вторым аргументом в слабом порядке. Но поскольку очередь с приоритетами возвращает самые большие элементы первыми, элементы, которые "идут раньше", фактически возвращаются последними. То есть, передняя часть очереди содержит "последний" элемент, в соответствии со слабым порядком, заданным Compare.

Типы элементы

Тип элемент	Определение
container_type	Container
value_compare	Compare
value_type	Container::value_type
size_type	Container::size_type
reference	Container::reference
const_reference	Container::const_reference

Функции-элементы

(конструктор)	создаёт priority_queue (public функция-элемент)
(деструктор)	уничтожает priority_queue (public функция-элемент)
operator=	присваивает значения адаптеру контейнера (public функция-элемент)
Доступ к элементам
top	предоставляет доступ к элементу на вершине (public функция-элемент)
Ёмкость
empty	проверяет, пуст ли базовый контейнер (public функция-элемент)
size	возвращает количество элементов (public функция-элемент)
Модификаторы
push	вставляет элемент и сортирует базовый контейнер (public функция-элемент)
push_range (C++23)	вставляет диапазон элементов и сортирует базовый контейнер (public функция-элемент)
emplace (C++11)	создаёт элемент на месте и сортирует базовый контейнер (public функция-элемент)
pop	удаляет элемент с вершины (public функция-элемент)
swap (C++11)	обменивает содержимое (public функция-элемент)
Объекты элементы
Container c	базовый контейнер (protected объект-элемент)
Compare comp	объект функция сравнения (protected объект-элемент)

Функции, не являющиеся элементами

std::swap(std::priority_queue) (C++11)

специализация алгоритма std::swap (шаблон функции)

Вспомогательные классы

std::uses_allocator<std::priority_queue> (C++11)

специализирует свойство типа std::uses_allocator (специализация шаблона класса)

Правила вывода

(начиная с C++17)

Примечание

Макрос тест функциональности	Значение	Стандарт	Комментарий
__cpp_lib_containers_ranges	202202L	(C++23)	Создание и вставка контейнеров с учётом диапазонов

Пример

Запустить этот код

#include <functional>
#include <iostream>
#include <queue>
#include <string_view>
#include <vector>
 
template<typename T>
void print(std::string_view name, T const& q) {
    std::cout << name << ": \t";
    for (auto const& n : q)
        std::cout << n << ' ';
    std::cout << '\n';
}
 
template<typename Adaptor>
requires (std::ranges::input_range<typename Adaptor::container_type>)
void print(std::string_view name, const Adaptor& adaptor)
{
    struct Printer : Adaptor // для доступа к защищённому Adaptor::Container c;
    {
        void print(std::string_view name) const { ::print(name, this->c); }
    };
 
    static_cast<Printer const&>(adaptor).print(name);
}
 
int main() {
    const auto data = {1,8,5,6,3,4,0,9,7,2};
    print("data", data);
 
    std::priority_queue<int> q1; // Очередь с максимальным приоритетом
    for(int n : data)
        q1.push(n);
 
    print("q1", q1);
 
    // Очередь с минимальным приоритетом
    // std::greater<int> заставляет очередь с максимальным приоритетом
    // действовать как очередь с минимальным приоритетом
    std::priority_queue<int, std::vector<int>, std::greater<int>>
        minq1(data.begin(), data.end());
 
    print("minq1", minq1);
 
    // Второй способ определить очередь с минимальным приоритетом
    std::priority_queue minq2(data.begin(), data.end(), std::greater<int>());
 
    print("minq2", minq2);
 
    // Использование объекта пользовательской функции для сравнения элементов
    struct {
        bool operator() (const int l, const int r) const { return l > r; }
    } customLess;
    std::priority_queue minq3(data.begin(), data.end(), customLess);
 
    print("minq3", minq3);
 
    // Использование лямбда для сравнения элементов
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> q5(cmp);
 
    for(int n : data)
        q5.push(n);
 
    print("q5", q5);
}

Вывод:

data: 	1 8 5 6 3 4 0 9 7 2 
q1: 	9 8 7 6 5 4 3 2 1 0 
minq1: 	0 1 2 3 4 5 6 7 8 9 
minq2: 	0 1 2 3 4 5 6 7 8 9 
minq3: 	0 1 2 3 4 5 6 7 8 9 
q5: 	8 9 6 7 4 5 2 3 0 1

Отчёты о дефектах

Следующие изменения поведения были применены с обратной силой к ранее опубликованным стандартам C++:

Номер	Применён	Поведение в стандарте	Корректное поведение
LWG 2684	C++98	priority_queue принимает компаратор, но не имеет для него элемента typedef	добавлено

Смотрите также

vector	динамический непрерывный массив (шаблон класса)
vector<bool>	компактный динамический битовый набор (специализация шаблона класса)
deque	двусторонняя очередь (шаблон класса)