std::pop_heap
| Definido en el encabezado <algorithm>
|
||
template< class RandomIt >
void pop_heap( RandomIt first, RandomIt last );
|
(1) | (constexpr desde C++20) |
template< class RandomIt, class Compare >
void pop_heap( RandomIt first, RandomIt last, Compare comp );
|
(2) | (constexpr desde C++20) |
Intercambia el valor en la posición first y el valor en la posición last - 1 y convierte el subrango [first, last - 1) en un montículo. Esto tiene el efecto de eliminar el primer elemento del montículo [first, last).
[first, last) es un montículo con respecto a operator<(hasta C++20)std::less{}(desde C++20).[first, last) es un montículo con respecto a comp.Si se cumple alguna de las siguientes condiciones, el comportamiento no está definido:
[first,last)está vacío.[first,last)no es un montículo con respecto al comparador correspondiente.
|
(hasta C++11) |
|
(desde C++11) |
Parámetros
| first, last | - | el par de iteradores que definen el rango del montículo binario no vacío de elementos a modificar (extraer elemento raíz) |
| comp | - | objeto función de comparación (es decir, un objeto que satisface los requisitos de Compare) que devuelve true si el primer argumento es menor que el segundo.La firma de la función de comparación debe ser equivalente a la siguiente:
Aunque la firma no necesita tener |
| Requisitos de tipo | ||
-RandomIt debe cumplir los requisitos de LegacyRandomAccessIterator.
| ||
-Compare debe cumplir los requisitos de Compare.
| ||
Complejidad
Dado N como std::distance(first, last):
operator<(hasta C++20)std::less{}(desde C++20).comp.Ejemplo
#include <algorithm>
#include <iostream>
#include <string_view>
#include <type_traits>
#include <vector>
void println(std::string_view rem, const auto& v)
{
std::cout << rem;
if constexpr (std::is_scalar_v<std::decay_t<decltype(v)>>)
std::cout << v;
else
for (int e : v)
std::cout << e << ' ';
std::cout << '\n';
}
int main()
{
std::vector<int> v{3, 1, 4, 1, 5, 9};
std::make_heap(v.begin(), v.end());
println("after make_heap: ", v);
std::pop_heap(v.begin(), v.end()); // moves the largest to the end
println("after pop_heap: ", v);
int largest = v.back();
println("largest element: ", largest);
v.pop_back(); // actually removes the largest element
println("after pop_back: ", v);
}
Salida:
after make_heap: 9 5 4 1 1 3
after pop_heap: 5 3 4 1 1 9
largest element: 9
after pop_back: 5 3 4 1 1
Informes de defectos
Los siguientes informes de defectos que cambian el comportamiento se aplicaron retroactivamente a los estándares C++ previamente publicados.
| DR | Aplicado a | Comportamiento publicado | Comportamiento correcto |
|---|---|---|---|
| LWG 1205 | C++98 | el comportamiento no estaba claro si [first, last) está vacío
|
el comportamiento no está definido en este caso |
Véase también
| añade un elemento a un montículo máximo (plantilla de función & objeto función de algoritmo) | |
(C++20) |
|
(C++11) |
comprueba si el rango dado es un montículo máximo (plantilla de función & objeto función de algoritmo) |
(C++20) |
|
(C++11) |
encuentra el subrango más grande que es un montículo máximo (plantilla de función & objeto función de algoritmo) |
(C++20) |
|
| crea un montículo máximo a partir de un rango de elementos (plantilla de función & objeto función de algoritmo) | |
(C++20) |
|
| convierte un montículo máximo en un rango de elementos ordenados en orden ascendente (plantilla de función & objeto función de algoritmo) | |
(C++20) |
|
(C++20) |
elimina el elemento más grande de un montículo máximo (objeto función de algoritmo) |