std:: partial_sort

요소들을 재배열하여 [ first , middle ) 범위가 [ first , last ) 범위에서 가장 작은 middle − first 개의 요소를 정렬된 상태로 포함하도록 합니다.

동일한 요소들의 순서는 보존된다고 보장되지 않습니다. 범위 [ middle , last ) 내 남은 요소들의 순서는 명시되지 않습니다.

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

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

매개변수

복잡도

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

예외

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

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

가능한 구현

다음 구현들도 참조하십시오: libstdc++ 와 libc++ .

template<typename RandomIt>
constexpr //< since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last)
{
    typedef typename std::iterator_traits<RandomIt>::value_type VT;
    std::partial_sort(first, middle, last, std::less<VT>());
}

namespace impl
{
    template<typename RandomIt, typename Compare>
    constexpr //< since C++20
    void sift_down(RandomIt first, RandomIt last, const Compare& comp)
    {
        // sift down element at “first”
        const auto length = static_cast<std::size_t>(last - first);
        std::size_t current = 0;
        std::size_t next = 2;
        while (next < length)
        {
            if (comp(*(first + next), *(first + (next - 1))))
                --next;
            if (!comp(*(first + current), *(first + next)))
                return;
            std::iter_swap(first + current, first + next);
            current = next;
            next = 2 * current + 2;
        }
        --next;
        if (next < length && comp(*(first + current), *(first + next)))
            std::iter_swap(first + current, first + next);
    }
    template<typename RandomIt, typename Compare>
    constexpr //< since C++20
    void heap_select(RandomIt first, RandomIt middle, RandomIt last, const Compare& comp)
    {
        std::make_heap(first, middle, comp);
        for (auto i = middle; i != last; ++i)
        {
            if (comp(*i, *first))
            {
                std::iter_swap(first, i);
                sift_down(first, middle, comp);
            }
        }
    }
} // namespace impl
template<typename RandomIt, typename Compare>
constexpr //< since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp)
{
    impl::heap_select(first, middle, last, comp);
    std::sort_heap(first, middle, comp);
}

참고 사항

알고리즘

사용된 알고리즘은 일반적으로 heap select 로 가장 작은 요소들을 선택하고, heap sort 로 힙 내에서 선택된 요소들을 오름차순으로 정렬합니다.

요소를 선택하기 위해 힙이 사용됩니다( heap 참조). 예를 들어, operator < 를 비교 함수로 사용할 경우, max-heap 이 middle − first 개의 가장 작은 요소들을 선택하는 데 사용됩니다.

힙 정렬 은 선택 후에 [ first , middle ) 범위의 선택된 요소들을 정렬하는 데 사용됩니다(참조: std::sort_heap ).

사용 목적

std::partial_sort 알고리즘은 작은 상수 개수 의 [ first , middle ) 선택된 요소들에 사용되도록 설계되었습니다.

예제

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
void print(const auto& s, int middle)
{
    for (int a : s)
        std::cout << a << ' ';
    std::cout << '\n';
    if (middle > 0)
    {
        while (middle-- > 0)
            std::cout << "--";
        std::cout << '^';
    }
    else if (middle < 0)
    {
        for (auto i = s.size() + middle; --i; std::cout << "  ")
        {}
        for (std::cout << '^'; middle++ < 0; std::cout << "--")
        {}
    }
    std::cout << '\n';
};
int main()
{
    std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    print(s, 0);
    std::partial_sort(s.begin(), s.begin() + 3, s.end());
    print(s, 3);
    std::partial_sort(s.rbegin(), s.rbegin() + 4, s.rend());
    print(s, -4);
    std::partial_sort(s.rbegin(), s.rbegin() + 5, s.rend(), std::greater{});
    print(s, -5);
}

5 7 4 2 8 6 1 9 0 3
0 1 2 7 8 6 5 9 4 3
------^
4 5 6 7 8 9 3 2 1 0
          ^--------
4 3 2 1 0 5 6 7 8 9
        ^----------

결함 보고서

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

참고 항목