std:: nth_element

nth_element 는 [ first , last ) 범위 내의 요소들을 재배열하여 재배열 후 다음과 같은 상태가 되도록 합니다:

• nth 가 가리키는 요소는 [ first , last ) 구간이 정렬되었을 때 해당 위치에 오게 될 요소로 변경됩니다.
• [ first , nth ) 구간의 모든 반복자 i 와 [ nth , last ) 구간의 모든 반복자 j 에 대해 다음 조건이 만족됩니다:

다음 조건 중 하나라도 충족되면, 동작은 정의되지 않습니다:

• [ first , nth ) 또는 [ nth , last ) 이 유효한 범위 가 아닙니다.

매개변수

복잡도

주어진 \(\scriptsize N\) N 을 last - first 로:

예외

ExecutionPolicy 라는 템플릿 매개변수를 사용하는 오버로드는 다음과 같이 오류를 보고합니다:

• 알고리즘의 일부로 호출된 함수 실행 중 예외가 발생하고 ExecutionPolicy 가 표준 정책 중 하나인 경우, std::terminate 가 호출됩니다. 다른 ExecutionPolicy 의 경우 동작은 구현에 따라 정의됩니다.
• 알고리즘이 메모리 할당에 실패하는 경우, std::bad_alloc 이 throw됩니다.

가능한 구현

다음 구현도 참조하십시오: libstdc++ , libc++ , 그리고 MSVC STL .

참고 사항

사용된 알고리즘은 일반적으로 Introselect 이지만, 적절한 평균 경우 복잡도를 가진 다른 Selection algorithm 도 허용됩니다.

예제

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>
void printVec(const std::vector<int>& vec)
{
    std::cout << "v = {";
    for (char sep[]{0, ' ', 0}; const int i : vec)
        std::cout << sep << i, sep[0] = ',';
    std::cout << "};\n";
}
int main()
{
    std::vector<int> v{5, 10, 6, 4, 3, 2, 6, 7, 9, 3};
    printVec(v);
    auto m = v.begin() + v.size() / 2;
    std::nth_element(v.begin(), m, v.end());
    std::cout << "\nThe median is " << v[v.size() / 2] << '\n';
    // N번째 요소 앞/뒤 요소들의 불균등성 결과:
    assert(std::accumulate(v.begin(), m, 0) < std::accumulate(m, v.end(), 0));
    printVec(v);
    // 참고: comp 함수 변경됨
    std::nth_element(v.begin(), v.begin() + 1, v.end(), std::greater{});
    std::cout << "\nThe second largest element is " << v[1] << '\n';
    std::cout << "The largest element is " << v[0] << '\n';
    printVec(v);
}

v = {5, 10, 6, 4, 3, 2, 6, 7, 9, 3};
The median is 6
v = {3, 2, 3, 4, 5, 6, 10, 7, 9, 6};
The second largest element is 9
The largest element is 10
v = {10, 9, 6, 7, 6, 3, 5, 4, 3, 2};

결함 보고서

다음의 동작 변경 결함 보고서들은 이전에 발표된 C++ 표준에 소급 적용되었습니다.

참고 항목