Namespaces
Variants

    std::nth_element

    cppreference.net에서
     
    C++
     
    알고리즘 라이브러리
    제약된 알고리즘 및 범위에 대한 알고리즘 (C++20)
    제약된 알고리즘, 예: ranges::copy, ranges::sort, ...
    정렬 및 관련 연산
    분할 연산
    (C++11)    
    (C++11)

    정렬 연산
    이진 탐색 연산
    (분할된 범위에 대해)
    집합 연산 (정렬된 범위에 대해)
    병합 연산 (정렬된 범위에 대해)
    힙 연산
    최소/최대 연산
    (C++11)
    (C++17)
    사전식 비교 연산
    (C++20)
    순열 연산


     
    헤더 <algorithm> 
    template< class RandomIt >
void nth_element( RandomIt first, RandomIt nth, RandomIt last );
    		에 정의됨 (1) (C++20부터 constexpr) 
    template< class ExecutionPolicy, class RandomIt >
void nth_element( ExecutionPolicy&& policy,
                  RandomIt first, RandomIt nth, RandomIt last );
    		(2) (C++17부터) 
    template< class RandomIt, class Compare >
void nth_element( RandomIt first, RandomIt nth, RandomIt last,
                  Compare comp );
    		(3) (C++20부터 constexpr) 
    template< class ExecutionPolicy, class RandomIt, class Compare >
void nth_element( ExecutionPolicy&& policy,
                  RandomIt first, RandomIt nth, RandomIt last,
                  Compare comp );
    		(4) (C++17부터)

    nth_element [first, last)의 요소들을 재배열하여, 재배열 후 다음을 만족하도록 합니다:

    • nth가 가리키는 요소는 [first, last)이 정렬되었을 때 그 위치에 오게 될 요소로 변경됩니다.
    • i이 [first, nth)의 모든 반복자와 j이 [nth, last)의 모든 반복자에 대해, 다음 조건이 충족됩니다:
    1,2) bool(*j < *i)(C++20까지)std::less{}(*j, *i)(C++20부터)은(는) false입니다.
    3,4) bool(comp(*j, *i))은(는) false입니다.


    1) 요소들은 정렬된 것으로 가정하며, operator<(C++20까지)std::less{}(C++20부터)을(를) 기준으로 합니다.
    3) 요소들은 comp을(를) 기준으로 정렬된 것으로 가정합니다.
    2,4) (1,3)과 동일하지만, policy에 따라 실행됩니다.
    이 오버로드들은 다음 표현식의 값이 true인 경우에만 오버로드 해결에 참여합니다:

    std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>

    		(C++20까지)

    std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>

    		(C++20부터)

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

    • *first의 타입이 Swappable이 아닙니다.
    		 (C++11까지)
    (C++11부터)

    매개변수

    first, last - 부분 정렬할 요소들의 범위 를 정의하는 반복자 쌍
    nth - 정렬 분할 지점을 정의하는 임의 접근 반복자
    policy - 사용할 실행 정책
    comp - 비교 함수 객체(즉 Compare 요구 사항을 만족하는 객체)로 첫 번째 인수가 두 번째 인수보다 작은 경우(즉 앞에 오는 경우) ​ true 를 반환함

    비교 함수의 시그니처는 다음과 동일해야 함:

    bool cmp ( const Type1 & a, const Type2 & b ) ;

    시그니처에 const & 가 필요하지는 않지만, 함수는 전달된 객체를 수정해서는 안 되며 값 범주 에 관계없이 Type1 과 Type2 타입의 모든 값을 받아들일 수 있어야 함(따라서 Type1& 는 허용되지 않으며 , Type1 에 대한 이동이 복사와 동등하지 않는 한 Type1 도 허용되지 않음 (C++11부터) ).
    Type1 과 Type2 타입은 RandomIt 타입의 객체를 역참조한 후 두 타입 모두로 암시적으로 변환 가능해야 함 ​

    타입 요구 사항
    -
    RandomIt 는 LegacyRandomAccessIterator 요구 사항을 충족해야 함
    -
    Compare 는 Compare 요구 사항을 충족해야 함

    복잡도

    주어진 N 을 last - first 로:

    1) O(N) 비교를 평균적으로 operator < (until C++20) std:: less { } (since C++20) 사용하여 수행합니다.
    2) O(N) 비교를 사용하며 operator < (C++20 이전) std:: less { } (C++20 이후) , 그리고 O(N·log(N)) 스왑이 발생합니다.
    3) O(N) 비교자 comp 의 평균 적용 횟수.
    4) O(N) 비교자 comp 의 적용, 그리고 O(N·log(N)) 교환 연산.

    예외

    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++ 표준에 소급 적용되었습니다.

    DR 적용 대상 게시된 동작 올바른 동작
    LWG 2150 C++98 재배열 후, nth 이전의 한 요소만이 nth 이후의 한 요소보다
    크지 않아야 한다고 요구됨     		요구사항을
    수정함
    LWG 2163 C++98 오버로드 ( 1 ) 가 요소 비교에 operator > 사용 operator < 로 변경됨
    P0896R4 C++98 [ first , nth ) 와 [ nth , last )
    가 유효한 범위일 필요가 없었음     		둘 중 하나라도 유효하지 않으면
    동작이 정의되지 않음

    참고 항목

    		 범위에서 가장 큰 요소를 반환합니다
    (함수 템플릿 & 알고리즘 함수 객체)
    (C++20)
    		범위에서 가장 작은 요소를 반환합니다
    (함수 템플릿 & 알고리즘 함수 객체)
    (C++20)
    		요소 범위를 복사하여 부분 정렬합니다
    (함수 템플릿 & 알고리즘 함수 객체)
    (C++20)
    		동등한 요소 간의 상대적 순서를 유지하면서 요소 범위를 정렬합니다
    (함수 템플릿 & 알고리즘 함수 객체)
    (C++20)
    		요소 범위를 정렬합니다
    (함수 템플릿 & 알고리즘 함수 객체)
    (C++20)
    (C++20)
    		 범위가 정렬된 경우 n번째 요소를 찾습니다
    (알고리즘 함수 객체)