21 #ifndef RANGES_V3_ALGORITHM_STABLE_PARTITION_HPP
22 #define RANGES_V3_ALGORITHM_STABLE_PARTITION_HPP
26 #include <type_traits>
46 #include <range/v3/utility/static_const.hpp>
49 #include <range/v3/detail/prologue.hpp>
59 template<
typename I,
typename C,
typename P,
typename D,
typename Pair>
60 I stable_partition_impl(I
first, I last, C pred, P proj, D len, Pair
const p,
61 std::forward_iterator_tag fi)
72 ranges::iter_swap(
first, tmp);
81 auto tmpbuf = make_raw_buffer(p.first);
82 auto buf = tmpbuf.begin();
83 *buf = iter_move(
first);
85 auto res = partition_copy(make_move_iterator(next(
first)),
86 make_move_sentinel(last),
94 ranges::move(p.first, res.out2.base().base(), res.out1);
102 I middle = next(
first, half);
107 detail::stable_partition_impl(
first, middle, pred, proj, half, p, fi);
113 D len_half = len - half;
117 return ranges::rotate(begin_false, middle, last).begin();
123 detail::stable_partition_impl(m1, last, pred, proj, len_half, p, fi);
126 return ranges::rotate(begin_false, middle, end_false).begin();
131 template<
typename I,
typename S,
typename C,
typename P>
132 I stable_partition_impl(I
first, S last, C pred, P proj,
133 std::forward_iterator_tag fi)
135 using difference_type = iter_difference_t<I>;
136 difference_type
const alloc_limit = 3;
149 using value_type = iter_value_t<I>;
150 auto len_end = enumerate(
first, last);
151 auto p = len_end.first >= alloc_limit
152 ? detail::get_temporary_buffer<value_type>(len_end.first)
153 : detail::value_init{};
154 std::unique_ptr<value_type, detail::return_temporary_buffer>
const h{p.first};
155 return detail::stable_partition_impl(
156 first, len_end.second, pred, proj, len_end.first, p, fi);
159 template<
typename I,
typename C,
typename P,
typename D,
typename Pair>
160 I stable_partition_impl(I
first, I last, C pred, P proj, D len, Pair p,
161 std::bidirectional_iterator_tag bi)
168 ranges::iter_swap(
first, last);
176 ranges::iter_swap(
first, tmp);
177 ranges::iter_swap(tmp, last);
180 ranges::iter_swap(tmp, last);
181 ranges::iter_swap(
first, tmp);
188 auto tmpbuf = ranges::make_raw_buffer(p.first);
189 auto buf = tmpbuf.begin();
190 *buf = iter_move(
first);
192 auto res = partition_copy(make_move_iterator(next(
first)),
193 make_move_sentinel(last),
200 *
first = iter_move(res.in);
205 ranges::move(p.first, res.out2.base().base(),
first);
214 advance(middle, half);
218 I begin_false =
first;
223 goto first_half_done;
229 detail::stable_partition_impl(
first, m1, pred, proj, len_half, p, bi);
236 len_half = len - half;
240 return ranges::rotate(begin_false, middle, ++last).begin();
246 detail::stable_partition_impl(m1, last, pred, proj, len_half, p, bi);
249 return ranges::rotate(begin_false, middle, end_false).begin();
254 template<
typename I,
typename S,
typename C,
typename P>
255 I stable_partition_impl(I
first, S end_, C pred, P proj,
256 std::bidirectional_iterator_tag bi)
258 using difference_type = iter_difference_t<I>;
259 using value_type = iter_value_t<I>;
260 difference_type
const alloc_limit =
274 I last = ranges::next(
first, end_);
284 auto len = distance(
first, last) + 1;
285 auto p = len >= alloc_limit ? detail::get_temporary_buffer<value_type>(len)
286 : detail::value_init{};
287 std::unique_ptr<value_type, detail::return_temporary_buffer>
const h{p.first};
288 return detail::stable_partition_impl(
first, last, pred, proj, len, p, bi);
293 RANGES_FUNC_BEGIN(stable_partition)
296 template(
typename I,
typename S,
typename C,
typename P = identity)(
297 requires bidirectional_iterator<I> AND sentinel_for<S, I> AND
299 I RANGES_FUNC(stable_partition)(I
first, S last, C pred, P proj = P{})
301 return detail::stable_partition_impl(std::move(
first),
305 iterator_tag_of<I>());
310 template(
typename Rng,
typename C,
typename P = identity)(
311 requires bidirectional_range<Rng> AND
314 borrowed_iterator_t<Rng>
315 RANGES_FUNC(stable_partition)(Rng && rng, C pred, P proj = P{})
317 return (*
this)(begin(rng), end(rng), std::move(pred), std::move(proj));
320 RANGES_FUNC_END(stable_partition)
324 using ranges::stable_partition;
329 #include <range/v3/detail/epilogue.hpp>
CPP_concept permutable
\concept permutable
Definition: concepts.hpp:840
CPP_concept indirect_unary_predicate
\concept indirect_unary_predicate
Definition: concepts.hpp:632
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