Namespaces
Variants

std:: priority_queue

From cppreference.net
C++
Containers library
std::priority_queue
Definido en el encabezado <queue>
template <

class T,
class Container = std:: vector < T > ,
class Compare = std:: less < typename Container :: value_type >

> class priority_queue ;

La cola de prioridad es un adaptador de contenedor que proporciona búsqueda en tiempo constante del elemento más grande (por defecto), a costa de inserción y extracción logarítmicas.

Se puede proporcionar un Compare definido por el usuario para cambiar el orden, por ejemplo, usando std:: greater < T > haría que el elemento más pequeño apareciera como el top() .

Trabajar con una priority_queue es similar a gestionar un heap en algún contenedor de acceso aleatorio, con la ventaja de no poder invalidar accidentalmente el heap.

Todas las funciones miembro de std::priority_queue son constexpr : es posible crear y utilizar objetos std::priority_queue en la evaluación de una expresión constante.

Sin embargo, los objetos std::priority_queue generalmente no pueden ser constexpr , porque cualquier almacenamiento asignado dinámicamente debe liberarse en la misma evaluación de la expresión constante.

(since C++26)

Contenidos

Parámetros de plantilla

T - El tipo de los elementos almacenados. El programa está mal formado si T no es del mismo tipo que Container::value_type .
Container - El tipo del contenedor subyacente utilizado para almacenar los elementos. El contenedor debe satisfacer los requisitos de SequenceContainer , y sus iteradores deben satisfacer los requisitos de LegacyRandomAccessIterator . Adicionalmente, debe proporcionar las siguientes funciones con la semántica habitual :

Los contenedores estándar std::vector (sin incluir std::vector<bool> ) y std::deque satisfacen estos requisitos.

Compare - Un tipo Compare que proporciona un ordenamiento débil estricto.

Nótese que el parámetro Compare está definido de modo que devuelve true si su primer argumento viene antes que su segundo argumento en un ordenamiento débil. Pero debido a que la cola de prioridad emite los elementos más grandes primero, los elementos que "vienen antes" en realidad se emiten al final. Es decir, el frente de la cola contiene el "último" elemento según el ordenamiento débil impuesto por Compare .

Tipos de miembros

Tipo de miembro Definición
container_type Container
value_compare Compare
value_type Container::value_type
size_type Container :: size_type
reference Container::reference
const_reference Container::const_reference

Objetos miembro

Nombre del miembro Definición
Container c
el contenedor subyacente
(objeto miembro protegido)
Compare comp
el objeto función de comparación
(objeto miembro protegido)

Funciones miembro

construye el priority_queue
(función miembro pública)
destruye el priority_queue
(función miembro pública)
asigna valores al adaptador de contenedor
(función miembro pública)
Acceso a elementos
accede al elemento superior
(función miembro pública)
Capacidad
comprueba si el adaptador de contenedor está vacío
(función miembro pública)
devuelve el número de elementos
(función miembro pública)
Modificadores
inserta elemento y ordena el contenedor subyacente
(función miembro pública)
(C++23)
inserta un rango de elementos y ordena el contenedor subyacente
(función miembro pública)
(C++11)
construye elemento in-situ y ordena el contenedor subyacente
(función miembro pública)
elimina el elemento superior
(función miembro pública)
(C++11)
intercambia los contenidos
(función miembro pública)

Funciones no miembro

(C++11)
especializa el algoritmo std::swap
(plantilla de función)

Clases auxiliares

(C++11)
especializa el rasgo de tipo std::uses_allocator
(especialización de plantilla de clase)
(C++23)
soporte de formato para std::priority_queue
(especialización de plantilla de clase)

Guías de deducción

(desde C++17)

Notas

Macro de prueba de características Valor Estándar Característica
__cpp_lib_containers_ranges 202202L (C++23) Construcción e inserción compatibles con rangos para contenedores
__cpp_lib_constexpr_queue 202502L (C++26) constexpr std::priority_queue

Ejemplo

Ejecutar este código 
#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("data", data);
    std::priority_queue<int> max_priority_queue;
    // Llenar 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 máxima actúe como una cola de prioridad mínima.
    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 forma de definir una cola de prioridad mínima.
    std::priority_queue min_priority_queue2(data.begin(), data.end(), std::greater<int>());
    pop_println("min_priority_queue2", min_priority_queue2);
    // Usando un objeto de 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 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: 

data: 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 que modifican el comportamiento se aplicaron retroactivamente a los estándares publicados anteriormente de C++.

DR Se aplica a Comportamiento publicado Comportamiento correcto
LWG 307 C++98 Container no podía ser std::vector<bool> permitido
LWG 2566 C++98 Faltaba el requisito para Container::value_type mal formado si T no es del mismo tipo que Container::value_type
LWG 2684 C++98 priority_queue toma un comparador
pero carecía de typedef miembro para él 		añadido

Véase también

matriz contigua redimensionable
(class template)
bitset dinámico eficiente en espacio
(class template specialization)
cola de doble extremo
(class template)