std::make_heap
De fr.cppreference.net
| Défini dans l'en-tête <algorithm>
|
||
template< class RandomIt >
void make_heap( RandomIt first, RandomIt last );
|
(1) | (constexpr depuis C++20) |
template< class RandomIt, class Compare >
void make_heap( RandomIt first, RandomIt last, Compare comp );
|
(2) | (constexpr depuis C++20) |
Construit un tas dans la plage [first, last).
1) Le tas construit est par rapport à
operator<(jusqu'à C++20)std::less{}(depuis C++20).2) Le tas construit est par rapport à
comp.Si l'une des conditions suivantes est satisfaite, le comportement est indéfini :
|
(jusqu'à C++11) |
|
(depuis C++11) |
Paramètres
| first, last | - | la paire d'itérateurs définissant la plage d'éléments à transformer en tas binaire |
| comp | - | objet fonction de comparaison (c'est-à-dire un objet qui satisfait les exigences de Compare) qui retourne truetrue si le premier argument est inférieurau second.
La signature de la fonction de comparaison doit être équivalente à la suivante :
|
| puisse être déréférencé et ensuite implicitement converti vers les deux. | ||
Exigences de type
RandomIt- doit satisfaire les exigences de LegacyRandomAccessIterator | ||
.
Compare- doit satisfaire les exigences de Compare | ||
.
Complexité\(\scriptsize N\)Nstd::distance(first, last) comme
:
1)\(\scriptsize 3N\)3N
operator< comparaisons utilisant std::less{}(jusqu'à C++20)(depuis C++20).2)\(\scriptsize 3N\)3N
comp applications de la fonction de comparaison .
Exemple
#include <algorithm>
#include <functional>
#include <iostream>
#include <string_view>
#include <vector>
void print(std::string_view text, const std::vector<int>& v = {})
{
std::cout << text << ": ";
for (const auto& e : v)
std::cout << e << ' ';
std::cout << '\n';
}
int main()
{
print("Max heap");
std::vector<int> v{3, 2, 4, 1, 5, 9};
print("initially, v", v);
std::make_heap(v.begin(), v.end());
print("after make_heap, v", v);
std::pop_heap(v.begin(), v.end());
print("after pop_heap, v", v);
auto top = v.back();
v.pop_back();
print("former top element", {top});
print("after removing the former top element, v", v);
print("\nMin heap");
std::vector<int> v1{3, 2, 4, 1, 5, 9};
print("initially, v1", v1);
std::make_heap(v1.begin(), v1.end(), std::greater<>{});
print("after make_heap, v1", v1);
std::pop_heap(v1.begin(), v1.end(), std::greater<>{});
print("after pop_heap, v1", v1);
auto top1 = v1.back();
v1.pop_back();
print("former top element", {top1});
print("after removing the former top element, v1", v1);
}
Exécuter ce code
Max heap:
initially, v: 3 2 4 1 5 9
after make_heap, v: 9 5 4 1 2 3
after pop_heap, v: 5 3 4 1 2 9
former top element: 9
after removing the former top element, v: 5 3 4 1 2
Min heap:
initially, v1: 3 2 4 1 5 9
after make_heap, v1: 1 2 4 3 5 9
after pop_heap, v1: 2 3 4 9 5 1
former top element: 1
after removing the former top element, v1: 2 3 4 9 5
Sortie :
Rapports de défauts
| Les rapports de défauts suivants, modifiant le comportement, ont été appliqués rétroactivement aux normes C++ précédemment publiées. | DR | Appliqué à | Comportement tel que publié |
|---|---|---|---|
| Comportement correct | LWG 3032 | C++98
[first, last)les éléments de |
n'étaient pas tenus d'être Swappable |
requis
is_heap |
(C++11) vérifie si la plage donnée est un tas max&(modèle de fonction |
ranges::is_heap |
|
is_heap_until |
(C++11) trouve la plus grande sous-plage qui est un tas max&(modèle de fonction |
ranges::is_heap_until |
|
| push_heap ajoute un élément à un tas max&(modèle de fonction | |
ranges::push_heap |
|
| pop_heap retire le plus grand élément d'un tas max&(modèle de fonction | |
ranges::pop_heap |
|
| sort_heap transforme un tas max en une plage d'éléments triés par ordre croissant&(modèle de fonction | |
ranges::sort_heap |
|
| priority_queue adapte un conteneur pour fournir une file de priorité | |
ranges::make_heap |
(C++20) crée un tas max à partir d'une plage d'éléments |