База знанияИзпитен център
BGБългарски
Избери език13

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

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници