CKTIS / C++
std::nth_element — výběr prvku podle pořadí
std::nth_element umístí prvek na pozici, kterou by měl po úplném seřazení, aniž by seřadil celý rozsah. Hodí se k nalezení mediánu nebo k-tého nejmenšího prvku.
Verze: C++23; repository compiler flag, production runtime not attested
Syntaxe
#include <algorithm>
std::nth_element(first, nth, last);
std::nth_element(first, nth, last, comp);std::nth_element deklarované v <algorithm> přeuspořádá [first, last) a vrací void. Pokud nth != last, odpovídá *nth pozici nth - first v seřazeném rozsahu; pozice se počítají od nuly. Žádný prvek v [nth, last) není podle porovnání před žádným prvkem v [first, nth). Obě části mohou zůstat neseřazené.
Jsou vyžadovány iterátory s náhodným přístupem. Prvky musí podporovat výměnu, konstrukci přesunem a přiřazení přesunem. Rozsahy [first, nth) a [nth, last) musí být platné. nth == last je povoleno, ale v takovém případě se *nth nesmí dereferencovat.
Výchozí porovnání řadí čísla vzestupně. Vlastní comp musí definovat striktní slabé uspořádání: nepoužívejte <=. U přetížení bez zásady provádění je složitost v průměru lineární vzhledem k last - first; v nejhorším případě není lineární složitost zaručena.
Příklad vybere pozici 3, tedy čtvrtý nejmenší prvek: 6. Vypíše pouze vybranou hodnotu, protože úplné uspořádání pole není určeno.
Pří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ýsledek
6
Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.