std::pop_heap
| Défini dans l'en-tête <algorithm>
|
||
template< class RandomIt >
void pop_heap( RandomIt first, RandomIt last );
|
(1) | (constexpr depuis C++20) |
template< class RandomIt, class Compare >
void pop_heap( RandomIt first, RandomIt last, Compare comp );
|
(2) | (constexpr depuis C++20) |
Échange la valeur à la position first et la valeur à la position last - 1 et transforme la sous-plage [first, last - 1) en un tas. Cela a pour effet de supprimer le premier élément du tas [first, last).
[first, last) est un tas par rapport à operator<(jusqu'à C++20)std::less{}(depuis C++20).[first, last) est un tas par rapport à comp.Si l'une des conditions suivantes est satisfaite, le comportement est indéfini :
[first,last)est vide.[first,last)n'est pas un tas par rapport au comparateur correspondant.
|
(jusqu'à C++11) |
|
(depuis C++11) |
Paramètres
| first, last - | la paire d'itérateurs définissant la plage de tas binaire non vide des éléments à modifier (extraire l'élément racine) | la paire d'itérateurs définissant la plage de tas binaire non vide des éléments à modifier (extraire l'élément racine)plage des éléments à modifier (extraire l'élément racine) |
| comp - | objet fonction de comparaison (c'est-à-dire un objet qui satisfait aux exigences de | Compare) qui renvoie truetrue si le premier argument est inférieur au second.La signature de la fonction de comparaison doit être équivalente à la suivante :
Bien que la signature n'ait pas besoin d'avoir |
| Exigences de type | ||
-RandomIt doit satisfaire aux exigences de LegacyRandomAccessIterator.
| ||
-Compare doit satisfaire aux exigences de Compare.
| ||
Complexité
Étant donné N comme std::distance(first, last):
operator<(jusqu'à C++20)std::less{}(depuis C++20).comp.Exemple
#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);
}
Sortie :
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
Rapports de défauts
Les rapports de défauts suivants, modifiant le comportement, ont été appliqués rétroactivement aux normes C++ publiées précédemment.
| DR | Appliqué à | Comportement publié | Comportement corrigé |
|---|---|---|---|
| LWG 1205 | C++98 | le comportement n'était pas clair si [first, last) est vide
|
le comportement est indéfini dans ce cas |
Voir aussi
| ajoute un élément à un tas max (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
(C++11) |
vérifie si la plage donnée est un tas max (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
(C++11) |
trouve la plus grande sous-plage qui est un tas max (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
| crée un tas max à partir d'une plage d'éléments (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| transforme un tas max en une plage d'éléments triés par ordre croissant (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
(C++20) |
supprime le plus grand élément d'un tas max (algorithme objet fonction) |