CKTIS / C++
std::nth_element — izbira elementa po rangu
std::nth_element postavi element na mesto, ki bi ga zasedal po popolnem razvrščanju, ne da bi razvrstil celoten obseg. Uporaben je za iskanje mediane ali k-tega najmanjšega elementa.
Različica: C++23; repository compiler flag, production runtime not attested
Sintaksa
#include <algorithm>
std::nth_element(first, nth, last);
std::nth_element(first, nth, last, comp);std::nth_element, deklariran v <algorithm>, preuredi [first, last) in vrne void. Če velja nth != last, *nth ustreza mestu nth - first v razvrščenem obsegu; mesta se štejejo od nič. Noben element v [nth, last) po primerjavi ni pred nobenim elementom v [first, nth). Oba dela lahko ostaneta nerazvrščena.
Zahtevani so iteratorji z naključnim dostopom. Elementi morajo podpirati zamenjavo, konstrukcijo s premikom in prirejanje s premikom. Obsega [first, nth) in [nth, last) morata biti veljavna. nth == last je dovoljeno, vendar v tem primeru *nth ne smete dereferencirati.
Privzeta primerjava razvrsti števila naraščajoče. Prilagojeni comp mora določati strogo šibko urejenost: ne uporabljajte <=. Pri preobremenitvah brez izvedbene politike je zahtevnost v povprečju linearna glede na last - first; v najslabšem primeru linearna zahtevnost ni zagotovljena.
Primer izbere mesto 3, torej četrti najmanjši element: 6. Izpiše samo izbrano vrednost, saj celotna razporeditev polja ni določena.
Primeri
#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';
}
Rezultat
6
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.