std::priority_queue
De cppreference.com
<tbody>
</tbody>
| 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:
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 |
Tipos miembro
| Tipo 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 de 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 contenedor priority_queue. (función miembro pública) | |
Destruye el contenedor priority_queue. (función miembro pública) | |
| Asigna valores al adaptador de contenedor. (función miembro pública) | |
Acceso a elementos | |
| Accede al elemento en la parte superior. (función miembro pública) | |
Capacidad | |
| Comprueba si el contenedor subyacente está vacío. (función miembro pública) | |
| Devuelve el número de elementos. (función miembro pública) | |
Modificadores | |
| Encola un 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) |
Encola el elemento en el sitio y ordena el contenedor subyacente. (función miembro pública) |
| Desencola el elemento en la parte superior de la cola de prioridad. (función miembro pública) | |
(C++11) |
Intercambia el contenido. (función miembro pública) |
Funciones no miembro
| Especializa el algoritmo std::swap. (plantilla de función) |
Clases auxiliares
| Especializa el rasgo de tipo std::uses_allocator. (plantilla de función) | |
Apoyo 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ística | Valor | Estándar | Comentario |
|---|---|---|---|
__cpp_lib_containers_ranges |
202202L |
(C++23) | Construcción e inserción de rangos para contenedores. |
Ejemplo
Ejecuta 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("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 queContainer::value_type.
|
| LWG 2684 | C++98 | priority_queue toma un comparador pero le faltaba unadefinición de tipo miembro ( typedef).
|
Se le agregó. |
Véase también
| Array dinámico contiguo. (plantilla de clase) | |
| Conjunto de bits eficiente en el uso de espacio. (plantilla de clase) | |
Cola doblemente terminada (deque). (plantilla de clase) |