Horizon
Loading...
Searching...
No Matches
partial_sort_copy.hpp
Go to the documentation of this file.
1
2// Range v3 library
3//
4// Copyright Eric Niebler 2013-present
5//
6// Use, modification and distribution is subject to the
7// Boost Software License, Version 1.0. (See accompanying
8// file LICENSE_1_0.txt or copy at
9// http://www.boost.org/LICENSE_1_0.txt)
10//
11// Project home: https://github.com/ericniebler/range-v3
12//
13#ifndef RANGES_V3_ALGORITHM_PARTIAL_SORT_COPY_HPP
14#define RANGES_V3_ALGORITHM_PARTIAL_SORT_COPY_HPP
15
16#include <meta/meta.hpp>
17
19
30#include <range/v3/utility/static_const.hpp>
31
32#include <range/v3/detail/prologue.hpp>
33
34namespace ranges
35{
38 RANGES_FUNC_BEGIN(partial_sort_copy)
39
40
41 template(typename I,
42 typename SI,
43 typename O,
44 typename SO,
45 typename C = less,
46 typename PI = identity,
47 typename PO = identity)(
48 requires input_iterator<I> AND sentinel_for<SI, I> AND
49 random_access_iterator<O> AND sentinel_for<SO, O> AND
50 indirectly_copyable<I, O> AND sortable<O, C, PO> AND
51 indirect_strict_weak_order<C, projected<I, PI>, projected<O, PO>>)
52 constexpr O RANGES_FUNC(partial_sort_copy)(I first,
53 SI last,
54 O out_begin,
55 SO out_end,
56 C pred = C{},
57 PI in_proj = PI{},
58 PO out_proj = PO{}) //
59 {
60 O r = out_begin;
61 if(r != out_end)
62 {
63 for(; first != last && r != out_end; ++first, ++r)
64 *r = *first;
65 make_heap(out_begin, r, ranges::ref(pred), ranges::ref(out_proj));
66 auto len = r - out_begin;
67 for(; first != last; ++first)
68 {
69 auto && x = *first;
70 if(invoke(pred, invoke(in_proj, x), invoke(out_proj, *out_begin)))
71 {
72 *out_begin = (decltype(x) &&)x;
73 detail::sift_down_n(out_begin,
74 len,
75 out_begin,
76 ranges::ref(pred),
77 ranges::ref(out_proj));
78 }
79 }
80 sort_heap(out_begin, r, ranges::ref(pred), ranges::ref(out_proj));
81 }
82 return r;
83 }
84
86 template(typename InRng,
87 typename OutRng,
88 typename C = less,
89 typename PI = identity,
90 typename PO = identity)(
95 projected<iterator_t<InRng>, PI>,
96 projected<iterator_t<OutRng>, PO>>)
97 constexpr borrowed_iterator_t<OutRng> RANGES_FUNC(partial_sort_copy)(InRng && in_rng,
98 OutRng && out_rng,
99 C pred = C{},
100 PI in_proj = PI{},
101 PO out_proj = PO{}) //
102 {
103 return (*this)(begin(in_rng),
104 end(in_rng),
105 begin(out_rng),
106 end(out_rng),
107 std::move(pred),
108 std::move(in_proj),
109 std::move(out_proj));
110 }
111
112 RANGES_FUNC_END(partial_sort_copy)
113
114 namespace cpp20
115 {
116 using ranges::partial_sort_copy;
117 }
119} // namespace ranges
120
121#include <range/v3/detail/epilogue.hpp>
122
123#endif
The indirect_strict_weak_order concept.
The indirectly_copyable concept.
The input_iterator concept.
The input_range concept.
The random_access_iterator concept.
The random_access_range concept.
The sentinel_for concept.
The sortable concept.
decltype(begin(declval(Rng &))) iterator_t
Definition access.hpp:698
typename Fn::template invoke< Args... > invoke
Evaluate the invocable Fn with the arguments Args.
Definition meta.hpp:541
front< Pair > first
Retrieve the first element of the pair Pair.
Definition meta.hpp:2251
Tiny meta-programming library.
Definition identity.hpp:25
Definition comparisons.hpp:50