std::sort_heap
| Défini dans l'en-tête <algorithm>
|
||
template< class RandomIt >
void sort_heap( RandomIt first, RandomIt last );
|
(1) | (constexpr depuis C++20) |
template< class RandomIt, class Compare >
void sort_heap( RandomIt first, RandomIt last, Compare comp );
|
(2) | (constexpr depuis C++20) |
Convertit le tas [first, last) en une plage triée. La propriété de tas n'est plus maintenue.
operator<(jusqu'à C++20)std::less{}(depuis C++20), et sera trié selon operator<(jusqu'à C++20)std::less{}(depuis C++20).comp, et sera trié selon comp.Si l'une des conditions suivantes est satisfaite, le comportement est indéfini :
[first,last)n'est pas un tas.
|
(jusqu'à C++11) |
|
(depuis C++11) |
Paramètres
| first, last | - | la paire d'itérateurs définissant la plage du tas binaire des éléments à transformer en plage triée |
| comp | - |
objet fonction de comparaison (c'est-à-dire un objet qui satisfait aux exigences de
Compare
) qui renvoie
true
si le premier argument est
inférieur
au second.
La signature de la fonction de comparaison doit être équivalente à ce qui suit : bool cmp ( const Type1 & a, const Type2 & b ) ;
Bien que la signature n'ait pas besoin d'avoir
const
&
, la fonction ne doit pas modifier les objets qui lui sont passés et doit pouvoir accepter toutes les valeurs du type (éventuellement const)
|
| 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 ) :
Implémentation possible
| sort_heap (1) |
|---|
template<class RandomIt> void sort_heap(RandomIt first, RandomIt last) { while (first != last) std::pop_heap(first, last--); } |
| sort_heap (2) |
template<class RandomIt, class Compare> void sort_heap(RandomIt first, RandomIt last, Compare comp) { while (first != last) std::pop_heap(first, last--, comp); } |
Exemple
#include <algorithm> #include <iostream> #include <string_view> #include <vector> void println(std::string_view fmt, const auto& v) { for (std::cout << fmt; const auto &i : v) std::cout << i << ' '; 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: ", v); std::sort_heap(v.begin(), v.end()); println("after sort_heap, v: ", v); }
Sortie :
after make_heap, v: 9 4 5 1 1 3 after sort_heap, v: 1 1 3 4 5 9
Rapports de défauts
Les rapports de défauts modifiant le comportement suivants ont été appliqués rétroactivement aux normes C++ précédemment publiées.
| DR | Applicable à | Comportement publié | Comportement corrigé |
|---|---|---|---|
| LWG 2444 | C++98 | au plus N⋅log(N) comparaisons étaient autorisées | augmenté à 2N⋅log(N) |
Voir aussi
(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) |
|
| supprime le plus grand élément d'un tas max (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| ajoute un élément à un tas max (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
(C++20) |
transforme un tas max en une plage triée d'éléments (objet fonction d'algorithme) |