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.
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
:
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
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
Miembro
Descripción
Contenedor c
el contenedor subyacente (objeto miembro protegido)
Comparar comp
el objeto función de comparación (objeto miembro protegido)
#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(constauto& e : v)std::cout<< e <<' ';std::cout<<'\n';}int main(){constauto 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()(constint l, constint 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);}