23#ifndef RANGES_V3_ALGORITHM_NTH_ELEMENT_HPP
24#define RANGES_V3_ALGORITHM_NTH_ELEMENT_HPP
42#include <range/v3/utility/static_const.hpp>
45#include <range/v3/detail/prologue.hpp>
54 template(
typename I,
typename C,
typename P)(
55 requires forward_iterator<I> AND indirect_relation<C, projected<I, P>>)
56 unsigned sort3(I x, I y, I z, C & pred, P & proj)
64 ranges::iter_swap(y, z);
68 ranges::iter_swap(x, y);
75 ranges::iter_swap(x, z);
79 ranges::iter_swap(x, y);
83 ranges::iter_swap(y, z);
89 template(
typename I,
typename C,
typename P)(
90 requires bidirectional_iterator<I> AND indirect_relation<C, projected<I, P>>)
91 void selection_sort(I first, I last, C & pred, P & proj)
93 RANGES_EXPECT(first != last);
94 for(I lm1 = ranges::prev(last);
first != lm1; ++
first)
96 I i = ranges::min_element(first, last, std::ref(pred), std::ref(proj));
98 ranges::iter_swap(first, i);
106 RANGES_FUNC_BEGIN(nth_element)
109 template(
typename I,
typename S,
typename C =
less,
typename P = identity)(
110 requires random_access_iterator<I> AND sortable<I, C, P>)
111 constexpr I RANGES_FUNC(nth_element)(
112 I
first, I nth, S end_, C pred = C{}, P proj = P{})
114 I last = ranges::next(nth, end_), end_orig = last;
116 using difference_type = iter_difference_t<I>;
117 difference_type
const limit = 7;
122 difference_type len = last -
first;
130 ranges::iter_swap(first, last);
135 detail::sort3(first, ++m, --last, pred, proj);
141 detail::selection_sort(first, last, pred, proj);
145 I m =
first + len / 2;
147 unsigned n_swaps = detail::sort3(first, m, --lm1, pred, proj);
184 ranges::iter_swap(i, j);
206 ranges::iter_swap(i, j);
221 ranges::iter_swap(i, j);
244 ranges::iter_swap(i, j);
256 ranges::iter_swap(i, m);
274 return ranges::nullopt;
288 return ranges::nullopt;
295 return ranges::nullopt;
299 return *optional_return;
317 template(
typename Rng,
typename C =
less,
typename P = identity)(
318 requires random_access_range<Rng> AND sortable<iterator_t<Rng>, C, P>)
319 constexpr borrowed_iterator_t<Rng> RANGES_FUNC(nth_element)(
320 Rng && rng, iterator_t<Rng> nth, C pred = C{}, P proj = P{})
323 begin(rng), std::move(nth), end(rng), std::move(pred), std::move(proj));
326 RANGES_FUNC_END(nth_element)
330 using ranges::nth_element;
335#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
Definition optional.hpp:501