algorithm_partial_sort_copy
algorithm_partial_sort_copy (부분 정렬 복사)
std::partial_sort_copy는 소스 범위의 요소들을 정렬해서 처음 요소들만 목적지 범위에 복사해요. 전체를 정렬하지 않고 상위 K개를 얻을 때 써요.
출처: cppreference
본문
std::partial_sort_copy는 소스 범위 [first, last)의 요소들을 정렬하고 그 중 처음 min(std::distance(first, last), std::distance(d_first, d_last))개를 목적지 범위 [d_first, d_last)에 놓아요. <algorithm> 헤더에 정의되어 있어요.
template< class InputIt, class RandomIt >
RandomIt partial_sort_copy( InputIt first, InputIt last,
RandomIt d_first, RandomIt d_last );
template< class InputIt, class RandomIt, class Compare >
RandomIt partial_sort_copy( InputIt first, InputIt last,
RandomIt d_first, RandomIt d_last,
Compare comp );
- 1번 오버로드 — 요소를
operator<(즉std::less{})로 비교해요. - 2번 오버로드 — 요소를 비교 함수
comp로 비교해요. - 병렬 실행 정책을 받는 오버로드도 있어요.
반환값 (Return value)
목적지 범위에서 마지막으로 쓰여진 요소 다음의 반복자예요.
복잡도 (Complexity)
N을 std::distance(first, last), M을 std::distance(d_first, d_last)라고 하면 𝓞(N·log(min(N, M)))번의 비교가 필요해요.
예제 (Example)
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> source{5, 3, 8, 1, 9, 2};
std::vector<int> dest(3);
std::partial_sort_copy(source.begin(), source.end(), dest.begin(), dest.end());
for (int x : dest) std::cout << x << ' ';
std::cout << '\n';
}
출력:
1 2 3