Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C++

std::nth_element — selecting an element by rank

std::nth_element places an element at the position it would occupy after a full sort without sorting the entire range. It is useful for finding a median or the kth smallest element.

Version: 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, declared in <algorithm>, rearranges [first, last) and returns void. If nth != last, *nth corresponds to position nth - first in the sorted range; positions are zero-based. No element in [nth, last) compares before any element in [first, nth). Both parts may remain unsorted.

Random-access iterators are required, and elements must support swapping, move construction, and move assignment. The ranges [first, nth) and [nth, last) must be valid. nth == last is permitted, but you must not dereference *nth in that case.

The default comparison orders numbers ascending. A custom comp must define a strict weak ordering: do not use <=. For overloads without an execution policy, complexity is linear on average in last - first, not guaranteed linear in the worst case.

The example selects position 3, the fourth smallest element: 6. It prints only the selected value because the complete array arrangement is unspecified.

Examples

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

Result

6

The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.

Sources