std::ranges::partial_sort_copy, std::ranges::partial_sort_copy_result

Definiert in Header `<algorithm>`
Aufrufsignatur
template< std::input_iterator I1, std::sentinel_for<I1> S1, std::random_access_iterator I2, std::sentinel_for<I2> S2, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::indirectly_copyable<I1, I2> && std::sortable<I2, Comp, Proj2> && std::indirect_strict_weak_order<Comp, std::projected<I1, Proj1>, std::projected<I2, Proj2>> constexpr partial_sort_copy_result<I1, I2> partial_sort_copy( I1 first, S1 last, I2 result_first, S2 result_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(1)	(seit C++20)
template< ranges::input_range R1, ranges::random_access_range R2, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::indirectly_copyable<ranges::iterator_t<R1>, ranges::iterator_t<R2>> && std::sortable<ranges::iterator_t<R2>, Comp, Proj2> && std::indirect_strict_weak_order<Comp, std::projected<ranges::iterator_t<R1>, Proj1>, std::projected<ranges::iterator_t<R2>, Proj2>> constexpr partial_sort_copy_result<ranges::borrowed_iterator_t<R1>, ranges::borrowed_iterator_t<R2>> partial_sort_copy( R1&& r, R2&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(2)	(seit C++20)
Hilfstypen
template< class I, class O > using partial_sort_copy_result = ranges::in_out_result<I, O>;	(3)	(seit C++20)

Kopiert die ersten N Elemente aus dem Quellbereich [first, last), als ob sie bezüglich comp und proj1 teilweise sortiert wären, in den Zielbereich [result_first, result_first + N), wobei $\scriptsize N = \min{(L_1, L_2)}$ $N = min(L₁, L₂)$ , $\scriptsize L_1$ $L₁$ gleich ranges::distance(first, last) ist und $\scriptsize L_2$ $L₂$ gleich ranges::distance(result_first, result_last) ist.

Die Reihenfolge gleicher Elemente ist nicht garantiert erhalten zu bleiben.

1) Die Elemente des Quellbereichs werden mittels des Funktionsobjekts proj1 projiziert, und die Zielelemente werden mittels des Funktionsobjekts proj2 projiziert.

2) Entspricht (1), verwendet aber r als Quellbereich und result_r als Zielbereich, als ob ranges::begin(r) als first, ranges::end(r) als last, ranges::begin(result_r) als result_first und ranges::end(result_r) als result_last verwendet würden.

Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell bekannt als Niebloids), das heißt:

Explizite Vorlagenargumentlisten können beim Aufruf keiner von ihnen angegeben werden.
Keine von ihnen ist für die argumentabhängige Suche sichtbar.
Wenn eine von ihnen durch normale unqualifizierte Suche als Name links vom Funktionsaufrufoperator gefunden wird, wird die argumentabhängige Suche unterbunden.

Parameter

first, last	-	das Iterator-Sentinel-Paar, das den Quell- Bereich der zu kopierenden Elemente definiert
r	-	der Quellbereich, von dem kopiert wird
result_first, result_last	-	das Iterator-Sentinel-Paar, das den Ziel- Bereich der Elemente definiert
result_r	-	der Zielbereich
comp	-	Vergleich, der auf die projizierten Elemente angewendet wird
proj1	-	Projektion, die auf die Elemente des Quellbereichs angewendet wird
proj2	-	Projektion, die auf die Elemente des Zielbereichs angewendet wird

Rückgabewert

Ein Objekt gleich { last, result_first + N } .

Komplexität

Höchstens $L₁•log(N)$ Vergleiche und $2•L₁•log(N)$ Projektionen.

Mögliche Implementierung

