CKTIS / C++
std::nth_element — избор на елемент по ранг
std::nth_element поставя елемент на позицията, която би заемал след пълно сортиране, без да сортира целия диапазон. Полезен е за намиране на медиана или на k-тия най-малък елемент.
Версия: C++23; repository compiler flag, production runtime not attested
Синтаксис
#include <algorithm>
std::nth_element(first, nth, last);
std::nth_element(first, nth, last, comp);std::nth_element, деклариран в <algorithm>, пренарежда [first, last) и връща void. Ако nth != last, *nth съответства на позиция nth - first в сортирания диапазон; позициите се броят от нула. Нито един елемент в [nth, last) не предхожда според сравнението елемент от [first, nth). И двете части могат да останат несортирани.
Изискват се итератори с произволен достъп. Елементите трябва да поддържат размяна, конструиране чрез преместване и присвояване чрез преместване. Диапазоните [first, nth) и [nth, last) трябва да са валидни. nth == last е позволено, но в този случай не трябва да се дереферира *nth.
Сравнението по подразбиране подрежда числата във възходящ ред. Персонализираният comp трябва да задава строго слабо подреждане: не използвайте <=. За претоварванията без политика за изпълнение сложността е линейна средно спрямо last - first; линейна сложност в най-лошия случай не е гарантирана.
Примерът избира позиция 3, тоест четвъртия най-малък елемент: 6. Той отпечатва само избраната стойност, тъй като пълното подреждане на масива не е определено.
Примери
#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';
}
Резултат
6
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.