std::ranges::sort_heap

 

C++

Compiler-Unterstützung

Freestanding und gehostet

Sprache

Standardbibliothek

Header der Standardbibliothek

Benannte Anforderungen

Feature-Test-Makros (C++20)

Bibliothek für Sprachunterstützung

Konzepte-Bibliothek (C++20)

Diagnostik-Bibliothek

Speicherverwaltungsbibliothek

Metaprogrammierungsbibliothek (C++11)

Allgemeine Dienstprogramme-Bibliothek

Container-Bibliothek

Iterator-Bibliothek

Ranges-Bibliothek (C++20)

Algorithmen-Bibliothek

Bibliothek für Zeichenketten

Textverarbeitungsbibliothek

Numerik-Bibliothek

Datums- und Zeitbibliothek

Ein-/Ausgabe-Bibliothek

Dateisystembibliothek (C++17)

Unterstützung für nebenläufige Programmierung (C++11)

Ausführungssteuerungsbibliothek (C++26)

Technische Spezifikationen

Symbolverzeichnis

Externe Bibliotheken

 

Algorithmenbibliothek

Beschränkte Algorithmen und Algorithmen für Bereiche (C++20)
Beschränkte Algorithmen, z.B. ranges::copy, ranges::sort, ...
Ausführungsrichtlinien (C++17)
is_execution_policy (C++17)   execution::seqexecution::parexecution::par_unseqexecution::unseq (C++17)    (C++17)(C++17)(C++20)	execution::sequenced_policyexecution::parallel_policyexecution::parallel_unsequenced_policyexecution::parallel_unsequenced (C++17)(C++17)(C++17)(C++20)
Nicht-modifizierende Sequenzoperationen Stapeloperationen for_each for_each_n (C++17) Suchoperationen all_ofany_ofnone_of (C++11)                (C++11)(C++11) countcount_if mismatch equal findfind_iffind_if_not (C++11) find_end find_first_of adjacent_find search search_n Modifizierende Sequenzoperationen Kopieroperationen copycopy_if (C++11) copy_backward copy_n (C++11) move (C++11) move_backward (C++11) Tauschoperationen swap iter_swap swap_ranges Transformationsoperationen replacereplace_if transform replace_copyreplace_copy_if Generierungsoperationen fill fill_n generate generate_n Entfernungsoperationen removeremove_if unique remove_copyremove_copy_if unique_copy Ordnungsändernde Operationen reverse reverse_copy rotate rotate_copy random_shuffleshuffle (bis C++17)(C++11) shift_leftshift_right (C++20)(C++20) Stichprobenoperationen sample (C++17)	Sortier- und verwandte Operationen Partitionierungsoperationen partition partition_copy (C++11)   stable_partition is_partitioned (C++11) partition_point (C++11) Sortieroperationen sort stable_sort partial_sort partial_sort_copy is_sorted (C++11) is_sorted_until (C++11) nth_element Binäre Suchoperationen (auf partitionierten Bereichen) lower_bound upper_bound equal_range binary_search Mengenoperationen (auf sortierten Bereichen) includes set_union set_intersection set_difference set_symmetric_difference Zusammenführungsoperationen (auf sortierten Bereichen) merge inplace_merge Heapoperationen push_heap pop_heap make_heap sort_heap is_heap (C++11) is_heap_until (C++11) Minimum/Maximum-Operationen max min minmax (C++11) clamp (C++17) max_element min_element minmax_element (C++11) Lexikographische Vergleichsoperationen lexicographical_compare lexicographical_compare_three_way (C++20) Permutationsoperationen next_permutation prev_permutation is_permutation (C++11) C-Bibliothek qsort bsearch
Numerische Operationen
iota (C++11) inner_product adjacent_difference    accumulate reduce (C++17) transform_reduce (C++17)	partial_sum inclusive_scan (C++17)    exclusive_scan (C++17) transform_inclusive_scan (C++17) transform_exclusive_scan (C++17)
Operationen auf uninitialisiertem Speicher
uninitialized_copy uninitialized_move (C++17)    uninitialized_fill uninitialized_copy_n (C++11) uninitialized_move_n (C++17) uninitialized_fill_n	destroy (C++17) destroy_n (C++17) destroy_at (C++17) construct_at (C++20)       uninitialized_default_construct (C++17) uninitialized_value_construct (C++17) uninitialized_default_construct_n (C++17) uninitialized_value_construct_n (C++17)

 

Eingeschränkte Algorithmen

Alle Namen in diesem Menü gehören zum Namespace std::ranges

Nicht-modifizierende Sequenzoperationen

all_ofany_ofnone_of for_each for_each_n    countcount_if adjacent_find mismatch equal lexicographical_compare    containscontains_subrange (C++23)(C++23) findfind_iffind_if_not find_lastfind_last_iffind_last_if_not (C++23)(C++23)(C++23)   find_end find_first_of search search_n starts_with (C++23) ends_with (C++23)

Modifizierende Sequenzoperationen

copycopy_if copy_n copy_backward    move move_backward shift_leftshift_right (C++23)(C++23)   fill fill_n generate generate_n    transform swap_ranges    shuffle sample removeremove_if replacereplace_if reverse rotate remove_copyremove_copy_if    unique replace_copyreplace_copy_if reverse_copy rotate_copy unique_copy

Partitionierungsoperationen

is_partitioned    partition_point    partition    partition_copy    stable_partition

Sortieroperationen

is_sorted is_sorted_until     sort stable_sort         partial_sort       nth_element partial_sort_copy

Binäre Suchoperationen (auf sortierten Bereichen)

lower_bound         upper_bound         binary_search      equal_range

Mengenoperationen (auf sortierten Bereichen)

