Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::nth_element — wybór elementu według pozycji

std::nth_element ustawia na wskazanej pozycji element odpowiadający tej pozycji po pełnym sortowaniu, ale nie sortuje całego zakresu. Przydaje się do znajdowania mediany lub k-tego najmniejszego elementu.

Wersja: C++23; repository compiler flag, production runtime not attested

Składnia

#include <algorithm>
std::nth_element(first, nth, last);
std::nth_element(first, nth, last, comp);

std::nth_element z <algorithm> przestawia elementy w [first, last) i zwraca void. Jeśli nth != last, *nth odpowiada pozycji nth - first w posortowanym zakresie; pozycje są liczone od zera. Żaden element z [nth, last) nie poprzedza według porównania żadnego elementu z [first, nth). Obie części mogą pozostać nieposortowane.

Wymagane są iteratory dostępu swobodnego oraz elementy obsługujące zamianę, konstrukcję przez przeniesienie i przypisanie przez przeniesienie. Zakresy [first, nth) i [nth, last) muszą być poprawne. nth == last jest dozwolone, lecz nie wolno wtedy odczytywać *nth.

Domyślne porównanie porządkuje liczby rosnąco. Własny comp musi definiować ścisły słaby porządek: nie używaj <=. Dla przeciążeń bez polityki wykonania złożoność jest średnio liniowa względem last - first, nie gwarantowanie liniowa w najgorszym przypadku.

Przykład wybiera pozycję 3, czyli czwarty najmniejszy element: 6. Wypisuje tylko wybraną wartość, ponieważ pełny układ tablicy nie jest określony.

Przykłady

#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';
}

Wynik

6

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła