Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

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.

Izvori