std::ranges:: partial_sort
std::ranges
| Non-modifying sequence operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Modifying sequence operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Partitioning operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Sorting operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Binary search operations (on sorted ranges) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Set operations (on sorted ranges) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Heap operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Minimum/maximum operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Permutation operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Fold operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Operations on uninitialized storage | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Return types | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
헤더 파일에 정의됨
<algorithm>
|
||
|
함수 시그니처
|
||
|
template
<
std::
random_access_iterator
I,
std::
sentinel_for
<
I
>
S,
class
Comp
=
ranges::
less
,
class
Proj
=
std::
identity
>
|
(1) | (C++20 이후) |
|
template
<
ranges::
random_access_range
R,
class
Comp
=
ranges::
less
,
class
Proj
=
std::
identity
>
|
(2) | (C++20 이후) |
[
first
,
middle
)
범위가
[
first
,
last
)
범위에서 정렬된
middle
-
first
개의 가장 작은 요소들을 포함하도록 합니다.
[
middle
,
last
)
는
명시되지 않음
입니다.
이 페이지에서 설명하는 함수형 개체들은 algorithm function objects (일반적으로 niebloids 로 알려진)입니다. 즉:
- 명시적 템플릿 인수 목록은 이들 중 어느 것을 호출할 때도 지정할 수 없습니다.
- 이들 중 어느 것도 인수 의존 이름 검색 에 보이지 않습니다.
- 이들 중 어느 것이 함수 호출 연산자 왼쪽의 이름으로 일반 비한정 이름 검색 에 의해 발견될 때, 인수 의존 이름 검색 이 억제됩니다.
목차 |
매개변수
| first, last | - | 요소를 재배열할 범위 를 정의하는 반복자-감시자 쌍 |
| r | - | 재배열할 요소들의 범위 |
| middle | - |
[
first
,
middle
)
범위가 정렬될 것임
|
| comp | - | 투영된 요소들에 적용할 비교자 |
| proj | - | 요소들에 적용할 투영 |
반환값
last 와 동일한 반복자.
복잡도
\(\scriptsize \mathcal{O}(N\cdot\log{(M)})\) 𝓞(N·log(M)) 번의 비교와 그 두 배 횟수의 projection 연산을 수행하며, 여기서 \(\scriptsize N\) N 은 ranges:: distance ( first, last ) 이고, \(\scriptsize M\) 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)
|
주어진 요소로 분할되도록 주어진 범위를 부분적으로 정렬함
(알고리즘 함수 객체) |
|
(C++20)
|
범위의 요소들로 최대 힙을 생성함
(알고리즘 함수 객체) |
|
(C++20)
|
최대 힙에서 가장 큰 요소를 제거함
(알고리즘 함수 객체) |
|
(C++20)
|
최대 힙에 요소를 추가함
(알고리즘 함수 객체) |
|
(C++20)
|
최대 힙을 오름차순으로 정렬된 요소 범위로 변환함
(알고리즘 함수 객체) |
|
범위의 처음 N개 요소를 정렬함
(함수 템플릿) |