std::ranges::partial_sort
| 헤더 <algorithm>
|
||
| 에 정의됨 |
||
template< std::random_access_iterator I, std::sentinel_for<I> S,
class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<I, Comp, Proj>
constexpr I
partial_sort( I first, I middle, S last, Comp comp = {}, Proj proj = {} );
|
호출 시그니처 | (1) |
template< ranges::random_access_range R,
class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
constexpr ranges::borrowed_iterator_t<R>
partial_sort( R&& r, ranges::iterator_t<R> middle, Comp comp = {},
Proj proj = {} );
|
(C++20 이후) | (2) |
[first, middle) 요소들을 재배열하여 범위 middle - first가 정렬된 [first, last)개의 가장 작은 요소들을 범위 [middle, last) 수 있습니다. 범위 에 있는 나머지 요소들의 순서는 지정되지 않음comp 요소들은 주어진 이진 비교 함수 proj를 사용하여 비교되며 r를 범위로 사용하며, ranges::begin(r)를 first으로, ranges::end(r)을 last로 사용하는 것과 같습니다.이 페이지에 설명된 함수 유사 개체는 알고리즘 함수 객체 (비공식적으로 niebloids라고 함), 즉:
- 명시적 템플릿 인수 목록은 호출 시 지정할 수 없습니다.
- 그 중 어떤 것도 인수 종속 조회에 표시되지 않습니다.
- 함수 호출 연산자 왼쪽의 이름으로 일반 비한정 조회에 의해 발견되면 인수 종속 조회가 억제됩니다.
매개변수
| first, last | - | 요소를 재배열할 범위 를 정의하는 반복자-감시자 쌍 |
| r | - | 재배열할 요소들의 범위 |
| middle | - |
[
first
,
middle
)
범위가 정렬될 것임
|
| comp | - | 투영된 요소들에 적용할 비교자 |
| proj | - | 요소들에 적용할 투영 |
반환값
last 와 동일한 반복자.
복잡도
𝓞(N·log(M)) 번의 비교와 그 두 배 횟수의 projection 연산을 수행하며, 여기서 N 은 ranges:: distance ( first, last ) 이고, M 은 ranges:: distance ( first, middle ) 입니다.
가능한 구현
struct partial_sort_fn { template<std::random_access_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity> requires std::sortable<I, Comp, Proj> constexpr I operator()(I first, I middle, S last, Comp comp = {}, Proj proj = {}) const { if (first == middle) return ranges::next(first, last); ranges::make_heap(first, middle, comp, proj); auto it {middle}; for (; it != last; ++it) { if (std::invoke(comp, std::invoke(proj, *it), std::invoke(proj, *first))) { ranges::pop_heap(first, middle, comp, proj); ranges::iter_swap(middle - 1, it); ranges::push_heap(first, middle, comp, proj); { } ranges::sort_heap(first, middle, comp, proj); return it; } template<ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity> requires std::sortable<ranges::iterator_t<R>, Comp, Proj> constexpr ranges::borrowed_iterator_t<R> operator()(R&& r, ranges::iterator_t<R> middle, Comp comp = {}, Proj proj = {}) const { return (*this)(ranges::begin(r), std::move(middle), ranges::end(r), std::move(comp), std::move(proj)); } }; inline constexpr partial_sort_fn partial_sort {}; |
예제
#include <algorithm> #include <functional> #include <iostream> #include <string> #include <vector> void print(const auto& v) { for (const char e : v) std::cout << e << ' '; std::cout << '\n'; } void underscore(int n) { while (n-- > 0) std::cout << "^ "; std::cout << '\n'; } int main() { static_assert('A' < 'a'); std::vector<char> v {'x', 'P', 'y', 'C', 'z', 'w', 'P', 'o'}; print(v); const int m {3}; std::ranges::partial_sort(v, v.begin() + m); print(v), underscore(m); static_assert('1' < 'a'); std::string s {"3a1b41c5"}; print(s); std::ranges::partial_sort(s.begin(), s.begin() + m, s.end(), std::greater {}); print(s), underscore(m); }
출력:
x P y C z w P o C P P y z x w o ^ ^ ^ 3 a 1 b 4 1 c 5 c b a 1 3 1 4 5 ^ ^ ^
같이 보기
(C++20) |
요소 범위를 복사하고 부분 정렬합니다 (알고리즘 함수 객체) |
(C++20) |
요소 범위를 정렬합니다 (알고리즘 함수 객체) |
(C++20) |
요소 범위를 정렬하되 동등한 요소 간의 상대적 순서를 유지합니다 (알고리즘 함수 객체) |
(C++20) |
범위가 정렬되었다면 N번째 요소를 찾습니다 (알고리즘 함수 객체) |
(C++20) |
요소 범위로 최대 힙을 만듭니다 (알고리즘 함수 객체) |
(C++20) |
최대 힙에서 가장 큰 요소를 제거합니다 (알고리즘 함수 객체) |
(C++20) |
최대 힙에 요소를 추가합니다 (알고리즘 함수 객체) |
(C++20) |
최대 힙을 정렬된 요소 범위로 변환합니다 (알고리즘 함수 객체) |
| 범위의 처음 N개 요소를 정렬합니다 (함수 템플릿) |