Daily bit(e) C++. std::priority_queue

Daily bit(e) C++ #234, адаптер контейнера упорядоченной очереди: std::priority_queue.

std::priority_queue – это адаптер контейнера, реализующий упорядоченную очередь, то есть очередь, в которой самый большой элемент всегда находится на вершине и извлекается первым.

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

#include <queue>
#include <iostream>
#include <iomanip>


std::priority_queue<int> queue;
// push() – операция O(logn)
queue.push(1);
queue.push(2);
queue.push(3);
queue.push(4);

// Печатает: 4 3 2 1
while (!queue.empty()) {
    // top() - это O(1)
    std::cout << queue.top() << " ";
    // pop() - это O(logn)
    queue.pop();
}
std::cout << "\n";

// Пример с пользовательским компаратором:
std::priority_queue<
    // Тип элемента
    std::string,
    // Базовый контейнер для использования
    std::vector<std::string>,
    // Пользовательский компаратор
    decltype([](const auto& left, const auto& right) {
        return left.length() > right.length();
    })> custom;

custom.push("a");
custom.push("aa");
custom.push("aaa");

// Печатает "a" "aa" "aaa"
while (!custom.empty()) {
    std::cout << std::quoted(custom.top()) << " ";
    custom.pop();
}
std::cout << "\n";

Открыть пример на Compiler Explorer.

Теги