// Core algorithmic facilities -*- C++ -*-
// Copyright (C) 2020-2025 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// .
/** @file bits/ranges_algo.h
* This is an internal header file, included by other library headers.
* Do not attempt to use it directly. @headername{algorithm}
*/
#ifndef _RANGES_ALGO_H
#define _RANGES_ALGO_H 1
#if __cplusplus > 201703L
#include // __bit_width
#if __cplusplus > 202002L
#include
#endif
#include
#include
#include // concept uniform_random_bit_generator
#if __glibcxx_concepts
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
namespace ranges
{
namespace __detail
{
template
using __by_ref_or_value_fn
= __conditional_t || is_empty_v<_Fp>, _Fp, _Fp&>;
template
struct _Comp_proj
{
[[no_unique_address]] __by_ref_or_value_fn<_Comp> _M_comp;
[[no_unique_address]] __by_ref_or_value_fn<_Proj> _M_proj;
constexpr
_Comp_proj(_Comp& __comp, _Proj& __proj)
: _M_comp(__comp), _M_proj(__proj)
{ }
template
constexpr bool
operator()(_Tp&& __x, _Up&& __y)
{
return std::__invoke(_M_comp,
std::__invoke(_M_proj, std::forward<_Tp>(__x)),
std::__invoke(_M_proj, std::forward<_Up>(__y)));
}
};
template
constexpr _Comp_proj<_Comp, _Proj>
__make_comp_proj(_Comp& __comp, _Proj& __proj)
{ return {__comp, __proj}; }
template
struct _Pred_proj
{
[[no_unique_address]] __by_ref_or_value_fn<_Pred> _M_pred;
[[no_unique_address]] __by_ref_or_value_fn<_Proj> _M_proj;
constexpr
_Pred_proj(_Pred& __pred, _Proj& __proj)
: _M_pred(__pred), _M_proj(__proj)
{ }
template
constexpr bool
operator()(_Tp&& __x)
{
return std::__invoke(_M_pred,
std::__invoke(_M_proj, std::forward<_Tp>(__x)));
}
};
template
constexpr _Pred_proj<_Pred, _Proj>
__make_pred_proj(_Pred& __pred, _Proj& __proj)
{ return {__pred, __proj}; }
} // namespace __detail
struct __all_of_fn
{
template _Sent,
typename _Proj = identity,
indirect_unary_predicate> _Pred>
constexpr bool
operator()(_Iter __first, _Sent __last,
_Pred __pred, _Proj __proj = {}) const
{
for (; __first != __last; ++__first)
if (!(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
return false;
return true;
}
template, _Proj>>
_Pred>
constexpr bool
operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__pred), std::move(__proj));
}
};
inline constexpr __all_of_fn all_of{};
struct __any_of_fn
{
template _Sent,
typename _Proj = identity,
indirect_unary_predicate> _Pred>
constexpr bool
operator()(_Iter __first, _Sent __last,
_Pred __pred, _Proj __proj = {}) const
{
for (; __first != __last; ++__first)
if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
return true;
return false;
}
template, _Proj>>
_Pred>
constexpr bool
operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__pred), std::move(__proj));
}
};
inline constexpr __any_of_fn any_of{};
struct __none_of_fn
{
template _Sent,
typename _Proj = identity,
indirect_unary_predicate> _Pred>
constexpr bool
operator()(_Iter __first, _Sent __last,
_Pred __pred, _Proj __proj = {}) const
{
for (; __first != __last; ++__first)
if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
return false;
return true;
}
template, _Proj>>
_Pred>
constexpr bool
operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__pred), std::move(__proj));
}
};
inline constexpr __none_of_fn none_of{};
template
struct in_fun_result
{
[[no_unique_address]] _Iter in;
[[no_unique_address]] _Fp fun;
template
requires convertible_to
&& convertible_to
constexpr
operator in_fun_result<_Iter2, _F2p>() const &
{ return {in, fun}; }
template
requires convertible_to<_Iter, _Iter2> && convertible_to<_Fp, _F2p>
constexpr
operator in_fun_result<_Iter2, _F2p>() &&
{ return {std::move(in), std::move(fun)}; }
};
template
using for_each_result = in_fun_result<_Iter, _Fp>;
struct __for_each_fn
{
template _Sent,
typename _Proj = identity,
indirectly_unary_invocable> _Fun>
constexpr for_each_result<_Iter, _Fun>
operator()(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {}) const
{
for (; __first != __last; ++__first)
std::__invoke(__f, std::__invoke(__proj, *__first));
return { std::move(__first), std::move(__f) };
}
template, _Proj>>
_Fun>
constexpr for_each_result, _Fun>
operator()(_Range&& __r, _Fun __f, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__f), std::move(__proj));
}
};
inline constexpr __for_each_fn for_each{};
template
using for_each_n_result = in_fun_result<_Iter, _Fp>;
struct __for_each_n_fn
{
template> _Fun>
constexpr for_each_n_result<_Iter, _Fun>
operator()(_Iter __first, iter_difference_t<_Iter> __n,
_Fun __f, _Proj __proj = {}) const
{
if constexpr (random_access_iterator<_Iter>)
{
if (__n <= 0)
return {std::move(__first), std::move(__f)};
auto __last = __first + __n;
return ranges::for_each(std::move(__first), std::move(__last),
std::move(__f), std::move(__proj));
}
else
{
while (__n-- > 0)
{
std::__invoke(__f, std::__invoke(__proj, *__first));
++__first;
}
return {std::move(__first), std::move(__f)};
}
}
};
inline constexpr __for_each_n_fn for_each_n{};
// find, find_if and find_if_not are defined in .
struct __find_first_of_fn
{
template _Sent1,
forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
typename _Pred = ranges::equal_to,
typename _Proj1 = identity, typename _Proj2 = identity>
requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
constexpr _Iter1
operator()(_Iter1 __first1, _Sent1 __last1,
_Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
{
for (; __first1 != __last1; ++__first1)
for (auto __iter = __first2; __iter != __last2; ++__iter)
if (std::__invoke(__pred,
std::__invoke(__proj1, *__first1),
std::__invoke(__proj2, *__iter)))
return __first1;
return __first1;
}
template
requires indirectly_comparable, iterator_t<_Range2>,
_Pred, _Proj1, _Proj2>
constexpr borrowed_iterator_t<_Range1>
operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
{
return (*this)(ranges::begin(__r1), ranges::end(__r1),
ranges::begin(__r2), ranges::end(__r2),
std::move(__pred),
std::move(__proj1), std::move(__proj2));
}
};
inline constexpr __find_first_of_fn find_first_of{};
struct __count_fn
{
template _Sent,
typename _Proj = identity,
typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)>
requires indirect_binary_predicate,
const _Tp*>
constexpr iter_difference_t<_Iter>
operator()(_Iter __first, _Sent __last,
const _Tp& __value, _Proj __proj = {}) const
{
iter_difference_t<_Iter> __n = 0;
for (; __first != __last; ++__first)
if (std::__invoke(__proj, *__first) == __value)
++__n;
return __n;
}
template, _Proj)>
requires indirect_binary_predicate, _Proj>,
const _Tp*>
constexpr range_difference_t<_Range>
operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
__value, std::move(__proj));
}
};
inline constexpr __count_fn count{};
struct __count_if_fn
{
template _Sent,
typename _Proj = identity,
indirect_unary_predicate> _Pred>
constexpr iter_difference_t<_Iter>
operator()(_Iter __first, _Sent __last,
_Pred __pred, _Proj __proj = {}) const
{
iter_difference_t<_Iter> __n = 0;
for (; __first != __last; ++__first)
if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
++__n;
return __n;
}
template, _Proj>>
_Pred>
constexpr range_difference_t<_Range>
operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__pred), std::move(__proj));
}
};
inline constexpr __count_if_fn count_if{};
// in_in_result, mismatch and search are defined in .
struct __search_n_fn
{
template _Sent,
typename _Pred = ranges::equal_to, typename _Proj = identity,
typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)>
requires indirectly_comparable<_Iter, const _Tp*, _Pred, _Proj>
constexpr subrange<_Iter>
operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __count,
const _Tp& __value, _Pred __pred = {}, _Proj __proj = {}) const
{
if (__count <= 0)
return {__first, __first};
auto __value_comp = [&] (_Rp&& __arg) -> bool {
return std::__invoke(__pred, std::forward<_Rp>(__arg), __value);
};
if (__count == 1)
{
__first = ranges::find_if(std::move(__first), __last,
std::move(__value_comp),
std::move(__proj));
if (__first == __last)
return {__first, __first};
else
{
auto __end = __first;
return {__first, ++__end};
}
}
if constexpr (sized_sentinel_for<_Sent, _Iter>
&& random_access_iterator<_Iter>)
{
auto __tail_size = __last - __first;
auto __remainder = __count;
while (__remainder <= __tail_size)
{
__first += __remainder;
__tail_size -= __remainder;
auto __backtrack = __first;
while (__value_comp(std::__invoke(__proj, *--__backtrack)))
{
if (--__remainder == 0)
return {__first - __count, __first};
}
__remainder = __count + 1 - (__first - __backtrack);
}
auto __i = __first + __tail_size;
return {__i, __i};
}
else
{
__first = ranges::find_if(__first, __last, __value_comp, __proj);
while (__first != __last)
{
auto __n = __count;
auto __i = __first;
++__i;
while (__i != __last && __n != 1
&& __value_comp(std::__invoke(__proj, *__i)))
{
++__i;
--__n;
}
if (__n == 1)
return {__first, __i};
if (__i == __last)
return {__i, __i};
__first = ranges::find_if(++__i, __last, __value_comp, __proj);
}
return {__first, __first};
}
}
template, _Proj)>
requires indirectly_comparable, const _Tp*,
_Pred, _Proj>
constexpr borrowed_subrange_t<_Range>
operator()(_Range&& __r, range_difference_t<_Range> __count,
const _Tp& __value, _Pred __pred = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__count), __value,
std::move(__pred), std::move(__proj));
}
};
inline constexpr __search_n_fn search_n{};
#if __glibcxx_ranges_starts_ends_with // C++ >= 23
struct __starts_with_fn
{
template _Sent1,
input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
typename _Pred = ranges::equal_to,
typename _Proj1 = identity, typename _Proj2 = identity>
requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
constexpr bool
operator()(_Iter1 __first1, _Sent1 __last1,
_Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
{
iter_difference_t<_Iter1> __n1 = -1;
iter_difference_t<_Iter2> __n2 = -1;
if constexpr (sized_sentinel_for<_Sent1, _Iter1>)
__n1 = __last1 - __first1;
if constexpr (sized_sentinel_for<_Sent2, _Iter2>)
__n2 = __last2 - __first2;
return _S_impl(std::move(__first1), __last1, __n1,
std::move(__first2), __last2, __n2,
std::move(__pred),
std::move(__proj1), std::move(__proj2));
}
template
requires indirectly_comparable, iterator_t<_Range2>,
_Pred, _Proj1, _Proj2>
constexpr bool
operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
{
range_difference_t<_Range1> __n1 = -1;
range_difference_t<_Range2> __n2 = -1;
if constexpr (sized_range<_Range1>)
__n1 = ranges::size(__r1);
if constexpr (sized_range<_Range2>)
__n2 = ranges::size(__r2);
return _S_impl(ranges::begin(__r1), ranges::end(__r1), __n1,
ranges::begin(__r2), ranges::end(__r2), __n2,
std::move(__pred),
std::move(__proj1), std::move(__proj2));
}
private:
template
static constexpr bool
_S_impl(_Iter1 __first1, _Sent1 __last1, iter_difference_t<_Iter1> __n1,
_Iter2 __first2, _Sent2 __last2, iter_difference_t<_Iter2> __n2,
_Pred __pred, _Proj1 __proj1, _Proj2 __proj2)
{
if (__first2 == __last2) [[unlikely]]
return true;
else if (__n1 == -1 || __n2 == -1)
return ranges::mismatch(std::move(__first1), __last1,
std::move(__first2), __last2,
std::move(__pred),
std::move(__proj1), std::move(__proj2)).in2 == __last2;
else if (__n1 < __n2)
return false;
else if constexpr (random_access_iterator<_Iter1>)
return ranges::equal(__first1, __first1 + iter_difference_t<_Iter1>(__n2),
std::move(__first2), __last2,
std::move(__pred),
std::move(__proj1), std::move(__proj2));
else
return ranges::equal(counted_iterator(std::move(__first1),
iter_difference_t<_Iter1>(__n2)),
default_sentinel,
std::move(__first2), __last2,
std::move(__pred),
std::move(__proj1), std::move(__proj2));
}
friend struct __ends_with_fn;
};
inline constexpr __starts_with_fn starts_with{};
struct __ends_with_fn
{
template _Sent1,
input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
typename _Pred = ranges::equal_to,
typename _Proj1 = identity, typename _Proj2 = identity>
requires (forward_iterator<_Iter1> || sized_sentinel_for<_Sent1, _Iter1>)
&& (forward_iterator<_Iter2> || sized_sentinel_for<_Sent2, _Iter2>)
&& indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
constexpr bool
operator()(_Iter1 __first1, _Sent1 __last1,
_Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
{
iter_difference_t<_Iter1> __n1 = -1;
iter_difference_t<_Iter2> __n2 = -1;
if constexpr (sized_sentinel_for<_Sent1, _Iter1>)
__n1 = __last1 - __first1;
if constexpr (sized_sentinel_for<_Sent2, _Iter2>)
__n2 = __last2 - __first2;
return _S_impl(std::move(__first1), __last1, __n1,
std::move(__first2), __last2, __n2,
std::move(__pred),
std::move(__proj1), std::move(__proj2));
}
template
requires (forward_range<_Range1> || sized_range<_Range1>)
&& (forward_range<_Range2> || sized_range<_Range2>)
&& indirectly_comparable, iterator_t<_Range2>,
_Pred, _Proj1, _Proj2>
constexpr bool
operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
{
range_difference_t<_Range1> __n1 = -1;
range_difference_t<_Range2> __n2 = -1;
if constexpr (sized_range<_Range1>)
__n1 = ranges::size(__r1);
if constexpr (sized_range<_Range2>)
__n2 = ranges::size(__r2);
return _S_impl(ranges::begin(__r1), ranges::end(__r1), __n1,
ranges::begin(__r2), ranges::end(__r2), __n2,
std::move(__pred),
std::move(__proj1), std::move(__proj2));
}
private:
template
static constexpr bool
_S_impl(_Iter1 __first1, _Sent1 __last1, iter_difference_t<_Iter1> __n1,
_Iter2 __first2, _Sent2 __last2, iter_difference_t<_Iter2> __n2,
_Pred __pred, _Proj1 __proj1, _Proj2 __proj2)
{
if constexpr (!random_access_iterator<_Iter1>
&& bidirectional_iterator<_Iter1> && same_as<_Iter1, _Sent1>
&& bidirectional_iterator<_Iter2> && same_as<_Iter2, _Sent2>)
return starts_with._S_impl(std::make_reverse_iterator(__last1),
std::make_reverse_iterator(__first1),
__n1,
std::make_reverse_iterator(__last2),
std::make_reverse_iterator(__first2),
__n2,
std::move(__pred),
std::move(__proj1), std::move(__proj2));
if (__first2 == __last2) [[unlikely]]
return true;
if constexpr (forward_iterator<_Iter2>)
if (__n2 == -1)
__n2 = ranges::distance(__first2, __last2);
// __glibcxx_assert(__n2 != -1);
if (__n1 != -1)
{
if (__n1 < __n2)
return false;
auto __shift = __n1 - iter_difference_t<_Iter1>(__n2);
if (random_access_iterator<_Iter1>
|| !bidirectional_iterator<_Iter1>
|| !same_as<_Iter1, _Sent1>
|| __shift < __n2)
{
ranges::advance(__first1, __shift);
return ranges::equal(std::move(__first1), __last1,
std::move(__first2), __last2,
std::move(__pred),
std::move(__proj1), std::move(__proj2));
}
}
if constexpr (bidirectional_iterator<_Iter1> && same_as<_Iter1, _Sent1>)
{
_Iter1 __it1 = __last1;
if (__n1 != -1)
ranges::advance(__it1, -iter_difference_t<_Iter1>(__n2));
else
{
// We can't use ranges::advance if the haystack size is
// unknown, since we need to detect and return false if
// it's smaller than the needle.
iter_difference_t<_Iter2> __m = __n2;
while (__m != 0 && __it1 != __first1)
{
--__m;
--__it1;
}
if (__m != 0)
return false;
}
return ranges::equal(__it1, __last1,
std::move(__first2), __last2,
std::move(__pred),
std::move(__proj1), std::move(__proj2));
}
else if constexpr (forward_iterator<_Iter1>)
{
// __glibcxx_assert(__n1 == -1);
_Iter1 __prev_first1;
__n1 = 0;
while (true)
{
iter_difference_t<_Iter2> __m = __n2;
_Iter1 __it1 = __first1;
while (__m != 0 && __it1 != __last1)
{
++__n1;
--__m;
++__it1;
}
if (__m != 0)
{
// __glibcxx_assert(__it1 == __last1);
if (__n1 < __n2)
return false;
__first1 = ranges::next(__prev_first1,
iter_difference_t<_Iter1>(__n2 - __m));
break;
}
__prev_first1 = __first1;
__first1 = __it1;
}
return ranges::equal(__first1, __last1,
std::move(__first2), __last2,
std::move(__pred),
std::move(__proj1), std::move(__proj2));
}
else
// If the haystack is non-forward then it must be sized, in which case
// we already returned via the __n1 != 1 case.
__builtin_unreachable();
}
};
inline constexpr __ends_with_fn ends_with{};
#endif // __glibcxx_ranges_starts_ends_with
struct __find_end_fn
{
template _Sent1,
forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
typename _Pred = ranges::equal_to,
typename _Proj1 = identity, typename _Proj2 = identity>
requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
constexpr subrange<_Iter1>
operator()(_Iter1 __first1, _Sent1 __last1,
_Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
{
if constexpr (bidirectional_iterator<_Iter1>
&& bidirectional_iterator<_Iter2>)
{
auto __i1 = ranges::next(__first1, __last1);
auto __i2 = ranges::next(__first2, __last2);
auto __rresult
= ranges::search(reverse_iterator<_Iter1>{__i1},
reverse_iterator<_Iter1>{__first1},
reverse_iterator<_Iter2>{__i2},
reverse_iterator<_Iter2>{__first2},
std::move(__pred),
std::move(__proj1), std::move(__proj2));
auto __result_first = ranges::end(__rresult).base();
auto __result_last = ranges::begin(__rresult).base();
if (__result_last == __first1)
return {__i1, __i1};
else
return {__result_first, __result_last};
}
else
{
auto __i = ranges::next(__first1, __last1);
if (__first2 == __last2)
return {__i, __i};
auto __result_begin = __i;
auto __result_end = __i;
for (;;)
{
auto __new_range = ranges::search(__first1, __last1,
__first2, __last2,
__pred, __proj1, __proj2);
auto __new_result_begin = ranges::begin(__new_range);
auto __new_result_end = ranges::end(__new_range);
if (__new_result_begin == __last1)
return {__result_begin, __result_end};
else
{
__result_begin = __new_result_begin;
__result_end = __new_result_end;
__first1 = __result_begin;
++__first1;
}
}
}
}
template
requires indirectly_comparable, iterator_t<_Range2>,
_Pred, _Proj1, _Proj2>
constexpr borrowed_subrange_t<_Range1>
operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
{
return (*this)(ranges::begin(__r1), ranges::end(__r1),
ranges::begin(__r2), ranges::end(__r2),
std::move(__pred),
std::move(__proj1), std::move(__proj2));
}
};
inline constexpr __find_end_fn find_end{};
// adjacent_find is defined in .
struct __is_permutation_fn
{
template _Sent1,
forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
typename _Proj1 = identity, typename _Proj2 = identity,
indirect_equivalence_relation,
projected<_Iter2, _Proj2>> _Pred
= ranges::equal_to>
constexpr bool
operator()(_Iter1 __first1, _Sent1 __last1,
_Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
{
constexpr bool __sized_iters
= (sized_sentinel_for<_Sent1, _Iter1>
&& sized_sentinel_for<_Sent2, _Iter2>);
if constexpr (__sized_iters)
{
auto __d1 = ranges::distance(__first1, __last1);
auto __d2 = ranges::distance(__first2, __last2);
if (__d1 != __d2)
return false;
}
// Efficiently compare identical prefixes: O(N) if sequences
// have the same elements in the same order.
for (; __first1 != __last1 && __first2 != __last2;
++__first1, (void)++__first2)
if (!(bool)std::__invoke(__pred,
std::__invoke(__proj1, *__first1),
std::__invoke(__proj2, *__first2)))
break;
if constexpr (__sized_iters)
{
if (__first1 == __last1)
return true;
}
else
{
auto __d1 = ranges::distance(__first1, __last1);
auto __d2 = ranges::distance(__first2, __last2);
if (__d1 == 0 && __d2 == 0)
return true;
if (__d1 != __d2)
return false;
}
for (auto __scan = __first1; __scan != __last1; ++__scan)
{
auto&& __scan_deref = *__scan;
auto&& __proj_scan =
std::__invoke(__proj1, std::forward(__scan_deref));
auto __comp_scan = [&] (_Tp&& __arg) -> bool {
return std::__invoke(__pred,
std::forward(__proj_scan),
std::forward<_Tp>(__arg));
};
if (__scan != ranges::find_if(__first1, __scan,
__comp_scan, __proj1))
continue; // We've seen this one before.
auto __matches = ranges::count_if(__first2, __last2,
__comp_scan, __proj2);
if (__matches == 0
|| ranges::count_if(__scan, __last1,
__comp_scan, __proj1) != __matches)
return false;
}
return true;
}
template, _Proj1>,
projected, _Proj2>> _Pred = ranges::equal_to>
constexpr bool
operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
{
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 3560. ranges::is_permutation should short-circuit for sized_ranges
if constexpr (sized_range<_Range1>)
if constexpr (sized_range<_Range2>)
if (ranges::distance(__r1) != ranges::distance(__r2))
return false;
return (*this)(ranges::begin(__r1), ranges::end(__r1),
ranges::begin(__r2), ranges::end(__r2),
std::move(__pred),
std::move(__proj1), std::move(__proj2));
}
};
inline constexpr __is_permutation_fn is_permutation{};
template
using copy_if_result = in_out_result<_Iter, _Out>;
struct __copy_if_fn
{
template _Sent,
weakly_incrementable _Out, typename _Proj = identity,
indirect_unary_predicate> _Pred>
requires indirectly_copyable<_Iter, _Out>
constexpr copy_if_result<_Iter, _Out>
operator()(_Iter __first, _Sent __last, _Out __result,
_Pred __pred, _Proj __proj = {}) const
{
for (; __first != __last; ++__first)
if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
{
*__result = *__first;
++__result;
}
return {std::move(__first), std::move(__result)};
}
template, _Proj>>
_Pred>
requires indirectly_copyable, _Out>
constexpr copy_if_result, _Out>
operator()(_Range&& __r, _Out __result,
_Pred __pred, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__result),
std::move(__pred), std::move(__proj));
}
};
inline constexpr __copy_if_fn copy_if{};
template
using swap_ranges_result = in_in_result<_Iter1, _Iter2>;
struct __swap_ranges_fn
{
template _Sent1,
input_iterator _Iter2, sentinel_for<_Iter2> _Sent2>
requires indirectly_swappable<_Iter1, _Iter2>
constexpr swap_ranges_result<_Iter1, _Iter2>
operator()(_Iter1 __first1, _Sent1 __last1,
_Iter2 __first2, _Sent2 __last2) const
{
for (; __first1 != __last1 && __first2 != __last2;
++__first1, (void)++__first2)
ranges::iter_swap(__first1, __first2);
return {std::move(__first1), std::move(__first2)};
}
template
requires indirectly_swappable, iterator_t<_Range2>>
constexpr swap_ranges_result,
borrowed_iterator_t<_Range2>>
operator()(_Range1&& __r1, _Range2&& __r2) const
{
return (*this)(ranges::begin(__r1), ranges::end(__r1),
ranges::begin(__r2), ranges::end(__r2));
}
};
inline constexpr __swap_ranges_fn swap_ranges{};
template
using unary_transform_result = in_out_result<_Iter, _Out>;
template
struct in_in_out_result
{
[[no_unique_address]] _Iter1 in1;
[[no_unique_address]] _Iter2 in2;
[[no_unique_address]] _Out out;
template
requires convertible_to
&& convertible_to
&& convertible_to
constexpr
operator in_in_out_result<_IIter1, _IIter2, _OOut>() const &
{ return {in1, in2, out}; }
template
requires convertible_to<_Iter1, _IIter1>
&& convertible_to<_Iter2, _IIter2>
&& convertible_to<_Out, _OOut>
constexpr
operator in_in_out_result<_IIter1, _IIter2, _OOut>() &&
{ return {std::move(in1), std::move(in2), std::move(out)}; }
};
template
using binary_transform_result = in_in_out_result<_Iter1, _Iter2, _Out>;
struct __transform_fn
{
template _Sent,
weakly_incrementable _Out,
copy_constructible _Fp, typename _Proj = identity>
requires indirectly_writable<_Out,
indirect_result_t<_Fp&,
projected<_Iter, _Proj>>>
constexpr unary_transform_result<_Iter, _Out>
operator()(_Iter __first1, _Sent __last1, _Out __result,
_Fp __op, _Proj __proj = {}) const
{
for (; __first1 != __last1; ++__first1, (void)++__result)
*__result = std::__invoke(__op, std::__invoke(__proj, *__first1));
return {std::move(__first1), std::move(__result)};
}
template
requires indirectly_writable<_Out,
indirect_result_t<_Fp&,
projected, _Proj>>>
constexpr unary_transform_result, _Out>
operator()(_Range&& __r, _Out __result, _Fp __op, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__result),
std::move(__op), std::move(__proj));
}
template _Sent1,
input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
weakly_incrementable _Out, copy_constructible _Fp,
typename _Proj1 = identity, typename _Proj2 = identity>
requires indirectly_writable<_Out,
indirect_result_t<_Fp&,
projected<_Iter1, _Proj1>,
projected<_Iter2, _Proj2>>>
constexpr binary_transform_result<_Iter1, _Iter2, _Out>
operator()(_Iter1 __first1, _Sent1 __last1,
_Iter2 __first2, _Sent2 __last2,
_Out __result, _Fp __binary_op,
_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
{
for (; __first1 != __last1 && __first2 != __last2;
++__first1, (void)++__first2, ++__result)
*__result = std::__invoke(__binary_op,
std::__invoke(__proj1, *__first1),
std::__invoke(__proj2, *__first2));
return {std::move(__first1), std::move(__first2), std::move(__result)};
}
template
requires indirectly_writable<_Out,
indirect_result_t<_Fp&,
projected, _Proj1>,
projected, _Proj2>>>
constexpr binary_transform_result,
borrowed_iterator_t<_Range2>, _Out>
operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, _Fp __binary_op,
_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
{
return (*this)(ranges::begin(__r1), ranges::end(__r1),
ranges::begin(__r2), ranges::end(__r2),
std::move(__result), std::move(__binary_op),
std::move(__proj1), std::move(__proj2));
}
};
inline constexpr __transform_fn transform{};
struct __replace_fn
{
template _Sent,
typename _Proj = identity,
typename _Tp1 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj),
typename _Tp2 _GLIBCXX26_DEF_VAL_T(_Tp1)>
requires indirectly_writable<_Iter, const _Tp2&>
&& indirect_binary_predicate,
const _Tp1*>
constexpr _Iter
operator()(_Iter __first, _Sent __last,
const _Tp1& __old_value, const _Tp2& __new_value,
_Proj __proj = {}) const
{
for (; __first != __last; ++__first)
if (std::__invoke(__proj, *__first) == __old_value)
*__first = __new_value;
return __first;
}
template, _Proj),
typename _Tp2 _GLIBCXX26_DEF_VAL_T(_Tp1)>
requires indirectly_writable, const _Tp2&>
&& indirect_binary_predicate, _Proj>,
const _Tp1*>
constexpr borrowed_iterator_t<_Range>
operator()(_Range&& __r,
const _Tp1& __old_value, const _Tp2& __new_value,
_Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
__old_value, __new_value, std::move(__proj));
}
};
inline constexpr __replace_fn replace{};
struct __replace_if_fn
{
template _Sent,
typename _Proj = identity,
typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj),
indirect_unary_predicate> _Pred>
requires indirectly_writable<_Iter, const _Tp&>
constexpr _Iter
operator()(_Iter __first, _Sent __last,
_Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
{
for (; __first != __last; ++__first)
if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
*__first = __new_value;
return std::move(__first);
}
template, _Proj),
indirect_unary_predicate, _Proj>>
_Pred>
requires indirectly_writable, const _Tp&>
constexpr borrowed_iterator_t<_Range>
operator()(_Range&& __r,
_Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__pred), __new_value, std::move(__proj));
}
};
inline constexpr __replace_if_fn replace_if{};
template
using replace_copy_result = in_out_result<_Iter, _Out>;
struct __replace_copy_fn
{
template _Sent,
typename _Out, typename _Proj = identity,
typename _Tp1 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj),
typename _Tp2 _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>)>
requires indirectly_copyable<_Iter, _Out>
&& indirect_binary_predicate, const _Tp1*>
&& output_iterator<_Out, const _Tp2&>
constexpr replace_copy_result<_Iter, _Out>
operator()(_Iter __first, _Sent __last, _Out __result,
const _Tp1& __old_value, const _Tp2& __new_value,
_Proj __proj = {}) const
{
for (; __first != __last; ++__first, (void)++__result)
if (std::__invoke(__proj, *__first) == __old_value)
*__result = __new_value;
else
*__result = *__first;
return {std::move(__first), std::move(__result)};
}
template, _Proj),
typename _Tp2 _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>)>
requires indirectly_copyable, _Out>
&& indirect_binary_predicate, _Proj>,
const _Tp1*>
&& output_iterator<_Out, const _Tp2&>
constexpr replace_copy_result, _Out>
operator()(_Range&& __r, _Out __result,
const _Tp1& __old_value, const _Tp2& __new_value,
_Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__result), __old_value,
__new_value, std::move(__proj));
}
};
inline constexpr __replace_copy_fn replace_copy{};
template
using replace_copy_if_result = in_out_result<_Iter, _Out>;
struct __replace_copy_if_fn
{
template _Sent,
typename _Out,
typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>),
typename _Proj = identity,
indirect_unary_predicate> _Pred>
requires indirectly_copyable<_Iter, _Out>
&& output_iterator<_Out, const _Tp&>
constexpr replace_copy_if_result<_Iter, _Out>
operator()(_Iter __first, _Sent __last, _Out __result,
_Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
{
for (; __first != __last; ++__first, (void)++__result)
if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
*__result = __new_value;
else
*__result = *__first;
return {std::move(__first), std::move(__result)};
}
template),
typename _Proj = identity,
indirect_unary_predicate, _Proj>>
_Pred>
requires indirectly_copyable, _Out>
&& output_iterator<_Out, const _Tp&>
constexpr replace_copy_if_result, _Out>
operator()(_Range&& __r, _Out __result,
_Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__result), std::move(__pred),
__new_value, std::move(__proj));
}
};
inline constexpr __replace_copy_if_fn replace_copy_if{};
struct __generate_n_fn
{
template
requires invocable<_Fp&>
&& indirectly_writable<_Out, invoke_result_t<_Fp&>>
constexpr _Out
operator()(_Out __first, iter_difference_t<_Out> __n, _Fp __gen) const
{
for (; __n > 0; --__n, (void)++__first)
*__first = std::__invoke(__gen);
return __first;
}
};
inline constexpr __generate_n_fn generate_n{};
struct __generate_fn
{
template _Sent,
copy_constructible _Fp>
requires invocable<_Fp&>
&& indirectly_writable<_Out, invoke_result_t<_Fp&>>
constexpr _Out
operator()(_Out __first, _Sent __last, _Fp __gen) const
{
for (; __first != __last; ++__first)
*__first = std::__invoke(__gen);
return __first;
}
template
requires invocable<_Fp&> && output_range<_Range, invoke_result_t<_Fp&>>
constexpr borrowed_iterator_t<_Range>
operator()(_Range&& __r, _Fp __gen) const
{
return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__gen));
}
};
inline constexpr __generate_fn generate{};
struct __remove_if_fn
{
template _Sent,
typename _Proj = identity,
indirect_unary_predicate> _Pred>
constexpr subrange<_Iter>
operator()(_Iter __first, _Sent __last,
_Pred __pred, _Proj __proj = {}) const
{
__first = ranges::find_if(__first, __last, __pred, __proj);
if (__first == __last)
return {__first, __first};
auto __result = __first;
++__first;
for (; __first != __last; ++__first)
if (!std::__invoke(__pred, std::__invoke(__proj, *__first)))
{
*__result = ranges::iter_move(__first);
++__result;
}
return {__result, __first};
}
template, _Proj>>
_Pred>
requires permutable>
constexpr borrowed_subrange_t<_Range>
operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__pred), std::move(__proj));
}
};
inline constexpr __remove_if_fn remove_if{};
struct __remove_fn
{
template _Sent,
typename _Proj = identity,
typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)>
requires indirect_binary_predicate,
const _Tp*>
constexpr subrange<_Iter>
operator()(_Iter __first, _Sent __last,
const _Tp& __value, _Proj __proj = {}) const
{
auto __pred = [&] (auto&& __arg) -> bool {
return std::forward(__arg) == __value;
};
return ranges::remove_if(__first, __last,
std::move(__pred), std::move(__proj));
}
template, _Proj)>
requires permutable>
&& indirect_binary_predicate, _Proj>,
const _Tp*>
constexpr borrowed_subrange_t<_Range>
operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
__value, std::move(__proj));
}
};
inline constexpr __remove_fn remove{};
template
using remove_copy_if_result = in_out_result<_Iter, _Out>;
struct __remove_copy_if_fn
{
template _Sent,
weakly_incrementable _Out, typename _Proj = identity,
indirect_unary_predicate> _Pred>
requires indirectly_copyable<_Iter, _Out>
constexpr remove_copy_if_result<_Iter, _Out>
operator()(_Iter __first, _Sent __last, _Out __result,
_Pred __pred, _Proj __proj = {}) const
{
for (; __first != __last; ++__first)
if (!std::__invoke(__pred, std::__invoke(__proj, *__first)))
{
*__result = *__first;
++__result;
}
return {std::move(__first), std::move(__result)};
}
template, _Proj>>
_Pred>
requires indirectly_copyable, _Out>
constexpr remove_copy_if_result, _Out>
operator()(_Range&& __r, _Out __result,
_Pred __pred, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__result),
std::move(__pred), std::move(__proj));
}
};
inline constexpr __remove_copy_if_fn remove_copy_if{};
template
using remove_copy_result = in_out_result<_Iter, _Out>;
struct __remove_copy_fn
{
template _Sent,
weakly_incrementable _Out, typename _Proj = identity,
typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)>
requires indirectly_copyable<_Iter, _Out>
&& indirect_binary_predicate,
const _Tp*>
constexpr remove_copy_result<_Iter, _Out>
operator()(_Iter __first, _Sent __last, _Out __result,
const _Tp& __value, _Proj __proj = {}) const
{
for (; __first != __last; ++__first)
if (!(std::__invoke(__proj, *__first) == __value))
{
*__result = *__first;
++__result;
}
return {std::move(__first), std::move(__result)};
}
template, _Proj)>
requires indirectly_copyable, _Out>
&& indirect_binary_predicate, _Proj>,
const _Tp*>
constexpr remove_copy_result, _Out>
operator()(_Range&& __r, _Out __result,
const _Tp& __value, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__result), __value, std::move(__proj));
}
};
inline constexpr __remove_copy_fn remove_copy{};
struct __unique_fn
{
template _Sent,
typename _Proj = identity,
indirect_equivalence_relation<
projected<_Iter, _Proj>> _Comp = ranges::equal_to>
constexpr subrange<_Iter>
operator()(_Iter __first, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
__first = ranges::adjacent_find(__first, __last, __comp, __proj);
if (__first == __last)
return {__first, __first};
auto __dest = __first;
++__first;
while (++__first != __last)
if (!std::__invoke(__comp,
std::__invoke(__proj, *__dest),
std::__invoke(__proj, *__first)))
*++__dest = ranges::iter_move(__first);
return {++__dest, __first};
}
template, _Proj>> _Comp = ranges::equal_to>
requires permutable>
constexpr borrowed_subrange_t<_Range>
operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__comp), std::move(__proj));
}
};
inline constexpr __unique_fn unique{};
namespace __detail
{
template
concept __can_reread_output = input_iterator<_Out>
&& same_as<_Tp, iter_value_t<_Out>>;
}
template
using unique_copy_result = in_out_result<_Iter, _Out>;
struct __unique_copy_fn
{
template _Sent,
weakly_incrementable _Out, typename _Proj = identity,
indirect_equivalence_relation<
projected<_Iter, _Proj>> _Comp = ranges::equal_to>
requires indirectly_copyable<_Iter, _Out>
&& (forward_iterator<_Iter>
|| __detail::__can_reread_output<_Out, iter_value_t<_Iter>>
|| indirectly_copyable_storable<_Iter, _Out>)
constexpr unique_copy_result<_Iter, _Out>
operator()(_Iter __first, _Sent __last, _Out __result,
_Comp __comp = {}, _Proj __proj = {}) const
{
if (__first == __last)
return {std::move(__first), std::move(__result)};
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 4269. unique_copy passes arguments to its predicate backwards
// TODO: perform a closer comparison with reference implementations
if constexpr (forward_iterator<_Iter>)
{
auto __next = __first;
*__result = *__next;
while (++__next != __last)
if (!std::__invoke(__comp,
std::__invoke(__proj, *__first),
std::__invoke(__proj, *__next)))
{
__first = __next;
*++__result = *__first;
}
return {__next, std::move(++__result)};
}
else if constexpr (__detail::__can_reread_output<_Out, iter_value_t<_Iter>>)
{
*__result = *__first;
while (++__first != __last)
if (!std::__invoke(__comp,
std::__invoke(__proj, *__result),
std::__invoke(__proj, *__first)))
*++__result = *__first;
return {std::move(__first), std::move(++__result)};
}
else // indirectly_copyable_storable<_Iter, _Out>
{
auto __value = *__first;
*__result = __value;
while (++__first != __last)
{
if (!(bool)std::__invoke(__comp,
std::__invoke(__proj, __value),
std::__invoke(__proj, *__first)))
{
__value = *__first;
*++__result = __value;
}
}
return {std::move(__first), std::move(++__result)};
}
}
template, _Proj>> _Comp = ranges::equal_to>
requires indirectly_copyable, _Out>
&& (forward_iterator>
|| __detail::__can_reread_output<_Out, range_value_t<_Range>>
|| indirectly_copyable_storable, _Out>)
constexpr unique_copy_result, _Out>
operator()(_Range&& __r, _Out __result,
_Comp __comp = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__result),
std::move(__comp), std::move(__proj));
}
};
inline constexpr __unique_copy_fn unique_copy{};
struct __reverse_fn
{
template _Sent>
requires permutable<_Iter>
constexpr _Iter
operator()(_Iter __first, _Sent __last) const
{
auto __i = ranges::next(__first, __last);
auto __tail = __i;
if constexpr (random_access_iterator<_Iter>)
{
if (__first != __last)
{
--__tail;
while (__first < __tail)
{
ranges::iter_swap(__first, __tail);
++__first;
--__tail;
}
}
return __i;
}
else
{
for (;;)
if (__first == __tail || __first == --__tail)
break;
else
{
ranges::iter_swap(__first, __tail);
++__first;
}
return __i;
}
}
template
requires permutable>
constexpr borrowed_iterator_t<_Range>
operator()(_Range&& __r) const
{
return (*this)(ranges::begin(__r), ranges::end(__r));
}
};
inline constexpr __reverse_fn reverse{};
template
using reverse_copy_result = in_out_result<_Iter, _Out>;
struct __reverse_copy_fn
{
template _Sent,
weakly_incrementable _Out>
requires indirectly_copyable<_Iter, _Out>
constexpr reverse_copy_result<_Iter, _Out>
operator()(_Iter __first, _Sent __last, _Out __result) const
{
auto __i = ranges::next(__first, __last);
auto __tail = __i;
while (__first != __tail)
{
--__tail;
*__result = *__tail;
++__result;
}
return {__i, std::move(__result)};
}
template
requires indirectly_copyable, _Out>
constexpr reverse_copy_result, _Out>
operator()(_Range&& __r, _Out __result) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__result));
}
};
inline constexpr __reverse_copy_fn reverse_copy{};
struct __rotate_fn
{
template _Sent>
constexpr subrange<_Iter>
operator()(_Iter __first, _Iter __middle, _Sent __last) const
{
auto __lasti = ranges::next(__first, __last);
if (__first == __middle)
return {__lasti, __lasti};
if (__last == __middle)
return {std::move(__first), std::move(__lasti)};
if constexpr (random_access_iterator<_Iter>)
{
auto __n = __lasti - __first;
auto __k = __middle - __first;
if (__k == __n - __k)
{
ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
return {std::move(__middle), std::move(__lasti)};
}
auto __p = __first;
auto __ret = __first + (__lasti - __middle);
for (;;)
{
if (__k < __n - __k)
{
// TODO: is_pod is deprecated, but this condition is
// consistent with the STL implementation.
if constexpr (__is_pod(iter_value_t<_Iter>))
if (__k == 1)
{
auto __t = std::move(*__p);
ranges::move(__p + 1, __p + __n, __p);
*(__p + __n - 1) = std::move(__t);
return {std::move(__ret), std::move(__lasti)};
}
auto __q = __p + __k;
for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
{
ranges::iter_swap(__p, __q);
++__p;
++__q;
}
__n %= __k;
if (__n == 0)
return {std::move(__ret), std::move(__lasti)};
ranges::swap(__n, __k);
__k = __n - __k;
}
else
{
__k = __n - __k;
// TODO: is_pod is deprecated, but this condition is
// consistent with the STL implementation.
if constexpr (__is_pod(iter_value_t<_Iter>))
if (__k == 1)
{
auto __t = std::move(*(__p + __n - 1));
ranges::move_backward(__p, __p + __n - 1, __p + __n);
*__p = std::move(__t);
return {std::move(__ret), std::move(__lasti)};
}
auto __q = __p + __n;
__p = __q - __k;
for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
{
--__p;
--__q;
ranges::iter_swap(__p, __q);
}
__n %= __k;
if (__n == 0)
return {std::move(__ret), std::move(__lasti)};
std::swap(__n, __k);
}
}
}
else if constexpr (bidirectional_iterator<_Iter>)
{
auto __tail = __lasti;
ranges::reverse(__first, __middle);
ranges::reverse(__middle, __tail);
while (__first != __middle && __middle != __tail)
{
ranges::iter_swap(__first, --__tail);
++__first;
}
if (__first == __middle)
{
ranges::reverse(__middle, __tail);
return {std::move(__tail), std::move(__lasti)};
}
else
{
ranges::reverse(__first, __middle);
return {std::move(__first), std::move(__lasti)};
}
}
else
{
auto __first2 = __middle;
do
{
ranges::iter_swap(__first, __first2);
++__first;
++__first2;
if (__first == __middle)
__middle = __first2;
} while (__first2 != __last);
auto __ret = __first;
__first2 = __middle;
while (__first2 != __last)
{
ranges::iter_swap(__first, __first2);
++__first;
++__first2;
if (__first == __middle)
__middle = __first2;
else if (__first2 == __last)
__first2 = __middle;
}
return {std::move(__ret), std::move(__lasti)};
}
}
template
requires permutable>
constexpr borrowed_subrange_t<_Range>
operator()(_Range&& __r, iterator_t<_Range> __middle) const
{
return (*this)(ranges::begin(__r), std::move(__middle),
ranges::end(__r));
}
};
inline constexpr __rotate_fn rotate{};
template
using rotate_copy_result = in_out_result<_Iter, _Out>;
struct __rotate_copy_fn
{
template _Sent,
weakly_incrementable _Out>
requires indirectly_copyable<_Iter, _Out>
constexpr rotate_copy_result<_Iter, _Out>
operator()(_Iter __first, _Iter __middle, _Sent __last,
_Out __result) const
{
auto __copy1 = ranges::copy(__middle,
std::move(__last),
std::move(__result));
auto __copy2 = ranges::copy(std::move(__first),
std::move(__middle),
std::move(__copy1.out));
return { std::move(__copy1.in), std::move(__copy2.out) };
}
template
requires indirectly_copyable, _Out>
constexpr rotate_copy_result, _Out>
operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result) const
{
return (*this)(ranges::begin(__r), std::move(__middle),
ranges::end(__r), std::move(__result));
}
};
inline constexpr __rotate_copy_fn rotate_copy{};
struct __sample_fn
{
template _Sent,
weakly_incrementable _Out, typename _Gen>
requires (forward_iterator<_Iter> || random_access_iterator<_Out>)
&& indirectly_copyable<_Iter, _Out>
&& uniform_random_bit_generator>
_Out
operator()(_Iter __first, _Sent __last, _Out __out,
iter_difference_t<_Iter> __n, _Gen&& __g) const
{
// FIXME: Correctly handle integer-class difference types.
if constexpr (forward_iterator<_Iter>)
{
using _Size = iter_difference_t<_Iter>;
using __distrib_type = uniform_int_distribution<_Size>;
using __param_type = typename __distrib_type::param_type;
using _USize = __detail::__make_unsigned_like_t<_Size>;
using __uc_type
= common_type_t::result_type, _USize>;
if (__first == __last)
return __out;
__distrib_type __d{};
_Size __unsampled_sz = ranges::distance(__first, __last);
__n = std::min(__n, __unsampled_sz);
// If possible, we use __gen_two_uniform_ints to efficiently produce
// two random numbers using a single distribution invocation:
const __uc_type __urngrange = __g.max() - __g.min();
if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
// I.e. (__urngrange >= __unsampled_sz * __unsampled_sz) but without
// wrapping issues.
{
while (__n != 0 && __unsampled_sz >= 2)
{
const pair<_Size, _Size> __p =
__gen_two_uniform_ints(__unsampled_sz, __unsampled_sz - 1, __g);
--__unsampled_sz;
if (__p.first < __n)
{
*__out = *__first;
++__out;
--__n;
}
++__first;
if (__n == 0) break;
--__unsampled_sz;
if (__p.second < __n)
{
*__out = *__first;
++__out;
--__n;
}
++__first;
}
}
// The loop above is otherwise equivalent to this one-at-a-time version:
for (; __n != 0; ++__first)
if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
{
*__out = *__first;
++__out;
--__n;
}
return __out;
}
else
{
using __distrib_type
= uniform_int_distribution>;
using __param_type = typename __distrib_type::param_type;
__distrib_type __d{};
iter_difference_t<_Iter> __sample_sz = 0;
while (__first != __last && __sample_sz != __n)
{
__out[__sample_sz++] = *__first;
++__first;
}
for (auto __pop_sz = __sample_sz; __first != __last;
++__first, (void) ++__pop_sz)
{
const auto __k = __d(__g, __param_type{0, __pop_sz});
if (__k < __n)
__out[__k] = *__first;
}
return __out + iter_difference_t<_Out>(__sample_sz);
}
}
template
requires (forward_range<_Range> || random_access_iterator<_Out>)
&& indirectly_copyable, _Out>
&& uniform_random_bit_generator>
_Out
operator()(_Range&& __r, _Out __out,
range_difference_t<_Range> __n, _Gen&& __g) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__out), __n,
std::forward<_Gen>(__g));
}
};
inline constexpr __sample_fn sample{};
struct __shuffle_fn
{
template _Sent,
typename _Gen>
requires permutable<_Iter>
&& uniform_random_bit_generator>
_Iter
operator()(_Iter __first, _Sent __last, _Gen&& __g) const
{
// FIXME: Correctly handle integer-class difference types.
if (__first == __last)
return __first;
using _DistanceType = iter_difference_t<_Iter>;
using __ud_type = __detail::__make_unsigned_like_t<_DistanceType>;
using __distr_type = std::uniform_int_distribution<__ud_type>;
using __p_type = typename __distr_type::param_type;
using __uc_type
= common_type_t::result_type, __ud_type>;
const __uc_type __urngrange = __g.max() - __g.min();
const __uc_type __urange = __uc_type(__last - __first);
if (__urngrange / __urange >= __urange)
// I.e. (__urngrange >= __urange * __urange) but without wrap issues.
{
_Iter __i = __first + 1;
// Since we know the range isn't empty, an even number of elements
// means an uneven number of elements /to swap/, in which case we
// do the first one up front:
if ((__urange % 2) == 0)
{
__distr_type __d{0, 1};
ranges::iter_swap(__i++, __first + __d(__g));
}
// Now we know that __last - __i is even, so we do the rest in pairs,
// using a single distribution invocation to produce swap positions
// for two successive elements at a time:
while (__i != __last)
{
const __uc_type __swap_range = __uc_type(__i - __first) + 1;
const pair<__uc_type, __uc_type> __pospos =
__gen_two_uniform_ints(__swap_range, __swap_range + 1, __g);
ranges::iter_swap(__i++, __first + __pospos.first);
ranges::iter_swap(__i++, __first + __pospos.second);
}
return __i;
}
__distr_type __d;
_Iter __i = __first + 1;
for (; __i != __last; ++__i)
ranges::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
return __i;
}
template
requires permutable>
&& uniform_random_bit_generator>
borrowed_iterator_t<_Range>
operator()(_Range&& __r, _Gen&& __g) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::forward<_Gen>(__g));
}
};
inline constexpr __shuffle_fn shuffle{};
namespace __detail
{
template
constexpr void
__push_heap(_Iter __first,
iter_difference_t<_Iter> __holeIndex,
iter_difference_t<_Iter> __topIndex,
iter_value_t<_Iter> __value,
_Comp __comp)
{
auto __parent = (__holeIndex - 1) / 2;
while (__holeIndex > __topIndex
&& __comp(*(__first + __parent), __value))
{
*(__first + __holeIndex) = ranges::iter_move(__first + __parent);
__holeIndex = __parent;
__parent = (__holeIndex - 1) / 2;
}
*(__first + __holeIndex) = std::move(__value);
}
} // namespace __detail
struct __push_heap_fn
{
template _Sent,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<_Iter, _Comp, _Proj>
constexpr _Iter
operator()(_Iter __first, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
if constexpr (!same_as<_Iter, _Sent>)
return (*this)(__first, ranges::next(__first, __last),
std::move(__comp), std::move(__proj));
else
{
auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
__detail::__push_heap(__first, (__last - __first) - 1,
0, ranges::iter_move(__last - 1),
__comp_proj);
return __last;
}
}
template
requires sortable, _Comp, _Proj>
constexpr borrowed_iterator_t<_Range>
operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__comp), std::move(__proj));
}
};
inline constexpr __push_heap_fn push_heap{};
namespace __detail
{
template
constexpr void
__adjust_heap(_Iter __first,
iter_difference_t<_Iter> __holeIndex,
iter_difference_t<_Iter> __len,
iter_value_t<_Iter> __value,
_Comp __comp)
{
auto __topIndex = __holeIndex;
auto __secondChild = __holeIndex;
while (__secondChild < (__len - 1) / 2)
{
__secondChild = 2 * (__secondChild + 1);
if (__comp(*(__first + __secondChild),
*(__first + (__secondChild - 1))))
__secondChild--;
*(__first + __holeIndex) = ranges::iter_move(__first + __secondChild);
__holeIndex = __secondChild;
}
if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
{
__secondChild = 2 * (__secondChild + 1);
*(__first + __holeIndex) = ranges::iter_move(__first + (__secondChild - 1));
__holeIndex = __secondChild - 1;
}
__detail::__push_heap(__first, __holeIndex, __topIndex,
std::move(__value), __comp);
}
template
constexpr void
__pop_heap(_Iter __first, _Iter __last, _Iter __result, _Comp __comp)
{
iter_value_t<_Iter> __value = ranges::iter_move(__result);
*__result = ranges::iter_move(__first);
__detail::__adjust_heap(__first, 0, __last - __first,
std::move(__value), __comp);
}
} // namespace __detail
struct __pop_heap_fn
{
template _Sent,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<_Iter, _Comp, _Proj>
constexpr _Iter
operator()(_Iter __first, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
if constexpr (!same_as<_Iter, _Sent>)
return (*this)(__first, ranges::next(__first, __last),
std::move(__comp), std::move(__proj));
else
{
if (__last - __first > 1)
{
auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
__detail::__pop_heap(__first, __last - 1, __last - 1, __comp_proj);
}
return __last;
}
}
template
requires sortable, _Comp, _Proj>
constexpr borrowed_iterator_t<_Range>
operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__comp), std::move(__proj));
}
};
inline constexpr __pop_heap_fn pop_heap{};
struct __make_heap_fn
{
template _Sent,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<_Iter, _Comp, _Proj>
constexpr _Iter
operator()(_Iter __first, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
if constexpr (!same_as<_Iter, _Sent>)
return (*this)(__first, ranges::next(__first, __last),
std::move(__comp), std::move(__proj));
else
{
const auto __len = __last - __first;
if (__len < 2)
return __last;
auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
auto __parent = (__len - 2) / 2;
while (true)
{
iter_value_t<_Iter> __value = ranges::iter_move(__first + __parent);
__detail::__adjust_heap(__first, __parent, __len,
std::move(__value),
__comp_proj);
if (__parent == 0)
break;
__parent--;
}
return __last;
}
}
template
requires sortable, _Comp, _Proj>
constexpr borrowed_iterator_t<_Range>
operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__comp), std::move(__proj));
}
};
inline constexpr __make_heap_fn make_heap{};
struct __sort_heap_fn
{
template _Sent,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<_Iter, _Comp, _Proj>
constexpr _Iter
operator()(_Iter __first, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
if constexpr (!same_as<_Iter, _Sent>)
return (*this)(__first, ranges::next(__first, __last),
std::move(__comp), std::move(__proj));
else
{
auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
_Iter __ret = __last;
while (__last - __first > 1)
{
--__last;
__detail::__pop_heap(__first, __last, __last, __comp_proj);
}
return __ret;
}
}
template
requires sortable, _Comp, _Proj>
constexpr borrowed_iterator_t<_Range>
operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__comp), std::move(__proj));
}
};
inline constexpr __sort_heap_fn sort_heap{};
struct __is_heap_until_fn
{
template _Sent,
typename _Proj = identity,
indirect_strict_weak_order>
_Comp = ranges::less>
constexpr _Iter
operator()(_Iter __first, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
iter_difference_t<_Iter> __n = ranges::distance(__first, __last);
iter_difference_t<_Iter> __parent = 0, __child = 1;
for (; __child < __n; ++__child)
if (std::__invoke(__comp,
std::__invoke(__proj, *(__first + __parent)),
std::__invoke(__proj, *(__first + __child))))
return __first + __child;
else if ((__child & 1) == 0)
++__parent;
return __first + __n;
}
template, _Proj>>
_Comp = ranges::less>
constexpr borrowed_iterator_t<_Range>
operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__comp), std::move(__proj));
}
};
inline constexpr __is_heap_until_fn is_heap_until{};
struct __is_heap_fn
{
template _Sent,
typename _Proj = identity,
indirect_strict_weak_order>
_Comp = ranges::less>
constexpr bool
operator()(_Iter __first, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
return (__last
== ranges::is_heap_until(__first, __last,
std::move(__comp),
std::move(__proj)));
}
template, _Proj>>
_Comp = ranges::less>
constexpr bool
operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__comp), std::move(__proj));
}
};
inline constexpr __is_heap_fn is_heap{};
namespace __detail
{
template
constexpr void
__move_median_to_first(_Iter __result, _Iter __a, _Iter __b, _Iter __c,
_Comp __comp)
{
if (__comp(*__a, *__b))
{
if (__comp(*__b, *__c))
ranges::iter_swap(__result, __b);
else if (__comp(*__a, *__c))
ranges::iter_swap(__result, __c);
else
ranges::iter_swap(__result, __a);
}
else if (__comp(*__a, *__c))
ranges::iter_swap(__result, __a);
else if (__comp(*__b, *__c))
ranges::iter_swap(__result, __c);
else
ranges::iter_swap(__result, __b);
}
template
constexpr void
__unguarded_linear_insert(_Iter __last, _Comp __comp)
{
iter_value_t<_Iter> __val = ranges::iter_move(__last);
_Iter __next = __last;
--__next;
while (__comp(__val, *__next))
{
*__last = ranges::iter_move(__next);
__last = __next;
--__next;
}
*__last = std::move(__val);
}
template
constexpr void
__insertion_sort(_Iter __first, _Iter __last, _Comp __comp)
{
if (__first == __last)
return;
for (_Iter __i = __first + 1; __i != __last; ++__i)
{
if (__comp(*__i, *__first))
{
iter_value_t<_Iter> __val = ranges::iter_move(__i);
ranges::move_backward(__first, __i, __i + 1);
*__first = std::move(__val);
}
else
__detail::__unguarded_linear_insert(__i, __comp);
}
}
template
constexpr void
__unguarded_insertion_sort(_Iter __first, _Iter __last, _Comp __comp)
{
for (_Iter __i = __first; __i != __last; ++__i)
__detail::__unguarded_linear_insert(__i, __comp);
}
inline constexpr int __sort_threshold = 16;
template
constexpr void
__final_insertion_sort(_Iter __first, _Iter __last, _Comp __comp)
{
if (__last - __first > __sort_threshold)
{
__detail::__insertion_sort(__first, __first + __sort_threshold, __comp);
__detail::__unguarded_insertion_sort(__first + __sort_threshold, __last,
__comp);
}
else
__detail::__insertion_sort(__first, __last, __comp);
}
template
constexpr _Iter
__unguarded_partition(_Iter __first, _Iter __last, _Iter __pivot, _Comp __comp)
{
while (true)
{
while (__comp(*__first, *__pivot))
++__first;
--__last;
while (__comp(*__pivot, *__last))
--__last;
if (!(__first < __last))
return __first;
ranges::iter_swap(__first, __last);
++__first;
}
}
template
constexpr _Iter
__unguarded_partition_pivot(_Iter __first, _Iter __last, _Comp __comp)
{
_Iter __mid = __first + (__last - __first) / 2;
__detail::__move_median_to_first(__first, __first + 1, __mid, __last - 1, __comp);
return __detail::__unguarded_partition(__first + 1, __last, __first, __comp);
}
template
constexpr void
__heap_select(_Iter __first, _Iter __middle, _Iter __last, _Comp __comp)
{
ranges::make_heap(__first, __middle, __comp);
for (_Iter __i = __middle; __i < __last; ++__i)
if (__comp(*__i, *__first))
__detail::__pop_heap(__first, __middle, __i, __comp);
}
template
constexpr void
__partial_sort(_Iter __first, _Iter __middle, _Iter __last, _Comp __comp)
{
__detail::__heap_select(__first, __middle, __last, __comp);
ranges::sort_heap(__first, __middle, __comp);
}
template
constexpr void
__introsort_loop(_Iter __first, _Iter __last, unsigned __depth_limit, _Comp __comp)
{
while (__last - __first > __sort_threshold)
{
if (__depth_limit == 0)
{
__detail::__partial_sort(__first, __last, __last, __comp);
return;
}
--__depth_limit;
_Iter __cut = __detail::__unguarded_partition_pivot(__first, __last, __comp);
__detail::__introsort_loop(__cut, __last, __depth_limit, __comp);
__last = __cut;
}
}
} // namespace __detail
struct __sort_fn
{
template _Sent,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<_Iter, _Comp, _Proj>
constexpr _Iter
operator()(_Iter __first, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
if constexpr (!same_as<_Iter, _Sent>)
return (*this)(__first, ranges::next(__first, __last),
std::move(__comp), std::move(__proj));
else
{
if (__first != __last)
{
auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
auto __n = __detail::__to_unsigned_like(__last - __first);
unsigned __depth_limit = (std::__bit_width(__n) - 1) * 2;
__detail::__introsort_loop(__first, __last, __depth_limit, __comp_proj);
__detail::__final_insertion_sort(__first, __last, __comp_proj);
}
return __last;
}
}
template
requires sortable, _Comp, _Proj>
constexpr borrowed_iterator_t<_Range>
operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__comp), std::move(__proj));
}
};
inline constexpr __sort_fn sort{};
namespace __detail
{
// This is a helper function for the __merge_sort_loop routines.
template
_Out
__move_merge(_Iter __first1, _Iter __last1,
_Iter __first2, _Iter __last2,
_Out __result, _Comp __comp)
{
while (__first1 != __last1 && __first2 != __last2)
{
if (__comp(*__first2, *__first1))
{
*__result = ranges::iter_move(__first2);
++__first2;
}
else
{
*__result = ranges::iter_move(__first1);
++__first1;
}
++__result;
}
return ranges::move(__first2, __last2,
ranges::move(__first1, __last1, __result).out).out;
}
template
void
__merge_sort_loop(_Iter __first, _Iter __last, _Out __result,
_Distance __step_size, _Comp __comp)
{
const _Distance __two_step = 2 * __step_size;
while (__last - __first >= __two_step)
{
__result = __detail::__move_merge(__first, __first + __step_size,
__first + __step_size,
__first + __two_step,
__result, __comp);
__first += __two_step;
}
__step_size = ranges::min(_Distance(__last - __first), __step_size);
__detail::__move_merge(__first, __first + __step_size,
__first + __step_size, __last, __result, __comp);
}
template
constexpr void
__chunk_insertion_sort(_Iter __first, _Iter __last,
_Distance __chunk_size, _Compare __comp)
{
while (__last - __first >= __chunk_size)
{
__detail::__insertion_sort(__first, __first + __chunk_size, __comp);
__first += __chunk_size;
}
__detail::__insertion_sort(__first, __last, __comp);
}
template
void
__merge_sort_with_buffer(_Iter __first, _Iter __last,
_Pointer __buffer, _Comp __comp)
{
using _Distance = iter_difference_t<_Iter>;
const _Distance __len = __last - __first;
const _Pointer __buffer_last = __buffer + ptrdiff_t(__len);
constexpr int __chunk_size = 7;
_Distance __step_size = __chunk_size;
__detail::__chunk_insertion_sort(__first, __last, __step_size, __comp);
while (__step_size < __len)
{
__detail::__merge_sort_loop(__first, __last, __buffer,
__step_size, __comp);
__step_size *= 2;
__detail::__merge_sort_loop(__buffer, __buffer_last, __first,
ptrdiff_t(__step_size), __comp);
__step_size *= 2;
}
}
template
void
__merge_adaptive(_Iter __first, _Iter __middle, _Iter __last,
iter_difference_t<_Iter> __len1,
iter_difference_t<_Iter> __len2,
_Pointer __buffer, _Comp __comp); // defined near inplace_merge
template
void
__merge_adaptive_resize(_Iter __first, _Iter __middle, _Iter __last,
_Distance __len1, _Distance __len2,
_Pointer __buffer, _Distance __buffer_size,
_Comp __comp); // defined near inplace_merge
template
constexpr void
__merge_without_buffer(_Iter __first, _Iter __middle, _Iter __last,
_Distance __len1, _Distance __len2,
_Comp __comp); // defined near inplace_merge
template
void
__stable_sort_adaptive(_Iter __first, _Iter __middle, _Iter __last,
_Pointer __buffer, _Comp __comp)
{
__detail::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
__detail::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
__detail::__merge_adaptive(__first, __middle, __last,
__middle - __first, __last - __middle,
__buffer, __comp);
}
template
void
__stable_sort_adaptive_resize(_Iter __first, _Iter __last,
_Pointer __buffer, _Distance __buffer_size,
_Comp __comp)
{
const _Distance __len = (__last - __first + 1) / 2;
const _Iter __middle = __first + __len;
if (__len > __buffer_size)
{
__detail::__stable_sort_adaptive_resize(__first, __middle, __buffer,
__buffer_size, __comp);
__detail::__stable_sort_adaptive_resize(__middle, __last, __buffer,
__buffer_size, __comp);
__detail::__merge_adaptive_resize(__first, __middle, __last,
_Distance(__middle - __first),
_Distance(__last - __middle),
__buffer, __buffer_size,
__comp);
}
else
__detail::__stable_sort_adaptive(__first, __middle, __last,
__buffer, __comp);
}
template
constexpr void
__inplace_stable_sort(_Iter __first, _Iter __last, _Comp __comp)
{
if (__last - __first < 15)
{
__detail::__insertion_sort(__first, __last, __comp);
return;
}
_Iter __middle = __first + (__last - __first) / 2;
__detail::__inplace_stable_sort(__first, __middle, __comp);
__detail::__inplace_stable_sort(__middle, __last, __comp);
__detail::__merge_without_buffer(__first, __middle, __last,
__middle - __first,
__last - __middle,
__comp);
}
} // namespace __detail
struct __stable_sort_fn
{
template _Sent,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<_Iter, _Comp, _Proj>
_GLIBCXX26_CONSTEXPR
_Iter
operator()(_Iter __first, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
if constexpr (!same_as<_Iter, _Sent>)
return (*this)(__first, ranges::next(__first, __last),
std::move(__comp), std::move(__proj));
else
{
using _DistanceType = iter_difference_t<_Iter>;
if (__first == __last)
return __last;
auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
#if _GLIBCXX_HOSTED
# if __glibcxx_constexpr_algorithms >= 202306L // >= C++26
if consteval {
__detail::__inplace_stable_sort(__first, __last, __comp_proj);
return __last;
}
# endif
typedef _Temporary_buffer<_Iter, iter_value_t<_Iter>> _TmpBuf;
// __stable_sort_adaptive sorts the range in two halves,
// so the buffer only needs to fit half the range at once.
_TmpBuf __buf(__first, ptrdiff_t((__last - __first + 1) / 2));
if (__buf._M_requested_size() == __buf.size()) [[likely]]
__detail::__stable_sort_adaptive(__first,
__first + _DistanceType(__buf.size()),
__last, __buf.begin(), __comp_proj);
else if (__buf.begin()) [[unlikely]]
__detail::__inplace_stable_sort(__first, __last, __comp_proj);
else
__detail::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
_DistanceType(__buf.size()),
__comp_proj);
#else
__detail::__inplace_stable_sort(__first, __last, __comp_proj);
#endif
return __last;
}
}
template
requires sortable, _Comp, _Proj>
_GLIBCXX26_CONSTEXPR
borrowed_iterator_t<_Range>
operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__comp), std::move(__proj));
}
};
inline constexpr __stable_sort_fn stable_sort{};
struct __partial_sort_fn
{
template _Sent,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<_Iter, _Comp, _Proj>
constexpr _Iter
operator()(_Iter __first, _Iter __middle, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
if (__first == __middle)
return ranges::next(__first, __last);
ranges::make_heap(__first, __middle, __comp, __proj);
auto __i = __middle;
for (; __i != __last; ++__i)
if (std::__invoke(__comp,
std::__invoke(__proj, *__i),
std::__invoke(__proj, *__first)))
{
ranges::pop_heap(__first, __middle, __comp, __proj);
ranges::iter_swap(__middle-1, __i);
ranges::push_heap(__first, __middle, __comp, __proj);
}
ranges::sort_heap(__first, __middle, __comp, __proj);
return __i;
}
template
requires sortable, _Comp, _Proj>
constexpr borrowed_iterator_t<_Range>
operator()(_Range&& __r, iterator_t<_Range> __middle,
_Comp __comp = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), std::move(__middle),
ranges::end(__r),
std::move(__comp), std::move(__proj));
}
};
inline constexpr __partial_sort_fn partial_sort{};
template
using partial_sort_copy_result = in_out_result<_Iter, _Out>;
struct __partial_sort_copy_fn
{
template _Sent1,
random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
typename _Comp = ranges::less,
typename _Proj1 = identity, typename _Proj2 = identity>
requires indirectly_copyable<_Iter1, _Iter2>
&& sortable<_Iter2, _Comp, _Proj2>
&& indirect_strict_weak_order<_Comp,
projected<_Iter1, _Proj1>,
projected<_Iter2, _Proj2>>
constexpr partial_sort_copy_result<_Iter1, _Iter2>
operator()(_Iter1 __first, _Sent1 __last,
_Iter2 __result_first, _Sent2 __result_last,
_Comp __comp = {},
_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
{
if (__result_first == __result_last)
{
// TODO: Eliminating the variable __lasti triggers an ICE.
auto __lasti = ranges::next(std::move(__first),
std::move(__last));
return {std::move(__lasti), std::move(__result_first)};
}
auto __result_real_last = __result_first;
while (__first != __last && __result_real_last != __result_last)
{
*__result_real_last = *__first;
++__result_real_last;
++__first;
}
ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
for (; __first != __last; ++__first)
if (std::__invoke(__comp,
std::__invoke(__proj1, *__first),
std::__invoke(__proj2, *__result_first)))
{
ranges::pop_heap(__result_first, __result_real_last,
__comp, __proj2);
*(__result_real_last-1) = *__first;
ranges::push_heap(__result_first, __result_real_last,
__comp, __proj2);
}
ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
return {std::move(__first), std::move(__result_real_last)};
}
template
requires indirectly_copyable, iterator_t<_Range2>>
&& sortable, _Comp, _Proj2>
&& indirect_strict_weak_order<_Comp,
projected, _Proj1>,
projected, _Proj2>>
constexpr partial_sort_copy_result,
borrowed_iterator_t<_Range2>>
operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
ranges::begin(__out), ranges::end(__out),
std::move(__comp),
std::move(__proj1), std::move(__proj2));
}
};
inline constexpr __partial_sort_copy_fn partial_sort_copy{};
struct __is_sorted_until_fn
{
template _Sent,
typename _Proj = identity,
indirect_strict_weak_order>
_Comp = ranges::less>
constexpr _Iter
operator()(_Iter __first, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
if (__first == __last)
return __first;
auto __next = __first;
for (++__next; __next != __last; __first = __next, (void)++__next)
if (std::__invoke(__comp,
std::__invoke(__proj, *__next),
std::__invoke(__proj, *__first)))
return __next;
return __next;
}
template, _Proj>>
_Comp = ranges::less>
constexpr borrowed_iterator_t<_Range>
operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__comp), std::move(__proj));
}
};
inline constexpr __is_sorted_until_fn is_sorted_until{};
struct __is_sorted_fn
{
template _Sent,
typename _Proj = identity,
indirect_strict_weak_order>
_Comp = ranges::less>
constexpr bool
operator()(_Iter __first, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
if (__first == __last)
return true;
auto __next = __first;
for (++__next; __next != __last; __first = __next, (void)++__next)
if (std::__invoke(__comp,
std::__invoke(__proj, *__next),
std::__invoke(__proj, *__first)))
return false;
return true;
}
template, _Proj>>
_Comp = ranges::less>
constexpr bool
operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__comp), std::move(__proj));
}
};
inline constexpr __is_sorted_fn is_sorted{};
namespace __detail
{
template
constexpr void
__introselect(_Iter __first, _Iter __nth, _Iter __last,
iter_difference_t<_Iter> __depth_limit, _Comp __comp)
{
while (__last - __first > 3)
{
if (__depth_limit == 0)
{
__detail::__heap_select(__first, __nth + 1, __last, __comp);
// Place the nth largest element in its final position.
ranges::iter_swap(__first, __nth);
return;
}
--__depth_limit;
_Iter __cut = __detail::__unguarded_partition_pivot(__first, __last, __comp);
if (__cut <= __nth)
__first = __cut;
else
__last = __cut;
}
__detail::__insertion_sort(__first, __last, __comp);
}
} // namespace __detail
struct __nth_element_fn
{
template _Sent,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<_Iter, _Comp, _Proj>
constexpr _Iter
operator()(_Iter __first, _Iter __nth, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
if constexpr (!same_as<_Iter, _Sent>)
return (*this)(__first, __nth, ranges::next(__first, __last),
std::move(__comp), std::move(__proj));
else
{
if (__first == __last || __nth == __last)
return __last;
auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
auto __n = __detail::__to_unsigned_like(__last - __first);
__detail::__introselect(__first, __nth, __last,
std::__bit_width(__n) * 2,
__comp_proj);
return __last;
}
}
template