CKTIS / C++
std::nth_element — odabir elementa prema rangu
std::nth_element postavlja element na mjesto koje bi zauzeo nakon potpunog sortiranja, a da pritom ne sortira cijeli raspon. Koristan je za pronalaženje medijana ili k-tog najmanjeg elementa.
Verzija: 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 u <algorithm>, preslaguje [first, last) i vraća void. Ako je nth != last, *nth odgovara položaju nth - first u sortiranom rasponu; položaji se broje od nule. Nijedan element u [nth, last) prema usporedbi nije ispred nijednog elementa u [first, nth). Oba dijela mogu ostati nesortirana.
Potrebni su iteratori s nasumičnim pristupom. Elementi moraju podržavati zamjenu, konstrukciju premještanjem i dodjelu premještanjem. Rasponi [first, nth) i [nth, last) moraju biti valjani. nth == last je dopušteno, ali u tom slučaju ne smijete dereferencirati *nth.
Zadana usporedba sortira brojeve uzlazno. Prilagođeni comp mora definirati strogi slabi poredak: nemojte koristiti <=. Za preopterećenja bez pravila izvođenja, složenost je u prosjeku linearna u odnosu na last - first; linearna složenost nije zajamčena u najgorem slučaju.
Primjer odabire položaj 3, odnosno četvrti najmanji element: 6. Ispisuje samo odabranu vrijednost jer potpuni raspored polja nije specificiran.
Primjeri
#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
Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.