36#ifndef RANGES_V3_ALGORITHM_SORT_HPP
37#define RANGES_V3_ALGORITHM_SORT_HPP
54#include <range/v3/utility/static_const.hpp>
56#include <range/v3/detail/prologue.hpp>
63 template<
typename I,
typename C,
typename P>
64 inline constexpr I unguarded_partition(I first, I last, C & pred, P & proj)
66 I mid =
first + (last -
first) / 2, penultimate = ranges::prev(last);
67 auto &&x = *
first, &&y = *mid, &&z = *penultimate;
68 auto &&a =
invoke(proj, (
decltype(x) &&)x),
69 &&b =
invoke(proj, (
decltype(y) &&)y),
70 &&c =
invoke(proj, (
decltype(z) &&)z);
75 ? (
invoke(pred, b, c) ? mid
78 : (
invoke(pred, b, c) ? penultimate : mid));
83 auto && v = *pivot_pnt;
84 auto && pivot =
invoke(proj, (
decltype(v) &&)v);
92 ranges::iter_swap(first, last);
94 pivot_pnt ==
first ? last : (pivot_pnt == last ?
first : pivot_pnt);
99 template<
typename I,
typename C,
typename P>
100 inline constexpr void unguarded_linear_insert(I last,
105 I next_ = prev(last);
108 *last = iter_move(next_);
112 *last = std::move(val);
115 template<
typename I,
typename C,
typename P>
116 inline constexpr void linear_insert(I first, I last, C & pred, P & proj)
118 iter_value_t<I> val = iter_move(last);
121 move_backward(first, last, last + 1);
122 *
first = std::move(val);
125 detail::unguarded_linear_insert(last, std::move(val), pred, proj);
128 template<
typename I,
typename C,
typename P>
129 inline constexpr void insertion_sort(I first, I last, C & pred, P & proj)
133 for(I i = next(first); i != last; ++i)
134 detail::linear_insert(first, i, pred, proj);
137 template<
typename I,
typename C,
typename P>
138 inline constexpr void unguarded_insertion_sort(I first, I last, C & pred, P & proj)
140 for(I i = first; i != last; ++i)
141 detail::unguarded_linear_insert(i, iter_move(i), pred, proj);
144 constexpr int introsort_threshold()
149 template<
typename I,
typename C,
typename P>
150 inline constexpr void final_insertion_sort(I first, I last, C & pred, P & proj)
152 if(last - first > detail::introsort_threshold())
154 detail::insertion_sort(
155 first, first + detail::introsort_threshold(), pred, proj);
156 detail::unguarded_insertion_sort(
157 first + detail::introsort_threshold(), last, pred, proj);
160 detail::insertion_sort(first, last, pred, proj);
163 template<
typename Size>
164 inline constexpr Size log2(Size n)
167 for(; n != 1; n >>= 1)
172 template<
typename I,
typename Size,
typename C,
typename P>
173 inline constexpr void introsort_loop(I first, I last, Size depth_limit, C & pred, P & proj)
175 while(last - first > detail::introsort_threshold())
179 first, last, last, std::ref(pred), std::ref(proj)),
181 I cut = detail::unguarded_partition(first, last, pred, proj);
182 detail::introsort_loop(cut, last, --depth_limit, pred, proj);
196 RANGES_FUNC_BEGIN(sort)
199 template(
typename I,
typename S,
typename C =
less,
typename P = identity)(
200 requires sortable<I, C, P> AND random_access_iterator<I> AND
202 constexpr I RANGES_FUNC(sort)(I
first, S end_, C pred = C{}, P proj = P{})
204 I last = ranges::next(first, std::move(end_));
207 detail::introsort_loop(
208 first, last, detail::log2(last - first) * 2, pred, proj);
209 detail::final_insertion_sort(first, last, pred, proj);
215 template(
typename Rng,
typename C =
less,
typename P = identity)(
216 requires sortable<iterator_t<Rng>, C, P> AND random_access_range<Rng>)
217 constexpr borrowed_iterator_t<Rng>
218 RANGES_FUNC(sort)(Rng && rng, C pred = C{}, P proj = P{})
220 return (*
this)(begin(rng), end(rng), std::move(pred), std::move(proj));
223 RANGES_FUNC_END(sort)
232#include <range/v3/detail/epilogue.hpp>
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