std::priority_queue - cppreference.com

De cppreference.com

Definido en el archivo de encabezado `<queue>`
`template< class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type> > class priority_queue;`

La clase std::priority_queue o cola de prioridad, es un adaptador de contenedor que proporciona una búsqueda en tiempo constante del elemento mayor (por defecto), a expensas de la inserción y extracción logarítmicas.

Se puede suplementar un comparador Compare proporcionado por el usuario para cambiar el orden. Por ejemplo, el uso de std::greater<T> ocasionaría que el elemento más pequeño apareciera en la parte superior, top().

Trabajar con un contenedor priority_queue es similar a gestionar un montículo (heap) en algún contenedor de acceso aleatorio con el beneficio de no ser capaz de invalidar el montículo accidentalmente.

Parámetros de plantilla

T - El tipo de los elementos almacenados. El comportamiento no está definido si T no es el mismo tipo que Container::value_type.

Container

El tipo del contenedor subyacente a usar para almacenar los elementos. El contenedor debe satisfacer los requisitos de ContenedorDeSecuencia, y sus iteradores deben cumplir con los requisitos de IteradorDeAccesoAleatorioLegado. Además, debe proporcionar las siguientes funciones con la semántica habitual:

front(), p. ej., std::vector::front(),
push_back(), p. ej., std::deque::push_back(),
pop_back(), p. ej., std::vector::pop_back().

Los contenedores estándar std::vector y std::deque cumplen con estos requisitos.

Compare

Un tipo Comparar de comparación que proporciona un orden estricto débil.

Observa que el parámetro Comparar se define de manera tal que devuelve true si su primer argumento se encuentra antes que su segundo argumento en un orden débil. Pero como la cola de prioridad emite primero los elementos mayores, los elementos que "vienen antes" actualmente se emiten al último. Es decir, el frente de la cola contiene el "último" elemento de acuerdo al orden débil impuesto por Comparar.

Tipos miembro

Tipo miembro	Definición
`container_type`	`Container` [editar]
`value_compare`	`Compare`
`value_type`	`Container::value_type` [editar]
`size_type`	`Container::size_type` [editar]
`reference`	`Container::reference` [editar]
`const_reference`	`Container::const_reference` [editar]

Objetos miembro

Nombre de miembro	Definición
	El contenedor subyacente. (objeto miembro protegido) [editar]
	El objeto función de comparación. (objeto miembro protegido)

Funciones miembro

(constructor)	Construye el contenedor `priority_queue`. (función miembro pública) [editar]
(destructor)	Destruye el contenedor `priority_queue`. (función miembro pública) [editar]
operator=	Asigna valores al adaptador de contenedor. (función miembro pública) [editar]
Acceso a elementos
top	Accede al elemento en la parte superior. (función miembro pública) [editar]
Capacidad
empty	Comprueba si el contenedor subyacente está vacío. (función miembro pública) [editar]
size	Devuelve el número de elementos. (función miembro pública) [editar]
Modificadores
push	Encola un elemento y ordena el contenedor subyacente. (función miembro pública) [editar]
push_range (C++23)	Inserta un rango de elementos y ordena el contenedor subyacente. (función miembro pública) [editar]
emplace (C++11)	Encola el elemento en el sitio y ordena el contenedor subyacente. (función miembro pública) [editar]
pop	Desencola el elemento en la parte superior de la cola de prioridad. (función miembro pública) [editar]
swap (C++11)	Intercambia el contenido. (función miembro pública) [editar]

Funciones no miembro

Clases auxiliares

Notas

Macro de prueba de característica	Valor	Estándar	Comentario
`__cpp_lib_containers_ranges`	`202202L`	(C++23)	Construcción e inserción de rangos para contenedores.

Ejemplo

#include <functional>
#include <iostream>
#include <queue>
#include <string_view>
#include <vector>

template<typename T>
void pop_println(std::string_view rem, T& pq)
{
    std::cout << rem << ": ";
    for (; !pq.empty(); pq.pop())
        std::cout << pq.top() << ' ';
    std::cout << '\n';
}

template<typename T>
void println(std::string_view rem, const T& v)
{
    std::cout << rem << ": ";
    for (const auto& e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}

int main()
{
    const auto data = {1, 8, 5, 6, 3, 4, 0, 9, 7, 2};
    println("datos", data);

    std::priority_queue<int> max_priority_queue;

    // Poblar la cola de prioridad.
    for (int n : data)
        max_priority_queue.push(n);

    pop_println("max_priority_queue", max_priority_queue);

    // std::greater<int> hace que la cola de prioridad con
    // montículo de máximos actúe como una cola de prioridad
    // con montículo de mínimos.
    std::priority_queue<int, std::vector<int>, std::greater<int>>
        min_priority_queue1(data.begin(), data.end());

    pop_println("min_priority_queue1", min_priority_queue1);

    // Segunda manera de definir una cola de prioridad
    // con montículo de mínimos.
    std::priority_queue min_priority_queue2(data.begin(), data.end(), std::greater<int>());

    pop_println("min_priority_queue2", min_priority_queue2);

    // Usando un objeto función personalizado para comparar elementos.
    struct
    {
        bool operator()(const int l, const int r) const { return l > r; }
    } customLess;

    std::priority_queue custom_priority_queue(data.begin(), data.end(), customLess);

    pop_println("custom_priority_queue", custom_priority_queue);

    // Usando una lambda para comparar elementos.
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> lambda_priority_queue(cmp);

    for (int n : data)
        lambda_priority_queue.push(n);

    pop_println("lambda_priority_queue", lambda_priority_queue);
}

Salida:

datos: 1 8 5 6 3 4 0 9 7 2
max_priority_queue: 9 8 7 6 5 4 3 2 1 0
min_priority_queue1: 0 1 2 3 4 5 6 7 8 9
min_priority_queue2: 0 1 2 3 4 5 6 7 8 9
custom_priority_queue: 0 1 2 3 4 5 6 7 8 9
lambda_priority_queue: 8 9 6 7 4 5 2 3 0 1

Informes de defectos

Los siguientes informes de defectos de cambio de comportamiento se aplicaron de manera retroactiva a los estándares de C++ publicados anteriormente.

ID	Aplicado a	Comportamiento según lo publicado	Comportamiento correcto
LWG 307	C++98	`Container` no podía ser `std::vector<bool>`.	Se admite.
LWG 2566	C++98	Faltaba el requisito de `Container::value_type`.	Mal formado si `T` no es el mismo tipo que `Container::value_type`.
LWG 2684	C++98	`priority_queue` toma un comparador pero le faltaba una definición de tipo miembro (`typedef`).	Se le agregó.