std::ranges::nth_element
Von cppreference.com
| 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 > |
(1) | (seit C++20) |
| template< ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity > |
(2) | (seit C++20) |
Ordnet die Elemente im Bereich [first, last) so um, dass
- Das Element, auf das von nth gezeigt wird, zu dem Element geändert wird, das an dieser Position auftreten würde, wenn
[first,last)mit Bezug auf comp und proj sortiert wäre. - Alle Elemente vor diesem neuen
nth-Element sind kleiner oder gleich den Elementen nach dem neuen nth-Element. Das heißt, für jeden Iterator i, j in den Bereichen[first,nth)bzw.[nth,last), wertet der Ausdruck std::invoke(comp, std::invoke(proj, *j), std::invoke(proj, *i)) zu false aus. - Wenn nth == last, hat die Funktion keine Auswirkung.
1) Elemente werden mit dem gegebenen binären Vergleichsfunktions-Objekt comp und dem Projektions-Objekt proj verglichen.
2) Dasselbe wie (1), verwendet aber r als Bereich, als ob ranges::begin(r) als first und ranges::end(r) als last verwendet würden.
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.
Inhalt |
[edit] Parameter
| first, last | - | das Iterator-Sentinel-Paar, das den Bereich der neu anzuordnenden Elemente definiert |
| r | - | der Bereich der neu anzuordnenden Elemente |
| nth | - | der Iterator, der den Partitionierungspunkt definiert |
| comp | - | Comparator, der zum Vergleichen der projizierten Elemente verwendet wird |
| proj | - | Projektion, die auf die Elemente angewendet wird |
[edit] Rückgabewert
1) Ein Iterator, der gleich last ist.
2) Wie bei (1), wenn r ein lvalue oder vom Typ
borrowed_range ist. Andernfalls wird std::ranges::dangling zurückgegeben.[edit] Komplexität
Linear in ranges::distance(first, last) im Durchschnitt.
[edit] Hinweise
Der verwendete Algorithmus ist typischerweise Introselect, obwohl auch andere Selektionsalgorithmen mit geeigneter durchschnittlicher Komplexität zulässig sind.
[edit] Mögliche Implementierung
Siehe auch die Implementierung in msvc stl, libstdc++ und libc++: (1) / (2).
[edit] Beispiel
Führen Sie diesen Code aus
#include <algorithm> #include <array> #include <functional> #include <iostream> #include <ranges> #include <string_view> void print(std::string_view rem, std::ranges::input_range auto const& a) { for (std::cout << rem; const auto e : a) std::cout << e << ' '; std::cout << '\n'; } int main() { std::array v{5, 6, 4, 3, 2, 6, 7, 9, 3}; print("Before nth_element: ", v); std::ranges::nth_element(v, v.begin() + v.size() / 2); print("After nth_element: ", v); std::cout << "The median is: " << v[v.size() / 2] << '\n'; std::ranges::nth_element(v, v.begin() + 1, std::greater<int>()); print("After nth_element: ", v); std::cout << "The second largest element is: " << v[1] << '\n'; std::cout << "The largest element is: " << v[0] << "\n\n"; using namespace std::literals; std::array names { "Diva"sv, "Cornelius"sv, "Munro"sv, "Rhod"sv, "Zorg"sv, "Korben"sv, "Bender"sv, "Leeloo"sv, }; print("Before nth_element: ", names); auto fifth_element{std::ranges::next(names.begin(), 4)}; std::ranges::nth_element(names, fifth_element); print("After nth_element: ", names); std::cout << "The 5th element is: " << *fifth_element << '\n'; }
Ausgabe
Before nth_element: 5 6 4 3 2 6 7 9 3 After nth_element: 2 3 3 4 5 6 6 7 9 The median is: 5 After nth_element: 9 7 6 6 5 4 3 3 2 The second largest element is: 7 The largest element is: 9 Before nth_element: Diva Cornelius Munro Rhod Zorg Korben Bender Leeloo After nth_element: Diva Cornelius Bender Korben Leeloo Rhod Munro Zorg The 5th element is: Leeloo
[edit] Siehe auch
| (C++20) |
Gibt das größte Element in einem Bereich zurück (Algorithmus-Funktionsobjekt) |
| (C++20) |
gibt das kleinste Element in einem Bereich zurück (Algorithmus-Funktionsobjekt) |
| (C++20) |
Teilt einen Bereich von Elementen in zwei Gruppen auf (Algorithmus-Funktionsobjekt) |
| (C++20) |
Sortiert die ersten N Elemente eines Bereichs (Algorithmus-Funktionsobjekt) |
| Sortiert den gegebenen Bereich teilweise, so dass er durch das gegebene Element partitioniert wird (Funktionstemplate) |
