CKTIS / C++
std::nth_element — Element nach Rang auswählen
std::nth_element platziert ein Element an der Position, die es nach einer vollständigen Sortierung einnehmen würde, ohne den gesamten Bereich zu sortieren. Der Algorithmus eignet sich zum Finden des Medians oder des k-kleinsten Elements.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
std::nth_element(first, nth, last);
std::nth_element(first, nth, last, comp);std::nth_element aus <algorithm> ordnet [first, last) um und gibt void zurück. Wenn nth != last gilt, entspricht *nth der Position nth - first im sortierten Bereich; die Positionen werden ab null gezählt. Kein Element in [nth, last) steht im Vergleich vor einem Element in [first, nth). Beide Teilbereiche dürfen unsortiert bleiben.
Erforderlich sind Iteratoren mit wahlfreiem Zugriff. Die Elemente müssen sich tauschen, per Move konstruieren und per Move zuweisen lassen. Die Bereiche [first, nth) und [nth, last) müssen gültig sein. nth == last ist zulässig; in diesem Fall darf *nth jedoch nicht dereferenziert werden.
Der Standardvergleich ordnet Zahlen aufsteigend. Ein benutzerdefiniertes comp muss eine strikte schwache Ordnung definieren: Verwende nicht <=. Bei Überladungen ohne Ausführungsrichtlinie ist die Komplexität im Durchschnitt linear bezüglich last - first; im ungünstigsten Fall ist eine lineare Laufzeit nicht garantiert.
Das Beispiel wählt Position 3, also das viertkleinste Element: 6. Es gibt nur den ausgewählten Wert aus, da die vollständige Anordnung des Arrays nicht festgelegt ist.
Beispiele
#include <algorithm>
#include <array>
#include <iostream>
int main() {
std::array<int, 7> values{9, 1, 8, 2, 7, 3, 6};
auto nth = values.begin() + 3;
std::nth_element(values.begin(), nth, values.end());
std::cout << *nth << '\n';
}
Ergebnis
6
Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.