| // Core algorithmic facilities -*- C++ -*- | |
| // Copyright (C) 2020-2026 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 | |
| // <http://www.gnu.org/licenses/>. | |
| /** @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> // __bit_width | |
| #if __cplusplus > 202002L | |
| #include <optional> | |
| #endif | |
| #include <bits/ranges_algobase.h> | |
| #include <bits/ranges_util.h> | |
| #include <bits/uniform_int_dist.h> // concept uniform_random_bit_generator | |
| #if __glibcxx_concepts | |
| namespace std _GLIBCXX_VISIBILITY(default) | |
| { | |
| _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
| namespace ranges | |
| { | |
| namespace __detail | |
| { | |
| template<typename _Fp> | |
| using __by_ref_or_value_fn | |
| = __conditional_t<is_scalar_v<_Fp> || is_empty_v<_Fp>, _Fp, _Fp&>; | |
| template<typename _Comp, typename _Proj> | |
| 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<typename _Tp, typename _Up> | |
| 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<typename _Comp, typename _Proj> | |
| constexpr _Comp_proj<_Comp, _Proj> | |
| __make_comp_proj(_Comp& __comp, _Proj& __proj) | |
| { return {__comp, __proj}; } | |
| template<typename _Pred, typename _Proj> | |
| 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<typename _Tp> | |
| constexpr bool | |
| operator()(_Tp&& __x) | |
| { | |
| return std::__invoke(_M_pred, | |
| std::__invoke(_M_proj, std::forward<_Tp>(__x))); | |
| } | |
| }; | |
| template<typename _Pred, typename _Proj> | |
| constexpr _Pred_proj<_Pred, _Proj> | |
| __make_pred_proj(_Pred& __pred, _Proj& __proj) | |
| { return {__pred, __proj}; } | |
| } // namespace __detail | |
| struct __all_of_fn | |
| { | |
| template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
| [[nodiscard]] 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<input_range _Range, typename _Proj = identity, | |
| indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
| _Pred> | |
| [[nodiscard]] 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<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
| [[nodiscard]] 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<input_range _Range, typename _Proj = identity, | |
| indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
| _Pred> | |
| [[nodiscard]] 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<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
| [[nodiscard]] 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<input_range _Range, typename _Proj = identity, | |
| indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
| _Pred> | |
| [[nodiscard]] 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<typename _Iter, typename _Fp> | |
| struct in_fun_result | |
| { | |
| [[no_unique_address]] _Iter in; | |
| [[no_unique_address]] _Fp fun; | |
| template<typename _Iter2, typename _F2p> | |
| requires convertible_to<const _Iter&, _Iter2> | |
| && convertible_to<const _Fp&, _F2p> | |
| constexpr | |
| operator in_fun_result<_Iter2, _F2p>() const & | |
| { return {in, fun}; } | |
| template<typename _Iter2, typename _F2p> | |
| requires convertible_to<_Iter, _Iter2> && convertible_to<_Fp, _F2p> | |
| constexpr | |
| operator in_fun_result<_Iter2, _F2p>() && | |
| { return {std::move(in), std::move(fun)}; } | |
| }; | |
| template<typename _Iter, typename _Fp> | |
| using for_each_result = in_fun_result<_Iter, _Fp>; | |
| // Apply __f to the result of applying __proj to each element in | |
| // [__first, __last). | |
| // Dispatches to __for_each_segment for segmented iterators | |
| // (e.g. deque::iterator). | |
| // Returns an iterator equal to __last. | |
| template<typename _InputIterator, typename _Sentinel, typename _Function, | |
| typename _Proj> | |
| constexpr _InputIterator | |
| __for_each(_InputIterator __first, _Sentinel __last, _Function&& __f, | |
| _Proj& __proj) | |
| { | |
| if constexpr (__segmented_iterator<_InputIterator> | |
| && same_as<_InputIterator, _Sentinel>) | |
| { | |
| std::__for_each_segment(__first, __last, | |
| [&](auto __lfirst, auto __llast) | |
| { return ranges::__for_each(__lfirst, __llast, __f, __proj); }); | |
| return __last; | |
| } | |
| else | |
| { | |
| for (; __first != __last; ++__first) | |
| std::__invoke(__f, std::__invoke(__proj, *__first)); | |
| return __first; | |
| } | |
| } | |
| struct __for_each_fn | |
| { | |
| template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun> | |
| constexpr for_each_result<_Iter, _Fun> | |
| operator()(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {}) const | |
| { | |
| auto __end = ranges::__for_each(std::move(__first), std::move(__last), __f, | |
| __proj); | |
| return { std::move(__end), std::move(__f) }; | |
| } | |
| template<input_range _Range, typename _Proj = identity, | |
| indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>> | |
| _Fun> | |
| constexpr for_each_result<borrowed_iterator_t<_Range>, _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<typename _Iter, typename _Fp> | |
| using for_each_n_result = in_fun_result<_Iter, _Fp>; | |
| struct __for_each_n_fn | |
| { | |
| template<input_iterator _Iter, typename _Proj = identity, | |
| indirectly_unary_invocable<projected<_Iter, _Proj>> _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 <bits/ranges_util.h>. | |
| struct __find_first_of_fn | |
| { | |
| template<input_iterator _Iter1, sentinel_for<_Iter1> _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> | |
| [[nodiscard]] 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<input_range _Range1, forward_range _Range2, | |
| typename _Pred = ranges::equal_to, | |
| typename _Proj1 = identity, typename _Proj2 = identity> | |
| requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, | |
| _Pred, _Proj1, _Proj2> | |
| [[nodiscard]] 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<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)> | |
| requires indirect_binary_predicate<ranges::equal_to, | |
| projected<_Iter, _Proj>, | |
| const _Tp*> | |
| [[nodiscard]] 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<input_range _Range, typename _Proj = identity, | |
| typename _Tp | |
| _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)> | |
| requires indirect_binary_predicate<ranges::equal_to, | |
| projected<iterator_t<_Range>, _Proj>, | |
| const _Tp*> | |
| [[nodiscard]] 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<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirect_unary_predicate<projected<_Iter, _Proj>> _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<input_range _Range, | |
| typename _Proj = identity, | |
| indirect_unary_predicate<projected<iterator_t<_Range>, _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 <bits/ranges_util.h>. | |
| struct __search_n_fn | |
| { | |
| template<forward_iterator _Iter, sentinel_for<_Iter> _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 = [&] <typename _Rp> (_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<forward_range _Range, | |
| typename _Pred = ranges::equal_to, typename _Proj = identity, | |
| typename _Tp | |
| _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)> | |
| requires indirectly_comparable<iterator_t<_Range>, 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<input_iterator _Iter1, sentinel_for<_Iter1> _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<input_range _Range1, input_range _Range2, | |
| typename _Pred = ranges::equal_to, | |
| typename _Proj1 = identity, typename _Proj2 = identity> | |
| requires indirectly_comparable<iterator_t<_Range1>, 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<typename _Iter1, typename _Sent1, typename _Iter2, typename _Sent2, | |
| typename _Pred, | |
| typename _Proj1, typename _Proj2> | |
| 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<input_iterator _Iter1, sentinel_for<_Iter1> _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<input_range _Range1, input_range _Range2, | |
| typename _Pred = ranges::equal_to, | |
| typename _Proj1 = identity, typename _Proj2 = identity> | |
| requires (forward_range<_Range1> || sized_range<_Range1>) | |
| && (forward_range<_Range2> || sized_range<_Range2>) | |
| && indirectly_comparable<iterator_t<_Range1>, 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<typename _Iter1, typename _Sent1, | |
| typename _Iter2, typename _Sent2, | |
| typename _Pred, | |
| typename _Proj1, typename _Proj2> | |
| 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<forward_iterator _Iter1, sentinel_for<_Iter1> _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> | |
| [[nodiscard]] 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<forward_range _Range1, forward_range _Range2, | |
| typename _Pred = ranges::equal_to, | |
| typename _Proj1 = identity, typename _Proj2 = identity> | |
| requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, | |
| _Pred, _Proj1, _Proj2> | |
| [[nodiscard]] 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 <bits/ranges_util.h>. | |
| struct __is_permutation_fn | |
| { | |
| template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
| forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
| typename _Proj1 = identity, typename _Proj2 = identity, | |
| indirect_equivalence_relation<projected<_Iter1, _Proj1>, | |
| projected<_Iter2, _Proj2>> _Pred | |
| = ranges::equal_to> | |
| [[nodiscard]] 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<decltype(__scan_deref)>(__scan_deref)); | |
| auto __comp_scan = [&] <typename _Tp> (_Tp&& __arg) -> bool { | |
| return std::__invoke(__pred, | |
| std::forward<decltype(__proj_scan)>(__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<forward_range _Range1, forward_range _Range2, | |
| typename _Proj1 = identity, typename _Proj2 = identity, | |
| indirect_equivalence_relation< | |
| projected<iterator_t<_Range1>, _Proj1>, | |
| projected<iterator_t<_Range2>, _Proj2>> _Pred = ranges::equal_to> | |
| [[nodiscard]] 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<typename _Iter, typename _Out> | |
| using copy_if_result = in_out_result<_Iter, _Out>; | |
| struct __copy_if_fn | |
| { | |
| template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| weakly_incrementable _Out, typename _Proj = identity, | |
| indirect_unary_predicate<projected<_Iter, _Proj>> _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<input_range _Range, weakly_incrementable _Out, | |
| typename _Proj = identity, | |
| indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
| _Pred> | |
| requires indirectly_copyable<iterator_t<_Range>, _Out> | |
| constexpr copy_if_result<borrowed_iterator_t<_Range>, _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<typename _Iter1, typename _Iter2> | |
| using swap_ranges_result = in_in_result<_Iter1, _Iter2>; | |
| struct __swap_ranges_fn | |
| { | |
| template<input_iterator _Iter1, sentinel_for<_Iter1> _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<input_range _Range1, input_range _Range2> | |
| requires indirectly_swappable<iterator_t<_Range1>, iterator_t<_Range2>> | |
| constexpr swap_ranges_result<borrowed_iterator_t<_Range1>, | |
| 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<typename _Iter, typename _Out> | |
| using unary_transform_result = in_out_result<_Iter, _Out>; | |
| template<typename _Iter1, typename _Iter2, typename _Out> | |
| struct in_in_out_result | |
| { | |
| [[no_unique_address]] _Iter1 in1; | |
| [[no_unique_address]] _Iter2 in2; | |
| [[no_unique_address]] _Out out; | |
| template<typename _IIter1, typename _IIter2, typename _OOut> | |
| requires convertible_to<const _Iter1&, _IIter1> | |
| && convertible_to<const _Iter2&, _IIter2> | |
| && convertible_to<const _Out&, _OOut> | |
| constexpr | |
| operator in_in_out_result<_IIter1, _IIter2, _OOut>() const & | |
| { return {in1, in2, out}; } | |
| template<typename _IIter1, typename _IIter2, typename _OOut> | |
| 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<typename _Iter1, typename _Iter2, typename _Out> | |
| using binary_transform_result = in_in_out_result<_Iter1, _Iter2, _Out>; | |
| struct __transform_fn | |
| { | |
| template<input_iterator _Iter, sentinel_for<_Iter> _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<input_range _Range, weakly_incrementable _Out, | |
| copy_constructible _Fp, typename _Proj = identity> | |
| requires indirectly_writable<_Out, | |
| indirect_result_t<_Fp&, | |
| projected<iterator_t<_Range>, _Proj>>> | |
| constexpr unary_transform_result<borrowed_iterator_t<_Range>, _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<input_iterator _Iter1, sentinel_for<_Iter1> _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<input_range _Range1, input_range _Range2, | |
| weakly_incrementable _Out, copy_constructible _Fp, | |
| typename _Proj1 = identity, typename _Proj2 = identity> | |
| requires indirectly_writable<_Out, | |
| indirect_result_t<_Fp&, | |
| projected<iterator_t<_Range1>, _Proj1>, | |
| projected<iterator_t<_Range2>, _Proj2>>> | |
| constexpr binary_transform_result<borrowed_iterator_t<_Range1>, | |
| 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<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| typename _Tp1 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj), | |
| typename _Tp2 _GLIBCXX26_DEF_VAL_T(iter_value_t<_Iter>)> | |
| requires indirectly_writable<_Iter, const _Tp2&> | |
| && indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, | |
| 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<input_range _Range, typename _Proj = identity, | |
| typename _Tp1 | |
| _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj), | |
| typename _Tp2 _GLIBCXX26_DEF_VAL_T(range_value_t<_Range>)> | |
| requires indirectly_writable<iterator_t<_Range>, const _Tp2&> | |
| && indirect_binary_predicate<ranges::equal_to, | |
| projected<iterator_t<_Range>, _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<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Iter>), | |
| indirect_unary_predicate<projected<_Iter, _Proj>> _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<input_range _Range, typename _Proj = identity, | |
| typename _Tp | |
| _GLIBCXX26_DEF_VAL_T(range_value_t<_Range>), | |
| indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
| _Pred> | |
| requires indirectly_writable<iterator_t<_Range>, 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<typename _Iter, typename _Out> | |
| using replace_copy_result = in_out_result<_Iter, _Out>; | |
| struct __replace_copy_fn | |
| { | |
| template<input_iterator _Iter, sentinel_for<_Iter> _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<ranges::equal_to, | |
| projected<_Iter, _Proj>, 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<input_range _Range, typename _Out, | |
| typename _Proj = identity, | |
| typename _Tp1 | |
| _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj), | |
| typename _Tp2 _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>)> | |
| requires indirectly_copyable<iterator_t<_Range>, _Out> | |
| && indirect_binary_predicate<ranges::equal_to, | |
| projected<iterator_t<_Range>, _Proj>, | |
| const _Tp1*> | |
| && output_iterator<_Out, const _Tp2&> | |
| constexpr replace_copy_result<borrowed_iterator_t<_Range>, _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<typename _Iter, typename _Out> | |
| using replace_copy_if_result = in_out_result<_Iter, _Out>; | |
| struct __replace_copy_if_fn | |
| { | |
| template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Out, | |
| typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>), | |
| typename _Proj = identity, | |
| indirect_unary_predicate<projected<_Iter, _Proj>> _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<input_range _Range, | |
| typename _Out, | |
| typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>), | |
| typename _Proj = identity, | |
| indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
| _Pred> | |
| requires indirectly_copyable<iterator_t<_Range>, _Out> | |
| && output_iterator<_Out, const _Tp&> | |
| constexpr replace_copy_if_result<borrowed_iterator_t<_Range>, _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<input_or_output_iterator _Out, copy_constructible _Fp> | |
| 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<input_or_output_iterator _Out, sentinel_for<_Out> _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<typename _Range, copy_constructible _Fp> | |
| 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<permutable _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
| [[nodiscard]] 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<forward_range _Range, typename _Proj = identity, | |
| indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
| _Pred> | |
| requires permutable<iterator_t<_Range>> | |
| [[nodiscard]] 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<permutable _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)> | |
| requires indirect_binary_predicate<ranges::equal_to, | |
| projected<_Iter, _Proj>, | |
| const _Tp*> | |
| [[nodiscard]] constexpr subrange<_Iter> | |
| operator()(_Iter __first, _Sent __last, | |
| const _Tp& __value, _Proj __proj = {}) const | |
| { | |
| auto __pred = [&] (auto&& __arg) -> bool { | |
| return std::forward<decltype(__arg)>(__arg) == __value; | |
| }; | |
| return ranges::remove_if(__first, __last, | |
| std::move(__pred), std::move(__proj)); | |
| } | |
| template<forward_range _Range, typename _Proj = identity, | |
| typename _Tp | |
| _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)> | |
| requires permutable<iterator_t<_Range>> | |
| && indirect_binary_predicate<ranges::equal_to, | |
| projected<iterator_t<_Range>, _Proj>, | |
| const _Tp*> | |
| [[nodiscard]] 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<typename _Iter, typename _Out> | |
| using remove_copy_if_result = in_out_result<_Iter, _Out>; | |
| struct __remove_copy_if_fn | |
| { | |
| template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| weakly_incrementable _Out, typename _Proj = identity, | |
| indirect_unary_predicate<projected<_Iter, _Proj>> _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<input_range _Range, weakly_incrementable _Out, | |
| typename _Proj = identity, | |
| indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
| _Pred> | |
| requires indirectly_copyable<iterator_t<_Range>, _Out> | |
| constexpr remove_copy_if_result<borrowed_iterator_t<_Range>, _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<typename _Iter, typename _Out> | |
| using remove_copy_result = in_out_result<_Iter, _Out>; | |
| struct __remove_copy_fn | |
| { | |
| template<input_iterator _Iter, sentinel_for<_Iter> _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<ranges::equal_to, | |
| projected<_Iter, _Proj>, | |
| 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<input_range _Range, weakly_incrementable _Out, | |
| typename _Proj = identity, | |
| typename _Tp | |
| _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)> | |
| requires indirectly_copyable<iterator_t<_Range>, _Out> | |
| && indirect_binary_predicate<ranges::equal_to, | |
| projected<iterator_t<_Range>, _Proj>, | |
| const _Tp*> | |
| constexpr remove_copy_result<borrowed_iterator_t<_Range>, _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<permutable _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirect_equivalence_relation< | |
| projected<_Iter, _Proj>> _Comp = ranges::equal_to> | |
| [[nodiscard]] 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<forward_range _Range, typename _Proj = identity, | |
| indirect_equivalence_relation< | |
| projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to> | |
| requires permutable<iterator_t<_Range>> | |
| [[nodiscard]] 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<typename _Out, typename _Tp> | |
| concept __can_reread_output = input_iterator<_Out> | |
| && same_as<_Tp, iter_value_t<_Out>>; | |
| } | |
| template<typename _Iter, typename _Out> | |
| using unique_copy_result = in_out_result<_Iter, _Out>; | |
| struct __unique_copy_fn | |
| { | |
| template<input_iterator _Iter, sentinel_for<_Iter> _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> | |
| { | |
| iter_value_t<_Iter> __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<input_range _Range, | |
| weakly_incrementable _Out, typename _Proj = identity, | |
| indirect_equivalence_relation< | |
| projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to> | |
| requires indirectly_copyable<iterator_t<_Range>, _Out> | |
| && (forward_iterator<iterator_t<_Range>> | |
| || __detail::__can_reread_output<_Out, range_value_t<_Range>> | |
| || indirectly_copyable_storable<iterator_t<_Range>, _Out>) | |
| constexpr unique_copy_result<borrowed_iterator_t<_Range>, _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<bidirectional_iterator _Iter, sentinel_for<_Iter> _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<bidirectional_range _Range> | |
| requires permutable<iterator_t<_Range>> | |
| constexpr borrowed_iterator_t<_Range> | |
| operator()(_Range&& __r) const | |
| { | |
| return (*this)(ranges::begin(__r), ranges::end(__r)); | |
| } | |
| }; | |
| inline constexpr __reverse_fn reverse{}; | |
| template<typename _Iter, typename _Out> | |
| using reverse_copy_result = in_out_result<_Iter, _Out>; | |
| struct __reverse_copy_fn | |
| { | |
| template<bidirectional_iterator _Iter, sentinel_for<_Iter> _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<bidirectional_range _Range, weakly_incrementable _Out> | |
| requires indirectly_copyable<iterator_t<_Range>, _Out> | |
| constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _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<permutable _Iter, sentinel_for<_Iter> _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 __mid = ranges::next(__p, __n - 1); | |
| auto __end = ranges::next(__mid); | |
| iter_value_t<_Iter> __t(ranges::iter_move(__p)); | |
| ranges::move(ranges::next(__p), __end, __p); | |
| *__mid = 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 __mid = ranges::next(__p, __n - 1); | |
| auto __end = ranges::next(__mid); | |
| iter_value_t<_Iter> __t(ranges::iter_move(__mid)); | |
| ranges::move_backward(__p, __mid, __end); | |
| *__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<forward_range _Range> | |
| requires permutable<iterator_t<_Range>> | |
| 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<typename _Iter, typename _Out> | |
| using rotate_copy_result = in_out_result<_Iter, _Out>; | |
| struct __rotate_copy_fn | |
| { | |
| template<forward_iterator _Iter, sentinel_for<_Iter> _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<forward_range _Range, weakly_incrementable _Out> | |
| requires indirectly_copyable<iterator_t<_Range>, _Out> | |
| constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _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<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| weakly_incrementable _Out, typename _Gen> | |
| requires (forward_iterator<_Iter> || random_access_iterator<_Out>) | |
| && indirectly_copyable<_Iter, _Out> | |
| && uniform_random_bit_generator<remove_reference_t<_Gen>> | |
| _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<decltype(__g()), _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<iter_difference_t<_Iter>>; | |
| 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<input_range _Range, weakly_incrementable _Out, typename _Gen> | |
| requires (forward_range<_Range> || random_access_iterator<_Out>) | |
| && indirectly_copyable<iterator_t<_Range>, _Out> | |
| && uniform_random_bit_generator<remove_reference_t<_Gen>> | |
| _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<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Gen> | |
| requires permutable<_Iter> | |
| && uniform_random_bit_generator<remove_reference_t<_Gen>> | |
| _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<decltype(__g()), __ud_type>; | |
| if constexpr (sized_sentinel_for<_Sent, _Iter>) | |
| { | |
| 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 = ranges::next(__first); | |
| // 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++, ranges::next(__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<_DistanceType, _DistanceType> __pospos = | |
| __gen_two_uniform_ints(__swap_range, __swap_range + 1, __g); | |
| ranges::iter_swap(__i++, ranges::next(__first, __pospos.first)); | |
| ranges::iter_swap(__i++, ranges::next(__first, __pospos.second)); | |
| } | |
| return __i; | |
| } | |
| } | |
| __distr_type __d; | |
| _Iter __i = ranges::next(__first); | |
| for (; __i != __last; ++__i) | |
| ranges::iter_swap(__i, | |
| ranges::next(__first, | |
| __d(__g, __p_type(0, __i - __first)))); | |
| return __i; | |
| } | |
| template<random_access_range _Range, typename _Gen> | |
| requires permutable<iterator_t<_Range>> | |
| && uniform_random_bit_generator<remove_reference_t<_Gen>> | |
| borrowed_iterator_t<_Range> | |
| operator()(_Range&& __r, _Gen&& __g) const | |
| { | |
| if constexpr (sized_range<_Range> | |
| && !sized_sentinel_for<sentinel_t<_Range>, | |
| iterator_t<_Range>>) | |
| return (*this)(ranges::begin(__r), | |
| ranges::begin(__r) + ranges::distance(__r), | |
| std::forward<_Gen>(__g)); | |
| else | |
| return (*this)(ranges::begin(__r), ranges::end(__r), | |
| std::forward<_Gen>(__g)); | |
| } | |
| }; | |
| inline constexpr __shuffle_fn shuffle{}; | |
| namespace __detail | |
| { | |
| template<typename _Iter, typename _Comp> | |
| 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<random_access_iterator _Iter, sentinel_for<_Iter> _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_value_t<_Iter> __value(ranges::iter_move(ranges::prev(__last))); | |
| __detail::__push_heap(__first, (__last - __first) - 1, | |
| 0, std::move(__value), __comp_proj); | |
| return __last; | |
| } | |
| } | |
| template<random_access_range _Range, | |
| typename _Comp = ranges::less, typename _Proj = identity> | |
| requires sortable<iterator_t<_Range>, _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<typename _Iter, typename _Comp> | |
| 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<typename _Iter, typename _Comp> | |
| 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<random_access_iterator _Iter, sentinel_for<_Iter> _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 __back = ranges::prev(__last); | |
| auto __comp_proj = __detail::__make_comp_proj(__comp, __proj); | |
| __detail::__pop_heap(__first, __back, __back, __comp_proj); | |
| } | |
| return __last; | |
| } | |
| } | |
| template<random_access_range _Range, | |
| typename _Comp = ranges::less, typename _Proj = identity> | |
| requires sortable<iterator_t<_Range>, _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<random_access_iterator _Iter, sentinel_for<_Iter> _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<random_access_range _Range, | |
| typename _Comp = ranges::less, typename _Proj = identity> | |
| requires sortable<iterator_t<_Range>, _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<random_access_iterator _Iter, sentinel_for<_Iter> _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<random_access_range _Range, | |
| typename _Comp = ranges::less, typename _Proj = identity> | |
| requires sortable<iterator_t<_Range>, _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<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirect_strict_weak_order<projected<_Iter, _Proj>> | |
| _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<random_access_range _Range, | |
| typename _Proj = identity, | |
| indirect_strict_weak_order<projected<iterator_t<_Range>, _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<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirect_strict_weak_order<projected<_Iter, _Proj>> | |
| _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<random_access_range _Range, | |
| typename _Proj = identity, | |
| indirect_strict_weak_order<projected<iterator_t<_Range>, _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<typename _Iter, typename _Comp> | |
| 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<typename _Iter, typename _Comp> | |
| 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<typename _Iter, typename _Comp> | |
| constexpr void | |
| __insertion_sort(_Iter __first, _Iter __last, _Comp __comp) | |
| { | |
| if (__first == __last) | |
| return; | |
| for (_Iter __i = ranges::next(__first); __i != __last; ++__i) | |
| { | |
| if (__comp(*__i, *__first)) | |
| { | |
| iter_value_t<_Iter> __val = ranges::iter_move(__i); | |
| ranges::move_backward(__first, __i, ranges::next(__i)); | |
| *__first = std::move(__val); | |
| } | |
| else | |
| __detail::__unguarded_linear_insert(__i, __comp); | |
| } | |
| } | |
| template<typename _Iter, typename _Comp> | |
| 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<typename _Iter, typename _Comp> | |
| constexpr void | |
| __final_insertion_sort(_Iter __first, _Iter __last, _Comp __comp) | |
| { | |
| constexpr iter_difference_t<_Iter> __threshold = __sort_threshold; | |
| if (__last - __first > __threshold) | |
| { | |
| __detail::__insertion_sort(__first, __first + __threshold, __comp); | |
| __detail::__unguarded_insertion_sort(__first + __threshold, __last, | |
| __comp); | |
| } | |
| else | |
| __detail::__insertion_sort(__first, __last, __comp); | |
| } | |
| template<typename _Iter, typename _Comp> | |
| 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<typename _Iter, typename _Comp> | |
| constexpr _Iter | |
| __unguarded_partition_pivot(_Iter __first, _Iter __last, _Comp __comp) | |
| { | |
| _Iter __mid = __first + (__last - __first) / 2; | |
| __detail::__move_median_to_first(__first, ranges::next(__first), __mid, | |
| ranges::prev(__last), __comp); | |
| return __detail::__unguarded_partition(ranges::next(__first), __last, | |
| __first, __comp); | |
| } | |
| template<typename _Iter, typename _Comp> | |
| 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<typename _Iter, typename _Comp> | |
| 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<typename _Iter, typename _Comp> | |
| 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<random_access_iterator _Iter, sentinel_for<_Iter> _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<random_access_range _Range, | |
| typename _Comp = ranges::less, typename _Proj = identity> | |
| requires sortable<iterator_t<_Range>, _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<typename _Iter, typename _Out, typename _Comp> | |
| _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<typename _Iter, typename _Out, typename _Distance, typename _Comp> | |
| 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<typename _Iter, typename _Distance, typename _Compare> | |
| 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<typename _Iter, typename _Pointer, typename _Comp> | |
| 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<typename _Iter, typename _Pointer, typename _Comp> | |
| 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<typename _Iter, typename _Distance, typename _Pointer, typename _Comp> | |
| 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<typename _Iter, typename _Distance, typename _Comp> | |
| constexpr void | |
| __merge_without_buffer(_Iter __first, _Iter __middle, _Iter __last, | |
| _Distance __len1, _Distance __len2, | |
| _Comp __comp); // defined near inplace_merge | |
| template<typename _Iter, typename _Pointer, typename _Comp> | |
| 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<typename _Iter, typename _Pointer, typename _Distance, typename _Comp> | |
| 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<typename _Iter, typename _Comp> | |
| 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<random_access_iterator _Iter, sentinel_for<_Iter> _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 | |
| using _TmpBuf = _Temporary_buffer<_Iter, iter_value_t<_Iter>>; | |
| // __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() == nullptr) [[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<random_access_range _Range, | |
| typename _Comp = ranges::less, typename _Proj = identity> | |
| requires sortable<iterator_t<_Range>, _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<random_access_iterator _Iter, sentinel_for<_Iter> _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(std::prev(__middle), __i); | |
| ranges::push_heap(__first, __middle, __comp, __proj); | |
| } | |
| ranges::sort_heap(__first, __middle, __comp, __proj); | |
| return __i; | |
| } | |
| template<random_access_range _Range, | |
| typename _Comp = ranges::less, typename _Proj = identity> | |
| requires sortable<iterator_t<_Range>, _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<typename _Iter, typename _Out> | |
| using partial_sort_copy_result = in_out_result<_Iter, _Out>; | |
| struct __partial_sort_copy_fn | |
| { | |
| template<input_iterator _Iter1, sentinel_for<_Iter1> _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); | |
| *ranges::prev(__result_real_last) = *__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<input_range _Range1, random_access_range _Range2, | |
| typename _Comp = ranges::less, | |
| typename _Proj1 = identity, typename _Proj2 = identity> | |
| requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>> | |
| && sortable<iterator_t<_Range2>, _Comp, _Proj2> | |
| && indirect_strict_weak_order<_Comp, | |
| projected<iterator_t<_Range1>, _Proj1>, | |
| projected<iterator_t<_Range2>, _Proj2>> | |
| constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>, | |
| 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<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirect_strict_weak_order<projected<_Iter, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] 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<forward_range _Range, typename _Proj = identity, | |
| indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] 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<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirect_strict_weak_order<projected<_Iter, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] 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<forward_range _Range, typename _Proj = identity, | |
| indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] 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<typename _Iter, typename _Comp> | |
| 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, ranges::next(__nth), __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<random_access_iterator _Iter, sentinel_for<_Iter> _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<random_access_range _Range, | |
| typename _Comp = ranges::less, typename _Proj = identity> | |
| requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
| constexpr borrowed_iterator_t<_Range> | |
| operator()(_Range&& __r, iterator_t<_Range> __nth, | |
| _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| return (*this)(ranges::begin(__r), std::move(__nth), | |
| ranges::end(__r), std::move(__comp), std::move(__proj)); | |
| } | |
| }; | |
| inline constexpr __nth_element_fn nth_element{}; | |
| struct __lower_bound_fn | |
| { | |
| template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj), | |
| indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr _Iter | |
| operator()(_Iter __first, _Sent __last, | |
| const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| auto __len = ranges::distance(__first, __last); | |
| while (__len > 0) | |
| { | |
| auto __half = __len / 2; | |
| auto __middle = __first; | |
| ranges::advance(__middle, __half); | |
| if (std::__invoke(__comp, std::__invoke(__proj, *__middle), __value)) | |
| { | |
| __first = __middle; | |
| ++__first; | |
| __len = __len - __half - 1; | |
| } | |
| else | |
| __len = __half; | |
| } | |
| return __first; | |
| } | |
| template<forward_range _Range, | |
| typename _Proj = identity, | |
| typename _Tp | |
| _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj), | |
| indirect_strict_weak_order<const _Tp*, | |
| projected<iterator_t<_Range>, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr borrowed_iterator_t<_Range> | |
| operator()(_Range&& __r, | |
| const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| return (*this)(ranges::begin(__r), ranges::end(__r), | |
| __value, std::move(__comp), std::move(__proj)); | |
| } | |
| }; | |
| inline constexpr __lower_bound_fn lower_bound{}; | |
| struct __upper_bound_fn | |
| { | |
| template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj), | |
| indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr _Iter | |
| operator()(_Iter __first, _Sent __last, | |
| const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| auto __len = ranges::distance(__first, __last); | |
| while (__len > 0) | |
| { | |
| auto __half = __len / 2; | |
| auto __middle = __first; | |
| ranges::advance(__middle, __half); | |
| if (std::__invoke(__comp, __value, std::__invoke(__proj, *__middle))) | |
| __len = __half; | |
| else | |
| { | |
| __first = __middle; | |
| ++__first; | |
| __len = __len - __half - 1; | |
| } | |
| } | |
| return __first; | |
| } | |
| template<forward_range _Range, | |
| typename _Proj = identity, | |
| typename _Tp | |
| _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj), | |
| indirect_strict_weak_order<const _Tp*, | |
| projected<iterator_t<_Range>, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr borrowed_iterator_t<_Range> | |
| operator()(_Range&& __r, | |
| const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| return (*this)(ranges::begin(__r), ranges::end(__r), | |
| __value, std::move(__comp), std::move(__proj)); | |
| } | |
| }; | |
| inline constexpr __upper_bound_fn upper_bound{}; | |
| struct __equal_range_fn | |
| { | |
| template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj), | |
| indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr subrange<_Iter> | |
| operator()(_Iter __first, _Sent __last, | |
| const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| auto __len = ranges::distance(__first, __last); | |
| while (__len > 0) | |
| { | |
| auto __half = __len / 2; | |
| auto __middle = __first; | |
| ranges::advance(__middle, __half); | |
| if (std::__invoke(__comp, | |
| std::__invoke(__proj, *__middle), | |
| __value)) | |
| { | |
| __first = __middle; | |
| ++__first; | |
| __len = __len - __half - 1; | |
| } | |
| else if (std::__invoke(__comp, | |
| __value, | |
| std::__invoke(__proj, *__middle))) | |
| __len = __half; | |
| else | |
| { | |
| auto __left | |
| = ranges::lower_bound(__first, __middle, | |
| __value, __comp, __proj); | |
| ranges::advance(__first, __len); | |
| auto __right | |
| = ranges::upper_bound(++__middle, __first, | |
| __value, __comp, __proj); | |
| return {__left, __right}; | |
| } | |
| } | |
| return {__first, __first}; | |
| } | |
| template<forward_range _Range, | |
| typename _Proj = identity, | |
| typename _Tp | |
| _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj), | |
| indirect_strict_weak_order<const _Tp*, | |
| projected<iterator_t<_Range>, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr borrowed_subrange_t<_Range> | |
| operator()(_Range&& __r, const _Tp& __value, | |
| _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| return (*this)(ranges::begin(__r), ranges::end(__r), | |
| __value, std::move(__comp), std::move(__proj)); | |
| } | |
| }; | |
| inline constexpr __equal_range_fn equal_range{}; | |
| struct __binary_search_fn | |
| { | |
| template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj), | |
| indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr bool | |
| operator()(_Iter __first, _Sent __last, | |
| const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj); | |
| if (__i == __last) | |
| return false; | |
| return !(bool)std::__invoke(__comp, __value, | |
| std::__invoke(__proj, *__i)); | |
| } | |
| template<forward_range _Range, | |
| typename _Proj = identity, | |
| typename _Tp | |
| _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj), | |
| indirect_strict_weak_order<const _Tp*, | |
| projected<iterator_t<_Range>, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr bool | |
| operator()(_Range&& __r, const _Tp& __value, _Comp __comp = {}, | |
| _Proj __proj = {}) const | |
| { | |
| return (*this)(ranges::begin(__r), ranges::end(__r), | |
| __value, std::move(__comp), std::move(__proj)); | |
| } | |
| }; | |
| inline constexpr __binary_search_fn binary_search{}; | |
| struct __is_partitioned_fn | |
| { | |
| template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
| [[nodiscard]] constexpr bool | |
| operator()(_Iter __first, _Sent __last, | |
| _Pred __pred, _Proj __proj = {}) const | |
| { | |
| __first = ranges::find_if_not(std::move(__first), __last, | |
| __pred, __proj); | |
| if (__first == __last) | |
| return true; | |
| ++__first; | |
| return ranges::none_of(std::move(__first), std::move(__last), | |
| std::move(__pred), std::move(__proj)); | |
| } | |
| template<input_range _Range, typename _Proj = identity, | |
| indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
| _Pred> | |
| [[nodiscard]] 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 __is_partitioned_fn is_partitioned{}; | |
| struct __partition_fn | |
| { | |
| template<permutable _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
| constexpr subrange<_Iter> | |
| operator()(_Iter __first, _Sent __last, | |
| _Pred __pred, _Proj __proj = {}) const | |
| { | |
| if constexpr (bidirectional_iterator<_Iter>) | |
| { | |
| auto __lasti = ranges::next(__first, __last); | |
| auto __tail = __lasti; | |
| for (;;) | |
| { | |
| for (;;) | |
| if (__first == __tail) | |
| return {std::move(__first), std::move(__lasti)}; | |
| else if (std::__invoke(__pred, | |
| std::__invoke(__proj, *__first))) | |
| ++__first; | |
| else | |
| break; | |
| --__tail; | |
| for (;;) | |
| if (__first == __tail) | |
| return {std::move(__first), std::move(__lasti)}; | |
| else if (!(bool)std::__invoke(__pred, | |
| std::__invoke(__proj, *__tail))) | |
| --__tail; | |
| else | |
| break; | |
| ranges::iter_swap(__first, __tail); | |
| ++__first; | |
| } | |
| } | |
| else | |
| { | |
| if (__first == __last) | |
| return {__first, __first}; | |
| while (std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
| if (++__first == __last) | |
| return {__first, __first}; | |
| auto __next = __first; | |
| while (++__next != __last) | |
| if (std::__invoke(__pred, std::__invoke(__proj, *__next))) | |
| { | |
| ranges::iter_swap(__first, __next); | |
| ++__first; | |
| } | |
| return {std::move(__first), std::move(__next)}; | |
| } | |
| } | |
| template<forward_range _Range, typename _Proj = identity, | |
| indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
| _Pred> | |
| requires permutable<iterator_t<_Range>> | |
| 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 __partition_fn partition{}; | |
| #if _GLIBCXX_HOSTED | |
| namespace __detail | |
| { | |
| // Like find_if_not(), but uses and updates a count of the | |
| // remaining range length instead of comparing against an end | |
| // iterator. | |
| template<typename _Iter, typename _Pred, typename _Distance> | |
| constexpr _Iter | |
| __find_if_not_n(_Iter __first, _Distance& __len, _Pred __pred) | |
| { | |
| for (; __len; --__len, (void) ++__first) | |
| if (!__pred(*__first)) | |
| break; | |
| return __first; | |
| } | |
| template<typename _Iter, typename _Sent, typename _Pointer, | |
| typename _Pred, typename _Distance> | |
| constexpr subrange<_Iter> | |
| __stable_partition_adaptive(_Iter __first, _Sent __last, | |
| _Pred __pred, _Distance __len, | |
| _Pointer __buffer, | |
| _Distance __buffer_size) | |
| { | |
| if (__len == 1) | |
| return {__first, ranges::next(__first, 1)}; | |
| if (__len <= __buffer_size) | |
| { | |
| _Iter __result1 = __first; | |
| _Pointer __result2 = __buffer; | |
| // The precondition guarantees that !__pred(__first), so | |
| // move that element to the buffer before starting the loop. | |
| // This ensures that we only call __pred once per element. | |
| *__result2 = ranges::iter_move(__first); | |
| ++__result2; | |
| ++__first; | |
| for (; __first != __last; ++__first) | |
| if (__pred(*__first)) | |
| { | |
| *__result1 = ranges::iter_move(__first); | |
| ++__result1; | |
| } | |
| else | |
| { | |
| *__result2 = ranges::iter_move(__first); | |
| ++__result2; | |
| } | |
| ranges::move(__buffer, __result2, __result1); | |
| return {__result1, __first}; | |
| } | |
| _Iter __middle = __first; | |
| ranges::advance(__middle, __len / 2); | |
| _Iter __left_split | |
| = __detail::__stable_partition_adaptive(__first, __middle, __pred, | |
| __len / 2, __buffer, | |
| __buffer_size).begin(); | |
| // Advance past true-predicate values to satisfy this | |
| // function's preconditions. | |
| _Distance __right_len = __len - __len / 2; | |
| _Iter __right_split = __detail::__find_if_not_n(__middle, __right_len, __pred); | |
| if (__right_len) | |
| __right_split | |
| = __detail::__stable_partition_adaptive(__right_split, __last, __pred, | |
| __right_len, __buffer, __buffer_size).begin(); | |
| return ranges::rotate(__left_split, __middle, __right_split); | |
| } | |
| } // namespace __detail | |
| struct __stable_partition_fn | |
| { | |
| template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
| requires permutable<_Iter> | |
| _GLIBCXX26_CONSTEXPR | |
| subrange<_Iter> | |
| operator()(_Iter __first, _Sent __last, | |
| _Pred __pred, _Proj __proj = {}) const | |
| { | |
| __first = ranges::find_if_not(__first, __last, __pred, __proj); | |
| if (__first == __last) | |
| return {__first, __first}; | |
| using _DistanceType = iter_difference_t<_Iter>; | |
| const _DistanceType __len = ranges::distance(__first, __last); | |
| auto __pred_proj = __detail::__make_pred_proj(__pred, __proj); | |
| #if __glibcxx_constexpr_algorithms >= 202306L // >= C++26 | |
| if consteval { | |
| // Simulate a _Temporary_buffer of length 1: | |
| iter_value_t<_Iter> __buf = ranges::iter_move(__first); | |
| *__first = std::move(__buf); | |
| return __detail::__stable_partition_adaptive(__first, __last, | |
| __pred_proj, | |
| __len, &__buf, | |
| _DistanceType(1)); | |
| } | |
| #endif | |
| _Temporary_buffer<_Iter, iter_value_t<_Iter>> __buf(__first, ptrdiff_t(__len)); | |
| return __detail::__stable_partition_adaptive(__first, __last, | |
| __pred_proj, | |
| __len, __buf.begin(), | |
| _DistanceType(__buf.size())); | |
| } | |
| template<bidirectional_range _Range, typename _Proj = identity, | |
| indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
| _Pred> | |
| requires permutable<iterator_t<_Range>> | |
| _GLIBCXX26_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 __stable_partition_fn stable_partition{}; | |
| #endif | |
| template<typename _Iter, typename _Out1, typename _Out2> | |
| struct in_out_out_result | |
| { | |
| [[no_unique_address]] _Iter in; | |
| [[no_unique_address]] _Out1 out1; | |
| [[no_unique_address]] _Out2 out2; | |
| template<typename _IIter, typename _OOut1, typename _OOut2> | |
| requires convertible_to<const _Iter&, _IIter> | |
| && convertible_to<const _Out1&, _OOut1> | |
| && convertible_to<const _Out2&, _OOut2> | |
| constexpr | |
| operator in_out_out_result<_IIter, _OOut1, _OOut2>() const & | |
| { return {in, out1, out2}; } | |
| template<typename _IIter, typename _OOut1, typename _OOut2> | |
| requires convertible_to<_Iter, _IIter> | |
| && convertible_to<_Out1, _OOut1> | |
| && convertible_to<_Out2, _OOut2> | |
| constexpr | |
| operator in_out_out_result<_IIter, _OOut1, _OOut2>() && | |
| { return {std::move(in), std::move(out1), std::move(out2)}; } | |
| }; | |
| template<typename _Iter, typename _Out1, typename _Out2> | |
| using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>; | |
| struct __partition_copy_fn | |
| { | |
| template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| weakly_incrementable _Out1, weakly_incrementable _Out2, | |
| typename _Proj = identity, | |
| indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
| requires indirectly_copyable<_Iter, _Out1> | |
| && indirectly_copyable<_Iter, _Out2> | |
| constexpr partition_copy_result<_Iter, _Out1, _Out2> | |
| operator()(_Iter __first, _Sent __last, | |
| _Out1 __out_true, _Out2 __out_false, | |
| _Pred __pred, _Proj __proj = {}) const | |
| { | |
| for (; __first != __last; ++__first) | |
| if (std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
| { | |
| *__out_true = *__first; | |
| ++__out_true; | |
| } | |
| else | |
| { | |
| *__out_false = *__first; | |
| ++__out_false; | |
| } | |
| return {std::move(__first), | |
| std::move(__out_true), std::move(__out_false)}; | |
| } | |
| template<input_range _Range, weakly_incrementable _Out1, | |
| weakly_incrementable _Out2, | |
| typename _Proj = identity, | |
| indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
| _Pred> | |
| requires indirectly_copyable<iterator_t<_Range>, _Out1> | |
| && indirectly_copyable<iterator_t<_Range>, _Out2> | |
| constexpr partition_copy_result<borrowed_iterator_t<_Range>, _Out1, _Out2> | |
| operator()(_Range&& __r, _Out1 __out_true, _Out2 __out_false, | |
| _Pred __pred, _Proj __proj = {}) const | |
| { | |
| return (*this)(ranges::begin(__r), ranges::end(__r), | |
| std::move(__out_true), std::move(__out_false), | |
| std::move(__pred), std::move(__proj)); | |
| } | |
| }; | |
| inline constexpr __partition_copy_fn partition_copy{}; | |
| struct __partition_point_fn | |
| { | |
| template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
| [[nodiscard]] constexpr _Iter | |
| operator()(_Iter __first, _Sent __last, | |
| _Pred __pred, _Proj __proj = {}) const | |
| { | |
| auto __len = ranges::distance(__first, __last); | |
| while (__len > 0) | |
| { | |
| auto __half = __len / 2; | |
| auto __middle = __first; | |
| ranges::advance(__middle, __half); | |
| if (std::__invoke(__pred, std::__invoke(__proj, *__middle))) | |
| { | |
| __first = __middle; | |
| ++__first; | |
| __len = __len - __half - 1; | |
| } | |
| else | |
| __len = __half; | |
| } | |
| return __first; | |
| } | |
| template<forward_range _Range, typename _Proj = identity, | |
| indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
| _Pred> | |
| [[nodiscard]] constexpr borrowed_iterator_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 __partition_point_fn partition_point{}; | |
| template<typename _Iter1, typename _Iter2, typename _Out> | |
| using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>; | |
| struct __merge_fn | |
| { | |
| template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
| input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
| weakly_incrementable _Out, typename _Comp = ranges::less, | |
| typename _Proj1 = identity, typename _Proj2 = identity> | |
| requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2> | |
| constexpr merge_result<_Iter1, _Iter2, _Out> | |
| operator()(_Iter1 __first1, _Sent1 __last1, | |
| _Iter2 __first2, _Sent2 __last2, _Out __result, | |
| _Comp __comp = {}, | |
| _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
| { | |
| while (__first1 != __last1 && __first2 != __last2) | |
| { | |
| if (std::__invoke(__comp, | |
| std::__invoke(__proj2, *__first2), | |
| std::__invoke(__proj1, *__first1))) | |
| { | |
| *__result = *__first2; | |
| ++__first2; | |
| } | |
| else | |
| { | |
| *__result = *__first1; | |
| ++__first1; | |
| } | |
| ++__result; | |
| } | |
| auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1), | |
| std::move(__result)); | |
| auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2), | |
| std::move(__copy1.out)); | |
| return { std::move(__copy1.in), std::move(__copy2.in), | |
| std::move(__copy2.out) }; | |
| } | |
| template<input_range _Range1, input_range _Range2, weakly_incrementable _Out, | |
| typename _Comp = ranges::less, | |
| typename _Proj1 = identity, typename _Proj2 = identity> | |
| requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out, | |
| _Comp, _Proj1, _Proj2> | |
| constexpr merge_result<borrowed_iterator_t<_Range1>, | |
| borrowed_iterator_t<_Range2>, | |
| _Out> | |
| operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, | |
| _Comp __comp = {}, | |
| _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
| { | |
| return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
| ranges::begin(__r2), ranges::end(__r2), | |
| std::move(__result), std::move(__comp), | |
| std::move(__proj1), std::move(__proj2)); | |
| } | |
| }; | |
| inline constexpr __merge_fn merge{}; | |
| namespace __detail | |
| { | |
| template<typename _Iter1, typename _Iter2, typename _Out, typename _Comp> | |
| void | |
| __move_merge_adaptive(_Iter1 __first1, _Iter1 __last1, | |
| _Iter2 __first2, _Iter2 __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; | |
| } | |
| if (__first1 != __last1) | |
| ranges::move(__first1, __last1, __result); | |
| } | |
| template<typename _Iter1, typename _Iter2, typename _Iter3, typename _Comp> | |
| void | |
| __move_merge_adaptive_backward(_Iter1 __first1, _Iter1 __last1, | |
| _Iter2 __first2, _Iter2 __last2, | |
| _Iter3 __result, _Comp __comp) | |
| { | |
| if (__first1 == __last1) | |
| { | |
| ranges::move_backward(__first2, __last2, __result); | |
| return; | |
| } | |
| else if (__first2 == __last2) | |
| return; | |
| --__last1; | |
| --__last2; | |
| while (true) | |
| { | |
| if (__comp(*__last2, *__last1)) | |
| { | |
| *--__result = ranges::iter_move(__last1); | |
| if (__first1 == __last1) | |
| { | |
| ranges::move_backward(__first2, ++__last2, __result); | |
| return; | |
| } | |
| --__last1; | |
| } | |
| else | |
| { | |
| *--__result = ranges::iter_move(__last2); | |
| if (__first2 == __last2) | |
| return; | |
| --__last2; | |
| } | |
| } | |
| } | |
| template<typename _Iter1, typename _Iter2> | |
| _Iter1 | |
| __rotate_adaptive(_Iter1 __first, _Iter1 __middle, _Iter1 __last, | |
| iter_difference_t<_Iter1> __len1, | |
| iter_difference_t<_Iter1> __len2, | |
| _Iter2 __buffer, | |
| iter_difference_t<_Iter1> __buffer_size) | |
| { | |
| _Iter2 __buffer_end; | |
| if (__len1 > __len2 && __len2 <= __buffer_size) | |
| { | |
| if (__len2) | |
| { | |
| __buffer_end = ranges::move(__middle, __last, __buffer).out; | |
| ranges::move_backward(__first, __middle, __last); | |
| return ranges::move(__buffer, __buffer_end, __first).out; | |
| } | |
| else | |
| return __first; | |
| } | |
| else if (__len1 <= __buffer_size) | |
| { | |
| if (__len1) | |
| { | |
| __buffer_end = ranges::move(__first, __middle, __buffer).out; | |
| ranges::move(__middle, __last, __first); | |
| return ranges::move_backward(__buffer, __buffer_end, __last).out; | |
| } | |
| else | |
| return __last; | |
| } | |
| else | |
| return ranges::rotate(__first, __middle, __last).begin(); | |
| } | |
| template<typename _Iter, typename _Pointer, typename _Comp> | |
| void | |
| __merge_adaptive(_Iter __first, _Iter __middle, _Iter __last, | |
| iter_difference_t<_Iter> __len1, | |
| iter_difference_t<_Iter> __len2, | |
| _Pointer __buffer, _Comp __comp) | |
| { | |
| if (__len1 <= __len2) | |
| { | |
| _Pointer __buffer_end = ranges::move(__first, __middle, __buffer).out; | |
| __detail::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last, | |
| __first, __comp); | |
| } | |
| else | |
| { | |
| _Pointer __buffer_end = ranges::move(__middle, __last, __buffer).out; | |
| __detail::__move_merge_adaptive_backward(__first, __middle, __buffer, | |
| __buffer_end, __last, __comp); | |
| } | |
| } | |
| template<typename _Iter, typename _Distance, typename _Pointer, typename _Comp> | |
| void | |
| __merge_adaptive_resize(_Iter __first, _Iter __middle, _Iter __last, | |
| _Distance __len1, _Distance __len2, | |
| _Pointer __buffer, _Distance __buffer_size, | |
| _Comp __comp) | |
| { | |
| if (__len1 <= __buffer_size || __len2 <= __buffer_size) | |
| __detail::__merge_adaptive(__first, __middle, __last, | |
| __len1, __len2, __buffer, __comp); | |
| else | |
| { | |
| _Iter __first_cut = __first; | |
| _Iter __second_cut = __middle; | |
| _Distance __len11 = 0; | |
| _Distance __len22 = 0; | |
| if (__len1 > __len2) | |
| { | |
| __len11 = __len1 / 2; | |
| ranges::advance(__first_cut, __len11); | |
| __second_cut = ranges::lower_bound(__middle, __last, *__first_cut, | |
| __comp); | |
| __len22 = ranges::distance(__middle, __second_cut); | |
| } | |
| else | |
| { | |
| __len22 = __len2 / 2; | |
| ranges::advance(__second_cut, __len22); | |
| __first_cut = ranges::upper_bound(__first, __middle, *__second_cut, | |
| __comp); | |
| __len11 = ranges::distance(__first, __first_cut); | |
| } | |
| _Iter __new_middle | |
| = __detail::__rotate_adaptive(__first_cut, __middle, __second_cut, | |
| _Distance(__len1 - __len11), __len22, | |
| __buffer, __buffer_size); | |
| __detail::__merge_adaptive_resize(__first, __first_cut, __new_middle, | |
| __len11, __len22, | |
| __buffer, __buffer_size, __comp); | |
| __detail::__merge_adaptive_resize(__new_middle, __second_cut, __last, | |
| _Distance(__len1 - __len11), | |
| _Distance(__len2 - __len22), | |
| __buffer, __buffer_size, __comp); | |
| } | |
| } | |
| template<typename _Iter, typename _Distance, typename _Comp> | |
| constexpr void | |
| __merge_without_buffer(_Iter __first, _Iter __middle, _Iter __last, | |
| _Distance __len1, _Distance __len2, _Comp __comp) | |
| { | |
| if (__len1 == 0 || __len2 == 0) | |
| return; | |
| if (__len1 + __len2 == 2) | |
| { | |
| if (__comp(*__middle, *__first)) | |
| ranges::iter_swap(__first, __middle); | |
| return; | |
| } | |
| _Iter __first_cut = __first; | |
| _Iter __second_cut = __middle; | |
| _Distance __len11 = 0; | |
| _Distance __len22 = 0; | |
| if (__len1 > __len2) | |
| { | |
| __len11 = __len1 / 2; | |
| ranges::advance(__first_cut, __len11); | |
| __second_cut = ranges::lower_bound(__middle, __last, *__first_cut, __comp); | |
| __len22 = ranges::distance(__middle, __second_cut); | |
| } | |
| else | |
| { | |
| __len22 = __len2 / 2; | |
| ranges::advance(__second_cut, __len22); | |
| __first_cut = ranges::upper_bound(__first, __middle, *__second_cut, __comp); | |
| __len11 = ranges::distance(__first, __first_cut); | |
| } | |
| _Iter __new_middle = ranges::rotate(__first_cut, __middle, __second_cut).begin(); | |
| __detail::__merge_without_buffer(__first, __first_cut, __new_middle, | |
| __len11, __len22, __comp); | |
| __detail::__merge_without_buffer(__new_middle, __second_cut, __last, | |
| __len1 - __len11, __len2 - __len22, __comp); | |
| } | |
| } // namespace __detail | |
| struct __inplace_merge_fn | |
| { | |
| template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Comp = ranges::less, | |
| typename _Proj = identity> | |
| requires sortable<_Iter, _Comp, _Proj> | |
| _GLIBCXX26_CONSTEXPR | |
| _Iter | |
| operator()(_Iter __first, _Iter __middle, _Sent __last, | |
| _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| if constexpr (!same_as<_Iter, _Sent>) | |
| return (*this)(__first, __middle, ranges::next(__middle, __last), | |
| std::move(__comp), std::move(__proj)); | |
| else | |
| { | |
| using _DistanceType = iter_difference_t<_Iter>; | |
| if (__first == __middle || __middle == __last) | |
| return __last; | |
| const _DistanceType __len1 = ranges::distance(__first, __middle); | |
| const _DistanceType __len2 = ranges::distance(__middle, __last); | |
| auto __comp_proj = __detail::__make_comp_proj(__comp, __proj); | |
| #if _GLIBCXX_HOSTED | |
| # if __glibcxx_constexpr_algorithms >= 202306L // >= C++26 | |
| if consteval { | |
| __detail::__merge_without_buffer(__first, __middle, __last, | |
| __len1, __len2, __comp_proj); | |
| return __last; | |
| } | |
| # endif | |
| using _TmpBuf = _Temporary_buffer<_Iter, iter_value_t<_Iter>>; | |
| // __merge_adaptive will use a buffer for the smaller of | |
| // [first,middle) and [middle,last). | |
| _TmpBuf __buf(__first, ptrdiff_t(ranges::min(__len1, __len2))); | |
| if (__buf.size() == __buf._M_requested_size()) [[likely]] | |
| __detail::__merge_adaptive | |
| (__first, __middle, __last, __len1, __len2, __buf.begin(), __comp_proj); | |
| else if (__buf.begin() == 0) [[unlikely]] | |
| __detail::__merge_without_buffer | |
| (__first, __middle, __last, __len1, __len2, __comp_proj); | |
| else | |
| __detail::__merge_adaptive_resize | |
| (__first, __middle, __last, __len1, __len2, __buf.begin(), | |
| _DistanceType(__buf.size()), __comp_proj); | |
| #else | |
| __detail::__merge_without_buffer | |
| (__first, __middle, __last, __len1, __len2, __comp_proj); | |
| #endif | |
| return __last; | |
| } | |
| } | |
| template<bidirectional_range _Range, | |
| typename _Comp = ranges::less, typename _Proj = identity> | |
| requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
| _GLIBCXX26_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 __inplace_merge_fn inplace_merge{}; | |
| struct __includes_fn | |
| { | |
| template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
| input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
| typename _Proj1 = identity, typename _Proj2 = identity, | |
| indirect_strict_weak_order<projected<_Iter1, _Proj1>, | |
| projected<_Iter2, _Proj2>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr bool | |
| operator()(_Iter1 __first1, _Sent1 __last1, | |
| _Iter2 __first2, _Sent2 __last2, | |
| _Comp __comp = {}, | |
| _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
| { | |
| while (__first1 != __last1 && __first2 != __last2) | |
| if (std::__invoke(__comp, | |
| std::__invoke(__proj2, *__first2), | |
| std::__invoke(__proj1, *__first1))) | |
| return false; | |
| else if (std::__invoke(__comp, | |
| std::__invoke(__proj1, *__first1), | |
| std::__invoke(__proj2, *__first2))) | |
| ++__first1; | |
| else | |
| { | |
| ++__first1; | |
| ++__first2; | |
| } | |
| return __first2 == __last2; | |
| } | |
| template<input_range _Range1, input_range _Range2, | |
| typename _Proj1 = identity, typename _Proj2 = identity, | |
| indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>, | |
| projected<iterator_t<_Range2>, _Proj2>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr bool | |
| operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {}, | |
| _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
| { | |
| return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
| ranges::begin(__r2), ranges::end(__r2), | |
| std::move(__comp), | |
| std::move(__proj1), std::move(__proj2)); | |
| } | |
| }; | |
| inline constexpr __includes_fn includes{}; | |
| template<typename _Iter1, typename _Iter2, typename _Out> | |
| using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>; | |
| struct __set_union_fn | |
| { | |
| template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
| input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
| weakly_incrementable _Out, typename _Comp = ranges::less, | |
| typename _Proj1 = identity, typename _Proj2 = identity> | |
| requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2> | |
| constexpr set_union_result<_Iter1, _Iter2, _Out> | |
| operator()(_Iter1 __first1, _Sent1 __last1, | |
| _Iter2 __first2, _Sent2 __last2, | |
| _Out __result, _Comp __comp = {}, | |
| _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
| { | |
| while (__first1 != __last1 && __first2 != __last2) | |
| { | |
| if (std::__invoke(__comp, | |
| std::__invoke(__proj1, *__first1), | |
| std::__invoke(__proj2, *__first2))) | |
| { | |
| *__result = *__first1; | |
| ++__first1; | |
| } | |
| else if (std::__invoke(__comp, | |
| std::__invoke(__proj2, *__first2), | |
| std::__invoke(__proj1, *__first1))) | |
| { | |
| *__result = *__first2; | |
| ++__first2; | |
| } | |
| else | |
| { | |
| *__result = *__first1; | |
| ++__first1; | |
| ++__first2; | |
| } | |
| ++__result; | |
| } | |
| auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1), | |
| std::move(__result)); | |
| auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2), | |
| std::move(__copy1.out)); | |
| return {std::move(__copy1.in), std::move(__copy2.in), | |
| std::move(__copy2.out)}; | |
| } | |
| template<input_range _Range1, input_range _Range2, weakly_incrementable _Out, | |
| typename _Comp = ranges::less, | |
| typename _Proj1 = identity, typename _Proj2 = identity> | |
| requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out, | |
| _Comp, _Proj1, _Proj2> | |
| constexpr set_union_result<borrowed_iterator_t<_Range1>, | |
| borrowed_iterator_t<_Range2>, _Out> | |
| operator()(_Range1&& __r1, _Range2&& __r2, | |
| _Out __result, _Comp __comp = {}, | |
| _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
| { | |
| return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
| ranges::begin(__r2), ranges::end(__r2), | |
| std::move(__result), std::move(__comp), | |
| std::move(__proj1), std::move(__proj2)); | |
| } | |
| }; | |
| inline constexpr __set_union_fn set_union{}; | |
| template<typename _Iter1, typename _Iter2, typename _Out> | |
| using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>; | |
| struct __set_intersection_fn | |
| { | |
| template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
| input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
| weakly_incrementable _Out, typename _Comp = ranges::less, | |
| typename _Proj1 = identity, typename _Proj2 = identity> | |
| requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2> | |
| constexpr set_intersection_result<_Iter1, _Iter2, _Out> | |
| operator()(_Iter1 __first1, _Sent1 __last1, | |
| _Iter2 __first2, _Sent2 __last2, _Out __result, | |
| _Comp __comp = {}, | |
| _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
| { | |
| while (__first1 != __last1 && __first2 != __last2) | |
| if (std::__invoke(__comp, | |
| std::__invoke(__proj1, *__first1), | |
| std::__invoke(__proj2, *__first2))) | |
| ++__first1; | |
| else if (std::__invoke(__comp, | |
| std::__invoke(__proj2, *__first2), | |
| std::__invoke(__proj1, *__first1))) | |
| ++__first2; | |
| else | |
| { | |
| *__result = *__first1; | |
| ++__first1; | |
| ++__first2; | |
| ++__result; | |
| } | |
| // TODO: Eliminating these variables triggers an ICE. | |
| auto __last1i = ranges::next(std::move(__first1), std::move(__last1)); | |
| auto __last2i = ranges::next(std::move(__first2), std::move(__last2)); | |
| return {std::move(__last1i), std::move(__last2i), std::move(__result)}; | |
| } | |
| template<input_range _Range1, input_range _Range2, weakly_incrementable _Out, | |
| typename _Comp = ranges::less, | |
| typename _Proj1 = identity, typename _Proj2 = identity> | |
| requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out, | |
| _Comp, _Proj1, _Proj2> | |
| constexpr set_intersection_result<borrowed_iterator_t<_Range1>, | |
| borrowed_iterator_t<_Range2>, _Out> | |
| operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, | |
| _Comp __comp = {}, | |
| _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
| { | |
| return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
| ranges::begin(__r2), ranges::end(__r2), | |
| std::move(__result), std::move(__comp), | |
| std::move(__proj1), std::move(__proj2)); | |
| } | |
| }; | |
| inline constexpr __set_intersection_fn set_intersection{}; | |
| template<typename _Iter, typename _Out> | |
| using set_difference_result = in_out_result<_Iter, _Out>; | |
| struct __set_difference_fn | |
| { | |
| template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
| input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
| weakly_incrementable _Out, typename _Comp = ranges::less, | |
| typename _Proj1 = identity, typename _Proj2 = identity> | |
| requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2> | |
| constexpr set_difference_result<_Iter1, _Out> | |
| operator()(_Iter1 __first1, _Sent1 __last1, | |
| _Iter2 __first2, _Sent2 __last2, _Out __result, | |
| _Comp __comp = {}, | |
| _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
| { | |
| while (__first1 != __last1 && __first2 != __last2) | |
| if (std::__invoke(__comp, | |
| std::__invoke(__proj1, *__first1), | |
| std::__invoke(__proj2, *__first2))) | |
| { | |
| *__result = *__first1; | |
| ++__first1; | |
| ++__result; | |
| } | |
| else if (std::__invoke(__comp, | |
| std::__invoke(__proj2, *__first2), | |
| std::__invoke(__proj1, *__first1))) | |
| ++__first2; | |
| else | |
| { | |
| ++__first1; | |
| ++__first2; | |
| } | |
| return ranges::copy(std::move(__first1), std::move(__last1), | |
| std::move(__result)); | |
| } | |
| template<input_range _Range1, input_range _Range2, weakly_incrementable _Out, | |
| typename _Comp = ranges::less, | |
| typename _Proj1 = identity, typename _Proj2 = identity> | |
| requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out, | |
| _Comp, _Proj1, _Proj2> | |
| constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out> | |
| operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, | |
| _Comp __comp = {}, | |
| _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
| { | |
| return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
| ranges::begin(__r2), ranges::end(__r2), | |
| std::move(__result), std::move(__comp), | |
| std::move(__proj1), std::move(__proj2)); | |
| } | |
| }; | |
| inline constexpr __set_difference_fn set_difference{}; | |
| template<typename _Iter1, typename _Iter2, typename _Out> | |
| using set_symmetric_difference_result | |
| = in_in_out_result<_Iter1, _Iter2, _Out>; | |
| struct __set_symmetric_difference_fn | |
| { | |
| template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
| input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
| weakly_incrementable _Out, typename _Comp = ranges::less, | |
| typename _Proj1 = identity, typename _Proj2 = identity> | |
| requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2> | |
| constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out> | |
| operator()(_Iter1 __first1, _Sent1 __last1, | |
| _Iter2 __first2, _Sent2 __last2, | |
| _Out __result, _Comp __comp = {}, | |
| _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
| { | |
| while (__first1 != __last1 && __first2 != __last2) | |
| if (std::__invoke(__comp, | |
| std::__invoke(__proj1, *__first1), | |
| std::__invoke(__proj2, *__first2))) | |
| { | |
| *__result = *__first1; | |
| ++__first1; | |
| ++__result; | |
| } | |
| else if (std::__invoke(__comp, | |
| std::__invoke(__proj2, *__first2), | |
| std::__invoke(__proj1, *__first1))) | |
| { | |
| *__result = *__first2; | |
| ++__first2; | |
| ++__result; | |
| } | |
| else | |
| { | |
| ++__first1; | |
| ++__first2; | |
| } | |
| auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1), | |
| std::move(__result)); | |
| auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2), | |
| std::move(__copy1.out)); | |
| return {std::move(__copy1.in), std::move(__copy2.in), | |
| std::move(__copy2.out)}; | |
| } | |
| template<input_range _Range1, input_range _Range2, weakly_incrementable _Out, | |
| typename _Comp = ranges::less, | |
| typename _Proj1 = identity, typename _Proj2 = identity> | |
| requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out, | |
| _Comp, _Proj1, _Proj2> | |
| constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>, | |
| borrowed_iterator_t<_Range2>, | |
| _Out> | |
| operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, | |
| _Comp __comp = {}, | |
| _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
| { | |
| return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
| ranges::begin(__r2), ranges::end(__r2), | |
| std::move(__result), std::move(__comp), | |
| std::move(__proj1), std::move(__proj2)); | |
| } | |
| }; | |
| inline constexpr __set_symmetric_difference_fn set_symmetric_difference{}; | |
| // min is defined in <bits/ranges_util.h>. | |
| struct __max_fn | |
| { | |
| template<typename _Tp, typename _Proj = identity, | |
| indirect_strict_weak_order<projected<const _Tp*, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr const _Tp& | |
| operator()(const _Tp& __a, const _Tp& __b, | |
| _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| if (std::__invoke(__comp, | |
| std::__invoke(__proj, __a), | |
| std::__invoke(__proj, __b))) | |
| return __b; | |
| else | |
| return __a; | |
| } | |
| template<input_range _Range, typename _Proj = identity, | |
| indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
| _Comp = ranges::less> | |
| requires indirectly_copyable_storable<iterator_t<_Range>, | |
| range_value_t<_Range>*> | |
| [[nodiscard]] constexpr range_value_t<_Range> | |
| operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| auto __first = ranges::begin(__r); | |
| auto __last = ranges::end(__r); | |
| __glibcxx_assert(__first != __last); | |
| range_value_t<_Range> __result(*__first); | |
| while (++__first != __last) | |
| { | |
| auto&& __tmp = *__first; | |
| if (std::__invoke(__comp, | |
| std::__invoke(__proj, __result), | |
| std::__invoke(__proj, __tmp))) | |
| __result = std::forward<decltype(__tmp)>(__tmp); | |
| } | |
| return __result; | |
| } | |
| template<copyable _Tp, typename _Proj = identity, | |
| indirect_strict_weak_order<projected<const _Tp*, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr _Tp | |
| operator()(initializer_list<_Tp> __r, | |
| _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| return (*this)(ranges::subrange(__r), | |
| std::move(__comp), std::move(__proj)); | |
| } | |
| }; | |
| inline constexpr __max_fn max{}; | |
| struct __clamp_fn | |
| { | |
| template<typename _Tp, typename _Proj = identity, | |
| indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp | |
| = ranges::less> | |
| [[nodiscard]] constexpr const _Tp& | |
| operator()(const _Tp& __val, const _Tp& __lo, const _Tp& __hi, | |
| _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| __glibcxx_assert(!(std::__invoke(__comp, | |
| std::__invoke(__proj, __hi), | |
| std::__invoke(__proj, __lo)))); | |
| auto&& __proj_val = std::__invoke(__proj, __val); | |
| if (std::__invoke(__comp, | |
| std::forward<decltype(__proj_val)>(__proj_val), | |
| std::__invoke(__proj, __lo))) | |
| return __lo; | |
| else if (std::__invoke(__comp, | |
| std::__invoke(__proj, __hi), | |
| std::forward<decltype(__proj_val)>(__proj_val))) | |
| return __hi; | |
| else | |
| return __val; | |
| } | |
| }; | |
| inline constexpr __clamp_fn clamp{}; | |
| template<typename _Tp> | |
| struct min_max_result | |
| { | |
| [[no_unique_address]] _Tp min; | |
| [[no_unique_address]] _Tp max; | |
| template<typename _Tp2> | |
| requires convertible_to<const _Tp&, _Tp2> | |
| constexpr | |
| operator min_max_result<_Tp2>() const & | |
| { return {min, max}; } | |
| template<typename _Tp2> | |
| requires convertible_to<_Tp, _Tp2> | |
| constexpr | |
| operator min_max_result<_Tp2>() && | |
| { return {std::move(min), std::move(max)}; } | |
| }; | |
| template<typename _Tp> | |
| using minmax_result = min_max_result<_Tp>; | |
| struct __minmax_fn | |
| { | |
| template<typename _Tp, typename _Proj = identity, | |
| indirect_strict_weak_order<projected<const _Tp*, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr minmax_result<const _Tp&> | |
| operator()(const _Tp& __a, const _Tp& __b, | |
| _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| if (std::__invoke(__comp, | |
| std::__invoke(__proj, __b), | |
| std::__invoke(__proj, __a))) | |
| return {__b, __a}; | |
| else | |
| return {__a, __b}; | |
| } | |
| template<input_range _Range, typename _Proj = identity, | |
| indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
| _Comp = ranges::less> | |
| requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*> | |
| [[nodiscard]] constexpr minmax_result<range_value_t<_Range>> | |
| operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| auto __first = ranges::begin(__r); | |
| auto __last = ranges::end(__r); | |
| __glibcxx_assert(__first != __last); | |
| auto __comp_proj = __detail::__make_comp_proj(__comp, __proj); | |
| minmax_result<range_value_t<_Range>> __result = {*__first, __result.min}; | |
| if (++__first == __last) | |
| return __result; | |
| else | |
| { | |
| // At this point __result.min == __result.max, so a single | |
| // comparison with the next element suffices. | |
| auto&& __val = *__first; | |
| if (__comp_proj(__val, __result.min)) | |
| __result.min = std::forward<decltype(__val)>(__val); | |
| else | |
| __result.max = std::forward<decltype(__val)>(__val); | |
| } | |
| while (++__first != __last) | |
| { | |
| // Now process two elements at a time so that we perform at most | |
| // 1 + 3*(N-2)/2 comparisons in total (each of the (N-2)/2 | |
| // iterations of this loop performs three comparisons). | |
| range_value_t<_Range> __val1 = *__first; | |
| if (++__first == __last) | |
| { | |
| // N is odd; in this final iteration, we perform at most two | |
| // comparisons, for a total of 1 + 3*(N-3)/2 + 2 comparisons, | |
| // which is not more than 3*N/2, as required. | |
| if (__comp_proj(__val1, __result.min)) | |
| __result.min = std::move(__val1); | |
| else if (!__comp_proj(__val1, __result.max)) | |
| __result.max = std::move(__val1); | |
| break; | |
| } | |
| auto&& __val2 = *__first; | |
| if (!__comp_proj(__val2, __val1)) | |
| { | |
| if (__comp_proj(__val1, __result.min)) | |
| __result.min = std::move(__val1); | |
| if (!__comp_proj(__val2, __result.max)) | |
| __result.max = std::forward<decltype(__val2)>(__val2); | |
| } | |
| else | |
| { | |
| if (__comp_proj(__val2, __result.min)) | |
| __result.min = std::forward<decltype(__val2)>(__val2); | |
| if (!__comp_proj(__val1, __result.max)) | |
| __result.max = std::move(__val1); | |
| } | |
| } | |
| return __result; | |
| } | |
| template<copyable _Tp, typename _Proj = identity, | |
| indirect_strict_weak_order<projected<const _Tp*, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr minmax_result<_Tp> | |
| operator()(initializer_list<_Tp> __r, | |
| _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| return (*this)(ranges::subrange(__r), | |
| std::move(__comp), std::move(__proj)); | |
| } | |
| }; | |
| inline constexpr __minmax_fn minmax{}; | |
| struct __min_element_fn | |
| { | |
| template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirect_strict_weak_order<projected<_Iter, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr _Iter | |
| operator()(_Iter __first, _Sent __last, | |
| _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| if (__first == __last) | |
| return __first; | |
| auto __i = __first; | |
| while (++__i != __last) | |
| { | |
| if (std::__invoke(__comp, | |
| std::__invoke(__proj, *__i), | |
| std::__invoke(__proj, *__first))) | |
| __first = __i; | |
| } | |
| return __first; | |
| } | |
| template<forward_range _Range, typename _Proj = identity, | |
| indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] 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 __min_element_fn min_element{}; | |
| struct __max_element_fn | |
| { | |
| template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirect_strict_weak_order<projected<_Iter, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr _Iter | |
| operator()(_Iter __first, _Sent __last, | |
| _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| if (__first == __last) | |
| return __first; | |
| auto __i = __first; | |
| while (++__i != __last) | |
| { | |
| if (std::__invoke(__comp, | |
| std::__invoke(__proj, *__first), | |
| std::__invoke(__proj, *__i))) | |
| __first = __i; | |
| } | |
| return __first; | |
| } | |
| template<forward_range _Range, typename _Proj = identity, | |
| indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] 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 __max_element_fn max_element{}; | |
| template<typename _Iter> | |
| using minmax_element_result = min_max_result<_Iter>; | |
| struct __minmax_element_fn | |
| { | |
| template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| indirect_strict_weak_order<projected<_Iter, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr minmax_element_result<_Iter> | |
| operator()(_Iter __first, _Sent __last, | |
| _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| auto __comp_proj = __detail::__make_comp_proj(__comp, __proj); | |
| minmax_element_result<_Iter> __result = {__first, __first}; | |
| if (__first == __last || ++__first == __last) | |
| return __result; | |
| else | |
| { | |
| // At this point __result.min == __result.max, so a single | |
| // comparison with the next element suffices. | |
| if (__comp_proj(*__first, *__result.min)) | |
| __result.min = __first; | |
| else | |
| __result.max = __first; | |
| } | |
| while (++__first != __last) | |
| { | |
| // Now process two elements at a time so that we perform at most | |
| // 1 + 3*(N-2)/2 comparisons in total (each of the (N-2)/2 | |
| // iterations of this loop performs three comparisons). | |
| auto __prev = __first; | |
| if (++__first == __last) | |
| { | |
| // N is odd; in this final iteration, we perform at most two | |
| // comparisons, for a total of 1 + 3*(N-3)/2 + 2 comparisons, | |
| // which is not more than 3*N/2, as required. | |
| if (__comp_proj(*__prev, *__result.min)) | |
| __result.min = __prev; | |
| else if (!__comp_proj(*__prev, *__result.max)) | |
| __result.max = __prev; | |
| break; | |
| } | |
| if (!__comp_proj(*__first, *__prev)) | |
| { | |
| if (__comp_proj(*__prev, *__result.min)) | |
| __result.min = __prev; | |
| if (!__comp_proj(*__first, *__result.max)) | |
| __result.max = __first; | |
| } | |
| else | |
| { | |
| if (__comp_proj(*__first, *__result.min)) | |
| __result.min = __first; | |
| if (!__comp_proj(*__prev, *__result.max)) | |
| __result.max = __prev; | |
| } | |
| } | |
| return __result; | |
| } | |
| template<forward_range _Range, typename _Proj = identity, | |
| indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr minmax_element_result<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 __minmax_element_fn minmax_element{}; | |
| struct __lexicographical_compare_fn | |
| { | |
| template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
| input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
| typename _Proj1 = identity, typename _Proj2 = identity, | |
| indirect_strict_weak_order<projected<_Iter1, _Proj1>, | |
| projected<_Iter2, _Proj2>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr bool | |
| operator()(_Iter1 __first1, _Sent1 __last1, | |
| _Iter2 __first2, _Sent2 __last2, | |
| _Comp __comp = {}, | |
| _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
| { | |
| if constexpr (__detail::__is_normal_iterator<_Iter1> | |
| && same_as<_Iter1, _Sent1>) | |
| return (*this)(__first1.base(), __last1.base(), | |
| std::move(__first2), std::move(__last2), | |
| std::move(__comp), | |
| std::move(__proj1), std::move(__proj2)); | |
| else if constexpr (__detail::__is_normal_iterator<_Iter2> | |
| && same_as<_Iter2, _Sent2>) | |
| return (*this)(std::move(__first1), std::move(__last1), | |
| __first2.base(), __last2.base(), | |
| std::move(__comp), | |
| std::move(__proj1), std::move(__proj2)); | |
| else | |
| { | |
| constexpr bool __sized_iters | |
| = (sized_sentinel_for<_Sent1, _Iter1> | |
| && sized_sentinel_for<_Sent2, _Iter2>); | |
| if constexpr (__sized_iters) | |
| { | |
| using _ValueType1 = iter_value_t<_Iter1>; | |
| using _ValueType2 = iter_value_t<_Iter2>; | |
| // This condition is consistent with the one in | |
| // __lexicographical_compare_aux in <bits/stl_algobase.h>. | |
| constexpr bool __use_memcmp | |
| = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value | |
| && __ptr_to_nonvolatile<_Iter1> | |
| && __ptr_to_nonvolatile<_Iter2> | |
| && (is_same_v<_Comp, ranges::less> | |
| || is_same_v<_Comp, ranges::greater>) | |
| && is_same_v<_Proj1, identity> | |
| && is_same_v<_Proj2, identity>); | |
| if constexpr (__use_memcmp) | |
| { | |
| const auto __d1 = __last1 - __first1; | |
| const auto __d2 = __last2 - __first2; | |
| if (const auto __len = std::min(__d1, __d2)) | |
| { | |
| const auto __c | |
| = std::__memcmp(__first1, __first2, __len); | |
| if constexpr (is_same_v<_Comp, ranges::less>) | |
| { | |
| if (__c < 0) | |
| return true; | |
| if (__c > 0) | |
| return false; | |
| } | |
| else if constexpr (is_same_v<_Comp, ranges::greater>) | |
| { | |
| if (__c > 0) | |
| return true; | |
| if (__c < 0) | |
| return false; | |
| } | |
| } | |
| return __d1 < __d2; | |
| } | |
| } | |
| for (; __first1 != __last1 && __first2 != __last2; | |
| ++__first1, (void) ++__first2) | |
| { | |
| if (std::__invoke(__comp, | |
| std::__invoke(__proj1, *__first1), | |
| std::__invoke(__proj2, *__first2))) | |
| return true; | |
| if (std::__invoke(__comp, | |
| std::__invoke(__proj2, *__first2), | |
| std::__invoke(__proj1, *__first1))) | |
| return false; | |
| } | |
| return __first1 == __last1 && __first2 != __last2; | |
| } | |
| } | |
| template<input_range _Range1, input_range _Range2, | |
| typename _Proj1 = identity, typename _Proj2 = identity, | |
| indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>, | |
| projected<iterator_t<_Range2>, _Proj2>> | |
| _Comp = ranges::less> | |
| [[nodiscard]] constexpr bool | |
| operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {}, | |
| _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
| { | |
| return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
| ranges::begin(__r2), ranges::end(__r2), | |
| std::move(__comp), | |
| std::move(__proj1), std::move(__proj2)); | |
| } | |
| private: | |
| template<typename _Iter, typename _Ref = iter_reference_t<_Iter>> | |
| static constexpr bool __ptr_to_nonvolatile | |
| = is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>; | |
| }; | |
| inline constexpr __lexicographical_compare_fn lexicographical_compare; | |
| template<typename _Iter> | |
| struct in_found_result | |
| { | |
| [[no_unique_address]] _Iter in; | |
| bool found; | |
| template<typename _Iter2> | |
| requires convertible_to<const _Iter&, _Iter2> | |
| constexpr | |
| operator in_found_result<_Iter2>() const & | |
| { return {in, found}; } | |
| template<typename _Iter2> | |
| requires convertible_to<_Iter, _Iter2> | |
| constexpr | |
| operator in_found_result<_Iter2>() && | |
| { return {std::move(in), found}; } | |
| }; | |
| template<typename _Iter> | |
| using next_permutation_result = in_found_result<_Iter>; | |
| struct __next_permutation_fn | |
| { | |
| template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Comp = ranges::less, typename _Proj = identity> | |
| requires sortable<_Iter, _Comp, _Proj> | |
| constexpr next_permutation_result<_Iter> | |
| operator()(_Iter __first, _Sent __last, | |
| _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| if (__first == __last) | |
| return {std::move(__first), false}; | |
| auto __i = __first; | |
| ++__i; | |
| if (__i == __last) | |
| return {std::move(__i), false}; | |
| auto __lasti = ranges::next(__first, __last); | |
| __i = __lasti; | |
| --__i; | |
| for (;;) | |
| { | |
| auto __ii = __i; | |
| --__i; | |
| if (std::__invoke(__comp, | |
| std::__invoke(__proj, *__i), | |
| std::__invoke(__proj, *__ii))) | |
| { | |
| auto __j = __lasti; | |
| while (!(bool)std::__invoke(__comp, | |
| std::__invoke(__proj, *__i), | |
| std::__invoke(__proj, *--__j))) | |
| ; | |
| ranges::iter_swap(__i, __j); | |
| ranges::reverse(__ii, __last); | |
| return {std::move(__lasti), true}; | |
| } | |
| if (__i == __first) | |
| { | |
| ranges::reverse(__first, __last); | |
| return {std::move(__lasti), false}; | |
| } | |
| } | |
| } | |
| template<bidirectional_range _Range, typename _Comp = ranges::less, | |
| typename _Proj = identity> | |
| requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
| constexpr next_permutation_result<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 __next_permutation_fn next_permutation{}; | |
| template<typename _Iter> | |
| using prev_permutation_result = in_found_result<_Iter>; | |
| struct __prev_permutation_fn | |
| { | |
| template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Comp = ranges::less, typename _Proj = identity> | |
| requires sortable<_Iter, _Comp, _Proj> | |
| constexpr prev_permutation_result<_Iter> | |
| operator()(_Iter __first, _Sent __last, | |
| _Comp __comp = {}, _Proj __proj = {}) const | |
| { | |
| if (__first == __last) | |
| return {std::move(__first), false}; | |
| auto __i = __first; | |
| ++__i; | |
| if (__i == __last) | |
| return {std::move(__i), false}; | |
| auto __lasti = ranges::next(__first, __last); | |
| __i = __lasti; | |
| --__i; | |
| for (;;) | |
| { | |
| auto __ii = __i; | |
| --__i; | |
| if (std::__invoke(__comp, | |
| std::__invoke(__proj, *__ii), | |
| std::__invoke(__proj, *__i))) | |
| { | |
| auto __j = __lasti; | |
| while (!(bool)std::__invoke(__comp, | |
| std::__invoke(__proj, *--__j), | |
| std::__invoke(__proj, *__i))) | |
| ; | |
| ranges::iter_swap(__i, __j); | |
| ranges::reverse(__ii, __last); | |
| return {std::move(__lasti), true}; | |
| } | |
| if (__i == __first) | |
| { | |
| ranges::reverse(__first, __last); | |
| return {std::move(__lasti), false}; | |
| } | |
| } | |
| } | |
| template<bidirectional_range _Range, typename _Comp = ranges::less, | |
| typename _Proj = identity> | |
| requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
| constexpr prev_permutation_result<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 __prev_permutation_fn prev_permutation{}; | |
| #if __glibcxx_ranges_contains >= 202207L // C++ >= 23 | |
| struct __contains_fn | |
| { | |
| template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)> | |
| requires indirect_binary_predicate<ranges::equal_to, | |
| projected<_Iter, _Proj>, const _Tp*> | |
| constexpr bool | |
| operator()(_Iter __first, _Sent __last, const _Tp& __value, _Proj __proj = {}) const | |
| { return ranges::find(std::move(__first), __last, __value, std::move(__proj)) != __last; } | |
| template<input_range _Range, | |
| typename _Proj = identity, | |
| typename _Tp | |
| _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)> | |
| requires indirect_binary_predicate<ranges::equal_to, | |
| projected<iterator_t<_Range>, _Proj>, const _Tp*> | |
| constexpr bool | |
| operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const | |
| { return (*this)(ranges::begin(__r), ranges::end(__r), __value, std::move(__proj)); } | |
| }; | |
| inline constexpr __contains_fn contains{}; | |
| struct __contains_subrange_fn | |
| { | |
| template<forward_iterator _Iter1, sentinel_for<_Iter1> _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 bool | |
| operator()(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, | |
| _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
| { | |
| return __first2 == __last2 | |
| || !ranges::search(__first1, __last1, __first2, __last2, | |
| std::move(__pred), std::move(__proj1), std::move(__proj2)).empty(); | |
| } | |
| template<forward_range _Range1, forward_range _Range2, | |
| typename _Pred = ranges::equal_to, | |
| typename _Proj1 = identity, typename _Proj2 = identity> | |
| requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, | |
| _Pred, _Proj1, _Proj2> | |
| constexpr bool | |
| 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 __contains_subrange_fn contains_subrange{}; | |
| #endif // __glibcxx_ranges_contains | |
| #if __glibcxx_ranges_find_last >= 202207L // C++ >= 23 | |
| struct __find_last_fn | |
| { | |
| template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Proj = identity, | |
| typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)> | |
| requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Tp*> | |
| [[nodiscard]] constexpr subrange<_Iter> | |
| operator()(_Iter __first, _Sent __last, const _Tp& __value, _Proj __proj = {}) const | |
| { | |
| if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>) | |
| { | |
| _Iter __found = ranges::find(reverse_iterator<_Iter>{__last}, | |
| reverse_iterator<_Iter>{__first}, | |
| __value, std::move(__proj)).base(); | |
| if (__found == __first) | |
| return {__last, __last}; | |
| else | |
| return {ranges::prev(__found), __last}; | |
| } | |
| else | |
| { | |
| _Iter __found = ranges::find(__first, __last, __value, __proj); | |
| if (__found == __last) | |
| return {__found, __found}; | |
| __first = __found; | |
| for (;;) | |
| { | |
| __first = ranges::find(ranges::next(__first), __last, __value, __proj); | |
| if (__first == __last) | |
| return {__found, __first}; | |
| __found = __first; | |
| } | |
| } | |
| } | |
| template<forward_range _Range, typename _Proj = identity, | |
| typename _Tp | |
| _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)> | |
| requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Tp*> | |
| [[nodiscard]] 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 __find_last_fn find_last{}; | |
| struct __find_last_if_fn | |
| { | |
| template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Proj = identity, | |
| indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
| [[nodiscard]] constexpr subrange<_Iter> | |
| operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const | |
| { | |
| if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>) | |
| { | |
| _Iter __found = ranges::find_if(reverse_iterator<_Iter>{__last}, | |
| reverse_iterator<_Iter>{__first}, | |
| std::move(__pred), std::move(__proj)).base(); | |
| if (__found == __first) | |
| return {__last, __last}; | |
| else | |
| return {ranges::prev(__found), __last}; | |
| } | |
| else | |
| { | |
| _Iter __found = ranges::find_if(__first, __last, __pred, __proj); | |
| if (__found == __last) | |
| return {__found, __found}; | |
| __first = __found; | |
| for (;;) | |
| { | |
| __first = ranges::find_if(ranges::next(__first), __last, __pred, __proj); | |
| if (__first == __last) | |
| return {__found, __first}; | |
| __found = __first; | |
| } | |
| } | |
| } | |
| template<forward_range _Range, typename _Proj = identity, | |
| indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> | |
| [[nodiscard]] 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 __find_last_if_fn find_last_if{}; | |
| struct __find_last_if_not_fn | |
| { | |
| template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Proj = identity, | |
| indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
| [[nodiscard]] constexpr subrange<_Iter> | |
| operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const | |
| { | |
| if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>) | |
| { | |
| _Iter __found = ranges::find_if_not(reverse_iterator<_Iter>{__last}, | |
| reverse_iterator<_Iter>{__first}, | |
| std::move(__pred), std::move(__proj)).base(); | |
| if (__found == __first) | |
| return {__last, __last}; | |
| else | |
| return {ranges::prev(__found), __last}; | |
| } | |
| else | |
| { | |
| _Iter __found = ranges::find_if_not(__first, __last, __pred, __proj); | |
| if (__found == __last) | |
| return {__found, __found}; | |
| __first = __found; | |
| for (;;) | |
| { | |
| __first = ranges::find_if_not(ranges::next(__first), __last, __pred, __proj); | |
| if (__first == __last) | |
| return {__found, __first}; | |
| __found = __first; | |
| } | |
| } | |
| } | |
| template<forward_range _Range, typename _Proj = identity, | |
| indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> | |
| [[nodiscard]] 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 __find_last_if_not_fn find_last_if_not{}; | |
| #endif // __glibcxx_ranges_find_last | |
| #if __glibcxx_ranges_fold >= 202207L // C++ >= 23 | |
| template<typename _Iter, typename _Tp> | |
| struct in_value_result | |
| { | |
| [[no_unique_address]] _Iter in; | |
| [[no_unique_address]] _Tp value; | |
| template<typename _Iter2, typename _Tp2> | |
| requires convertible_to<const _Iter&, _Iter2> | |
| && convertible_to<const _Tp&, _Tp2> | |
| constexpr | |
| operator in_value_result<_Iter2, _Tp2>() const & | |
| { return {in, value}; } | |
| template<typename _Iter2, typename _Tp2> | |
| requires convertible_to<_Iter, _Iter2> | |
| && convertible_to<_Tp, _Tp2> | |
| constexpr | |
| operator in_value_result<_Iter2, _Tp2>() && | |
| { return {std::move(in), std::move(value)}; } | |
| }; | |
| namespace __detail | |
| { | |
| template<typename _Fp> | |
| class __flipped | |
| { | |
| _Fp _M_f; | |
| public: | |
| template<typename _Tp, typename _Up> | |
| requires invocable<_Fp&, _Up, _Tp> | |
| invoke_result_t<_Fp&, _Up, _Tp> | |
| operator()(_Tp&&, _Up&&); // not defined | |
| }; | |
| template<typename _Fp, typename _Tp, typename _Iter, typename _Up> | |
| concept __indirectly_binary_left_foldable_impl = movable<_Tp> && movable<_Up> | |
| && convertible_to<_Tp, _Up> | |
| && invocable<_Fp&, _Up, iter_reference_t<_Iter>> | |
| && assignable_from<_Up&, invoke_result_t<_Fp&, _Up, iter_reference_t<_Iter>>>; | |
| template<typename _Fp, typename _Tp, typename _Iter> | |
| concept __indirectly_binary_left_foldable = copy_constructible<_Fp> | |
| && indirectly_readable<_Iter> | |
| && invocable<_Fp&, _Tp, iter_reference_t<_Iter>> | |
| && convertible_to<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>, | |
| decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>> | |
| && __indirectly_binary_left_foldable_impl | |
| <_Fp, _Tp, _Iter, decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>>; | |
| template <typename _Fp, typename _Tp, typename _Iter> | |
| concept __indirectly_binary_right_foldable | |
| = __indirectly_binary_left_foldable<__flipped<_Fp>, _Tp, _Iter>; | |
| } // namespace __detail | |
| template<typename _Iter, typename _Tp> | |
| using fold_left_with_iter_result = in_value_result<_Iter, _Tp>; | |
| struct __fold_left_with_iter_fn | |
| { | |
| template<typename _Ret_iter, | |
| typename _Iter, typename _Sent, typename _Tp, typename _Fp> | |
| static constexpr auto | |
| _S_impl(_Iter __first, _Sent __last, _Tp __init, _Fp __f) | |
| { | |
| using _Up = decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>; | |
| using _Ret = fold_left_with_iter_result<_Ret_iter, _Up>; | |
| if (__first == __last) | |
| return _Ret{std::move(__first), _Up(std::move(__init))}; | |
| _Up __accum = std::__invoke(__f, std::move(__init), *__first); | |
| for (++__first; __first != __last; ++__first) | |
| __accum = std::__invoke(__f, std::move(__accum), *__first); | |
| return _Ret{std::move(__first), std::move(__accum)}; | |
| } | |
| template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Iter>), | |
| __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp> | |
| constexpr auto | |
| operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const | |
| { | |
| using _Ret_iter = _Iter; | |
| return _S_impl<_Ret_iter>(std::move(__first), __last, | |
| std::move(__init), std::move(__f)); | |
| } | |
| template<input_range _Range, | |
| typename _Tp _GLIBCXX26_DEF_VAL_T(range_value_t<_Range>), | |
| __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp> | |
| constexpr auto | |
| operator()(_Range&& __r, _Tp __init, _Fp __f) const | |
| { | |
| using _Ret_iter = borrowed_iterator_t<_Range>; | |
| return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r), | |
| std::move(__init), std::move(__f)); | |
| } | |
| }; | |
| inline constexpr __fold_left_with_iter_fn fold_left_with_iter{}; | |
| struct __fold_left_fn | |
| { | |
| template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Iter>), | |
| __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp> | |
| constexpr auto | |
| operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const | |
| { | |
| return ranges::fold_left_with_iter(std::move(__first), __last, | |
| std::move(__init), std::move(__f)).value; | |
| } | |
| template<input_range _Range, | |
| typename _Tp _GLIBCXX26_DEF_VAL_T(range_value_t<_Range>), | |
| __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp> | |
| constexpr auto | |
| operator()(_Range&& __r, _Tp __init, _Fp __f) const | |
| { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__init), std::move(__f)); } | |
| }; | |
| inline constexpr __fold_left_fn fold_left{}; | |
| template<typename _Iter, typename _Tp> | |
| using fold_left_first_with_iter_result = in_value_result<_Iter, _Tp>; | |
| struct __fold_left_first_with_iter_fn | |
| { | |
| template<typename _Ret_iter, typename _Iter, typename _Sent, typename _Fp> | |
| static constexpr auto | |
| _S_impl(_Iter __first, _Sent __last, _Fp __f) | |
| { | |
| using _Up = decltype(ranges::fold_left(std::move(__first), __last, | |
| iter_value_t<_Iter>(*__first), __f)); | |
| using _Ret = fold_left_first_with_iter_result<_Ret_iter, optional<_Up>>; | |
| if (__first == __last) | |
| return _Ret{std::move(__first), optional<_Up>()}; | |
| optional<_Up> __init(in_place, *__first); | |
| for (++__first; __first != __last; ++__first) | |
| *__init = std::__invoke(__f, std::move(*__init), *__first); | |
| return _Ret{std::move(__first), std::move(__init)}; | |
| } | |
| template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp> | |
| requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>> | |
| constexpr auto | |
| operator()(_Iter __first, _Sent __last, _Fp __f) const | |
| { | |
| using _Ret_iter = _Iter; | |
| return _S_impl<_Ret_iter>(std::move(__first), __last, std::move(__f)); | |
| } | |
| template<input_range _Range, | |
| __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp> | |
| requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>> | |
| constexpr auto | |
| operator()(_Range&& __r, _Fp __f) const | |
| { | |
| using _Ret_iter = borrowed_iterator_t<_Range>; | |
| return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r), std::move(__f)); | |
| } | |
| }; | |
| inline constexpr __fold_left_first_with_iter_fn fold_left_first_with_iter{}; | |
| struct __fold_left_first_fn | |
| { | |
| template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp> | |
| requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>> | |
| constexpr auto | |
| operator()(_Iter __first, _Sent __last, _Fp __f) const | |
| { | |
| return ranges::fold_left_first_with_iter(std::move(__first), __last, | |
| std::move(__f)).value; | |
| } | |
| template<input_range _Range, | |
| __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp> | |
| requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>> | |
| constexpr auto | |
| operator()(_Range&& __r, _Fp __f) const | |
| { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__f)); } | |
| }; | |
| inline constexpr __fold_left_first_fn fold_left_first{}; | |
| struct __fold_right_fn | |
| { | |
| template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Iter>), | |
| __detail::__indirectly_binary_right_foldable<_Tp, _Iter> _Fp> | |
| constexpr auto | |
| operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const | |
| { | |
| using _Up = decay_t<invoke_result_t<_Fp&, iter_reference_t<_Iter>, _Tp>>; | |
| if (__first == __last) | |
| return _Up(std::move(__init)); | |
| _Iter __tail = ranges::next(__first, __last); | |
| _Up __accum = std::__invoke(__f, *--__tail, std::move(__init)); | |
| while (__first != __tail) | |
| __accum = std::__invoke(__f, *--__tail, std::move(__accum)); | |
| return __accum; | |
| } | |
| template<bidirectional_range _Range, | |
| typename _Tp _GLIBCXX26_DEF_VAL_T(range_value_t<_Range>), | |
| __detail::__indirectly_binary_right_foldable<_Tp, iterator_t<_Range>> _Fp> | |
| constexpr auto | |
| operator()(_Range&& __r, _Tp __init, _Fp __f) const | |
| { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__init), std::move(__f)); } | |
| }; | |
| inline constexpr __fold_right_fn fold_right{}; | |
| struct __fold_right_last_fn | |
| { | |
| template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, | |
| __detail::__indirectly_binary_right_foldable<iter_value_t<_Iter>, _Iter> _Fp> | |
| requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>> | |
| constexpr auto | |
| operator()(_Iter __first, _Sent __last, _Fp __f) const | |
| { | |
| using _Up = decltype(ranges::fold_right(__first, __last, | |
| iter_value_t<_Iter>(*__first), __f)); | |
| if (__first == __last) | |
| return optional<_Up>(); | |
| _Iter __tail = ranges::prev(ranges::next(__first, std::move(__last))); | |
| return optional<_Up>(in_place, | |
| ranges::fold_right(std::move(__first), __tail, | |
| iter_value_t<_Iter>(*__tail), | |
| std::move(__f))); | |
| } | |
| template<bidirectional_range _Range, | |
| __detail::__indirectly_binary_right_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp> | |
| requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>> | |
| constexpr auto | |
| operator()(_Range&& __r, _Fp __f) const | |
| { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__f)); } | |
| }; | |
| inline constexpr __fold_right_last_fn fold_right_last{}; | |
| #endif // __glibcxx_ranges_fold | |
| } // namespace ranges | |
| #if __glibcxx_shift >= 201806L // C++ >= 20 | |
| template<typename _ForwardIterator> | |
| constexpr _ForwardIterator | |
| shift_left(_ForwardIterator __first, _ForwardIterator __last, | |
| typename iterator_traits<_ForwardIterator>::difference_type __n) | |
| { | |
| __glibcxx_assert(__n >= 0); | |
| if (__n == 0) | |
| return __last; | |
| auto __mid = ranges::next(__first, __n, __last); | |
| if (__mid == __last) | |
| return __first; | |
| return std::move(std::move(__mid), std::move(__last), std::move(__first)); | |
| } | |
| template<typename _ForwardIterator> | |
| constexpr _ForwardIterator | |
| shift_right(_ForwardIterator __first, _ForwardIterator __last, | |
| typename iterator_traits<_ForwardIterator>::difference_type __n) | |
| { | |
| __glibcxx_assert(__n >= 0); | |
| if (__n == 0) | |
| return __first; | |
| using _Cat | |
| = typename iterator_traits<_ForwardIterator>::iterator_category; | |
| if constexpr (derived_from<_Cat, bidirectional_iterator_tag>) | |
| { | |
| auto __mid = ranges::next(__last, -__n, __first); | |
| if (__mid == __first) | |
| return __last; | |
| return std::move_backward(std::move(__first), std::move(__mid), | |
| std::move(__last)); | |
| } | |
| else | |
| { | |
| auto __result = ranges::next(__first, __n, __last); | |
| if (__result == __last) | |
| return __last; | |
| auto __dest_head = __first, __dest_tail = __result; | |
| while (__dest_head != __result) | |
| { | |
| if (__dest_tail == __last) | |
| { | |
| // If we get here, then we must have | |
| // 2*n >= distance(__first, __last) | |
| // i.e. we are shifting out at least half of the range. In | |
| // this case we can safely perform the shift with a single | |
| // move. | |
| std::move(std::move(__first), std::move(__dest_head), __result); | |
| return __result; | |
| } | |
| ++__dest_head; | |
| ++__dest_tail; | |
| } | |
| for (;;) | |
| { | |
| // At the start of each iteration of this outer loop, the range | |
| // [__first, __result) contains those elements that after shifting | |
| // the whole range right by __n, should end up in | |
| // [__dest_head, __dest_tail) in order. | |
| // The below inner loop swaps the elements of [__first, __result) | |
| // and [__dest_head, __dest_tail), while simultaneously shifting | |
| // the latter range by __n. | |
| auto __cursor = __first; | |
| while (__cursor != __result) | |
| { | |
| if (__dest_tail == __last) | |
| { | |
| // At this point the ranges [__first, result) and | |
| // [__dest_head, dest_tail) are disjoint, so we can safely | |
| // move the remaining elements. | |
| __dest_head = std::move(__cursor, __result, | |
| std::move(__dest_head)); | |
| std::move(std::move(__first), std::move(__cursor), | |
| std::move(__dest_head)); | |
| return __result; | |
| } | |
| std::iter_swap(__cursor, __dest_head); | |
| ++__dest_head; | |
| ++__dest_tail; | |
| ++__cursor; | |
| } | |
| } | |
| } | |
| } | |
| #endif | |
| namespace ranges | |
| { | |
| #if __glibcxx_shift >= 202202L // C++ >= 23 | |
| struct __shift_left_fn | |
| { | |
| template<permutable _Iter, sentinel_for<_Iter> _Sent> | |
| constexpr subrange<_Iter> | |
| operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __n) const | |
| { | |
| __glibcxx_assert(__n >= 0); | |
| if (__n == 0) | |
| return {__first, ranges::next(__first, __last)}; | |
| auto __mid = ranges::next(__first, __n, __last); | |
| if (__mid == __last) | |
| return {__first, __first}; | |
| return {__first, ranges::move(__mid, __last, __first).out}; | |
| } | |
| template<forward_range _Range> | |
| requires permutable<iterator_t<_Range>> | |
| constexpr borrowed_subrange_t<_Range> | |
| operator()(_Range&& __r, range_difference_t<_Range> __n) const | |
| { return (*this)(ranges::begin(__r), ranges::end(__r), __n); } | |
| }; | |
| inline constexpr __shift_left_fn shift_left{}; | |
| struct __shift_right_fn | |
| { | |
| template<permutable _Iter, sentinel_for<_Iter> _Sent> | |
| constexpr subrange<_Iter> | |
| operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __n) const | |
| { | |
| __glibcxx_assert(__n >= 0); | |
| if (__n == 0) | |
| return {__first, ranges::next(__first, __last)}; | |
| if constexpr (bidirectional_iterator<_Iter> && same_as<_Iter, _Sent>) | |
| { | |
| auto __mid = ranges::next(__last, -__n, __first); | |
| if (__mid == __first) | |
| return {__last, __last}; | |
| return {ranges::move_backward(__first, __mid, __last).out, __last}; | |
| } | |
| else | |
| { | |
| auto __result = ranges::next(__first, __n, __last); | |
| if (__result == __last) | |
| return {__result, __result}; | |
| auto __dest_head = __first, __dest_tail = __result; | |
| while (__dest_head != __result) | |
| { | |
| if (__dest_tail == __last) | |
| { | |
| // If we get here, then we must have | |
| // 2*n >= distance(__first, __last) | |
| // i.e. we are shifting out at least half of the range. In | |
| // this case we can safely perform the shift with a single | |
| // move. | |
| auto __lasti = ranges::move(__first, __dest_head, __result).out; | |
| // __glibcxx_assert(__lasti == __last); | |
| return {__result, __lasti}; | |
| } | |
| ++__dest_head; | |
| ++__dest_tail; | |
| } | |
| for (;;) | |
| { | |
| // At the start of each iteration of this outer loop, the range | |
| // [__first, __result) contains those elements that after shifting | |
| // the whole range right by __n, should end up in | |
| // [__dest_head, __dest_tail) in order. | |
| // The below inner loop swaps the elements of [__first, __result) | |
| // and [__dest_head, __dest_tail), while simultaneously shifting | |
| // the latter range by __n. | |
| auto __cursor = __first; | |
| while (__cursor != __result) | |
| { | |
| if (__dest_tail == __last) | |
| { | |
| // At this point the ranges [__first, result) and | |
| // [__dest_head, dest_tail) are disjoint, so we can safely | |
| // move the remaining elements. | |
| __dest_head = ranges::move(__cursor, __result, __dest_head).out; | |
| auto __lasti = ranges::move(__first, __cursor, __dest_head).out; | |
| // __glibcxx_assert(__lasti == __last); | |
| return {__result, __lasti}; | |
| } | |
| ranges::iter_swap(__cursor, __dest_head); | |
| ++__dest_head; | |
| ++__dest_tail; | |
| ++__cursor; | |
| } | |
| } | |
| } | |
| } | |
| template<forward_range _Range> | |
| requires permutable<iterator_t<_Range>> | |
| constexpr borrowed_subrange_t<_Range> | |
| operator()(_Range&& __r, range_difference_t<_Range> __n) const | |
| { return (*this)(ranges::begin(__r), ranges::end(__r), __n); } | |
| }; | |
| inline constexpr __shift_right_fn shift_right{}; | |
| #endif // C++23 | |
| } // namespace ranges | |
| _GLIBCXX_END_NAMESPACE_VERSION | |
| } // namespace std | |
| #endif // concepts | |
| #endif // C++20 | |
| #endif // _RANGES_ALGO_H |