std::priority_queue — cppreference.com

Материал из cppreference.com

Определено в заголовочном файле `<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 объект-элемент)

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

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

Примечание

Макрос тест функциональности	Значение	Стандарт	Комментарий
`__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	добавлено

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

Категории: