21#ifndef RANGES_V3_ALGORITHM_INPLACE_MERGE_HPP
22#define RANGES_V3_ALGORITHM_INPLACE_MERGE_HPP
51#include <range/v3/utility/static_const.hpp>
54#include <range/v3/detail/prologue.hpp>
61 struct merge_adaptive_fn
64 template<
typename I,
typename C,
typename P>
65 static void impl(I first, I middle, I last, iter_difference_t<I> len1,
66 iter_difference_t<I> len2, iter_value_t<I> *
const buf,
69 auto tmpbuf = make_raw_buffer(buf);
72 auto p = ranges::move(first, middle, tmpbuf.begin()).out;
73 merge(make_move_iterator(buf),
74 make_move_iterator(p.base().base()),
75 make_move_iterator(std::move(middle)),
76 make_move_iterator(std::move(last)),
84 auto p = ranges::move(middle, last, tmpbuf.begin()).out;
87 merge(make_move_iterator(RBi{std::move(middle)}),
88 make_move_iterator(RBi{std::move(first)}),
89 make_move_iterator(Rv{p.base().base()}),
90 make_move_iterator(Rv{buf}),
99 template(
typename I,
typename C =
less,
typename P = identity)(
100 requires bidirectional_iterator<I> AND sortable<I, C, P>)
101 void operator()(I first, I middle, I last, iter_difference_t<I> len1,
102 iter_difference_t<I> len2, iter_value_t<I> * buf,
103 std::ptrdiff_t buf_size, C pred = C{}, P proj = P{})
const
105 using D = iter_difference_t<I>;
113 for(;
true; ++
first, --len1)
120 if(len1 <= buf_size || len2 <= buf_size)
122 merge_adaptive_fn::impl(std::move(first),
149 m2 = next(middle, len21);
150 m1 = upper_bound(first,
155 len11 = distance(first, m1);
162 ranges::iter_swap(first, middle);
167 m1 = next(first, len11);
168 m2 = lower_bound(middle,
173 len21 = distance(middle, m2);
175 D len12 = len1 - len11;
176 D len22 = len2 - len21;
179 middle = rotate(m1, std::move(middle), m2).begin();
183 if(len11 + len21 < len12 + len22)
185 (*this)(std::move(first),
194 first = std::move(middle);
195 middle = std::move(m2);
210 last = std::move(middle);
211 middle = std::move(m1);
219 RANGES_INLINE_VARIABLE(merge_adaptive_fn, merge_adaptive)
221 struct inplace_merge_no_buffer_fn
223 template(
typename I,
typename C =
less,
typename P = identity)(
224 requires bidirectional_iterator<I> AND sortable<I, C, P>)
225 void operator()(I first, I middle, I last, iter_difference_t<I> len1,
226 iter_difference_t<I> len2, C pred = C{}, P proj = P{})
const
228 merge_adaptive(std::move(first),
233 static_cast<iter_value_t<I> *
>(
nullptr),
240 RANGES_INLINE_VARIABLE(inplace_merge_no_buffer_fn, inplace_merge_no_buffer)
246 RANGES_FUNC_BEGIN(inplace_merge)
251 template(
typename I,
typename S,
typename C =
less,
typename P = identity)(
252 requires bidirectional_iterator<I> AND sortable<I, C, P>)
253 I RANGES_FUNC(inplace_merge)(
254 I
first, I middle, S last, C pred = C{}, P proj = P{})
256 using value_type = iter_value_t<I>;
257 auto len1 = distance(first, middle);
258 auto len2_and_end = enumerate(middle, last);
259 auto buf_size = ranges::min(len1, len2_and_end.first);
260 std::pair<value_type *, std::ptrdiff_t> buf{
nullptr, 0};
261 std::unique_ptr<value_type, detail::return_temporary_buffer> h;
262 if(detail::is_trivially_copy_assignable_v<value_type> && 8 < buf_size)
264 buf = detail::get_temporary_buffer<value_type>(buf_size);
267 detail::merge_adaptive(std::move(first),
276 return len2_and_end.second;
280 template(
typename Rng,
typename C =
less,
typename P = identity)(
281 requires bidirectional_range<Rng> AND sortable<iterator_t<Rng>, C, P>)
282 borrowed_iterator_t<Rng> RANGES_FUNC(inplace_merge)(
283 Rng && rng, iterator_t<Rng> middle, C pred = C{}, P proj = P{})
285 return (*
this)(begin(rng),
292 RANGES_FUNC_END(inplace_merge)
296 using ranges::inplace_merge;
301#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
compose< quote< not_ >, Fn > not_fn
Logically negate the result of invocable Fn.
Definition meta.hpp:3009
Definition basic_iterator.hpp:532