21#ifndef RANGES_V3_ALGORITHM_STABLE_PARTITION_HPP
22#define RANGES_V3_ALGORITHM_STABLE_PARTITION_HPP
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
298 indirect_unary_predicate<C, projected<I, P>> AND permutable<I>)
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
312 indirect_unary_predicate<C, projected<iterator_t<Rng>, P>> AND
313 permutable<iterator_t<Rng>>)
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>
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