struct partial_sort_copy_fn
{
    template<std::input_iterator I1, std::sentinel_for<I1> S1,
             std::random_access_iterator I2, std::sentinel_for<I2> S2,
             class Comp = ranges::less, class Proj1 = std::identity,
             class Proj2 = std::identity>
    requires std::indirectly_copyable<I1, I2> && std::sortable<I2, Comp, Proj2> &&
             std::indirect_strict_weak_order<Comp, std::projected<I1, Proj1>,
             std::projected<I2, Proj2>>
    constexpr ranges::partial_sort_copy_result<I1, I2>
        operator()(I1 first, S1 last, I2 result_first, S2 result_last,
                   Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        if (result_first == result_last)
            return {std::move(ranges::next(std::move(first), std::move(last))),
                    std::move(result_first)};
        auto out_last{result_first};
        // kopiere die ersten N Elemente
        for (; !(first == last or out_last == result_last); ++out_last, ++first)
            *out_last = *first;
        // konvertiere N kopierte Elemente in einen Max-Heap
        ranges::make_heap(result_first, out_last, comp, proj2);
        // Verarbeite den restlichen Eingabebereich (falls vorhanden) unter Beibehaltung der Heap-Eigenschaft
        for (; first != last; ++first)
        {
            if (std::invoke(comp, std::invoke(proj1, *first),
                                  std::invoke(proj2, *result_first)))
            {
                // größtes Element entfernen und neu gefundenes kleineres einfügen
                ranges::pop_heap(result_first, out_last, comp, proj2);
                *(out_last - 1) = *first;
                ranges::push_heap(result_first, out_last, comp, proj2);
            }
        }
        // first N elements in the output range is still
        // ein Heap - wandeln Sie ihn in einen sortierten Bereich um
        ranges::sort_heap(result_first, out_last, comp, proj2);
        return {std::move(first), std::move(out_last)};
    }
    template<ranges::input_range R1, ranges::random_access_range R2,
             class Comp = ranges::less, class Proj1 = std::identity,
             class Proj2 = std::identity>
    requires std::indirectly_copyable<ranges::iterator_t<R1>, ranges::iterator_t<R2>> &&
             std::sortable<ranges::iterator_t<R2>, Comp, Proj2> &&
             std::indirect_strict_weak_order<Comp, std::projected<ranges::iterator_t<R1>,
             Proj1>, std::projected<ranges::iterator_t<R2>, Proj2>>
    constexpr ranges::partial_sort_copy_result<ranges::borrowed_iterator_t<R1>,
              ranges::borrowed_iterator_t<R2>>
        operator()(R1&& r, R2&& result_r, Comp comp = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r),
                       ranges::begin(result_r), ranges::end(result_r),
                       std::move(comp), std::move(proj1), std::move(proj2));
    }
};
inline constexpr partial_sort_copy_fn partial_sort_copy {};

Beispiel

Diesen Code ausführen

#include <algorithm>
#include <forward_list>
#include <functional>
#include <iostream>
#include <ranges>
#include <string_view>
#include <vector>
void print(std::string_view rem, std::ranges::input_range auto const& v)
{
    for (std::cout << rem; const auto& e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}
int main()
{
    const std::forward_list source{4, 2, 5, 1, 3};
    print("Write to the smaller vector in ascending order: ", "");
    std::vector dest1{10, 11, 12};
    print("const source list: ", source);
    print("destination range: ", dest1);
    std::ranges::partial_sort_copy(source, dest1);
    print("partial_sort_copy: ", dest1);
    print("Write to the larger vector in descending order:", "");
    std::vector dest2{10, 11, 12, 13, 14, 15, 16};
    print("const source list: ", source);
    print("destination range: ", dest2);
    std::ranges::partial_sort_copy(source, dest2, std::greater{});
    print("partial_sort_copy: ", dest2);
}

Ausgabe:

Write to the smaller vector in ascending order:
const source list: 4 2 5 1 3
destination range: 10 11 12
partial_sort_copy: 1 2 3
Write to the larger vector in descending order:
const source list: 4 2 5 1 3
destination range: 10 11 12 13 14 15 16
partial_sort_copy: 5 4 3 2 1 15 16

Siehe auch

ranges::partial_sort (C++20)	sortiert die ersten N Elemente einer Range (Algorithmus-Funktionsobjekt)
ranges::sort (C++20)	sortiert eine Range von Elementen (Algorithmus-Funktionsobjekt)
ranges::stable_sort (C++20)	sortiert eine Range von Elementen und behält die relative Reihenfolge zwischen äquivalenten Elementen bei (Algorithmus-Funktionsobjekt)
ranges::sort_heap (C++20)	wandelt einen Max-Heap in eine sortierte Range von Elementen um (Algorithmus-Funktionsobjekt)
ranges::make_heap (C++20)	erzeugt einen Max-Heap aus einer Range von Elementen (Algorithmus-Funktionsobjekt)
ranges::push_heap (C++20)	fügt ein Element zu einem Max-Heap hinzu (Algorithmus-Funktionsobjekt)
ranges::pop_heap (C++20)	entfernt das größte Element aus einem Max-Heap (Algorithmus-Funktionsobjekt)
partial_sort_copy	kopiert und sortiert eine Range von Elementen teilweise (Funktionstemplate)

Compiler-Unterstützung
Freestanding und gehostet
Sprache
Standardbibliothek
Standardbibliotheks-Header
Benannte Anforderungen
Feature-Test-Makros (C++20)
Sprachunterstützungsbibliothek
Konzepte-Bibliothek (C++20)
Diagnosebibliothek
Speicherverwaltungsbibliothek
Metaprogrammierungsbibliothek (C++11)
Allgemeine Dienstprogrammbibliothek
Container-Bibliothek
Iteratoren-Bibliothek
Bereiche-Bibliothek (C++20)
Algorithmenbibliothek
Zeichenkettenbibliothek
Textverarbeitungsbibliothek
Numerikbibliothek
Datums- und Zeitbibliothek
Ein-/Ausgabebibliothek
Dateisystembibliothek (C++17)
Nebenläufigkeitsunterstützungsbibliothek (C++11)
Ausführungssteuerungsbibliothek (C++26)
Technische Spezifikationen
Symbolindex
Externe Bibliotheken

de.cppreference.net

Namespaces

Variants