Horizon
Loading...
Searching...
No Matches
partial_sort.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_HPP
14#define RANGES_V3_ALGORITHM_PARTIAL_SORT_HPP
15
16#include <functional>
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)
39
40
41 template(typename I, typename S, typename C = less, typename P = identity)(
42 requires sortable<I, C, P> AND random_access_iterator<I> AND
43 sentinel_for<S, I>)
44 constexpr I RANGES_FUNC(partial_sort)(
45 I first, I middle, S last, C pred = C{}, P proj = P{}) //
46 {
47 make_heap(first, middle, ranges::ref(pred), ranges::ref(proj));
48 auto const len = middle - first;
49 I i = middle;
50 for(; i != last; ++i)
51 {
52 if(invoke(pred, invoke(proj, *i), invoke(proj, *first)))
53 {
54 iter_swap(i, first);
55 detail::sift_down_n(
56 first, len, first, ranges::ref(pred), ranges::ref(proj));
57 }
58 }
59 sort_heap(first, middle, ranges::ref(pred), ranges::ref(proj));
60 return i;
61 }
62
64 template(typename Rng, typename C = less, typename P = identity)(
66 constexpr borrowed_iterator_t<Rng> RANGES_FUNC(partial_sort)(
67 Rng && rng, iterator_t<Rng> middle, C pred = C{}, P proj = P{}) //
68 {
69 return (*this)(begin(rng),
70 std::move(middle),
71 end(rng),
72 std::move(pred),
73 std::move(proj));
74 }
75
76 RANGES_FUNC_END(partial_sort)
77
78 namespace cpp20
79 {
80 using ranges::partial_sort;
81 }
83} // namespace ranges
84
85#include <range/v3/detail/epilogue.hpp>
86
87#endif
The random_access_range 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
bool_<(T::type::value< U::type::value)> less
A Boolean integral constant wrapper around true if T::type::value is less than U::type::value; false,...
Definition meta.hpp:255
Definition identity.hpp:25
Definition comparisons.hpp:50