Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C++

std::nth_element — výber prvku podľa poradia

std::nth_element umiestni prvok na pozíciu, ktorú by mal po úplnom zoradení, bez zoradenia celého rozsahu. Hodí sa na nájdenie mediánu alebo k-teho najmenšieho prvku.

Verzia: 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 deklarované v <algorithm> preusporiada [first, last) a vracia void. Ak nth != last, *nth zodpovedá pozícii nth - first v zoradenom rozsahu; pozície sa počítajú od nuly. Žiadny prvok v [nth, last) nie je podľa porovnania pred žiadnym prvkom v [first, nth). Obe časti môžu zostať nezoradené.

Vyžadujú sa iterátory s náhodným prístupom. Prvky musia podporovať výmenu, konštrukciu presunom a priradenie presunom. Rozsahy [first, nth) a [nth, last) musia byť platné. nth == last je povolené, no v takom prípade sa *nth nesmie dereferencovať.

Predvolené porovnanie zoraďuje čísla vzostupne. Vlastné comp musí definovať striktne slabé usporiadanie: nepoužívajte <=. Pri preťaženiach bez politiky vykonávania je zložitosť v priemere lineárna vzhľadom na last - first; v najhoršom prípade sa lineárna zložitosť nezaručuje.

Príklad vyberie pozíciu 3, teda štvrtý najmenší prvok: 6. Vypíše iba vybranú hodnotu, pretože úplné usporiadanie poľa nie je určené.

Príklady

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

Výsledok

6

Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.

Zdroje