std::ranges:: nth_element

[ first , last ) 범위 내의 요소들을 다음과 같이 재배열합니다:

• nth 가 가리키는 요소는 [ first , last ) 범위가 comp 와 proj 를 기준으로 정렬되었을 때 해당 위치에 오게 될 요소로 변경됩니다.
• 이 새로운 nth 요소 이전의 모든 요소는 새로운 nth 요소 이후의 요소들보다 작거나 같습니다 . 즉, [ first , nth ) 과 [ nth , last ) 범위에 있는 모든 반복자 i , j 에 대해, 표현식 std:: invoke ( comp, std:: invoke ( proj, * j ) , std:: invoke ( proj, * i ) ) 가 false 로 평가됩니다.
• 만약 nth == last 이면 함수는 아무런 효과가 없습니다.

이 페이지에서 설명하는 함수형 개체들은 algorithm function objects (일반적으로 niebloids 로 알려진)입니다. 즉:

• 명시적 템플릿 인수 목록은 이들 중 어느 것을 호출할 때도 지정할 수 없습니다.
• 이들 중 어느 것도 인수 의존 이름 검색 에 보이지 않습니다.
• 이들 중 어느 것이 함수 호출 연산자 왼쪽의 이름으로 일반 비한정 이름 검색 에 의해 발견될 때, 인수 의존 이름 검색 이 억제됩니다.

매개변수

반환값

복잡도

평균적으로 ranges:: distance ( first, last ) 에 선형입니다.

참고 사항

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

가능한 구현

구현은 다음에서도 확인할 수 있습니다: msvc stl , libstdc++ , 그리고 libc++: (1) / (2) .

예제

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
#include <ranges>
#include <string_view>
void print(std::string_view rem, std::ranges::input_range auto const& a)
{
    for (std::cout << rem; const auto e : a)
        std::cout << e << ' ';
    std::cout << '\n';
}
int main()
{
    std::array v{5, 6, 4, 3, 2, 6, 7, 9, 3};
    print("Before nth_element: ", v);
    std::ranges::nth_element(v, v.begin() + v.size() / 2);
    print("After nth_element:  ", v);
    std::cout << "The median is: " << v[v.size() / 2] << '\n';
    std::ranges::nth_element(v, v.begin() + 1, std::greater<int>());
    print("After nth_element:  ", v);
    std::cout << "The second largest element is: " << v[1] << '\n';
    std::cout << "The largest element is: " << v[0] << "\n\n";
    using namespace std::literals;
    std::array names
    {
        "Diva"sv, "Cornelius"sv, "Munro"sv, "Rhod"sv,
        "Zorg"sv, "Korben"sv, "Bender"sv, "Leeloo"sv,
    };
    print("Before nth_element: ", names);
    auto fifth_element{std::ranges::next(names.begin(), 4)};
    std::ranges::nth_element(names, fifth_element);
    print("After nth_element:  ", names);
    std::cout << "The 5th element is: " << *fifth_element << '\n';
}

Before nth_element: 5 6 4 3 2 6 7 9 3 
After nth_element:  2 3 3 4 5 6 6 7 9 
The median is: 5
After nth_element:  9 7 6 6 5 4 3 3 2 
The second largest element is: 7
The largest element is: 9
Before nth_element: Diva Cornelius Munro Rhod Zorg Korben Bender Leeloo 
After nth_element:  Diva Cornelius Bender Korben Leeloo Rhod Munro Zorg 
The 5th element is: Leeloo

참고 항목