KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

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.

Bronnen