merge inplace_merge       set_difference set_intersection    set_union          includes set_symmetric_difference

Heapoperationen

is_heap is_heap_until       make_heap           sort_heap push_heap pop_heap

Minimum/Maximum-Operationen

max max_element         min min_element         minmax minmax_element     clamp

Permutationsoperationen

is_permutation      next_permutation    prev_permutation

Faltoperationen

fold_left (C++23) fold_left_first (C++23)   fold_right (C++23) fold_right_last (C++23)   fold_left_with_iter (C++23) fold_left_first_with_iter (C++23)

Numerische Operationen iota (C++23)             Zufallszahlengenerierung generate_random (C++26)

Operationen auf uninitialisiertem Speicher

construct_at    destroy destroy_n destroy_at uninitialized_copy    uninitialized_move uninitialized_fill uninitialized_copy_n    uninitialized_move_n uninitialized_fill_n uninitialized_default_construct uninitialized_default_construct_n uninitialized_value_construct uninitialized_value_construct_n

Rückgabetypen

in_fun_result in_in_result in_found_result    in_out_result in_in_out_result    in_out_out_result    min_max_result out_value_result (C++23) in_value_result (C++23)

 

Definiert in Header <algorithm>
Aufruf-Signatur
template< std::random_access_iterator I, std::sentinel_for<I> S,           class Comp = ranges::less, class Proj = std::identity >     erfordert std::sortable<I, Comp, Proj> constexpr I sort_heap( I first, S last, Comp comp = {}, Proj proj = {} );	(1)	(seit C++20)
template< ranges::random_access_range R,           class Comp = ranges::less, class Proj = std::identity >     erfordert std::sortable<ranges::iterator_t<R>, Comp, Proj> constexpr ranges::borrowed_iterator_t<R>     sort_heap( R&& r, Comp comp = {}, Proj proj = {} );	(2)	(seit C++20)

Sortiert die Elemente im angegebenen Bereich in Bezug auf comp und proj, wobei der Bereich ursprünglich einen Heap in Bezug auf comp und proj darstellt. Der sortierte Bereich behält die Heap-Eigenschaft nicht mehr bei.

1) Der angegebene Bereich ist [first, last).

2) Der angegebene Bereich ist r.

Wenn der angegebene Bereich kein Heap in Bezug auf comp und proj ist, ist das Verhalten undefiniert.

Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als niebloids bekannt), d.h.

• Können explizite Template-Argumentlisten bei keinem von ihnen angegeben werden.
• Keiner von ihnen ist für Argument-abhängige Suche sichtbar.
• Wenn einer von ihnen durch normale unqualifizierte Suche als Name links vom Funktionsaufrufoperator gefunden wird, wird die Argument-abhängige Suche unterdrückt.

Parameter

first, last	-	das Iterator-Sentinel-Paar, das den zu modifizierenden Bereich definiert
r	-	Der Bereich der zu ändernden Elemente
comp	-	Comparator, der auf die projizierten Elemente angewendet werden soll
proj	-	Projektion, die auf die Elemente angewendet wird

Rückgabewert

1) last

2) ranges::end(r)

Komplexität

Höchstens \(\scriptsize 2N \cdot \log(N)\)2N⋅log(N) Anwendungen von comp und \(\scriptsize 4N \cdot \log(N)\)4N⋅log(N) Anwendungen von proj, wobei \(\scriptsize N \)N die ist

1) ranges::distance(first, last)

2) ranges::distance(r)

Mögliche Implementierung

struct sort_heap_fn { template<std::random_access_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity> requires std::sortable<I, Comp, Proj> constexpr I operator()(I first, S last, Comp comp = {}, Proj proj = {}) const { auto ret{ranges::next(first, last)}; for (; first != last; --last) ranges::pop_heap(first, last, comp, proj); return ret; }   template<ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity> requires std::sortable<ranges::iterator_t<R>, Comp, Proj> constexpr ranges::borrowed_iterator_t<R> operator()(R&& r, Comp comp = {}, Proj proj = {}) const { return (*this)(ranges::begin(r), ranges::end(r), std::move(comp), std::move(proj)); } };   inline constexpr sort_heap_fn sort_heap{};

Beispiel

Führen Sie diesen Code aus

#include <algorithm>
#include <array>
#include <iostream>
 
void print(auto const& rem, const auto& v)
{
    std::cout << rem;
    for (const auto i : v)
        std::cout << i << ' ';
    std::cout << '\n';
}
 
int main()
{
    std::array v{3, 1, 4, 1, 5, 9};
    print("original array:  ", v);
 
    std::ranges::make_heap(v);
    print("after make_heap: ", v);
 
    std::ranges::sort_heap(v);
    print("after sort_heap: ", v);
}

Ausgabe

original array:  3 1 4 1 5 9
after make_heap: 9 5 4 1 1 3
after sort_heap: 1 1 3 4 5 9

Siehe auch

ranges::is_heap (C++20)	Prüft, ob der gegebene Bereich ein Max-Heap ist (Algorithmus-Funktionsobjekt)
ranges::is_heap_until (C++20)	Findet den größten Teilbereich, der ein Max-Heap ist (Algorithmus-Funktionsobjekt)
ranges::make_heap (C++20)	Erstellt aus einem Bereich von Elementen einen Max-Heap (Algorithmus-Funktionsobjekt)
ranges::pop_heap (C++20)	Entfernt das größte Element aus einem Max-Heap (Algorithmus-Funktionsobjekt)
ranges::push_heap (C++20)	Fügt ein Element zu einem Max-Heap hinzu (Algorithmus-Funktionsobjekt)
sort_heap	Verwandelt einen Max-Heap in einen aufsteigend sortierten Bereich von Elementen (Funktionstemplate)