CKTIS / C++
std::nth_element — een element op rang selecteren
std::nth_element plaatst een element op de positie die het na een volledige sortering zou innemen, zonder het hele bereik te sorteren. Het is handig om de mediaan of het k-de kleinste element te vinden.
Versie: 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, gedeclareerd in <algorithm>, herschikt [first, last) en retourneert void. Als nth != last, komt *nth overeen met positie nth - first in het gesorteerde bereik; posities beginnen bij nul. Geen element in [nth, last) komt volgens de vergelijking vóór een element in [first, nth). Beide delen mogen ongesorteerd blijven.
Iterators met willekeurige toegang zijn vereist. Elementen moeten kunnen worden verwisseld, verplaatsingsgeconstrueerd en verplaatsingstoegewezen. De bereiken [first, nth) en [nth, last) moeten geldig zijn. nth == last is toegestaan, maar in dat geval mag je *nth niet derefereren.
De standaardvergelijking sorteert getallen oplopend. Een aangepaste comp moet een strikte zwakke ordening definiëren: gebruik geen <=. Voor overloads zonder uitvoeringsbeleid is de complexiteit gemiddeld lineair ten opzichte van last - first; in het slechtste geval is een lineaire complexiteit niet gegarandeerd.
Het voorbeeld selecteert positie 3, het vierde kleinste element: 6. Het drukt alleen de geselecteerde waarde af, omdat de volledige rangschikking van de array niet is vastgelegd.
Voorbeelden
#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';
}
Resultaat
6
De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.