Where Online Learning is simpler!

The C and C++ Include Header Files

/usr/include/c++/13/bits/ranges_algo.h


$ cat -n /usr/include/c++/13/bits/ranges_algo.h

     1	// Core algorithmic facilities -*- C++ -*-
     2	
     3	// Copyright (C) 2020-2023 Free Software Foundation, Inc.
     4	//
     5	// This file is part of the GNU ISO C++ Library.  This library is free
     6	// software; you can redistribute it and/or modify it under the
     7	// terms of the GNU General Public License as published by the
     8	// Free Software Foundation; either version 3, or (at your option)
     9	// any later version.
    10	
    11	// This library is distributed in the hope that it will be useful,
    12	// but WITHOUT ANY WARRANTY; without even the implied warranty of
    13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    14	// GNU General Public License for more details.
    15	
    16	// Under Section 7 of GPL version 3, you are granted additional
    17	// permissions described in the GCC Runtime Library Exception, version
    18	// 3.1, as published by the Free Software Foundation.
    19	
    20	// You should have received a copy of the GNU General Public License and
    21	// a copy of the GCC Runtime Library Exception along with this program;
    22	// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
    23	// <http://www.gnu.org/licenses/>.
    24	
    25	/** @file bits/ranges_algo.h
    26	 *  This is an internal header file, included by other library headers.
    27	 *  Do not attempt to use it directly. @headername{algorithm}
    28	 */
    29	
    30	#ifndef _RANGES_ALGO_H
    31	#define _RANGES_ALGO_H 1
    32	
    33	#if __cplusplus > 201703L
    34	
    35	#if __cplusplus > 202002L
    36	#include <optional>
    37	#endif
    38	#include <bits/ranges_algobase.h>
    39	#include <bits/ranges_util.h>
    40	#include <bits/uniform_int_dist.h> // concept uniform_random_bit_generator
    41	
    42	#if __cpp_lib_concepts
    43	namespace std _GLIBCXX_VISIBILITY(default)
    44	{
    45	_GLIBCXX_BEGIN_NAMESPACE_VERSION
    46	namespace ranges
    47	{
    48	  namespace __detail
    49	  {
    50	    template<typename _Comp, typename _Proj>
    51	      constexpr auto
    52	      __make_comp_proj(_Comp& __comp, _Proj& __proj)
    53	      {
    54		return [&] (auto&& __lhs, auto&& __rhs) -> bool {
    55		  using _TL = decltype(__lhs);
    56		  using _TR = decltype(__rhs);
    57		  return std::__invoke(__comp,
    58				       std::__invoke(__proj, std::forward<_TL>(__lhs)),
    59				       std::__invoke(__proj, std::forward<_TR>(__rhs)));
    60		};
    61	      }
    62	
    63	    template<typename _Pred, typename _Proj>
    64	      constexpr auto
    65	      __make_pred_proj(_Pred& __pred, _Proj& __proj)
    66	      {
    67		return [&] <typename _Tp> (_Tp&& __arg) -> bool {
    68		  return std::__invoke(__pred,
    69				       std::__invoke(__proj, std::forward<_Tp>(__arg)));
    70		};
    71	      }
    72	  } // namespace __detail
    73	
    74	  struct __all_of_fn
    75	  {
    76	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
    77		     typename _Proj = identity,
    78		     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
    79	      constexpr bool
    80	      operator()(_Iter __first, _Sent __last,
    81			 _Pred __pred, _Proj __proj = {}) const
    82	      {
    83		for (; __first != __last; ++__first)
    84		  if (!(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
    85		    return false;
    86		return true;
    87	      }
    88	
    89	    template<input_range _Range, typename _Proj = identity,
    90		     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
    91		       _Pred>
    92	      constexpr bool
    93	      operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
    94	      {
    95		return (*this)(ranges::begin(__r), ranges::end(__r),
    96			       std::move(__pred), std::move(__proj));
    97	      }
    98	  };
    99	
   100	  inline constexpr __all_of_fn all_of{};
   101	
   102	  struct __any_of_fn
   103	  {
   104	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
   105		     typename _Proj = identity,
   106		     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
   107	      constexpr bool
   108	      operator()(_Iter __first, _Sent __last,
   109			 _Pred __pred, _Proj __proj = {}) const
   110	      {
   111		for (; __first != __last; ++__first)
   112		  if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
   113		    return true;
   114		return false;
   115	      }
   116	
   117	    template<input_range _Range, typename _Proj = identity,
   118		     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
   119		       _Pred>
   120	      constexpr bool
   121	      operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
   122	      {
   123		return (*this)(ranges::begin(__r), ranges::end(__r),
   124			       std::move(__pred), std::move(__proj));
   125	      }
   126	  };
   127	
   128	  inline constexpr __any_of_fn any_of{};
   129	
   130	  struct __none_of_fn
   131	  {
   132	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
   133		     typename _Proj = identity,
   134		     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
   135	      constexpr bool
   136	      operator()(_Iter __first, _Sent __last,
   137			 _Pred __pred, _Proj __proj = {}) const
   138	      {
   139		for (; __first != __last; ++__first)
   140		  if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
   141		    return false;
   142		return true;
   143	      }
   144	
   145	    template<input_range _Range, typename _Proj = identity,
   146		     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
   147		       _Pred>
   148	      constexpr bool
   149	      operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
   150	      {
   151		return (*this)(ranges::begin(__r), ranges::end(__r),
   152			       std::move(__pred), std::move(__proj));
   153	      }
   154	  };
   155	
   156	  inline constexpr __none_of_fn none_of{};
   157	
   158	  template<typename _Iter, typename _Fp>
   159	    struct in_fun_result
   160	    {
   161	      [[no_unique_address]] _Iter in;
   162	      [[no_unique_address]] _Fp fun;
   163	
   164	      template<typename _Iter2, typename _F2p>
   165		requires convertible_to<const _Iter&, _Iter2>
   166		  && convertible_to<const _Fp&, _F2p>
   167		constexpr
   168		operator in_fun_result<_Iter2, _F2p>() const &
   169		{ return {in, fun}; }
   170	
   171	      template<typename _Iter2, typename _F2p>
   172		requires convertible_to<_Iter, _Iter2> && convertible_to<_Fp, _F2p>
   173		constexpr
   174		operator in_fun_result<_Iter2, _F2p>() &&
   175		{ return {std::move(in), std::move(fun)}; }
   176	    };
   177	
   178	  template<typename _Iter, typename _Fp>
   179	    using for_each_result = in_fun_result<_Iter, _Fp>;
   180	
   181	  struct __for_each_fn
   182	  {
   183	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
   184		     typename _Proj = identity,
   185		     indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
   186	      constexpr for_each_result<_Iter, _Fun>
   187	      operator()(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {}) const
   188	      {
   189		for (; __first != __last; ++__first)
   190		  std::__invoke(__f, std::__invoke(__proj, *__first));
   191		return { std::move(__first), std::move(__f) };
   192	      }
   193	
   194	    template<input_range _Range, typename _Proj = identity,
   195		     indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>>
   196		       _Fun>
   197	      constexpr for_each_result<borrowed_iterator_t<_Range>, _Fun>
   198	      operator()(_Range&& __r, _Fun __f, _Proj __proj = {}) const
   199	      {
   200		return (*this)(ranges::begin(__r), ranges::end(__r),
   201			       std::move(__f), std::move(__proj));
   202	      }
   203	  };
   204	
   205	  inline constexpr __for_each_fn for_each{};
   206	
   207	  template<typename _Iter, typename _Fp>
   208	    using for_each_n_result = in_fun_result<_Iter, _Fp>;
   209	
   210	  struct __for_each_n_fn
   211	  {
   212	    template<input_iterator _Iter, typename _Proj = identity,
   213		     indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
   214	      constexpr for_each_n_result<_Iter, _Fun>
   215	      operator()(_Iter __first, iter_difference_t<_Iter> __n,
   216			 _Fun __f, _Proj __proj = {}) const
   217	      {
   218		if constexpr (random_access_iterator<_Iter>)
   219		  {
   220		    if (__n <= 0)
   221		      return {std::move(__first), std::move(__f)};
   222		    auto __last = __first + __n;
   223		    return ranges::for_each(std::move(__first), std::move(__last),
   224					    std::move(__f), std::move(__proj));
   225		  }
   226		else
   227		  {
   228		    while (__n-- > 0)
   229		      {
   230			std::__invoke(__f, std::__invoke(__proj, *__first));
   231			++__first;
   232		      }
   233		    return {std::move(__first), std::move(__f)};
   234		  }
   235	      }
   236	  };
   237	
   238	  inline constexpr __for_each_n_fn for_each_n{};
   239	
   240	  // find, find_if and find_if_not are defined in <bits/ranges_util.h>.
   241	
   242	  struct __find_first_of_fn
   243	  {
   244	    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
   245		     forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
   246		     typename _Pred = ranges::equal_to,
   247		     typename _Proj1 = identity, typename _Proj2 = identity>
   248	      requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
   249	      constexpr _Iter1
   250	      operator()(_Iter1 __first1, _Sent1 __last1,
   251			 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
   252			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
   253	      {
   254		for (; __first1 != __last1; ++__first1)
   255		  for (auto __iter = __first2; __iter != __last2; ++__iter)
   256		    if (std::__invoke(__pred,
   257				      std::__invoke(__proj1, *__first1),
   258				      std::__invoke(__proj2, *__iter)))
   259		      return __first1;
   260		return __first1;
   261	      }
   262	
   263	    template<input_range _Range1, forward_range _Range2,
   264		     typename _Pred = ranges::equal_to,
   265		     typename _Proj1 = identity, typename _Proj2 = identity>
   266	      requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
   267					     _Pred, _Proj1, _Proj2>
   268	      constexpr borrowed_iterator_t<_Range1>
   269	      operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
   270			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
   271	      {
   272		return (*this)(ranges::begin(__r1), ranges::end(__r1),
   273			       ranges::begin(__r2), ranges::end(__r2),
   274			       std::move(__pred),
   275			       std::move(__proj1), std::move(__proj2));
   276	      }
   277	  };
   278	
   279	  inline constexpr __find_first_of_fn find_first_of{};
   280	
   281	  struct __count_fn
   282	  {
   283	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
   284		     typename _Tp, typename _Proj = identity>
   285	      requires indirect_binary_predicate<ranges::equal_to,
   286						 projected<_Iter, _Proj>,
   287						 const _Tp*>
   288	      constexpr iter_difference_t<_Iter>
   289	      operator()(_Iter __first, _Sent __last,
   290			 const _Tp& __value, _Proj __proj = {}) const
   291	      {
   292		iter_difference_t<_Iter> __n = 0;
   293		for (; __first != __last; ++__first)
   294		  if (std::__invoke(__proj, *__first) == __value)
   295		    ++__n;
   296		return __n;
   297	      }
   298	
   299	    template<input_range _Range, typename _Tp, typename _Proj = identity>
   300	      requires indirect_binary_predicate<ranges::equal_to,
   301						 projected<iterator_t<_Range>, _Proj>,
   302						 const _Tp*>
   303	      constexpr range_difference_t<_Range>
   304	      operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
   305	      {
   306		return (*this)(ranges::begin(__r), ranges::end(__r),
   307			       __value, std::move(__proj));
   308	      }
   309	  };
   310	
   311	  inline constexpr __count_fn count{};
   312	
   313	  struct __count_if_fn
   314	  {
   315	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
   316		     typename _Proj = identity,
   317		     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
   318	      constexpr iter_difference_t<_Iter>
   319	      operator()(_Iter __first, _Sent __last,
   320			 _Pred __pred, _Proj __proj = {}) const
   321	      {
   322		iter_difference_t<_Iter> __n = 0;
   323		for (; __first != __last; ++__first)
   324		  if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
   325		    ++__n;
   326		return __n;
   327	      }
   328	
   329	    template<input_range _Range,
   330		     typename _Proj = identity,
   331		     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
   332		       _Pred>
   333	      constexpr range_difference_t<_Range>
   334	      operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
   335	      {
   336		return (*this)(ranges::begin(__r), ranges::end(__r),
   337			       std::move(__pred), std::move(__proj));
   338	      }
   339	  };
   340	
   341	  inline constexpr __count_if_fn count_if{};
   342	
   343	  // in_in_result, mismatch and search are defined in <bits/ranges_util.h>.
   344	
   345	  struct __search_n_fn
   346	  {
   347	    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
   348		     typename _Pred = ranges::equal_to, typename _Proj = identity>
   349	      requires indirectly_comparable<_Iter, const _Tp*, _Pred, _Proj>
   350	      constexpr subrange<_Iter>
   351	      operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __count,
   352			 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {}) const
   353	      {
   354		if (__count <= 0)
   355		  return {__first, __first};
   356	
   357		auto __value_comp = [&] <typename _Rp> (_Rp&& __arg) -> bool {
   358		    return std::__invoke(__pred, std::forward<_Rp>(__arg), __value);
   359		};
   360		if (__count == 1)
   361		  {
   362		    __first = ranges::find_if(std::move(__first), __last,
   363					      std::move(__value_comp),
   364					      std::move(__proj));
   365		    if (__first == __last)
   366		      return {__first, __first};
   367		    else
   368		      {
   369			auto __end = __first;
   370			return {__first, ++__end};
   371		      }
   372		  }
   373	
   374		if constexpr (sized_sentinel_for<_Sent, _Iter>
   375			      && random_access_iterator<_Iter>)
   376		  {
   377		    auto __tail_size = __last - __first;
   378		    auto __remainder = __count;
   379	
   380		    while (__remainder <= __tail_size)
   381		      {
   382			__first += __remainder;
   383			__tail_size -= __remainder;
   384			auto __backtrack = __first;
   385			while (__value_comp(std::__invoke(__proj, *--__backtrack)))
   386			  {
   387			    if (--__remainder == 0)
   388			      return {__first - __count, __first};
   389			  }
   390			__remainder = __count + 1 - (__first - __backtrack);
   391		      }
   392		    auto __i = __first + __tail_size;
   393		    return {__i, __i};
   394		  }
   395		else
   396		  {
   397		    __first = ranges::find_if(__first, __last, __value_comp, __proj);
   398		    while (__first != __last)
   399		      {
   400			auto __n = __count;
   401			auto __i = __first;
   402			++__i;
   403			while (__i != __last && __n != 1
   404			       && __value_comp(std::__invoke(__proj, *__i)))
   405			  {
   406			    ++__i;
   407			    --__n;
   408			  }
   409			if (__n == 1)
   410			  return {__first, __i};
   411			if (__i == __last)
   412			  return {__i, __i};
   413			__first = ranges::find_if(++__i, __last, __value_comp, __proj);
   414		      }
   415		    return {__first, __first};
   416		  }
   417	      }
   418	
   419	    template<forward_range _Range, typename _Tp,
   420		     typename _Pred = ranges::equal_to, typename _Proj = identity>
   421	      requires indirectly_comparable<iterator_t<_Range>, const _Tp*,
   422					     _Pred, _Proj>
   423	      constexpr borrowed_subrange_t<_Range>
   424	      operator()(_Range&& __r, range_difference_t<_Range> __count,
   425		       const _Tp& __value, _Pred __pred = {}, _Proj __proj = {}) const
   426	      {
   427		return (*this)(ranges::begin(__r), ranges::end(__r),
   428			       std::move(__count), __value,
   429			       std::move(__pred), std::move(__proj));
   430	      }
   431	  };
   432	
   433	  inline constexpr __search_n_fn search_n{};
   434	
   435	  struct __find_end_fn
   436	  {
   437	    template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
   438		     forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
   439		     typename _Pred = ranges::equal_to,
   440		     typename _Proj1 = identity, typename _Proj2 = identity>
   441	      requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
   442	      constexpr subrange<_Iter1>
   443	      operator()(_Iter1 __first1, _Sent1 __last1,
   444			 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
   445			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
   446	      {
   447		if constexpr (bidirectional_iterator<_Iter1>
   448			      && bidirectional_iterator<_Iter2>)
   449		  {
   450		    auto __i1 = ranges::next(__first1, __last1);
   451		    auto __i2 = ranges::next(__first2, __last2);
   452		    auto __rresult
   453		      = ranges::search(reverse_iterator<_Iter1>{__i1},
   454				       reverse_iterator<_Iter1>{__first1},
   455				       reverse_iterator<_Iter2>{__i2},
   456				       reverse_iterator<_Iter2>{__first2},
   457				       std::move(__pred),
   458				       std::move(__proj1), std::move(__proj2));
   459		    auto __result_first = ranges::end(__rresult).base();
   460		    auto __result_last = ranges::begin(__rresult).base();
   461		    if (__result_last == __first1)
   462		      return {__i1, __i1};
   463		    else
   464		      return {__result_first, __result_last};
   465		  }
   466		else
   467		  {
   468		    auto __i = ranges::next(__first1, __last1);
   469		    if (__first2 == __last2)
   470		      return {__i, __i};
   471	
   472		    auto __result_begin = __i;
   473		    auto __result_end = __i;
   474		    for (;;)
   475		      {
   476			auto __new_range = ranges::search(__first1, __last1,
   477							  __first2, __last2,
   478							  __pred, __proj1, __proj2);
   479			auto __new_result_begin = ranges::begin(__new_range);
   480			auto __new_result_end = ranges::end(__new_range);
   481			if (__new_result_begin == __last1)
   482			  return {__result_begin, __result_end};
   483			else
   484			  {
   485			    __result_begin = __new_result_begin;
   486			    __result_end = __new_result_end;
   487			    __first1 = __result_begin;
   488			    ++__first1;
   489			  }
   490		      }
   491		  }
   492	      }
   493	
   494	    template<forward_range _Range1, forward_range _Range2,
   495		     typename _Pred = ranges::equal_to,
   496		     typename _Proj1 = identity, typename _Proj2 = identity>
   497	      requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
   498					     _Pred, _Proj1, _Proj2>
   499	      constexpr borrowed_subrange_t<_Range1>
   500	      operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
   501			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
   502	      {
   503		return (*this)(ranges::begin(__r1), ranges::end(__r1),
   504			       ranges::begin(__r2), ranges::end(__r2),
   505			       std::move(__pred),
   506			       std::move(__proj1), std::move(__proj2));
   507	      }
   508	  };
   509	
   510	  inline constexpr __find_end_fn find_end{};
   511	
   512	  // adjacent_find is defined in <bits/ranges_util.h>.
   513	
   514	  struct __is_permutation_fn
   515	  {
   516	    template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
   517		     forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
   518		     typename _Proj1 = identity, typename _Proj2 = identity,
   519		     indirect_equivalence_relation<projected<_Iter1, _Proj1>,
   520						   projected<_Iter2, _Proj2>> _Pred
   521		       = ranges::equal_to>
   522	      constexpr bool
   523	      operator()(_Iter1 __first1, _Sent1 __last1,
   524			 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
   525			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
   526	      {
   527		constexpr bool __sized_iters
   528		  = (sized_sentinel_for<_Sent1, _Iter1>
   529		     && sized_sentinel_for<_Sent2, _Iter2>);
   530		if constexpr (__sized_iters)
   531		  {
   532		    auto __d1 = ranges::distance(__first1, __last1);
   533		    auto __d2 = ranges::distance(__first2, __last2);
   534		    if (__d1 != __d2)
   535		      return false;
   536		  }
   537	
   538		// Efficiently compare identical prefixes:  O(N) if sequences
   539		// have the same elements in the same order.
   540		for (; __first1 != __last1 && __first2 != __last2;
   541		     ++__first1, (void)++__first2)
   542		  if (!(bool)std::__invoke(__pred,
   543					   std::__invoke(__proj1, *__first1),
   544					   std::__invoke(__proj2, *__first2)))
   545		      break;
   546	
   547		if constexpr (__sized_iters)
   548		  {
   549		    if (__first1 == __last1)
   550		      return true;
   551		  }
   552		else
   553		  {
   554		    auto __d1 = ranges::distance(__first1, __last1);
   555		    auto __d2 = ranges::distance(__first2, __last2);
   556		    if (__d1 == 0 && __d2 == 0)
   557		      return true;
   558		    if (__d1 != __d2)
   559		      return false;
   560		  }
   561	
   562		for (auto __scan = __first1; __scan != __last1; ++__scan)
   563		  {
   564		    auto&& __proj_scan = std::__invoke(__proj1, *__scan);
   565		    auto __comp_scan = [&] <typename _Tp> (_Tp&& __arg) -> bool {
   566		      return std::__invoke(__pred, __proj_scan,
   567					   std::forward<_Tp>(__arg));
   568		    };
   569		    if (__scan != ranges::find_if(__first1, __scan,
   570						  __comp_scan, __proj1))
   571		      continue; // We've seen this one before.
   572	
   573		    auto __matches = ranges::count_if(__first2, __last2,
   574						      __comp_scan, __proj2);
   575		    if (__matches == 0
   576			|| ranges::count_if(__scan, __last1,
   577					    __comp_scan, __proj1) != __matches)
   578		      return false;
   579		  }
   580		return true;
   581	      }
   582	
   583	    template<forward_range _Range1, forward_range _Range2,
   584		     typename _Proj1 = identity, typename _Proj2 = identity,
   585		     indirect_equivalence_relation<
   586		       projected<iterator_t<_Range1>, _Proj1>,
   587		       projected<iterator_t<_Range2>, _Proj2>> _Pred = ranges::equal_to>
   588	      constexpr bool
   589	      operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
   590			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
   591	      {
   592		return (*this)(ranges::begin(__r1), ranges::end(__r1),
   593			       ranges::begin(__r2), ranges::end(__r2),
   594			       std::move(__pred),
   595			       std::move(__proj1), std::move(__proj2));
   596	      }
   597	  };
   598	
   599	  inline constexpr __is_permutation_fn is_permutation{};
   600	
   601	  template<typename _Iter, typename _Out>
   602	    using copy_if_result = in_out_result<_Iter, _Out>;
   603	
   604	  struct __copy_if_fn
   605	  {
   606	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
   607		     weakly_incrementable _Out, typename _Proj = identity,
   608		     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
   609	      requires indirectly_copyable<_Iter, _Out>
   610	      constexpr copy_if_result<_Iter, _Out>
   611	      operator()(_Iter __first, _Sent __last, _Out __result,
   612			 _Pred __pred, _Proj __proj = {}) const
   613	      {
   614		for (; __first != __last; ++__first)
   615		  if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
   616		    {
   617		      *__result = *__first;
   618		      ++__result;
   619		    }
   620		return {std::move(__first), std::move(__result)};
   621	      }
   622	
   623	    template<input_range _Range, weakly_incrementable _Out,
   624		     typename _Proj = identity,
   625		     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
   626		       _Pred>
   627	      requires indirectly_copyable<iterator_t<_Range>, _Out>
   628	      constexpr copy_if_result<borrowed_iterator_t<_Range>, _Out>
   629	      operator()(_Range&& __r, _Out __result,
   630			 _Pred __pred, _Proj __proj = {}) const
   631	      {
   632		return (*this)(ranges::begin(__r), ranges::end(__r),
   633			       std::move(__result),
   634			       std::move(__pred), std::move(__proj));
   635	      }
   636	  };
   637	
   638	  inline constexpr __copy_if_fn copy_if{};
   639	
   640	  template<typename _Iter1, typename _Iter2>
   641	    using swap_ranges_result = in_in_result<_Iter1, _Iter2>;
   642	
   643	  struct __swap_ranges_fn
   644	  {
   645	    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
   646		     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2>
   647	      requires indirectly_swappable<_Iter1, _Iter2>
   648	      constexpr swap_ranges_result<_Iter1, _Iter2>
   649	      operator()(_Iter1 __first1, _Sent1 __last1,
   650			 _Iter2 __first2, _Sent2 __last2) const
   651	      {
   652		for (; __first1 != __last1 && __first2 != __last2;
   653		     ++__first1, (void)++__first2)
   654		  ranges::iter_swap(__first1, __first2);
   655		return {std::move(__first1), std::move(__first2)};
   656	      }
   657	
   658	    template<input_range _Range1, input_range _Range2>
   659	      requires indirectly_swappable<iterator_t<_Range1>, iterator_t<_Range2>>
   660	      constexpr swap_ranges_result<borrowed_iterator_t<_Range1>,
   661					   borrowed_iterator_t<_Range2>>
   662	      operator()(_Range1&& __r1, _Range2&& __r2) const
   663	      {
   664		return (*this)(ranges::begin(__r1), ranges::end(__r1),
   665			       ranges::begin(__r2), ranges::end(__r2));
   666	      }
   667	  };
   668	
   669	  inline constexpr __swap_ranges_fn swap_ranges{};
   670	
   671	  template<typename _Iter, typename _Out>
   672	    using unary_transform_result = in_out_result<_Iter, _Out>;
   673	
   674	  template<typename _Iter1, typename _Iter2, typename _Out>
   675	    struct in_in_out_result
   676	    {
   677	      [[no_unique_address]] _Iter1 in1;
   678	      [[no_unique_address]] _Iter2 in2;
   679	      [[no_unique_address]] _Out  out;
   680	
   681	      template<typename _IIter1, typename _IIter2, typename _OOut>
   682		requires convertible_to<const _Iter1&, _IIter1>
   683		  && convertible_to<const _Iter2&, _IIter2>
   684		  && convertible_to<const _Out&, _OOut>
   685		constexpr
   686		operator in_in_out_result<_IIter1, _IIter2, _OOut>() const &
   687		{ return {in1, in2, out}; }
   688	
   689	      template<typename _IIter1, typename _IIter2, typename _OOut>
   690		requires convertible_to<_Iter1, _IIter1>
   691		  && convertible_to<_Iter2, _IIter2>
   692		  && convertible_to<_Out, _OOut>
   693		constexpr
   694		operator in_in_out_result<_IIter1, _IIter2, _OOut>() &&
   695		{ return {std::move(in1), std::move(in2), std::move(out)}; }
   696	    };
   697	
   698	  template<typename _Iter1, typename _Iter2, typename _Out>
   699	    using binary_transform_result = in_in_out_result<_Iter1, _Iter2, _Out>;
   700	
   701	  struct __transform_fn
   702	  {
   703	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
   704		     weakly_incrementable _Out,
   705		     copy_constructible _Fp, typename _Proj = identity>
   706	      requires indirectly_writable<_Out,
   707					   indirect_result_t<_Fp&,
   708					     projected<_Iter, _Proj>>>
   709	      constexpr unary_transform_result<_Iter, _Out>
   710	      operator()(_Iter __first1, _Sent __last1, _Out __result,
   711			 _Fp __op, _Proj __proj = {}) const
   712	      {
   713		for (; __first1 != __last1; ++__first1, (void)++__result)
   714		  *__result = std::__invoke(__op, std::__invoke(__proj, *__first1));
   715		return {std::move(__first1), std::move(__result)};
   716	      }
   717	
   718	    template<input_range _Range, weakly_incrementable _Out,
   719		     copy_constructible _Fp, typename _Proj = identity>
   720	      requires indirectly_writable<_Out,
   721					   indirect_result_t<_Fp&,
   722					     projected<iterator_t<_Range>, _Proj>>>
   723	      constexpr unary_transform_result<borrowed_iterator_t<_Range>, _Out>
   724	      operator()(_Range&& __r, _Out __result, _Fp __op, _Proj __proj = {}) const
   725	      {
   726		return (*this)(ranges::begin(__r), ranges::end(__r),
   727			       std::move(__result),
   728			       std::move(__op), std::move(__proj));
   729	      }
   730	
   731	    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
   732		     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
   733		     weakly_incrementable _Out, copy_constructible _Fp,
   734		     typename _Proj1 = identity, typename _Proj2 = identity>
   735	      requires indirectly_writable<_Out,
   736					   indirect_result_t<_Fp&,
   737					     projected<_Iter1, _Proj1>,
   738					     projected<_Iter2, _Proj2>>>
   739	      constexpr binary_transform_result<_Iter1, _Iter2, _Out>
   740	      operator()(_Iter1 __first1, _Sent1 __last1,
   741			 _Iter2 __first2, _Sent2 __last2,
   742			 _Out __result, _Fp __binary_op,
   743			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
   744	      {
   745		for (; __first1 != __last1 && __first2 != __last2;
   746		     ++__first1, (void)++__first2, ++__result)
   747		  *__result = std::__invoke(__binary_op,
   748					    std::__invoke(__proj1, *__first1),
   749					    std::__invoke(__proj2, *__first2));
   750		return {std::move(__first1), std::move(__first2), std::move(__result)};
   751	      }
   752	
   753	    template<input_range _Range1, input_range _Range2,
   754		     weakly_incrementable _Out, copy_constructible _Fp,
   755		     typename _Proj1 = identity, typename _Proj2 = identity>
   756	      requires indirectly_writable<_Out,
   757					   indirect_result_t<_Fp&,
   758					     projected<iterator_t<_Range1>, _Proj1>,
   759					     projected<iterator_t<_Range2>, _Proj2>>>
   760	      constexpr binary_transform_result<borrowed_iterator_t<_Range1>,
   761						borrowed_iterator_t<_Range2>, _Out>
   762	      operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, _Fp __binary_op,
   763			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
   764	      {
   765		return (*this)(ranges::begin(__r1), ranges::end(__r1),
   766			       ranges::begin(__r2), ranges::end(__r2),
   767			       std::move(__result), std::move(__binary_op),
   768			       std::move(__proj1), std::move(__proj2));
   769	      }
   770	  };
   771	
   772	  inline constexpr __transform_fn transform{};
   773	
   774	  struct __replace_fn
   775	  {
   776	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
   777		     typename _Tp1, typename _Tp2, typename _Proj = identity>
   778	      requires indirectly_writable<_Iter, const _Tp2&>
   779		&& indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
   780					     const _Tp1*>
   781	      constexpr _Iter
   782	      operator()(_Iter __first, _Sent __last,
   783			 const _Tp1& __old_value, const _Tp2& __new_value,
   784			 _Proj __proj = {}) const
   785	      {
   786		for (; __first != __last; ++__first)
   787		  if (std::__invoke(__proj, *__first) == __old_value)
   788		    *__first = __new_value;
   789		return __first;
   790	      }
   791	
   792	    template<input_range _Range,
   793		     typename _Tp1, typename _Tp2, typename _Proj = identity>
   794	      requires indirectly_writable<iterator_t<_Range>, const _Tp2&>
   795		&& indirect_binary_predicate<ranges::equal_to,
   796					     projected<iterator_t<_Range>, _Proj>,
   797					     const _Tp1*>
   798	      constexpr borrowed_iterator_t<_Range>
   799	      operator()(_Range&& __r,
   800			 const _Tp1& __old_value, const _Tp2& __new_value,
   801			 _Proj __proj = {}) const
   802	      {
   803		return (*this)(ranges::begin(__r), ranges::end(__r),
   804			       __old_value, __new_value, std::move(__proj));
   805	      }
   806	  };
   807	
   808	  inline constexpr __replace_fn replace{};
   809	
   810	  struct __replace_if_fn
   811	  {
   812	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
   813		     typename _Tp, typename _Proj = identity,
   814		     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
   815	      requires indirectly_writable<_Iter, const _Tp&>
   816	      constexpr _Iter
   817	      operator()(_Iter __first, _Sent __last,
   818			 _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
   819	      {
   820		for (; __first != __last; ++__first)
   821		  if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
   822		    *__first = __new_value;
   823		return std::move(__first);
   824	      }
   825	
   826	    template<input_range _Range, typename _Tp, typename _Proj = identity,
   827		     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
   828		       _Pred>
   829	      requires indirectly_writable<iterator_t<_Range>, const _Tp&>
   830	      constexpr borrowed_iterator_t<_Range>
   831	      operator()(_Range&& __r,
   832			 _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
   833	      {
   834		return (*this)(ranges::begin(__r), ranges::end(__r),
   835			       std::move(__pred), __new_value, std::move(__proj));
   836	      }
   837	  };
   838	
   839	  inline constexpr __replace_if_fn replace_if{};
   840	
   841	  template<typename _Iter, typename _Out>
   842	    using replace_copy_result = in_out_result<_Iter, _Out>;
   843	
   844	  struct __replace_copy_fn
   845	  {
   846	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
   847		     typename _Tp1, typename _Tp2, output_iterator<const _Tp2&> _Out,
   848		     typename _Proj = identity>
   849	      requires indirectly_copyable<_Iter, _Out>
   850		&& indirect_binary_predicate<ranges::equal_to,
   851					     projected<_Iter, _Proj>, const _Tp1*>
   852	      constexpr replace_copy_result<_Iter, _Out>
   853	      operator()(_Iter __first, _Sent __last, _Out __result,
   854			 const _Tp1& __old_value, const _Tp2& __new_value,
   855			 _Proj __proj = {}) const
   856	      {
   857		for (; __first != __last; ++__first, (void)++__result)
   858		  if (std::__invoke(__proj, *__first) == __old_value)
   859		    *__result = __new_value;
   860		  else
   861		    *__result = *__first;
   862		return {std::move(__first), std::move(__result)};
   863	      }
   864	
   865	    template<input_range _Range, typename _Tp1, typename _Tp2,
   866		     output_iterator<const _Tp2&> _Out, typename _Proj = identity>
   867	      requires indirectly_copyable<iterator_t<_Range>, _Out>
   868		&& indirect_binary_predicate<ranges::equal_to,
   869					     projected<iterator_t<_Range>, _Proj>,
   870					     const _Tp1*>
   871	      constexpr replace_copy_result<borrowed_iterator_t<_Range>, _Out>
   872	      operator()(_Range&& __r, _Out __result,
   873			 const _Tp1& __old_value, const _Tp2& __new_value,
   874			 _Proj __proj = {}) const
   875	      {
   876		return (*this)(ranges::begin(__r), ranges::end(__r),
   877			       std::move(__result), __old_value,
   878			       __new_value, std::move(__proj));
   879	      }
   880	  };
   881	
   882	  inline constexpr __replace_copy_fn replace_copy{};
   883	
   884	  template<typename _Iter, typename _Out>
   885	    using replace_copy_if_result = in_out_result<_Iter, _Out>;
   886	
   887	  struct __replace_copy_if_fn
   888	  {
   889	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
   890		     typename _Tp, output_iterator<const _Tp&> _Out,
   891		     typename _Proj = identity,
   892		     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
   893	      requires indirectly_copyable<_Iter, _Out>
   894	      constexpr replace_copy_if_result<_Iter, _Out>
   895	      operator()(_Iter __first, _Sent __last, _Out __result,
   896			 _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
   897	      {
   898		for (; __first != __last; ++__first, (void)++__result)
   899		  if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
   900		    *__result = __new_value;
   901		  else
   902		    *__result = *__first;
   903		return {std::move(__first), std::move(__result)};
   904	      }
   905	
   906	    template<input_range _Range,
   907		     typename _Tp, output_iterator<const _Tp&> _Out,
   908		     typename _Proj = identity,
   909		     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
   910		       _Pred>
   911	      requires indirectly_copyable<iterator_t<_Range>, _Out>
   912	      constexpr replace_copy_if_result<borrowed_iterator_t<_Range>, _Out>
   913	      operator()(_Range&& __r, _Out __result,
   914			 _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
   915	      {
   916		return (*this)(ranges::begin(__r), ranges::end(__r),
   917			       std::move(__result), std::move(__pred),
   918			       __new_value, std::move(__proj));
   919	      }
   920	  };
   921	
   922	  inline constexpr __replace_copy_if_fn replace_copy_if{};
   923	
   924	  struct __generate_n_fn
   925	  {
   926	    template<input_or_output_iterator _Out, copy_constructible _Fp>
   927	      requires invocable<_Fp&>
   928		&& indirectly_writable<_Out, invoke_result_t<_Fp&>>
   929	      constexpr _Out
   930	      operator()(_Out __first, iter_difference_t<_Out> __n, _Fp __gen) const
   931	      {
   932		for (; __n > 0; --__n, (void)++__first)
   933		  *__first = std::__invoke(__gen);
   934		return __first;
   935	      }
   936	  };
   937	
   938	  inline constexpr __generate_n_fn generate_n{};
   939	
   940	  struct __generate_fn
   941	  {
   942	    template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent,
   943		     copy_constructible _Fp>
   944	      requires invocable<_Fp&>
   945		&& indirectly_writable<_Out, invoke_result_t<_Fp&>>
   946	      constexpr _Out
   947	      operator()(_Out __first, _Sent __last, _Fp __gen) const
   948	      {
   949		for (; __first != __last; ++__first)
   950		  *__first = std::__invoke(__gen);
   951		return __first;
   952	      }
   953	
   954	    template<typename _Range, copy_constructible _Fp>
   955	      requires invocable<_Fp&> && output_range<_Range, invoke_result_t<_Fp&>>
   956	      constexpr borrowed_iterator_t<_Range>
   957	      operator()(_Range&& __r, _Fp __gen) const
   958	      {
   959		return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__gen));
   960	      }
   961	  };
   962	
   963	  inline constexpr __generate_fn generate{};
   964	
   965	  struct __remove_if_fn
   966	  {
   967	    template<permutable _Iter, sentinel_for<_Iter> _Sent,
   968		     typename _Proj = identity,
   969		     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
   970	      constexpr subrange<_Iter>
   971	      operator()(_Iter __first, _Sent __last,
   972			 _Pred __pred, _Proj __proj = {}) const
   973	      {
   974		__first = ranges::find_if(__first, __last, __pred, __proj);
   975		if (__first == __last)
   976		  return {__first, __first};
   977	
   978		auto __result = __first;
   979		++__first;
   980		for (; __first != __last; ++__first)
   981		  if (!std::__invoke(__pred, std::__invoke(__proj, *__first)))
   982		    {
   983		      *__result = std::move(*__first);
   984		      ++__result;
   985		    }
   986	
   987		return {__result, __first};
   988	      }
   989	
   990	    template<forward_range _Range, typename _Proj = identity,
   991		     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
   992		       _Pred>
   993	      requires permutable<iterator_t<_Range>>
   994	      constexpr borrowed_subrange_t<_Range>
   995	      operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
   996	      {
   997		return (*this)(ranges::begin(__r), ranges::end(__r),
   998			       std::move(__pred), std::move(__proj));
   999	      }
  1000	  };
  1001	
  1002	  inline constexpr __remove_if_fn remove_if{};
  1003	
  1004	  struct __remove_fn
  1005	  {
  1006	    template<permutable _Iter, sentinel_for<_Iter> _Sent,
  1007		     typename _Tp, typename _Proj = identity>
  1008	      requires indirect_binary_predicate<ranges::equal_to,
  1009						 projected<_Iter, _Proj>,
  1010						 const _Tp*>
  1011	      constexpr subrange<_Iter>
  1012	      operator()(_Iter __first, _Sent __last,
  1013			 const _Tp& __value, _Proj __proj = {}) const
  1014	      {
  1015		auto __pred = [&] (auto&& __arg) -> bool {
  1016		  return std::forward<decltype(__arg)>(__arg) == __value;
  1017		};
  1018		return ranges::remove_if(__first, __last,
  1019					 std::move(__pred), std::move(__proj));
  1020	      }
  1021	
  1022	    template<forward_range _Range, typename _Tp, typename _Proj = identity>
  1023	      requires permutable<iterator_t<_Range>>
  1024		&& indirect_binary_predicate<ranges::equal_to,
  1025					     projected<iterator_t<_Range>, _Proj>,
  1026					     const _Tp*>
  1027	      constexpr borrowed_subrange_t<_Range>
  1028	      operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
  1029	      {
  1030		return (*this)(ranges::begin(__r), ranges::end(__r),
  1031			       __value, std::move(__proj));
  1032	      }
  1033	  };
  1034	
  1035	  inline constexpr __remove_fn remove{};
  1036	
  1037	  template<typename _Iter, typename _Out>
  1038	    using remove_copy_if_result = in_out_result<_Iter, _Out>;
  1039	
  1040	  struct __remove_copy_if_fn
  1041	  {
  1042	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
  1043		     weakly_incrementable _Out, typename _Proj = identity,
  1044		     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
  1045	      requires indirectly_copyable<_Iter, _Out>
  1046	      constexpr remove_copy_if_result<_Iter, _Out>
  1047	      operator()(_Iter __first, _Sent __last, _Out __result,
  1048			 _Pred __pred, _Proj __proj = {}) const
  1049	      {
  1050		for (; __first != __last; ++__first)
  1051		  if (!std::__invoke(__pred, std::__invoke(__proj, *__first)))
  1052		    {
  1053		      *__result = *__first;
  1054		      ++__result;
  1055		    }
  1056		return {std::move(__first), std::move(__result)};
  1057	      }
  1058	
  1059	    template<input_range _Range, weakly_incrementable _Out,
  1060		     typename _Proj = identity,
  1061		     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
  1062		       _Pred>
  1063	      requires indirectly_copyable<iterator_t<_Range>, _Out>
  1064	      constexpr remove_copy_if_result<borrowed_iterator_t<_Range>, _Out>
  1065	      operator()(_Range&& __r, _Out __result,
  1066			 _Pred __pred, _Proj __proj = {}) const
  1067	      {
  1068		return (*this)(ranges::begin(__r), ranges::end(__r),
  1069			       std::move(__result),
  1070			       std::move(__pred), std::move(__proj));
  1071	      }
  1072	  };
  1073	
  1074	  inline constexpr __remove_copy_if_fn remove_copy_if{};
  1075	
  1076	  template<typename _Iter, typename _Out>
  1077	    using remove_copy_result = in_out_result<_Iter, _Out>;
  1078	
  1079	  struct __remove_copy_fn
  1080	  {
  1081	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
  1082		     weakly_incrementable _Out, typename _Tp, typename _Proj = identity>
  1083	      requires indirectly_copyable<_Iter, _Out>
  1084		&& indirect_binary_predicate<ranges::equal_to,
  1085					     projected<_Iter, _Proj>,
  1086					     const _Tp*>
  1087	      constexpr remove_copy_result<_Iter, _Out>
  1088	      operator()(_Iter __first, _Sent __last, _Out __result,
  1089			 const _Tp& __value, _Proj __proj = {}) const
  1090	      {
  1091		for (; __first != __last; ++__first)
  1092		  if (!(std::__invoke(__proj, *__first) == __value))
  1093		    {
  1094		      *__result = *__first;
  1095		      ++__result;
  1096		    }
  1097		return {std::move(__first), std::move(__result)};
  1098	      }
  1099	
  1100	    template<input_range _Range, weakly_incrementable _Out,
  1101		     typename _Tp, typename _Proj = identity>
  1102	      requires indirectly_copyable<iterator_t<_Range>, _Out>
  1103		&& indirect_binary_predicate<ranges::equal_to,
  1104					     projected<iterator_t<_Range>, _Proj>,
  1105					     const _Tp*>
  1106	      constexpr remove_copy_result<borrowed_iterator_t<_Range>, _Out>
  1107	      operator()(_Range&& __r, _Out __result,
  1108			 const _Tp& __value, _Proj __proj = {}) const
  1109	      {
  1110		return (*this)(ranges::begin(__r), ranges::end(__r),
  1111			       std::move(__result), __value, std::move(__proj));
  1112	      }
  1113	  };
  1114	
  1115	  inline constexpr __remove_copy_fn remove_copy{};
  1116	
  1117	  struct __unique_fn
  1118	  {
  1119	    template<permutable _Iter, sentinel_for<_Iter> _Sent,
  1120		     typename _Proj = identity,
  1121		     indirect_equivalence_relation<
  1122		       projected<_Iter, _Proj>> _Comp = ranges::equal_to>
  1123	      constexpr subrange<_Iter>
  1124	      operator()(_Iter __first, _Sent __last,
  1125			 _Comp __comp = {}, _Proj __proj = {}) const
  1126	      {
  1127		__first = ranges::adjacent_find(__first, __last, __comp, __proj);
  1128		if (__first == __last)
  1129		  return {__first, __first};
  1130	
  1131		auto __dest = __first;
  1132		++__first;
  1133		while (++__first != __last)
  1134		  if (!std::__invoke(__comp,
  1135				     std::__invoke(__proj, *__dest),
  1136				     std::__invoke(__proj, *__first)))
  1137		    *++__dest = std::move(*__first);
  1138		return {++__dest, __first};
  1139	      }
  1140	
  1141	    template<forward_range _Range, typename _Proj = identity,
  1142		     indirect_equivalence_relation<
  1143		       projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
  1144	      requires permutable<iterator_t<_Range>>
  1145	      constexpr borrowed_subrange_t<_Range>
  1146	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  1147	      {
  1148		return (*this)(ranges::begin(__r), ranges::end(__r),
  1149			       std::move(__comp), std::move(__proj));
  1150	      }
  1151	  };
  1152	
  1153	  inline constexpr __unique_fn unique{};
  1154	
  1155	  namespace __detail
  1156	  {
  1157	    template<typename _Out, typename _Tp>
  1158	      concept __can_reread_output = input_iterator<_Out>
  1159		&& same_as<_Tp, iter_value_t<_Out>>;
  1160	  }
  1161	
  1162	  template<typename _Iter, typename _Out>
  1163	    using unique_copy_result = in_out_result<_Iter, _Out>;
  1164	
  1165	  struct __unique_copy_fn
  1166	  {
  1167	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
  1168		     weakly_incrementable _Out, typename _Proj = identity,
  1169		     indirect_equivalence_relation<
  1170		       projected<_Iter, _Proj>> _Comp = ranges::equal_to>
  1171	      requires indirectly_copyable<_Iter, _Out>
  1172		&& (forward_iterator<_Iter>
  1173		    || __detail::__can_reread_output<_Out, iter_value_t<_Iter>>
  1174		    || indirectly_copyable_storable<_Iter, _Out>)
  1175	      constexpr unique_copy_result<_Iter, _Out>
  1176	      operator()(_Iter __first, _Sent __last, _Out __result,
  1177			 _Comp __comp = {}, _Proj __proj = {}) const
  1178	      {
  1179		if (__first == __last)
  1180		  return {std::move(__first), std::move(__result)};
  1181	
  1182		// TODO: perform a closer comparison with reference implementations
  1183		if constexpr (forward_iterator<_Iter>)
  1184		  {
  1185		    auto __next = __first;
  1186		    *__result = *__next;
  1187		    while (++__next != __last)
  1188		      if (!std::__invoke(__comp,
  1189					 std::__invoke(__proj, *__first),
  1190					 std::__invoke(__proj, *__next)))
  1191			{
  1192			  __first = __next;
  1193			  *++__result = *__first;
  1194			}
  1195		    return {__next, std::move(++__result)};
  1196		  }
  1197		else if constexpr (__detail::__can_reread_output<_Out, iter_value_t<_Iter>>)
  1198		  {
  1199		    *__result = *__first;
  1200		    while (++__first != __last)
  1201		      if (!std::__invoke(__comp,
  1202					 std::__invoke(__proj, *__result),
  1203					 std::__invoke(__proj, *__first)))
  1204			  *++__result = *__first;
  1205		    return {std::move(__first), std::move(++__result)};
  1206		  }
  1207		else // indirectly_copyable_storable<_Iter, _Out>
  1208		  {
  1209		    auto __value = *__first;
  1210		    *__result = __value;
  1211		    while (++__first != __last)
  1212		      {
  1213			if (!(bool)std::__invoke(__comp,
  1214						 std::__invoke(__proj, *__first),
  1215						 std::__invoke(__proj, __value)))
  1216			  {
  1217			    __value = *__first;
  1218			    *++__result = __value;
  1219			  }
  1220		      }
  1221		    return {std::move(__first), std::move(++__result)};
  1222		  }
  1223	      }
  1224	
  1225	    template<input_range _Range,
  1226		     weakly_incrementable _Out, typename _Proj = identity,
  1227		     indirect_equivalence_relation<
  1228		       projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
  1229	      requires indirectly_copyable<iterator_t<_Range>, _Out>
  1230		&& (forward_iterator<iterator_t<_Range>>
  1231		    || __detail::__can_reread_output<_Out, range_value_t<_Range>>
  1232		    || indirectly_copyable_storable<iterator_t<_Range>, _Out>)
  1233	      constexpr unique_copy_result<borrowed_iterator_t<_Range>, _Out>
  1234	      operator()(_Range&& __r, _Out __result,
  1235			 _Comp __comp = {}, _Proj __proj = {}) const
  1236	      {
  1237		return (*this)(ranges::begin(__r), ranges::end(__r),
  1238			       std::move(__result),
  1239			       std::move(__comp), std::move(__proj));
  1240	      }
  1241	  };
  1242	
  1243	  inline constexpr __unique_copy_fn unique_copy{};
  1244	
  1245	  struct __reverse_fn
  1246	  {
  1247	    template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
  1248	      requires permutable<_Iter>
  1249	      constexpr _Iter
  1250	      operator()(_Iter __first, _Sent __last) const
  1251	      {
  1252		auto __i = ranges::next(__first, __last);
  1253		auto __tail = __i;
  1254	
  1255		if constexpr (random_access_iterator<_Iter>)
  1256		  {
  1257		    if (__first != __last)
  1258		      {
  1259			--__tail;
  1260			while (__first < __tail)
  1261			  {
  1262			    ranges::iter_swap(__first, __tail);
  1263			    ++__first;
  1264			    --__tail;
  1265			  }
  1266		      }
  1267		    return __i;
  1268		  }
  1269		else
  1270		  {
  1271		    for (;;)
  1272		      if (__first == __tail || __first == --__tail)
  1273			break;
  1274		      else
  1275			{
  1276			  ranges::iter_swap(__first, __tail);
  1277			  ++__first;
  1278			}
  1279		    return __i;
  1280		  }
  1281	      }
  1282	
  1283	    template<bidirectional_range _Range>
  1284	      requires permutable<iterator_t<_Range>>
  1285	      constexpr borrowed_iterator_t<_Range>
  1286	      operator()(_Range&& __r) const
  1287	      {
  1288		return (*this)(ranges::begin(__r), ranges::end(__r));
  1289	      }
  1290	  };
  1291	
  1292	  inline constexpr __reverse_fn reverse{};
  1293	
  1294	  template<typename _Iter, typename _Out>
  1295	    using reverse_copy_result = in_out_result<_Iter, _Out>;
  1296	
  1297	  struct __reverse_copy_fn
  1298	  {
  1299	    template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
  1300		     weakly_incrementable _Out>
  1301	      requires indirectly_copyable<_Iter, _Out>
  1302	      constexpr reverse_copy_result<_Iter, _Out>
  1303	      operator()(_Iter __first, _Sent __last, _Out __result) const
  1304	      {
  1305		auto __i = ranges::next(__first, __last);
  1306		auto __tail = __i;
  1307		while (__first != __tail)
  1308		  {
  1309		    --__tail;
  1310		    *__result = *__tail;
  1311		    ++__result;
  1312		  }
  1313		return {__i, std::move(__result)};
  1314	      }
  1315	
  1316	    template<bidirectional_range _Range, weakly_incrementable _Out>
  1317	      requires indirectly_copyable<iterator_t<_Range>, _Out>
  1318	      constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _Out>
  1319	      operator()(_Range&& __r, _Out __result) const
  1320	      {
  1321		return (*this)(ranges::begin(__r), ranges::end(__r),
  1322			       std::move(__result));
  1323	      }
  1324	  };
  1325	
  1326	  inline constexpr __reverse_copy_fn reverse_copy{};
  1327	
  1328	  struct __rotate_fn
  1329	  {
  1330	    template<permutable _Iter, sentinel_for<_Iter> _Sent>
  1331	      constexpr subrange<_Iter>
  1332	      operator()(_Iter __first, _Iter __middle, _Sent __last) const
  1333	      {
  1334		auto __lasti = ranges::next(__first, __last);
  1335		if (__first == __middle)
  1336		  return {__lasti, __lasti};
  1337		if (__last == __middle)
  1338		  return {std::move(__first), std::move(__lasti)};
  1339	
  1340		if constexpr (random_access_iterator<_Iter>)
  1341		  {
  1342		    auto __n = __lasti - __first;
  1343		    auto __k = __middle - __first;
  1344	
  1345		    if (__k == __n - __k)
  1346		      {
  1347			ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
  1348			return {std::move(__middle), std::move(__lasti)};
  1349		      }
  1350	
  1351		    auto __p = __first;
  1352		    auto __ret = __first + (__lasti - __middle);
  1353	
  1354		    for (;;)
  1355		      {
  1356			if (__k < __n - __k)
  1357			  {
  1358			    // TODO: is_pod is deprecated, but this condition is
  1359			    // consistent with the STL implementation.
  1360			    if constexpr (__is_pod(iter_value_t<_Iter>))
  1361			      if (__k == 1)
  1362				{
  1363				  auto __t = std::move(*__p);
  1364				  ranges::move(__p + 1, __p + __n, __p);
  1365				  *(__p + __n - 1) = std::move(__t);
  1366				  return {std::move(__ret), std::move(__lasti)};
  1367				}
  1368			    auto __q = __p + __k;
  1369			    for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
  1370			      {
  1371				ranges::iter_swap(__p, __q);
  1372				++__p;
  1373				++__q;
  1374			      }
  1375			    __n %= __k;
  1376			    if (__n == 0)
  1377			      return {std::move(__ret), std::move(__lasti)};
  1378			    ranges::swap(__n, __k);
  1379			    __k = __n - __k;
  1380			  }
  1381			else
  1382			  {
  1383			    __k = __n - __k;
  1384			    // TODO: is_pod is deprecated, but this condition is
  1385			    // consistent with the STL implementation.
  1386			    if constexpr (__is_pod(iter_value_t<_Iter>))
  1387			      if (__k == 1)
  1388				{
  1389				  auto __t = std::move(*(__p + __n - 1));
  1390				  ranges::move_backward(__p, __p + __n - 1, __p + __n);
  1391				  *__p = std::move(__t);
  1392				  return {std::move(__ret), std::move(__lasti)};
  1393				}
  1394			    auto __q = __p + __n;
  1395			    __p = __q - __k;
  1396			    for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
  1397			      {
  1398				--__p;
  1399				--__q;
  1400				ranges::iter_swap(__p, __q);
  1401			      }
  1402			    __n %= __k;
  1403			    if (__n == 0)
  1404			      return {std::move(__ret), std::move(__lasti)};
  1405			    std::swap(__n, __k);
  1406			  }
  1407		      }
  1408		  }
  1409		else if constexpr (bidirectional_iterator<_Iter>)
  1410		  {
  1411		    auto __tail = __lasti;
  1412	
  1413		    ranges::reverse(__first, __middle);
  1414		    ranges::reverse(__middle, __tail);
  1415	
  1416		    while (__first != __middle && __middle != __tail)
  1417		      {
  1418			ranges::iter_swap(__first, --__tail);
  1419			++__first;
  1420		      }
  1421	
  1422		    if (__first == __middle)
  1423		      {
  1424			ranges::reverse(__middle, __tail);
  1425			return {std::move(__tail), std::move(__lasti)};
  1426		      }
  1427		    else
  1428		      {
  1429			ranges::reverse(__first, __middle);
  1430			return {std::move(__first), std::move(__lasti)};
  1431		      }
  1432		  }
  1433		else
  1434		  {
  1435		    auto __first2 = __middle;
  1436		    do
  1437		      {
  1438			ranges::iter_swap(__first, __first2);
  1439			++__first;
  1440			++__first2;
  1441			if (__first == __middle)
  1442			  __middle = __first2;
  1443		      } while (__first2 != __last);
  1444	
  1445		    auto __ret = __first;
  1446	
  1447		    __first2 = __middle;
  1448	
  1449		    while (__first2 != __last)
  1450		      {
  1451			ranges::iter_swap(__first, __first2);
  1452			++__first;
  1453			++__first2;
  1454			if (__first == __middle)
  1455			  __middle = __first2;
  1456			else if (__first2 == __last)
  1457			  __first2 = __middle;
  1458		      }
  1459		    return {std::move(__ret), std::move(__lasti)};
  1460		  }
  1461	      }
  1462	
  1463	    template<forward_range _Range>
  1464	      requires permutable<iterator_t<_Range>>
  1465	      constexpr borrowed_subrange_t<_Range>
  1466	      operator()(_Range&& __r, iterator_t<_Range> __middle) const
  1467	      {
  1468		return (*this)(ranges::begin(__r), std::move(__middle),
  1469			       ranges::end(__r));
  1470	      }
  1471	  };
  1472	
  1473	  inline constexpr __rotate_fn rotate{};
  1474	
  1475	  template<typename _Iter, typename _Out>
  1476	    using rotate_copy_result = in_out_result<_Iter, _Out>;
  1477	
  1478	  struct __rotate_copy_fn
  1479	  {
  1480	    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
  1481		     weakly_incrementable _Out>
  1482	      requires indirectly_copyable<_Iter, _Out>
  1483	      constexpr rotate_copy_result<_Iter, _Out>
  1484	      operator()(_Iter __first, _Iter __middle, _Sent __last,
  1485			 _Out __result) const
  1486	      {
  1487		auto __copy1 = ranges::copy(__middle,
  1488					    std::move(__last),
  1489					    std::move(__result));
  1490		auto __copy2 = ranges::copy(std::move(__first),
  1491					    std::move(__middle),
  1492					    std::move(__copy1.out));
  1493		return { std::move(__copy1.in), std::move(__copy2.out) };
  1494	      }
  1495	
  1496	    template<forward_range _Range, weakly_incrementable _Out>
  1497	      requires indirectly_copyable<iterator_t<_Range>, _Out>
  1498	      constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _Out>
  1499	      operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result) const
  1500	      {
  1501		return (*this)(ranges::begin(__r), std::move(__middle),
  1502			       ranges::end(__r), std::move(__result));
  1503	      }
  1504	  };
  1505	
  1506	  inline constexpr __rotate_copy_fn rotate_copy{};
  1507	
  1508	  struct __sample_fn
  1509	  {
  1510	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
  1511		     weakly_incrementable _Out, typename _Gen>
  1512	      requires (forward_iterator<_Iter> || random_access_iterator<_Out>)
  1513		&& indirectly_copyable<_Iter, _Out>
  1514		&& uniform_random_bit_generator<remove_reference_t<_Gen>>
  1515	      _Out
  1516	      operator()(_Iter __first, _Sent __last, _Out __out,
  1517			 iter_difference_t<_Iter> __n, _Gen&& __g) const
  1518	      {
  1519		if constexpr (forward_iterator<_Iter>)
  1520		  {
  1521		    // FIXME: Forwarding to std::sample here requires computing __lasti
  1522		    // which may take linear time.
  1523		    auto __lasti = ranges::next(__first, __last);
  1524		    return _GLIBCXX_STD_A::
  1525		      sample(std::move(__first), std::move(__lasti), std::move(__out),
  1526			     __n, std::forward<_Gen>(__g));
  1527		  }
  1528		else
  1529		  {
  1530		    using __distrib_type
  1531		      = uniform_int_distribution<iter_difference_t<_Iter>>;
  1532		    using __param_type = typename __distrib_type::param_type;
  1533		    __distrib_type __d{};
  1534		    iter_difference_t<_Iter> __sample_sz = 0;
  1535		    while (__first != __last && __sample_sz != __n)
  1536		      {
  1537			__out[__sample_sz++] = *__first;
  1538			++__first;
  1539		      }
  1540		    for (auto __pop_sz = __sample_sz; __first != __last;
  1541			++__first, (void) ++__pop_sz)
  1542		      {
  1543			const auto __k = __d(__g, __param_type{0, __pop_sz});
  1544			if (__k < __n)
  1545			  __out[__k] = *__first;
  1546		      }
  1547		    return __out + __sample_sz;
  1548		  }
  1549	      }
  1550	
  1551	    template<input_range _Range, weakly_incrementable _Out, typename _Gen>
  1552	      requires (forward_range<_Range> || random_access_iterator<_Out>)
  1553		&& indirectly_copyable<iterator_t<_Range>, _Out>
  1554		&& uniform_random_bit_generator<remove_reference_t<_Gen>>
  1555	      _Out
  1556	      operator()(_Range&& __r, _Out __out,
  1557			 range_difference_t<_Range> __n, _Gen&& __g) const
  1558	      {
  1559		return (*this)(ranges::begin(__r), ranges::end(__r),
  1560			       std::move(__out), __n,
  1561			       std::forward<_Gen>(__g));
  1562	      }
  1563	  };
  1564	
  1565	  inline constexpr __sample_fn sample{};
  1566	
  1567	#ifdef _GLIBCXX_USE_C99_STDINT_TR1
  1568	  struct __shuffle_fn
  1569	  {
  1570	    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
  1571		     typename _Gen>
  1572	      requires permutable<_Iter>
  1573		&& uniform_random_bit_generator<remove_reference_t<_Gen>>
  1574	      _Iter
  1575	      operator()(_Iter __first, _Sent __last, _Gen&& __g) const
  1576	      {
  1577		auto __lasti = ranges::next(__first, __last);
  1578		std::shuffle(std::move(__first), __lasti, std::forward<_Gen>(__g));
  1579		return __lasti;
  1580	      }
  1581	
  1582	    template<random_access_range _Range, typename _Gen>
  1583	      requires permutable<iterator_t<_Range>>
  1584		&& uniform_random_bit_generator<remove_reference_t<_Gen>>
  1585	      borrowed_iterator_t<_Range>
  1586	      operator()(_Range&& __r, _Gen&& __g) const
  1587	      {
  1588		return (*this)(ranges::begin(__r), ranges::end(__r),
  1589			       std::forward<_Gen>(__g));
  1590	      }
  1591	  };
  1592	
  1593	  inline constexpr __shuffle_fn shuffle{};
  1594	#endif
  1595	
  1596	  struct __push_heap_fn
  1597	  {
  1598	    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
  1599		     typename _Comp = ranges::less, typename _Proj = identity>
  1600	      requires sortable<_Iter, _Comp, _Proj>
  1601	      constexpr _Iter
  1602	      operator()(_Iter __first, _Sent __last,
  1603			 _Comp __comp = {}, _Proj __proj = {}) const
  1604	      {
  1605		auto __lasti = ranges::next(__first, __last);
  1606		std::push_heap(__first, __lasti,
  1607			       __detail::__make_comp_proj(__comp, __proj));
  1608		return __lasti;
  1609	      }
  1610	
  1611	    template<random_access_range _Range,
  1612		     typename _Comp = ranges::less, typename _Proj = identity>
  1613	      requires sortable<iterator_t<_Range>, _Comp, _Proj>
  1614	      constexpr borrowed_iterator_t<_Range>
  1615	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  1616	      {
  1617		return (*this)(ranges::begin(__r), ranges::end(__r),
  1618			       std::move(__comp), std::move(__proj));
  1619	      }
  1620	  };
  1621	
  1622	  inline constexpr __push_heap_fn push_heap{};
  1623	
  1624	  struct __pop_heap_fn
  1625	  {
  1626	    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
  1627		     typename _Comp = ranges::less, typename _Proj = identity>
  1628	      requires sortable<_Iter, _Comp, _Proj>
  1629	      constexpr _Iter
  1630	      operator()(_Iter __first, _Sent __last,
  1631			 _Comp __comp = {}, _Proj __proj = {}) const
  1632	      {
  1633		auto __lasti = ranges::next(__first, __last);
  1634		std::pop_heap(__first, __lasti,
  1635			      __detail::__make_comp_proj(__comp, __proj));
  1636		return __lasti;
  1637	      }
  1638	
  1639	    template<random_access_range _Range,
  1640		     typename _Comp = ranges::less, typename _Proj = identity>
  1641	      requires sortable<iterator_t<_Range>, _Comp, _Proj>
  1642	      constexpr borrowed_iterator_t<_Range>
  1643	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  1644	      {
  1645		return (*this)(ranges::begin(__r), ranges::end(__r),
  1646			       std::move(__comp), std::move(__proj));
  1647	      }
  1648	  };
  1649	
  1650	  inline constexpr __pop_heap_fn pop_heap{};
  1651	
  1652	  struct __make_heap_fn
  1653	  {
  1654	    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
  1655		     typename _Comp = ranges::less, typename _Proj = identity>
  1656	      requires sortable<_Iter, _Comp, _Proj>
  1657	      constexpr _Iter
  1658	      operator()(_Iter __first, _Sent __last,
  1659			 _Comp __comp = {}, _Proj __proj = {}) const
  1660	      {
  1661		auto __lasti = ranges::next(__first, __last);
  1662		std::make_heap(__first, __lasti,
  1663			       __detail::__make_comp_proj(__comp, __proj));
  1664		return __lasti;
  1665	      }
  1666	
  1667	    template<random_access_range _Range,
  1668		     typename _Comp = ranges::less, typename _Proj = identity>
  1669	      requires sortable<iterator_t<_Range>, _Comp, _Proj>
  1670	      constexpr borrowed_iterator_t<_Range>
  1671	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  1672	      {
  1673		return (*this)(ranges::begin(__r), ranges::end(__r),
  1674			       std::move(__comp), std::move(__proj));
  1675	      }
  1676	  };
  1677	
  1678	  inline constexpr __make_heap_fn make_heap{};
  1679	
  1680	  struct __sort_heap_fn
  1681	  {
  1682	    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
  1683		     typename _Comp = ranges::less, typename _Proj = identity>
  1684	      requires sortable<_Iter, _Comp, _Proj>
  1685	      constexpr _Iter
  1686	      operator()(_Iter __first, _Sent __last,
  1687			 _Comp __comp = {}, _Proj __proj = {}) const
  1688	      {
  1689		auto __lasti = ranges::next(__first, __last);
  1690		std::sort_heap(__first, __lasti,
  1691			       __detail::__make_comp_proj(__comp, __proj));
  1692		return __lasti;
  1693	      }
  1694	
  1695	    template<random_access_range _Range,
  1696		     typename _Comp = ranges::less, typename _Proj = identity>
  1697	      requires sortable<iterator_t<_Range>, _Comp, _Proj>
  1698	      constexpr borrowed_iterator_t<_Range>
  1699	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  1700	      {
  1701		return (*this)(ranges::begin(__r), ranges::end(__r),
  1702			       std::move(__comp), std::move(__proj));
  1703	      }
  1704	  };
  1705	
  1706	  inline constexpr __sort_heap_fn sort_heap{};
  1707	
  1708	  struct __is_heap_until_fn
  1709	  {
  1710	    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
  1711		     typename _Proj = identity,
  1712		     indirect_strict_weak_order<projected<_Iter, _Proj>>
  1713		       _Comp = ranges::less>
  1714	      constexpr _Iter
  1715	      operator()(_Iter __first, _Sent __last,
  1716			 _Comp __comp = {}, _Proj __proj = {}) const
  1717	      {
  1718		iter_difference_t<_Iter> __n = ranges::distance(__first, __last);
  1719		iter_difference_t<_Iter> __parent = 0, __child = 1;
  1720		for (; __child < __n; ++__child)
  1721		  if (std::__invoke(__comp,
  1722				    std::__invoke(__proj, *(__first + __parent)),
  1723				    std::__invoke(__proj, *(__first + __child))))
  1724		    return __first + __child;
  1725		  else if ((__child & 1) == 0)
  1726		    ++__parent;
  1727	
  1728		return __first + __n;
  1729	      }
  1730	
  1731	    template<random_access_range _Range,
  1732		     typename _Proj = identity,
  1733		     indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
  1734		       _Comp = ranges::less>
  1735	      constexpr borrowed_iterator_t<_Range>
  1736	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  1737	      {
  1738		return (*this)(ranges::begin(__r), ranges::end(__r),
  1739			       std::move(__comp), std::move(__proj));
  1740	      }
  1741	  };
  1742	
  1743	  inline constexpr __is_heap_until_fn is_heap_until{};
  1744	
  1745	  struct __is_heap_fn
  1746	  {
  1747	    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
  1748		     typename _Proj = identity,
  1749		     indirect_strict_weak_order<projected<_Iter, _Proj>>
  1750		       _Comp = ranges::less>
  1751	      constexpr bool
  1752	      operator()(_Iter __first, _Sent __last,
  1753			 _Comp __comp = {}, _Proj __proj = {}) const
  1754	      {
  1755		return (__last
  1756			== ranges::is_heap_until(__first, __last,
  1757						 std::move(__comp),
  1758						 std::move(__proj)));
  1759	      }
  1760	
  1761	    template<random_access_range _Range,
  1762		     typename _Proj = identity,
  1763		     indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
  1764		       _Comp = ranges::less>
  1765	      constexpr bool
  1766	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  1767	      {
  1768		return (*this)(ranges::begin(__r), ranges::end(__r),
  1769			       std::move(__comp), std::move(__proj));
  1770	      }
  1771	  };
  1772	
  1773	  inline constexpr __is_heap_fn is_heap{};
  1774	
  1775	  struct __sort_fn
  1776	  {
  1777	    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
  1778		     typename _Comp = ranges::less, typename _Proj = identity>
  1779	      requires sortable<_Iter, _Comp, _Proj>
  1780	      constexpr _Iter
  1781	      operator()(_Iter __first, _Sent __last,
  1782			 _Comp __comp = {}, _Proj __proj = {}) const
  1783	      {
  1784		auto __lasti = ranges::next(__first, __last);
  1785		_GLIBCXX_STD_A::sort(std::move(__first), __lasti,
  1786				     __detail::__make_comp_proj(__comp, __proj));
  1787		return __lasti;
  1788	      }
  1789	
  1790	    template<random_access_range _Range,
  1791		     typename _Comp = ranges::less, typename _Proj = identity>
  1792	      requires sortable<iterator_t<_Range>, _Comp, _Proj>
  1793	      constexpr borrowed_iterator_t<_Range>
  1794	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  1795	      {
  1796		return (*this)(ranges::begin(__r), ranges::end(__r),
  1797			       std::move(__comp), std::move(__proj));
  1798	      }
  1799	  };
  1800	
  1801	  inline constexpr __sort_fn sort{};
  1802	
  1803	  struct __stable_sort_fn
  1804	  {
  1805	    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
  1806		     typename _Comp = ranges::less, typename _Proj = identity>
  1807	      requires sortable<_Iter, _Comp, _Proj>
  1808	      _Iter
  1809	      operator()(_Iter __first, _Sent __last,
  1810			 _Comp __comp = {}, _Proj __proj = {}) const
  1811	      {
  1812		auto __lasti = ranges::next(__first, __last);
  1813		std::stable_sort(std::move(__first), __lasti,
  1814				 __detail::__make_comp_proj(__comp, __proj));
  1815		return __lasti;
  1816	      }
  1817	
  1818	    template<random_access_range _Range,
  1819		     typename _Comp = ranges::less, typename _Proj = identity>
  1820	      requires sortable<iterator_t<_Range>, _Comp, _Proj>
  1821	      borrowed_iterator_t<_Range>
  1822	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  1823	      {
  1824		return (*this)(ranges::begin(__r), ranges::end(__r),
  1825			       std::move(__comp), std::move(__proj));
  1826	      }
  1827	  };
  1828	
  1829	  inline constexpr __stable_sort_fn stable_sort{};
  1830	
  1831	  struct __partial_sort_fn
  1832	  {
  1833	    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
  1834		     typename _Comp = ranges::less, typename _Proj = identity>
  1835	      requires sortable<_Iter, _Comp, _Proj>
  1836	      constexpr _Iter
  1837	      operator()(_Iter __first, _Iter __middle, _Sent __last,
  1838			 _Comp __comp = {}, _Proj __proj = {}) const
  1839	      {
  1840		if (__first == __middle)
  1841		  return ranges::next(__first, __last);
  1842	
  1843		ranges::make_heap(__first, __middle, __comp, __proj);
  1844		auto __i = __middle;
  1845		for (; __i != __last; ++__i)
  1846		  if (std::__invoke(__comp,
  1847				    std::__invoke(__proj, *__i),
  1848				    std::__invoke(__proj, *__first)))
  1849		    {
  1850		      ranges::pop_heap(__first, __middle, __comp, __proj);
  1851		      ranges::iter_swap(__middle-1, __i);
  1852		      ranges::push_heap(__first, __middle, __comp, __proj);
  1853		    }
  1854		ranges::sort_heap(__first, __middle, __comp, __proj);
  1855	
  1856		return __i;
  1857	      }
  1858	
  1859	    template<random_access_range _Range,
  1860		     typename _Comp = ranges::less, typename _Proj = identity>
  1861	      requires sortable<iterator_t<_Range>, _Comp, _Proj>
  1862	      constexpr borrowed_iterator_t<_Range>
  1863	      operator()(_Range&& __r, iterator_t<_Range> __middle,
  1864			 _Comp __comp = {}, _Proj __proj = {}) const
  1865	      {
  1866		return (*this)(ranges::begin(__r), std::move(__middle),
  1867			       ranges::end(__r),
  1868			       std::move(__comp), std::move(__proj));
  1869	      }
  1870	  };
  1871	
  1872	  inline constexpr __partial_sort_fn partial_sort{};
  1873	
  1874	  template<typename _Iter, typename _Out>
  1875	    using partial_sort_copy_result = in_out_result<_Iter, _Out>;
  1876	
  1877	  struct __partial_sort_copy_fn
  1878	  {
  1879	    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
  1880		     random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
  1881		     typename _Comp = ranges::less,
  1882		     typename _Proj1 = identity, typename _Proj2 = identity>
  1883	      requires indirectly_copyable<_Iter1, _Iter2>
  1884		&& sortable<_Iter2, _Comp, _Proj2>
  1885		&& indirect_strict_weak_order<_Comp,
  1886					      projected<_Iter1, _Proj1>,
  1887					      projected<_Iter2, _Proj2>>
  1888	      constexpr partial_sort_copy_result<_Iter1, _Iter2>
  1889	      operator()(_Iter1 __first, _Sent1 __last,
  1890			 _Iter2 __result_first, _Sent2 __result_last,
  1891			 _Comp __comp = {},
  1892			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  1893	      {
  1894		if (__result_first == __result_last)
  1895		  {
  1896		    // TODO: Eliminating the variable __lasti triggers an ICE.
  1897		    auto __lasti = ranges::next(std::move(__first),
  1898						std::move(__last));
  1899		    return {std::move(__lasti), std::move(__result_first)};
  1900		  }
  1901	
  1902		auto __result_real_last = __result_first;
  1903		while (__first != __last && __result_real_last != __result_last)
  1904		  {
  1905		    *__result_real_last = *__first;
  1906		    ++__result_real_last;
  1907		    ++__first;
  1908		  }
  1909	
  1910		ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
  1911		for (; __first != __last; ++__first)
  1912		  if (std::__invoke(__comp,
  1913				    std::__invoke(__proj1, *__first),
  1914				    std::__invoke(__proj2, *__result_first)))
  1915		    {
  1916		      ranges::pop_heap(__result_first, __result_real_last,
  1917				       __comp, __proj2);
  1918		      *(__result_real_last-1) = *__first;
  1919		      ranges::push_heap(__result_first, __result_real_last,
  1920					__comp, __proj2);
  1921		    }
  1922		ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
  1923	
  1924		return {std::move(__first), std::move(__result_real_last)};
  1925	      }
  1926	
  1927	    template<input_range _Range1, random_access_range _Range2,
  1928		     typename _Comp = ranges::less,
  1929		     typename _Proj1 = identity, typename _Proj2 = identity>
  1930	      requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
  1931		&& sortable<iterator_t<_Range2>, _Comp, _Proj2>
  1932		&& indirect_strict_weak_order<_Comp,
  1933					      projected<iterator_t<_Range1>, _Proj1>,
  1934					      projected<iterator_t<_Range2>, _Proj2>>
  1935	      constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>,
  1936						 borrowed_iterator_t<_Range2>>
  1937	      operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
  1938			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  1939	      {
  1940		return (*this)(ranges::begin(__r), ranges::end(__r),
  1941			       ranges::begin(__out), ranges::end(__out),
  1942			       std::move(__comp),
  1943			       std::move(__proj1), std::move(__proj2));
  1944	      }
  1945	  };
  1946	
  1947	  inline constexpr __partial_sort_copy_fn partial_sort_copy{};
  1948	
  1949	  struct __is_sorted_until_fn
  1950	  {
  1951	    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
  1952		     typename _Proj = identity,
  1953		     indirect_strict_weak_order<projected<_Iter, _Proj>>
  1954		       _Comp = ranges::less>
  1955	      constexpr _Iter
  1956	      operator()(_Iter __first, _Sent __last,
  1957			 _Comp __comp = {}, _Proj __proj = {}) const
  1958	      {
  1959		if (__first == __last)
  1960		  return __first;
  1961	
  1962		auto __next = __first;
  1963		for (++__next; __next != __last; __first = __next, (void)++__next)
  1964		  if (std::__invoke(__comp,
  1965				    std::__invoke(__proj, *__next),
  1966				    std::__invoke(__proj, *__first)))
  1967		    return __next;
  1968		return __next;
  1969	      }
  1970	
  1971	    template<forward_range _Range, typename _Proj = identity,
  1972		     indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
  1973		       _Comp = ranges::less>
  1974	      constexpr borrowed_iterator_t<_Range>
  1975	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  1976	      {
  1977		return (*this)(ranges::begin(__r), ranges::end(__r),
  1978			       std::move(__comp), std::move(__proj));
  1979	      }
  1980	  };
  1981	
  1982	  inline constexpr __is_sorted_until_fn is_sorted_until{};
  1983	
  1984	  struct __is_sorted_fn
  1985	  {
  1986	    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
  1987		     typename _Proj = identity,
  1988		     indirect_strict_weak_order<projected<_Iter, _Proj>>
  1989		       _Comp = ranges::less>
  1990	      constexpr bool
  1991	      operator()(_Iter __first, _Sent __last,
  1992			 _Comp __comp = {}, _Proj __proj = {}) const
  1993	      {
  1994		if (__first == __last)
  1995		  return true;
  1996	
  1997		auto __next = __first;
  1998		for (++__next; __next != __last; __first = __next, (void)++__next)
  1999		  if (std::__invoke(__comp,
  2000				    std::__invoke(__proj, *__next),
  2001				    std::__invoke(__proj, *__first)))
  2002		    return false;
  2003		return true;
  2004	      }
  2005	
  2006	    template<forward_range _Range, typename _Proj = identity,
  2007		     indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
  2008		       _Comp = ranges::less>
  2009	      constexpr bool
  2010	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  2011	      {
  2012		return (*this)(ranges::begin(__r), ranges::end(__r),
  2013			       std::move(__comp), std::move(__proj));
  2014	      }
  2015	  };
  2016	
  2017	  inline constexpr __is_sorted_fn is_sorted{};
  2018	
  2019	  struct __nth_element_fn
  2020	  {
  2021	    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
  2022		     typename _Comp = ranges::less, typename _Proj = identity>
  2023	      requires sortable<_Iter, _Comp, _Proj>
  2024	      constexpr _Iter
  2025	      operator()(_Iter __first, _Iter __nth, _Sent __last,
  2026			 _Comp __comp = {}, _Proj __proj = {}) const
  2027	      {
  2028		auto __lasti = ranges::next(__first, __last);
  2029		_GLIBCXX_STD_A::nth_element(std::move(__first), std::move(__nth),
  2030					    __lasti,
  2031					    __detail::__make_comp_proj(__comp, __proj));
  2032		return __lasti;
  2033	      }
  2034	
  2035	    template<random_access_range _Range,
  2036		     typename _Comp = ranges::less, typename _Proj = identity>
  2037	      requires sortable<iterator_t<_Range>, _Comp, _Proj>
  2038	      constexpr borrowed_iterator_t<_Range>
  2039	      operator()(_Range&& __r, iterator_t<_Range> __nth,
  2040			 _Comp __comp = {}, _Proj __proj = {}) const
  2041	      {
  2042		return (*this)(ranges::begin(__r), std::move(__nth),
  2043			       ranges::end(__r), std::move(__comp), std::move(__proj));
  2044	      }
  2045	  };
  2046	
  2047	  inline constexpr __nth_element_fn nth_element{};
  2048	
  2049	  struct __lower_bound_fn
  2050	  {
  2051	    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
  2052		     typename _Tp, typename _Proj = identity,
  2053		     indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
  2054		       _Comp = ranges::less>
  2055	      constexpr _Iter
  2056	      operator()(_Iter __first, _Sent __last,
  2057			 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
  2058	      {
  2059		auto __len = ranges::distance(__first, __last);
  2060	
  2061		while (__len > 0)
  2062		  {
  2063		    auto __half = __len / 2;
  2064		    auto __middle = __first;
  2065		    ranges::advance(__middle, __half);
  2066		    if (std::__invoke(__comp, std::__invoke(__proj, *__middle), __value))
  2067		      {
  2068			__first = __middle;
  2069			++__first;
  2070			__len = __len - __half - 1;
  2071		      }
  2072		    else
  2073		      __len = __half;
  2074		  }
  2075		return __first;
  2076	      }
  2077	
  2078	    template<forward_range _Range, typename _Tp, typename _Proj = identity,
  2079		     indirect_strict_weak_order<const _Tp*,
  2080						projected<iterator_t<_Range>, _Proj>>
  2081		       _Comp = ranges::less>
  2082	      constexpr borrowed_iterator_t<_Range>
  2083	      operator()(_Range&& __r,
  2084			 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
  2085	      {
  2086		return (*this)(ranges::begin(__r), ranges::end(__r),
  2087			       __value, std::move(__comp), std::move(__proj));
  2088	      }
  2089	  };
  2090	
  2091	  inline constexpr __lower_bound_fn lower_bound{};
  2092	
  2093	  struct __upper_bound_fn
  2094	  {
  2095	    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
  2096		     typename _Tp, typename _Proj = identity,
  2097		     indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
  2098		       _Comp = ranges::less>
  2099	      constexpr _Iter
  2100	      operator()(_Iter __first, _Sent __last,
  2101			 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
  2102	      {
  2103		auto __len = ranges::distance(__first, __last);
  2104	
  2105		while (__len > 0)
  2106		  {
  2107		    auto __half = __len / 2;
  2108		    auto __middle = __first;
  2109		    ranges::advance(__middle, __half);
  2110		    if (std::__invoke(__comp, __value, std::__invoke(__proj, *__middle)))
  2111		      __len = __half;
  2112		    else
  2113		      {
  2114			__first = __middle;
  2115			++__first;
  2116			__len = __len - __half - 1;
  2117		      }
  2118		  }
  2119		return __first;
  2120	      }
  2121	
  2122	    template<forward_range _Range, typename _Tp, typename _Proj = identity,
  2123		     indirect_strict_weak_order<const _Tp*,
  2124						projected<iterator_t<_Range>, _Proj>>
  2125		       _Comp = ranges::less>
  2126	      constexpr borrowed_iterator_t<_Range>
  2127	      operator()(_Range&& __r,
  2128			 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
  2129	      {
  2130		return (*this)(ranges::begin(__r), ranges::end(__r),
  2131			       __value, std::move(__comp), std::move(__proj));
  2132	      }
  2133	  };
  2134	
  2135	  inline constexpr __upper_bound_fn upper_bound{};
  2136	
  2137	  struct __equal_range_fn
  2138	  {
  2139	    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
  2140		     typename _Tp, typename _Proj = identity,
  2141		     indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
  2142		       _Comp = ranges::less>
  2143	      constexpr subrange<_Iter>
  2144	      operator()(_Iter __first, _Sent __last,
  2145			 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
  2146	      {
  2147		auto __len = ranges::distance(__first, __last);
  2148	
  2149		while (__len > 0)
  2150		  {
  2151		    auto __half = __len / 2;
  2152		    auto __middle = __first;
  2153		    ranges::advance(__middle, __half);
  2154		    if (std::__invoke(__comp,
  2155				      std::__invoke(__proj, *__middle),
  2156				      __value))
  2157		      {
  2158			__first = __middle;
  2159			++__first;
  2160			__len = __len - __half - 1;
  2161		      }
  2162		    else if (std::__invoke(__comp,
  2163					   __value,
  2164					   std::__invoke(__proj, *__middle)))
  2165		      __len = __half;
  2166		    else
  2167		      {
  2168			auto __left
  2169			  = ranges::lower_bound(__first, __middle,
  2170						__value, __comp, __proj);
  2171			ranges::advance(__first, __len);
  2172			auto __right
  2173			  = ranges::upper_bound(++__middle, __first,
  2174						__value, __comp, __proj);
  2175			return {__left, __right};
  2176		      }
  2177		  }
  2178		return {__first, __first};
  2179	      }
  2180	
  2181	    template<forward_range _Range,
  2182		     typename _Tp, typename _Proj = identity,
  2183		     indirect_strict_weak_order<const _Tp*,
  2184						projected<iterator_t<_Range>, _Proj>>
  2185		       _Comp = ranges::less>
  2186	      constexpr borrowed_subrange_t<_Range>
  2187	      operator()(_Range&& __r, const _Tp& __value,
  2188			 _Comp __comp = {}, _Proj __proj = {}) const
  2189	      {
  2190		return (*this)(ranges::begin(__r), ranges::end(__r),
  2191			       __value, std::move(__comp), std::move(__proj));
  2192	      }
  2193	  };
  2194	
  2195	  inline constexpr __equal_range_fn equal_range{};
  2196	
  2197	  struct __binary_search_fn
  2198	  {
  2199	    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
  2200		     typename _Tp, typename _Proj = identity,
  2201		     indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
  2202		       _Comp = ranges::less>
  2203	      constexpr bool
  2204	      operator()(_Iter __first, _Sent __last,
  2205			 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
  2206	      {
  2207		auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
  2208		if (__i == __last)
  2209		  return false;
  2210		return !(bool)std::__invoke(__comp, __value,
  2211					    std::__invoke(__proj, *__i));
  2212	      }
  2213	
  2214	    template<forward_range _Range,
  2215		     typename _Tp, typename _Proj = identity,
  2216		     indirect_strict_weak_order<const _Tp*,
  2217						projected<iterator_t<_Range>, _Proj>>
  2218		       _Comp = ranges::less>
  2219	      constexpr bool
  2220	      operator()(_Range&& __r, const _Tp& __value, _Comp __comp = {},
  2221			 _Proj __proj = {}) const
  2222	      {
  2223		return (*this)(ranges::begin(__r), ranges::end(__r),
  2224			       __value, std::move(__comp), std::move(__proj));
  2225	      }
  2226	  };
  2227	
  2228	  inline constexpr __binary_search_fn binary_search{};
  2229	
  2230	  struct __is_partitioned_fn
  2231	  {
  2232	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
  2233		     typename _Proj = identity,
  2234		     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
  2235	      constexpr bool
  2236	      operator()(_Iter __first, _Sent __last,
  2237			 _Pred __pred, _Proj __proj = {}) const
  2238	      {
  2239		__first = ranges::find_if_not(std::move(__first), __last,
  2240					      __pred, __proj);
  2241		if (__first == __last)
  2242		  return true;
  2243		++__first;
  2244		return ranges::none_of(std::move(__first), std::move(__last),
  2245				       std::move(__pred), std::move(__proj));
  2246	      }
  2247	
  2248	    template<input_range _Range, typename _Proj = identity,
  2249		     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
  2250		       _Pred>
  2251	      constexpr bool
  2252	      operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
  2253	      {
  2254		return (*this)(ranges::begin(__r), ranges::end(__r),
  2255			       std::move(__pred), std::move(__proj));
  2256	      }
  2257	  };
  2258	
  2259	  inline constexpr __is_partitioned_fn is_partitioned{};
  2260	
  2261	  struct __partition_fn
  2262	  {
  2263	    template<permutable _Iter, sentinel_for<_Iter> _Sent,
  2264		     typename _Proj = identity,
  2265		     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
  2266	      constexpr subrange<_Iter>
  2267	      operator()(_Iter __first, _Sent __last,
  2268			 _Pred __pred, _Proj __proj = {}) const
  2269	      {
  2270		if constexpr (bidirectional_iterator<_Iter>)
  2271		  {
  2272		    auto __lasti = ranges::next(__first, __last);
  2273		    auto __tail = __lasti;
  2274		    for (;;)
  2275		      {
  2276			for (;;)
  2277			  if (__first == __tail)
  2278			    return {std::move(__first), std::move(__lasti)};
  2279			  else if (std::__invoke(__pred,
  2280						 std::__invoke(__proj, *__first)))
  2281			    ++__first;
  2282			  else
  2283			    break;
  2284			--__tail;
  2285			for (;;)
  2286			  if (__first == __tail)
  2287			    return {std::move(__first), std::move(__lasti)};
  2288			  else if (!(bool)std::__invoke(__pred,
  2289							std::__invoke(__proj, *__tail)))
  2290			    --__tail;
  2291			  else
  2292			    break;
  2293			ranges::iter_swap(__first, __tail);
  2294			++__first;
  2295		      }
  2296		  }
  2297		else
  2298		  {
  2299		    if (__first == __last)
  2300		      return {__first, __first};
  2301	
  2302		    while (std::__invoke(__pred, std::__invoke(__proj, *__first)))
  2303		      if (++__first == __last)
  2304			return {__first, __first};
  2305	
  2306		    auto __next = __first;
  2307		    while (++__next != __last)
  2308		      if (std::__invoke(__pred, std::__invoke(__proj, *__next)))
  2309			{
  2310			  ranges::iter_swap(__first, __next);
  2311			  ++__first;
  2312			}
  2313	
  2314		    return {std::move(__first), std::move(__next)};
  2315		  }
  2316	      }
  2317	
  2318	    template<forward_range _Range, typename _Proj = identity,
  2319		     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
  2320		       _Pred>
  2321	      requires permutable<iterator_t<_Range>>
  2322	      constexpr borrowed_subrange_t<_Range>
  2323	      operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
  2324	      {
  2325		return (*this)(ranges::begin(__r), ranges::end(__r),
  2326			       std::move(__pred), std::move(__proj));
  2327	      }
  2328	  };
  2329	
  2330	  inline constexpr __partition_fn partition{};
  2331	
  2332	#if _GLIBCXX_HOSTED
  2333	  struct __stable_partition_fn
  2334	  {
  2335	    template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
  2336		     typename _Proj = identity,
  2337		     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
  2338	      requires permutable<_Iter>
  2339	      subrange<_Iter>
  2340	      operator()(_Iter __first, _Sent __last,
  2341			 _Pred __pred, _Proj __proj = {}) const
  2342	      {
  2343		auto __lasti = ranges::next(__first, __last);
  2344		auto __middle
  2345		  = std::stable_partition(std::move(__first), __lasti,
  2346					  __detail::__make_pred_proj(__pred, __proj));
  2347		return {std::move(__middle), std::move(__lasti)};
  2348	      }
  2349	
  2350	    template<bidirectional_range _Range, typename _Proj = identity,
  2351		     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
  2352		       _Pred>
  2353	      requires permutable<iterator_t<_Range>>
  2354	      borrowed_subrange_t<_Range>
  2355	      operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
  2356	      {
  2357		return (*this)(ranges::begin(__r), ranges::end(__r),
  2358			       std::move(__pred), std::move(__proj));
  2359	      }
  2360	  };
  2361	
  2362	  inline constexpr __stable_partition_fn stable_partition{};
  2363	#endif
  2364	
  2365	  template<typename _Iter, typename _Out1, typename _Out2>
  2366	    struct in_out_out_result
  2367	    {
  2368	      [[no_unique_address]] _Iter  in;
  2369	      [[no_unique_address]] _Out1 out1;
  2370	      [[no_unique_address]] _Out2 out2;
  2371	
  2372	      template<typename _IIter, typename _OOut1, typename _OOut2>
  2373		requires convertible_to<const _Iter&, _IIter>
  2374		  && convertible_to<const _Out1&, _OOut1>
  2375		  && convertible_to<const _Out2&, _OOut2>
  2376		constexpr
  2377		operator in_out_out_result<_IIter, _OOut1, _OOut2>() const &
  2378		{ return {in, out1, out2}; }
  2379	
  2380	      template<typename _IIter, typename _OOut1, typename _OOut2>
  2381		requires convertible_to<_Iter, _IIter>
  2382		  && convertible_to<_Out1, _OOut1>
  2383		  && convertible_to<_Out2, _OOut2>
  2384		constexpr
  2385		operator in_out_out_result<_IIter, _OOut1, _OOut2>() &&
  2386		{ return {std::move(in), std::move(out1), std::move(out2)}; }
  2387	    };
  2388	
  2389	  template<typename _Iter, typename _Out1, typename _Out2>
  2390	    using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>;
  2391	
  2392	  struct __partition_copy_fn
  2393	  {
  2394	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
  2395		     weakly_incrementable _Out1, weakly_incrementable _Out2,
  2396		     typename _Proj = identity,
  2397		     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
  2398	      requires indirectly_copyable<_Iter, _Out1>
  2399		&& indirectly_copyable<_Iter, _Out2>
  2400	      constexpr partition_copy_result<_Iter, _Out1, _Out2>
  2401	      operator()(_Iter __first, _Sent __last,
  2402			 _Out1 __out_true, _Out2 __out_false,
  2403			 _Pred __pred, _Proj __proj = {}) const
  2404	      {
  2405		for (; __first != __last; ++__first)
  2406		  if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
  2407		    {
  2408		      *__out_true = *__first;
  2409		      ++__out_true;
  2410		    }
  2411		  else
  2412		    {
  2413		      *__out_false = *__first;
  2414		      ++__out_false;
  2415		    }
  2416	
  2417		return {std::move(__first),
  2418			std::move(__out_true), std::move(__out_false)};
  2419	      }
  2420	
  2421	    template<input_range _Range, weakly_incrementable _Out1,
  2422		     weakly_incrementable _Out2,
  2423		     typename _Proj = identity,
  2424		     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
  2425		       _Pred>
  2426	      requires indirectly_copyable<iterator_t<_Range>, _Out1>
  2427		&& indirectly_copyable<iterator_t<_Range>, _Out2>
  2428	      constexpr partition_copy_result<borrowed_iterator_t<_Range>, _Out1, _Out2>
  2429	      operator()(_Range&& __r, _Out1 __out_true, _Out2 __out_false,
  2430			 _Pred __pred, _Proj __proj = {}) const
  2431	      {
  2432		return (*this)(ranges::begin(__r), ranges::end(__r),
  2433			       std::move(__out_true), std::move(__out_false),
  2434			       std::move(__pred), std::move(__proj));
  2435	      }
  2436	  };
  2437	
  2438	  inline constexpr __partition_copy_fn partition_copy{};
  2439	
  2440	  struct __partition_point_fn
  2441	  {
  2442	    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
  2443		     typename _Proj = identity,
  2444		     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
  2445	      constexpr _Iter
  2446	      operator()(_Iter __first, _Sent __last,
  2447			 _Pred __pred, _Proj __proj = {}) const
  2448	      {
  2449		auto __len = ranges::distance(__first, __last);
  2450	
  2451		while (__len > 0)
  2452		  {
  2453		    auto __half = __len / 2;
  2454		    auto __middle = __first;
  2455		    ranges::advance(__middle, __half);
  2456		    if (std::__invoke(__pred, std::__invoke(__proj, *__middle)))
  2457		      {
  2458			__first = __middle;
  2459			++__first;
  2460			__len = __len - __half - 1;
  2461		      }
  2462		    else
  2463		      __len = __half;
  2464		  }
  2465		return __first;
  2466	      }
  2467	
  2468	    template<forward_range _Range, typename _Proj = identity,
  2469		     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
  2470		       _Pred>
  2471	      constexpr borrowed_iterator_t<_Range>
  2472	      operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
  2473	      {
  2474		return (*this)(ranges::begin(__r), ranges::end(__r),
  2475			       std::move(__pred), std::move(__proj));
  2476	      }
  2477	  };
  2478	
  2479	  inline constexpr __partition_point_fn partition_point{};
  2480	
  2481	  template<typename _Iter1, typename _Iter2, typename _Out>
  2482	    using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>;
  2483	
  2484	  struct __merge_fn
  2485	  {
  2486	    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
  2487		     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
  2488		     weakly_incrementable _Out, typename _Comp = ranges::less,
  2489		     typename _Proj1 = identity, typename _Proj2 = identity>
  2490	      requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
  2491	      constexpr merge_result<_Iter1, _Iter2, _Out>
  2492	      operator()(_Iter1 __first1, _Sent1 __last1,
  2493			 _Iter2 __first2, _Sent2 __last2, _Out __result,
  2494			 _Comp __comp = {},
  2495			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  2496	      {
  2497		while (__first1 != __last1 && __first2 != __last2)
  2498		  {
  2499		    if (std::__invoke(__comp,
  2500				      std::__invoke(__proj2, *__first2),
  2501				      std::__invoke(__proj1, *__first1)))
  2502		      {
  2503			*__result = *__first2;
  2504			++__first2;
  2505		      }
  2506		    else
  2507		      {
  2508			*__result = *__first1;
  2509			++__first1;
  2510		      }
  2511		    ++__result;
  2512		  }
  2513		auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
  2514					    std::move(__result));
  2515		auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
  2516					    std::move(__copy1.out));
  2517		return { std::move(__copy1.in), std::move(__copy2.in),
  2518			 std::move(__copy2.out) };
  2519	      }
  2520	
  2521	    template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
  2522		     typename _Comp = ranges::less,
  2523		     typename _Proj1 = identity, typename _Proj2 = identity>
  2524	      requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
  2525				 _Comp, _Proj1, _Proj2>
  2526	      constexpr merge_result<borrowed_iterator_t<_Range1>,
  2527				     borrowed_iterator_t<_Range2>,
  2528				     _Out>
  2529	      operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
  2530			 _Comp __comp = {},
  2531			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  2532	      {
  2533		return (*this)(ranges::begin(__r1), ranges::end(__r1),
  2534			       ranges::begin(__r2), ranges::end(__r2),
  2535			       std::move(__result), std::move(__comp),
  2536			       std::move(__proj1), std::move(__proj2));
  2537	      }
  2538	  };
  2539	
  2540	  inline constexpr __merge_fn merge{};
  2541	
  2542	  struct __inplace_merge_fn
  2543	  {
  2544	    template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
  2545		     typename _Comp = ranges::less,
  2546		     typename _Proj = identity>
  2547	      requires sortable<_Iter, _Comp, _Proj>
  2548	      _Iter
  2549	      operator()(_Iter __first, _Iter __middle, _Sent __last,
  2550			 _Comp __comp = {}, _Proj __proj = {}) const
  2551	      {
  2552		auto __lasti = ranges::next(__first, __last);
  2553		std::inplace_merge(std::move(__first), std::move(__middle), __lasti,
  2554				   __detail::__make_comp_proj(__comp, __proj));
  2555		return __lasti;
  2556	      }
  2557	
  2558	    template<bidirectional_range _Range,
  2559		     typename _Comp = ranges::less, typename _Proj = identity>
  2560	      requires sortable<iterator_t<_Range>, _Comp, _Proj>
  2561	      borrowed_iterator_t<_Range>
  2562	      operator()(_Range&& __r, iterator_t<_Range> __middle,
  2563			 _Comp __comp = {}, _Proj __proj = {}) const
  2564	      {
  2565		return (*this)(ranges::begin(__r), std::move(__middle),
  2566			       ranges::end(__r),
  2567			       std::move(__comp), std::move(__proj));
  2568	      }
  2569	  };
  2570	
  2571	  inline constexpr __inplace_merge_fn inplace_merge{};
  2572	
  2573	  struct __includes_fn
  2574	  {
  2575	    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
  2576		     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
  2577		     typename _Proj1 = identity, typename _Proj2 = identity,
  2578		     indirect_strict_weak_order<projected<_Iter1, _Proj1>,
  2579						projected<_Iter2, _Proj2>>
  2580		       _Comp = ranges::less>
  2581	      constexpr bool
  2582	      operator()(_Iter1 __first1, _Sent1 __last1,
  2583			 _Iter2 __first2, _Sent2 __last2,
  2584			 _Comp __comp = {},
  2585			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  2586	      {
  2587		while (__first1 != __last1 && __first2 != __last2)
  2588		  if (std::__invoke(__comp,
  2589				    std::__invoke(__proj2, *__first2),
  2590				    std::__invoke(__proj1, *__first1)))
  2591		    return false;
  2592		  else if (std::__invoke(__comp,
  2593					 std::__invoke(__proj1, *__first1),
  2594					 std::__invoke(__proj2, *__first2)))
  2595		    ++__first1;
  2596		  else
  2597		    {
  2598		      ++__first1;
  2599		      ++__first2;
  2600		    }
  2601	
  2602		return __first2 == __last2;
  2603	      }
  2604	
  2605	    template<input_range _Range1, input_range _Range2,
  2606		     typename _Proj1 = identity, typename _Proj2 = identity,
  2607		     indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
  2608						projected<iterator_t<_Range2>, _Proj2>>
  2609		       _Comp = ranges::less>
  2610	      constexpr bool
  2611	      operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
  2612			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  2613	      {
  2614		return (*this)(ranges::begin(__r1), ranges::end(__r1),
  2615			       ranges::begin(__r2), ranges::end(__r2),
  2616			       std::move(__comp),
  2617			       std::move(__proj1), std::move(__proj2));
  2618	      }
  2619	  };
  2620	
  2621	  inline constexpr __includes_fn includes{};
  2622	
  2623	  template<typename _Iter1, typename _Iter2, typename _Out>
  2624	    using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>;
  2625	
  2626	  struct __set_union_fn
  2627	  {
  2628	    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
  2629		     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
  2630		     weakly_incrementable _Out, typename _Comp = ranges::less,
  2631		     typename _Proj1 = identity, typename _Proj2 = identity>
  2632	      requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
  2633	      constexpr set_union_result<_Iter1, _Iter2, _Out>
  2634	      operator()(_Iter1 __first1, _Sent1 __last1,
  2635			 _Iter2 __first2, _Sent2 __last2,
  2636			 _Out __result, _Comp __comp = {},
  2637			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  2638	      {
  2639		while (__first1 != __last1 && __first2 != __last2)
  2640		  {
  2641		    if (std::__invoke(__comp,
  2642				      std::__invoke(__proj1, *__first1),
  2643				      std::__invoke(__proj2, *__first2)))
  2644		      {
  2645			*__result = *__first1;
  2646			++__first1;
  2647		      }
  2648		    else if (std::__invoke(__comp,
  2649					   std::__invoke(__proj2, *__first2),
  2650					   std::__invoke(__proj1, *__first1)))
  2651		      {
  2652			*__result = *__first2;
  2653			++__first2;
  2654		      }
  2655		    else
  2656		      {
  2657			*__result = *__first1;
  2658			++__first1;
  2659			++__first2;
  2660		      }
  2661		    ++__result;
  2662		  }
  2663		auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
  2664					    std::move(__result));
  2665		auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
  2666					    std::move(__copy1.out));
  2667		return {std::move(__copy1.in), std::move(__copy2.in),
  2668			std::move(__copy2.out)};
  2669	      }
  2670	
  2671	    template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
  2672		     typename _Comp = ranges::less,
  2673		     typename _Proj1 = identity, typename _Proj2 = identity>
  2674	      requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
  2675				 _Comp, _Proj1, _Proj2>
  2676	      constexpr set_union_result<borrowed_iterator_t<_Range1>,
  2677					 borrowed_iterator_t<_Range2>, _Out>
  2678	      operator()(_Range1&& __r1, _Range2&& __r2,
  2679			 _Out __result, _Comp __comp = {},
  2680			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  2681	      {
  2682		return (*this)(ranges::begin(__r1), ranges::end(__r1),
  2683			       ranges::begin(__r2), ranges::end(__r2),
  2684			       std::move(__result), std::move(__comp),
  2685			       std::move(__proj1), std::move(__proj2));
  2686	      }
  2687	  };
  2688	
  2689	  inline constexpr __set_union_fn set_union{};
  2690	
  2691	  template<typename _Iter1, typename _Iter2, typename _Out>
  2692	    using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>;
  2693	
  2694	  struct __set_intersection_fn
  2695	  {
  2696	    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
  2697		     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
  2698		     weakly_incrementable _Out, typename _Comp = ranges::less,
  2699		     typename _Proj1 = identity, typename _Proj2 = identity>
  2700	      requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
  2701	      constexpr set_intersection_result<_Iter1, _Iter2, _Out>
  2702	      operator()(_Iter1 __first1, _Sent1 __last1,
  2703			 _Iter2 __first2, _Sent2 __last2, _Out __result,
  2704			 _Comp __comp = {},
  2705			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  2706	      {
  2707		while (__first1 != __last1 && __first2 != __last2)
  2708		  if (std::__invoke(__comp,
  2709				    std::__invoke(__proj1, *__first1),
  2710				    std::__invoke(__proj2, *__first2)))
  2711		    ++__first1;
  2712		  else if (std::__invoke(__comp,
  2713					 std::__invoke(__proj2, *__first2),
  2714					 std::__invoke(__proj1, *__first1)))
  2715		    ++__first2;
  2716		  else
  2717		    {
  2718		      *__result = *__first1;
  2719		      ++__first1;
  2720		      ++__first2;
  2721		      ++__result;
  2722		    }
  2723		// TODO: Eliminating these variables triggers an ICE.
  2724		auto __last1i = ranges::next(std::move(__first1), std::move(__last1));
  2725		auto __last2i = ranges::next(std::move(__first2), std::move(__last2));
  2726		return {std::move(__last1i), std::move(__last2i), std::move(__result)};
  2727	      }
  2728	
  2729	    template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
  2730		     typename _Comp = ranges::less,
  2731		     typename _Proj1 = identity, typename _Proj2 = identity>
  2732	      requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
  2733				 _Comp, _Proj1, _Proj2>
  2734	      constexpr set_intersection_result<borrowed_iterator_t<_Range1>,
  2735						borrowed_iterator_t<_Range2>, _Out>
  2736	      operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
  2737			 _Comp __comp = {},
  2738			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  2739	      {
  2740		return (*this)(ranges::begin(__r1), ranges::end(__r1),
  2741			       ranges::begin(__r2), ranges::end(__r2),
  2742			       std::move(__result), std::move(__comp),
  2743			       std::move(__proj1), std::move(__proj2));
  2744	      }
  2745	  };
  2746	
  2747	  inline constexpr __set_intersection_fn set_intersection{};
  2748	
  2749	  template<typename _Iter, typename _Out>
  2750	    using set_difference_result = in_out_result<_Iter, _Out>;
  2751	
  2752	  struct __set_difference_fn
  2753	  {
  2754	    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
  2755		     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
  2756		     weakly_incrementable _Out, typename _Comp = ranges::less,
  2757		     typename _Proj1 = identity, typename _Proj2 = identity>
  2758	      requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
  2759	      constexpr set_difference_result<_Iter1, _Out>
  2760	      operator()(_Iter1 __first1, _Sent1 __last1,
  2761			 _Iter2 __first2, _Sent2 __last2, _Out __result,
  2762			 _Comp __comp = {},
  2763			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  2764	      {
  2765		while (__first1 != __last1 && __first2 != __last2)
  2766		  if (std::__invoke(__comp,
  2767				    std::__invoke(__proj1, *__first1),
  2768				    std::__invoke(__proj2, *__first2)))
  2769		    {
  2770		      *__result = *__first1;
  2771		      ++__first1;
  2772		      ++__result;
  2773		    }
  2774		  else if (std::__invoke(__comp,
  2775					 std::__invoke(__proj2, *__first2),
  2776					 std::__invoke(__proj1, *__first1)))
  2777		    ++__first2;
  2778		  else
  2779		    {
  2780		      ++__first1;
  2781		      ++__first2;
  2782		    }
  2783		return ranges::copy(std::move(__first1), std::move(__last1),
  2784				    std::move(__result));
  2785	      }
  2786	
  2787	    template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
  2788		     typename _Comp = ranges::less,
  2789		     typename _Proj1 = identity, typename _Proj2 = identity>
  2790	      requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
  2791				 _Comp, _Proj1, _Proj2>
  2792	      constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out>
  2793	      operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
  2794			 _Comp __comp = {},
  2795			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  2796	      {
  2797		return (*this)(ranges::begin(__r1), ranges::end(__r1),
  2798			       ranges::begin(__r2), ranges::end(__r2),
  2799			       std::move(__result), std::move(__comp),
  2800			       std::move(__proj1), std::move(__proj2));
  2801	      }
  2802	  };
  2803	
  2804	  inline constexpr __set_difference_fn set_difference{};
  2805	
  2806	  template<typename _Iter1, typename _Iter2, typename _Out>
  2807	    using set_symmetric_difference_result
  2808	      = in_in_out_result<_Iter1, _Iter2, _Out>;
  2809	
  2810	  struct __set_symmetric_difference_fn
  2811	  {
  2812	    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
  2813		     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
  2814		     weakly_incrementable _Out, typename _Comp = ranges::less,
  2815		     typename _Proj1 = identity, typename _Proj2 = identity>
  2816	      requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
  2817	      constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out>
  2818	      operator()(_Iter1 __first1, _Sent1 __last1,
  2819			 _Iter2 __first2, _Sent2 __last2,
  2820			 _Out __result, _Comp __comp = {},
  2821			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  2822	      {
  2823		while (__first1 != __last1 && __first2 != __last2)
  2824		  if (std::__invoke(__comp,
  2825				    std::__invoke(__proj1, *__first1),
  2826				    std::__invoke(__proj2, *__first2)))
  2827		    {
  2828		      *__result = *__first1;
  2829		      ++__first1;
  2830		      ++__result;
  2831		    }
  2832		  else if (std::__invoke(__comp,
  2833					 std::__invoke(__proj2, *__first2),
  2834					 std::__invoke(__proj1, *__first1)))
  2835		    {
  2836		      *__result = *__first2;
  2837		      ++__first2;
  2838		      ++__result;
  2839		    }
  2840		  else
  2841		    {
  2842		      ++__first1;
  2843		      ++__first2;
  2844		    }
  2845		auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
  2846					    std::move(__result));
  2847		auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
  2848					    std::move(__copy1.out));
  2849		return {std::move(__copy1.in), std::move(__copy2.in),
  2850			std::move(__copy2.out)};
  2851	      }
  2852	
  2853	    template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
  2854		     typename _Comp = ranges::less,
  2855		     typename _Proj1 = identity, typename _Proj2 = identity>
  2856	      requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
  2857				 _Comp, _Proj1, _Proj2>
  2858	      constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>,
  2859							borrowed_iterator_t<_Range2>,
  2860							_Out>
  2861	      operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
  2862			 _Comp __comp = {},
  2863			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  2864	      {
  2865		return (*this)(ranges::begin(__r1), ranges::end(__r1),
  2866			       ranges::begin(__r2), ranges::end(__r2),
  2867			       std::move(__result), std::move(__comp),
  2868			       std::move(__proj1), std::move(__proj2));
  2869	      }
  2870	  };
  2871	
  2872	  inline constexpr __set_symmetric_difference_fn set_symmetric_difference{};
  2873	
  2874	  // min is defined in <bits/ranges_util.h>.
  2875	
  2876	  struct __max_fn
  2877	  {
  2878	    template<typename _Tp, typename _Proj = identity,
  2879		     indirect_strict_weak_order<projected<const _Tp*, _Proj>>
  2880		       _Comp = ranges::less>
  2881	      constexpr const _Tp&
  2882	      operator()(const _Tp& __a, const _Tp& __b,
  2883			 _Comp __comp = {}, _Proj __proj = {}) const
  2884	      {
  2885		if (std::__invoke(__comp,
  2886				  std::__invoke(__proj, __a),
  2887				  std::__invoke(__proj, __b)))
  2888		  return __b;
  2889		else
  2890		  return __a;
  2891	      }
  2892	
  2893	    template<input_range _Range, typename _Proj = identity,
  2894		     indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
  2895		       _Comp = ranges::less>
  2896	      requires indirectly_copyable_storable<iterator_t<_Range>,
  2897						    range_value_t<_Range>*>
  2898	      constexpr range_value_t<_Range>
  2899	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  2900	      {
  2901		auto __first = ranges::begin(__r);
  2902		auto __last = ranges::end(__r);
  2903		__glibcxx_assert(__first != __last);
  2904		auto __result = *__first;
  2905		while (++__first != __last)
  2906		  {
  2907		    auto __tmp = *__first;
  2908		    if (std::__invoke(__comp,
  2909				      std::__invoke(__proj, __result),
  2910				      std::__invoke(__proj, __tmp)))
  2911		      __result = std::move(__tmp);
  2912		  }
  2913		return __result;
  2914	      }
  2915	
  2916	    template<copyable _Tp, typename _Proj = identity,
  2917		     indirect_strict_weak_order<projected<const _Tp*, _Proj>>
  2918		       _Comp = ranges::less>
  2919	      constexpr _Tp
  2920	      operator()(initializer_list<_Tp> __r,
  2921			 _Comp __comp = {}, _Proj __proj = {}) const
  2922	      {
  2923		return (*this)(ranges::subrange(__r),
  2924			       std::move(__comp), std::move(__proj));
  2925	      }
  2926	  };
  2927	
  2928	  inline constexpr __max_fn max{};
  2929	
  2930	  struct __clamp_fn
  2931	  {
  2932	    template<typename _Tp, typename _Proj = identity,
  2933		     indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp
  2934		       = ranges::less>
  2935	      constexpr const _Tp&
  2936	      operator()(const _Tp& __val, const _Tp& __lo, const _Tp& __hi,
  2937			 _Comp __comp = {}, _Proj __proj = {}) const
  2938	      {
  2939		__glibcxx_assert(!(std::__invoke(__comp,
  2940						 std::__invoke(__proj, __hi),
  2941						 std::__invoke(__proj, __lo))));
  2942		auto&& __proj_val = std::__invoke(__proj, __val);
  2943		if (std::__invoke(__comp, __proj_val, std::__invoke(__proj, __lo)))
  2944		  return __lo;
  2945		else if (std::__invoke(__comp, std::__invoke(__proj, __hi), __proj_val))
  2946		  return __hi;
  2947		else
  2948		  return __val;
  2949	      }
  2950	  };
  2951	
  2952	  inline constexpr __clamp_fn clamp{};
  2953	
  2954	  template<typename _Tp>
  2955	    struct min_max_result
  2956	    {
  2957	      [[no_unique_address]] _Tp min;
  2958	      [[no_unique_address]] _Tp max;
  2959	
  2960	      template<typename _Tp2>
  2961		requires convertible_to<const _Tp&, _Tp2>
  2962		constexpr
  2963		operator min_max_result<_Tp2>() const &
  2964		{ return {min, max}; }
  2965	
  2966	      template<typename _Tp2>
  2967		requires convertible_to<_Tp, _Tp2>
  2968		constexpr
  2969		operator min_max_result<_Tp2>() &&
  2970		{ return {std::move(min), std::move(max)}; }
  2971	    };
  2972	
  2973	  template<typename _Tp>
  2974	    using minmax_result = min_max_result<_Tp>;
  2975	
  2976	  struct __minmax_fn
  2977	  {
  2978	    template<typename _Tp, typename _Proj = identity,
  2979		     indirect_strict_weak_order<projected<const _Tp*, _Proj>>
  2980		       _Comp = ranges::less>
  2981	      constexpr minmax_result<const _Tp&>
  2982	      operator()(const _Tp& __a, const _Tp& __b,
  2983			 _Comp __comp = {}, _Proj __proj = {}) const
  2984	      {
  2985		if (std::__invoke(__comp,
  2986				  std::__invoke(__proj, __b),
  2987				  std::__invoke(__proj, __a)))
  2988		  return {__b, __a};
  2989		else
  2990		  return {__a, __b};
  2991	      }
  2992	
  2993	    template<input_range _Range, typename _Proj = identity,
  2994		     indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
  2995		       _Comp = ranges::less>
  2996	      requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*>
  2997	      constexpr minmax_result<range_value_t<_Range>>
  2998	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  2999	      {
  3000		auto __first = ranges::begin(__r);
  3001		auto __last = ranges::end(__r);
  3002		__glibcxx_assert(__first != __last);
  3003		auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
  3004		minmax_result<range_value_t<_Range>> __result = {*__first, __result.min};
  3005		if (++__first == __last)
  3006		  return __result;
  3007		else
  3008		  {
  3009		    // At this point __result.min == __result.max, so a single
  3010		    // comparison with the next element suffices.
  3011		    auto&& __val = *__first;
  3012		    if (__comp_proj(__val, __result.min))
  3013		      __result.min = std::forward<decltype(__val)>(__val);
  3014		    else
  3015		      __result.max = std::forward<decltype(__val)>(__val);
  3016		  }
  3017		while (++__first != __last)
  3018		  {
  3019		    // Now process two elements at a time so that we perform at most
  3020		    // 1 + 3*(N-2)/2 comparisons in total (each of the (N-2)/2
  3021		    // iterations of this loop performs three comparisons).
  3022		    range_value_t<_Range> __val1 = *__first;
  3023		    if (++__first == __last)
  3024		      {
  3025			// N is odd; in this final iteration, we perform at most two
  3026			// comparisons, for a total of 1 + 3*(N-3)/2 + 2 comparisons,
  3027			// which is not more than 3*N/2, as required.
  3028			if (__comp_proj(__val1, __result.min))
  3029			  __result.min = std::move(__val1);
  3030			else if (!__comp_proj(__val1, __result.max))
  3031			  __result.max = std::move(__val1);
  3032			break;
  3033		      }
  3034		    auto&& __val2 = *__first;
  3035		    if (!__comp_proj(__val2, __val1))
  3036		      {
  3037			if (__comp_proj(__val1, __result.min))
  3038			  __result.min = std::move(__val1);
  3039			if (!__comp_proj(__val2, __result.max))
  3040			  __result.max = std::forward<decltype(__val2)>(__val2);
  3041		      }
  3042		    else
  3043		      {
  3044			if (__comp_proj(__val2, __result.min))
  3045			  __result.min = std::forward<decltype(__val2)>(__val2);
  3046			if (!__comp_proj(__val1, __result.max))
  3047			  __result.max = std::move(__val1);
  3048		      }
  3049		  }
  3050		return __result;
  3051	      }
  3052	
  3053	    template<copyable _Tp, typename _Proj = identity,
  3054		     indirect_strict_weak_order<projected<const _Tp*, _Proj>>
  3055		       _Comp = ranges::less>
  3056	      constexpr minmax_result<_Tp>
  3057	      operator()(initializer_list<_Tp> __r,
  3058			 _Comp __comp = {}, _Proj __proj = {}) const
  3059	      {
  3060		return (*this)(ranges::subrange(__r),
  3061			       std::move(__comp), std::move(__proj));
  3062	      }
  3063	  };
  3064	
  3065	  inline constexpr __minmax_fn minmax{};
  3066	
  3067	  struct __min_element_fn
  3068	  {
  3069	    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
  3070		     typename _Proj = identity,
  3071		     indirect_strict_weak_order<projected<_Iter, _Proj>>
  3072		       _Comp = ranges::less>
  3073	      constexpr _Iter
  3074	      operator()(_Iter __first, _Sent __last,
  3075			 _Comp __comp = {}, _Proj __proj = {}) const
  3076	      {
  3077		if (__first == __last)
  3078		  return __first;
  3079	
  3080		auto __i = __first;
  3081		while (++__i != __last)
  3082		  {
  3083		    if (std::__invoke(__comp,
  3084				      std::__invoke(__proj, *__i),
  3085				      std::__invoke(__proj, *__first)))
  3086		      __first = __i;
  3087		  }
  3088		return __first;
  3089	      }
  3090	
  3091	    template<forward_range _Range, typename _Proj = identity,
  3092		     indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
  3093		       _Comp = ranges::less>
  3094	      constexpr borrowed_iterator_t<_Range>
  3095	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  3096	      {
  3097		return (*this)(ranges::begin(__r), ranges::end(__r),
  3098			       std::move(__comp), std::move(__proj));
  3099	      }
  3100	  };
  3101	
  3102	  inline constexpr __min_element_fn min_element{};
  3103	
  3104	  struct __max_element_fn
  3105	  {
  3106	    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
  3107		     typename _Proj = identity,
  3108		     indirect_strict_weak_order<projected<_Iter, _Proj>>
  3109		       _Comp = ranges::less>
  3110	      constexpr _Iter
  3111	      operator()(_Iter __first, _Sent __last,
  3112			 _Comp __comp = {}, _Proj __proj = {}) const
  3113	      {
  3114		if (__first == __last)
  3115		  return __first;
  3116	
  3117		auto __i = __first;
  3118		while (++__i != __last)
  3119		  {
  3120		    if (std::__invoke(__comp,
  3121				      std::__invoke(__proj, *__first),
  3122				      std::__invoke(__proj, *__i)))
  3123		      __first = __i;
  3124		  }
  3125		return __first;
  3126	      }
  3127	
  3128	    template<forward_range _Range, typename _Proj = identity,
  3129		     indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
  3130		       _Comp = ranges::less>
  3131	      constexpr borrowed_iterator_t<_Range>
  3132	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  3133	      {
  3134		return (*this)(ranges::begin(__r), ranges::end(__r),
  3135			       std::move(__comp), std::move(__proj));
  3136	      }
  3137	  };
  3138	
  3139	  inline constexpr __max_element_fn max_element{};
  3140	
  3141	  template<typename _Iter>
  3142	    using minmax_element_result = min_max_result<_Iter>;
  3143	
  3144	  struct __minmax_element_fn
  3145	  {
  3146	    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
  3147		     typename _Proj = identity,
  3148		     indirect_strict_weak_order<projected<_Iter, _Proj>>
  3149		       _Comp = ranges::less>
  3150	      constexpr minmax_element_result<_Iter>
  3151	      operator()(_Iter __first, _Sent __last,
  3152			 _Comp __comp = {}, _Proj __proj = {}) const
  3153	      {
  3154		auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
  3155		minmax_element_result<_Iter> __result = {__first, __first};
  3156		if (__first == __last || ++__first == __last)
  3157		  return __result;
  3158		else
  3159		  {
  3160		    // At this point __result.min == __result.max, so a single
  3161		    // comparison with the next element suffices.
  3162		    if (__comp_proj(*__first, *__result.min))
  3163		      __result.min = __first;
  3164		    else
  3165		      __result.max = __first;
  3166		  }
  3167		while (++__first != __last)
  3168		  {
  3169		    // Now process two elements at a time so that we perform at most
  3170		    // 1 + 3*(N-2)/2 comparisons in total (each of the (N-2)/2
  3171		    // iterations of this loop performs three comparisons).
  3172		    auto __prev = __first;
  3173		    if (++__first == __last)
  3174		      {
  3175			// N is odd; in this final iteration, we perform at most two
  3176			// comparisons, for a total of 1 + 3*(N-3)/2 + 2 comparisons,
  3177			// which is not more than 3*N/2, as required.
  3178			if (__comp_proj(*__prev, *__result.min))
  3179			  __result.min = __prev;
  3180			else if (!__comp_proj(*__prev, *__result.max))
  3181			  __result.max = __prev;
  3182			break;
  3183		      }
  3184		    if (!__comp_proj(*__first, *__prev))
  3185		      {
  3186			if (__comp_proj(*__prev, *__result.min))
  3187			  __result.min = __prev;
  3188			if (!__comp_proj(*__first, *__result.max))
  3189			  __result.max = __first;
  3190		      }
  3191		    else
  3192		      {
  3193			if (__comp_proj(*__first, *__result.min))
  3194			  __result.min = __first;
  3195			if (!__comp_proj(*__prev, *__result.max))
  3196			  __result.max = __prev;
  3197		      }
  3198		  }
  3199		return __result;
  3200	      }
  3201	
  3202	    template<forward_range _Range, typename _Proj = identity,
  3203		     indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
  3204		       _Comp = ranges::less>
  3205	      constexpr minmax_element_result<borrowed_iterator_t<_Range>>
  3206	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  3207	      {
  3208		return (*this)(ranges::begin(__r), ranges::end(__r),
  3209			       std::move(__comp), std::move(__proj));
  3210	      }
  3211	  };
  3212	
  3213	  inline constexpr __minmax_element_fn minmax_element{};
  3214	
  3215	  struct __lexicographical_compare_fn
  3216	  {
  3217	    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
  3218		     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
  3219		     typename _Proj1 = identity, typename _Proj2 = identity,
  3220		     indirect_strict_weak_order<projected<_Iter1, _Proj1>,
  3221						projected<_Iter2, _Proj2>>
  3222		       _Comp = ranges::less>
  3223	      constexpr bool
  3224	      operator()(_Iter1 __first1, _Sent1 __last1,
  3225			 _Iter2 __first2, _Sent2 __last2,
  3226			 _Comp __comp = {},
  3227			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  3228	      {
  3229		if constexpr (__detail::__is_normal_iterator<_Iter1>
  3230			      && same_as<_Iter1, _Sent1>)
  3231		  return (*this)(__first1.base(), __last1.base(),
  3232				 std::move(__first2), std::move(__last2),
  3233				 std::move(__comp),
  3234				 std::move(__proj1), std::move(__proj2));
  3235		else if constexpr (__detail::__is_normal_iterator<_Iter2>
  3236				   && same_as<_Iter2, _Sent2>)
  3237		  return (*this)(std::move(__first1), std::move(__last1),
  3238				 __first2.base(), __last2.base(),
  3239				 std::move(__comp),
  3240				 std::move(__proj1), std::move(__proj2));
  3241		else
  3242		  {
  3243		    constexpr bool __sized_iters
  3244		      = (sized_sentinel_for<_Sent1, _Iter1>
  3245			 && sized_sentinel_for<_Sent2, _Iter2>);
  3246		    if constexpr (__sized_iters)
  3247		      {
  3248			using _ValueType1 = iter_value_t<_Iter1>;
  3249			using _ValueType2 = iter_value_t<_Iter2>;
  3250			// This condition is consistent with the one in
  3251			// __lexicographical_compare_aux in <bits/stl_algobase.h>.
  3252			constexpr bool __use_memcmp
  3253			  = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
  3254			     && __ptr_to_nonvolatile<_Iter1>
  3255			     && __ptr_to_nonvolatile<_Iter2>
  3256			     && (is_same_v<_Comp, ranges::less>
  3257				 || is_same_v<_Comp, ranges::greater>)
  3258			     && is_same_v<_Proj1, identity>
  3259			     && is_same_v<_Proj2, identity>);
  3260			if constexpr (__use_memcmp)
  3261			  {
  3262			    const auto __d1 = __last1 - __first1;
  3263			    const auto __d2 = __last2 - __first2;
  3264	
  3265			    if (const auto __len = std::min(__d1, __d2))
  3266			      {
  3267				const auto __c
  3268				  = std::__memcmp(__first1, __first2, __len);
  3269				if constexpr (is_same_v<_Comp, ranges::less>)
  3270				  {
  3271				    if (__c < 0)
  3272				      return true;
  3273				    if (__c > 0)
  3274				      return false;
  3275				  }
  3276				else if constexpr (is_same_v<_Comp, ranges::greater>)
  3277				  {
  3278				    if (__c > 0)
  3279				      return true;
  3280				    if (__c < 0)
  3281				      return false;
  3282				  }
  3283			      }
  3284			    return __d1 < __d2;
  3285			  }
  3286		      }
  3287	
  3288		    for (; __first1 != __last1 && __first2 != __last2;
  3289			 ++__first1, (void) ++__first2)
  3290		      {
  3291			if (std::__invoke(__comp,
  3292					  std::__invoke(__proj1, *__first1),
  3293					  std::__invoke(__proj2, *__first2)))
  3294			  return true;
  3295			if (std::__invoke(__comp,
  3296					  std::__invoke(__proj2, *__first2),
  3297					  std::__invoke(__proj1, *__first1)))
  3298			  return false;
  3299		      }
  3300		    return __first1 == __last1 && __first2 != __last2;
  3301		  }
  3302	      }
  3303	
  3304	    template<input_range _Range1, input_range _Range2,
  3305		     typename _Proj1 = identity, typename _Proj2 = identity,
  3306		     indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
  3307						projected<iterator_t<_Range2>, _Proj2>>
  3308		       _Comp = ranges::less>
  3309	      constexpr bool
  3310	      operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
  3311			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  3312	      {
  3313		return (*this)(ranges::begin(__r1), ranges::end(__r1),
  3314			       ranges::begin(__r2), ranges::end(__r2),
  3315			       std::move(__comp),
  3316			       std::move(__proj1), std::move(__proj2));
  3317	      }
  3318	
  3319	  private:
  3320	    template<typename _Iter, typename _Ref = iter_reference_t<_Iter>>
  3321	      static constexpr bool __ptr_to_nonvolatile
  3322		= is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>;
  3323	  };
  3324	
  3325	  inline constexpr __lexicographical_compare_fn lexicographical_compare;
  3326	
  3327	  template<typename _Iter>
  3328	    struct in_found_result
  3329	    {
  3330	      [[no_unique_address]] _Iter in;
  3331	      bool found;
  3332	
  3333	      template<typename _Iter2>
  3334		requires convertible_to<const _Iter&, _Iter2>
  3335		constexpr
  3336		operator in_found_result<_Iter2>() const &
  3337		{ return {in, found}; }
  3338	
  3339	      template<typename _Iter2>
  3340		requires convertible_to<_Iter, _Iter2>
  3341		constexpr
  3342		operator in_found_result<_Iter2>() &&
  3343		{ return {std::move(in), found}; }
  3344	    };
  3345	
  3346	  template<typename _Iter>
  3347	    using next_permutation_result = in_found_result<_Iter>;
  3348	
  3349	  struct __next_permutation_fn
  3350	  {
  3351	    template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
  3352		     typename _Comp = ranges::less, typename _Proj = identity>
  3353	      requires sortable<_Iter, _Comp, _Proj>
  3354	      constexpr next_permutation_result<_Iter>
  3355	      operator()(_Iter __first, _Sent __last,
  3356			 _Comp __comp = {}, _Proj __proj = {}) const
  3357	      {
  3358		if (__first == __last)
  3359		  return {std::move(__first), false};
  3360	
  3361		auto __i = __first;
  3362		++__i;
  3363		if (__i == __last)
  3364		  return {std::move(__i), false};
  3365	
  3366		auto __lasti = ranges::next(__first, __last);
  3367		__i = __lasti;
  3368		--__i;
  3369	
  3370		for (;;)
  3371		  {
  3372		    auto __ii = __i;
  3373		    --__i;
  3374		    if (std::__invoke(__comp,
  3375				      std::__invoke(__proj, *__i),
  3376				      std::__invoke(__proj, *__ii)))
  3377		      {
  3378			auto __j = __lasti;
  3379			while (!(bool)std::__invoke(__comp,
  3380						    std::__invoke(__proj, *__i),
  3381						    std::__invoke(__proj, *--__j)))
  3382			  ;
  3383			ranges::iter_swap(__i, __j);
  3384			ranges::reverse(__ii, __last);
  3385			return {std::move(__lasti), true};
  3386		      }
  3387		    if (__i == __first)
  3388		      {
  3389			ranges::reverse(__first, __last);
  3390			return {std::move(__lasti), false};
  3391		      }
  3392		  }
  3393	      }
  3394	
  3395	    template<bidirectional_range _Range, typename _Comp = ranges::less,
  3396		     typename _Proj = identity>
  3397	      requires sortable<iterator_t<_Range>, _Comp, _Proj>
  3398	      constexpr next_permutation_result<borrowed_iterator_t<_Range>>
  3399	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  3400	      {
  3401		return (*this)(ranges::begin(__r), ranges::end(__r),
  3402			       std::move(__comp), std::move(__proj));
  3403	      }
  3404	  };
  3405	
  3406	  inline constexpr __next_permutation_fn next_permutation{};
  3407	
  3408	  template<typename _Iter>
  3409	    using prev_permutation_result = in_found_result<_Iter>;
  3410	
  3411	  struct __prev_permutation_fn
  3412	  {
  3413	    template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
  3414		     typename _Comp = ranges::less, typename _Proj = identity>
  3415	      requires sortable<_Iter, _Comp, _Proj>
  3416	      constexpr prev_permutation_result<_Iter>
  3417	      operator()(_Iter __first, _Sent __last,
  3418			 _Comp __comp = {}, _Proj __proj = {}) const
  3419	      {
  3420		if (__first == __last)
  3421		  return {std::move(__first), false};
  3422	
  3423		auto __i = __first;
  3424		++__i;
  3425		if (__i == __last)
  3426		  return {std::move(__i), false};
  3427	
  3428		auto __lasti = ranges::next(__first, __last);
  3429		__i = __lasti;
  3430		--__i;
  3431	
  3432		for (;;)
  3433		  {
  3434		    auto __ii = __i;
  3435		    --__i;
  3436		    if (std::__invoke(__comp,
  3437				      std::__invoke(__proj, *__ii),
  3438				      std::__invoke(__proj, *__i)))
  3439		      {
  3440			auto __j = __lasti;
  3441			while (!(bool)std::__invoke(__comp,
  3442						    std::__invoke(__proj, *--__j),
  3443						    std::__invoke(__proj, *__i)))
  3444			  ;
  3445			ranges::iter_swap(__i, __j);
  3446			ranges::reverse(__ii, __last);
  3447			return {std::move(__lasti), true};
  3448		      }
  3449		    if (__i == __first)
  3450		      {
  3451			ranges::reverse(__first, __last);
  3452			return {std::move(__lasti), false};
  3453		      }
  3454		  }
  3455	      }
  3456	
  3457	    template<bidirectional_range _Range, typename _Comp = ranges::less,
  3458		     typename _Proj = identity>
  3459	      requires sortable<iterator_t<_Range>, _Comp, _Proj>
  3460	      constexpr prev_permutation_result<borrowed_iterator_t<_Range>>
  3461	      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  3462	      {
  3463		return (*this)(ranges::begin(__r), ranges::end(__r),
  3464			       std::move(__comp), std::move(__proj));
  3465	      }
  3466	  };
  3467	
  3468	  inline constexpr __prev_permutation_fn prev_permutation{};
  3469	
  3470	#if __cplusplus > 202002L
  3471	
  3472	#define __cpp_lib_ranges_contains 202207L
  3473	
  3474	  struct __contains_fn
  3475	  {
  3476	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
  3477		    typename _Tp, typename _Proj = identity>
  3478	      requires indirect_binary_predicate<ranges::equal_to,
  3479						 projected<_Iter, _Proj>, const _Tp*>
  3480	      constexpr bool
  3481	      operator()(_Iter __first, _Sent __last, const _Tp& __value, _Proj __proj = {}) const
  3482	      { return ranges::find(std::move(__first), __last, __value, std::move(__proj)) != __last; }
  3483	
  3484	    template<input_range _Range, typename _Tp, typename _Proj = identity>
  3485	      requires indirect_binary_predicate<ranges::equal_to,
  3486						 projected<iterator_t<_Range>, _Proj>, const _Tp*>
  3487	      constexpr bool
  3488	      operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
  3489	      { return (*this)(ranges::begin(__r), ranges::end(__r), __value, std::move(__proj)); }
  3490	  };
  3491	
  3492	  inline constexpr __contains_fn contains{};
  3493	
  3494	  struct __contains_subrange_fn
  3495	  {
  3496	    template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
  3497		     forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
  3498		     typename _Pred = ranges::equal_to,
  3499		     typename _Proj1 = identity, typename _Proj2 = identity>
  3500	      requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
  3501	      constexpr bool
  3502	      operator()(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
  3503			 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  3504	      {
  3505		return __first2 == __last2
  3506		  || !ranges::search(__first1, __last1, __first2, __last2,
  3507				     std::move(__pred), std::move(__proj1), std::move(__proj2)).empty();
  3508	      }
  3509	
  3510	    template<forward_range _Range1, forward_range _Range2,
  3511		     typename _Pred = ranges::equal_to,
  3512		     typename _Proj1 = identity, typename _Proj2 = identity>
  3513	      requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
  3514					     _Pred, _Proj1, _Proj2>
  3515	      constexpr bool
  3516	      operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
  3517			 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
  3518	      {
  3519		return (*this)(ranges::begin(__r1), ranges::end(__r1),
  3520			       ranges::begin(__r2), ranges::end(__r2),
  3521			       std::move(__pred), std::move(__proj1), std::move(__proj2));
  3522	      }
  3523	  };
  3524	
  3525	  inline constexpr __contains_subrange_fn contains_subrange{};
  3526	
  3527	#define __cpp_lib_ranges_iota 202202L
  3528	
  3529	  template<typename _Out, typename _Tp>
  3530	    struct out_value_result
  3531	    {
  3532	      [[no_unique_address]] _Out out;
  3533	      [[no_unique_address]] _Tp value;
  3534	
  3535	      template<typename _Out2, typename _Tp2>
  3536		requires convertible_to<const _Out&, _Out2>
  3537		  && convertible_to<const _Tp&, _Tp2>
  3538		constexpr
  3539		operator out_value_result<_Out2, _Tp2>() const &
  3540		{ return {out, value}; }
  3541	
  3542	      template<typename _Out2, typename _Tp2>
  3543		requires convertible_to<_Out, _Out2>
  3544		  && convertible_to<_Tp, _Tp2>
  3545		constexpr
  3546		operator out_value_result<_Out2, _Tp2>() &&
  3547		{ return {std::move(out), std::move(value)}; }
  3548	    };
  3549	
  3550	  template<typename _Out, typename _Tp>
  3551	    using iota_result = out_value_result<_Out, _Tp>;
  3552	
  3553	  struct __iota_fn
  3554	  {
  3555	    template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent, weakly_incrementable _Tp>
  3556	      requires indirectly_writable<_Out, const _Tp&>
  3557	      constexpr iota_result<_Out, _Tp>
  3558	      operator()(_Out __first, _Sent __last, _Tp __value) const
  3559	      {
  3560		while (__first != __last)
  3561		  {
  3562		    *__first = static_cast<const _Tp&>(__value);
  3563		    ++__first;
  3564		    ++__value;
  3565		  }
  3566		return {std::move(__first), std::move(__value)};
  3567	      }
  3568	
  3569	    template<weakly_incrementable _Tp, output_range<const _Tp&> _Range>
  3570	      constexpr iota_result<borrowed_iterator_t<_Range>, _Tp>
  3571	      operator()(_Range&& __r, _Tp __value) const
  3572	      { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__value)); }
  3573	  };
  3574	
  3575	  inline constexpr __iota_fn iota{};
  3576	
  3577	#define __cpp_lib_ranges_find_last 202207L
  3578	
  3579	  struct __find_last_fn
  3580	  {
  3581	    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp, typename _Proj = identity>
  3582	      requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Tp*>
  3583	      constexpr subrange<_Iter>
  3584	      operator()(_Iter __first, _Sent __last, const _Tp& __value, _Proj __proj = {}) const
  3585	      {
  3586		if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
  3587		  {
  3588		    _Iter __found = ranges::find(reverse_iterator<_Iter>{__last},
  3589						 reverse_iterator<_Iter>{__first},
  3590						 __value, std::move(__proj)).base();
  3591		    if (__found == __first)
  3592		      return {__last, __last};
  3593		    else
  3594		      return {ranges::prev(__found), __last};
  3595		  }
  3596		else
  3597		  {
  3598		    _Iter __found = ranges::find(__first, __last, __value, __proj);
  3599		    if (__found == __last)
  3600		      return {__found, __found};
  3601		    __first = __found;
  3602		    for (;;)
  3603		      {
  3604			__first = ranges::find(ranges::next(__first), __last, __value, __proj);
  3605			if (__first == __last)
  3606			  return {__found, __first};
  3607			__found = __first;
  3608		      }
  3609		  }
  3610	      }
  3611	
  3612	    template<forward_range _Range, typename _Tp, typename _Proj = identity>
  3613	      requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Tp*>
  3614	      constexpr borrowed_subrange_t<_Range>
  3615	      operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
  3616	      { return (*this)(ranges::begin(__r), ranges::end(__r), __value, std::move(__proj)); }
  3617	  };
  3618	
  3619	  inline constexpr __find_last_fn find_last{};
  3620	
  3621	  struct __find_last_if_fn
  3622	  {
  3623	    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Proj = identity,
  3624		     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
  3625	      constexpr subrange<_Iter>
  3626	      operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const
  3627	      {
  3628		if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
  3629		  {
  3630		    _Iter __found = ranges::find_if(reverse_iterator<_Iter>{__last},
  3631						    reverse_iterator<_Iter>{__first},
  3632						    std::move(__pred), std::move(__proj)).base();
  3633		    if (__found == __first)
  3634		      return {__last, __last};
  3635		    else
  3636		      return {ranges::prev(__found), __last};
  3637		  }
  3638		else
  3639		  {
  3640		    _Iter __found = ranges::find_if(__first, __last, __pred, __proj);
  3641		    if (__found == __last)
  3642		      return {__found, __found};
  3643		    __first = __found;
  3644		    for (;;)
  3645		      {
  3646			__first = ranges::find_if(ranges::next(__first), __last, __pred, __proj);
  3647			if (__first == __last)
  3648			  return {__found, __first};
  3649			__found = __first;
  3650		      }
  3651		  }
  3652	      }
  3653	
  3654	    template<forward_range _Range, typename _Proj = identity,
  3655		     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
  3656	      constexpr borrowed_subrange_t<_Range>
  3657	      operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
  3658	      { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__pred), std::move(__proj)); }
  3659	  };
  3660	
  3661	  inline constexpr __find_last_if_fn find_last_if{};
  3662	
  3663	  struct __find_last_if_not_fn
  3664	  {
  3665	    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Proj = identity,
  3666		     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
  3667	      constexpr subrange<_Iter>
  3668	      operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const
  3669	      {
  3670		if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
  3671		  {
  3672		    _Iter __found = ranges::find_if_not(reverse_iterator<_Iter>{__last},
  3673							reverse_iterator<_Iter>{__first},
  3674							std::move(__pred), std::move(__proj)).base();
  3675		    if (__found == __first)
  3676		      return {__last, __last};
  3677		    else
  3678		      return {ranges::prev(__found), __last};
  3679		  }
  3680		else
  3681		  {
  3682		    _Iter __found = ranges::find_if_not(__first, __last, __pred, __proj);
  3683		    if (__found == __last)
  3684		      return {__found, __found};
  3685		    __first = __found;
  3686		    for (;;)
  3687		      {
  3688			__first = ranges::find_if_not(ranges::next(__first), __last, __pred, __proj);
  3689			if (__first == __last)
  3690			  return {__found, __first};
  3691			__found = __first;
  3692		      }
  3693		  }
  3694	      }
  3695	
  3696	    template<forward_range _Range, typename _Proj = identity,
  3697		     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
  3698	      constexpr borrowed_subrange_t<_Range>
  3699	      operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
  3700	      { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__pred), std::move(__proj)); }
  3701	  };
  3702	
  3703	  inline constexpr __find_last_if_not_fn find_last_if_not{};
  3704	
  3705	#define __cpp_lib_ranges_fold 202207L
  3706	
  3707	  template<typename _Iter, typename _Tp>
  3708	    struct in_value_result
  3709	    {
  3710	      [[no_unique_address]] _Iter in;
  3711	      [[no_unique_address]] _Tp value;
  3712	
  3713	      template<typename _Iter2, typename _Tp2>
  3714		requires convertible_to<const _Iter&, _Iter2>
  3715		  && convertible_to<const _Tp&, _Tp2>
  3716	      constexpr
  3717	      operator in_value_result<_Iter2, _Tp2>() const &
  3718	      { return {in, value}; }
  3719	
  3720	      template<typename _Iter2, typename _Tp2>
  3721		requires convertible_to<_Iter, _Iter2>
  3722		  && convertible_to<_Tp, _Tp2>
  3723	      constexpr
  3724	      operator in_value_result<_Iter2, _Tp2>() &&
  3725	      { return {std::move(in), std::move(value)}; }
  3726	    };
  3727	
  3728	  namespace __detail
  3729	  {
  3730	    template<typename _Fp>
  3731	      class __flipped
  3732	      {
  3733		_Fp _M_f;
  3734	
  3735	      public:
  3736		template<typename _Tp, typename _Up>
  3737		  requires invocable<_Fp&, _Up, _Tp>
  3738		invoke_result_t<_Fp&, _Up, _Tp>
  3739		operator()(_Tp&&, _Up&&); // not defined
  3740	      };
  3741	
  3742	      template<typename _Fp, typename _Tp, typename _Iter, typename _Up>
  3743	      concept __indirectly_binary_left_foldable_impl = movable<_Tp> && movable<_Up>
  3744		&& convertible_to<_Tp, _Up>
  3745		&& invocable<_Fp&, _Up, iter_reference_t<_Iter>>
  3746		&& assignable_from<_Up&, invoke_result_t<_Fp&, _Up, iter_reference_t<_Iter>>>;
  3747	
  3748	      template<typename _Fp, typename _Tp, typename _Iter>
  3749	      concept __indirectly_binary_left_foldable = copy_constructible<_Fp>
  3750		&& indirectly_readable<_Iter>
  3751		&& invocable<_Fp&, _Tp, iter_reference_t<_Iter>>
  3752		&& convertible_to<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>,
  3753				  decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>>
  3754		&& __indirectly_binary_left_foldable_impl
  3755		    <_Fp, _Tp, _Iter, decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>>;
  3756	
  3757	      template <typename _Fp, typename _Tp, typename _Iter>
  3758	      concept __indirectly_binary_right_foldable
  3759		= __indirectly_binary_left_foldable<__flipped<_Fp>, _Tp, _Iter>;
  3760	  } // namespace __detail
  3761	
  3762	  template<typename _Iter, typename _Tp>
  3763	    using fold_left_with_iter_result = in_value_result<_Iter, _Tp>;
  3764	
  3765	  struct __fold_left_with_iter_fn
  3766	  {
  3767	    template<typename _Ret_iter,
  3768		     typename _Iter, typename _Sent, typename _Tp, typename _Fp>
  3769	      static constexpr auto
  3770	      _S_impl(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
  3771	      {
  3772		using _Up = decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>;
  3773		using _Ret = fold_left_with_iter_result<_Ret_iter, _Up>;
  3774	
  3775		if (__first == __last)
  3776		  return _Ret{std::move(__first), _Up(std::move(__init))};
  3777	
  3778		_Up __accum = std::__invoke(__f, std::move(__init), *__first);
  3779		for (++__first; __first != __last; ++__first)
  3780		  __accum = std::__invoke(__f, std::move(__accum), *__first);
  3781		return _Ret{std::move(__first), std::move(__accum)};
  3782	      }
  3783	
  3784	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
  3785		     __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
  3786	      constexpr auto
  3787	      operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const
  3788	      {
  3789		using _Ret_iter = _Iter;
  3790		return _S_impl<_Ret_iter>(std::move(__first), __last,
  3791					  std::move(__init), std::move(__f));
  3792	      }
  3793	
  3794	    template<input_range _Range, typename _Tp,
  3795		     __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
  3796	      constexpr auto
  3797	      operator()(_Range&& __r, _Tp __init, _Fp __f) const
  3798	      {
  3799		using _Ret_iter = borrowed_iterator_t<_Range>;
  3800		return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r),
  3801					  std::move(__init), std::move(__f));
  3802	      }
  3803	  };
  3804	
  3805	  inline constexpr __fold_left_with_iter_fn fold_left_with_iter{};
  3806	
  3807	  struct __fold_left_fn
  3808	  {
  3809	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
  3810		     __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
  3811	      constexpr auto
  3812	      operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const
  3813	      {
  3814		return ranges::fold_left_with_iter(std::move(__first), __last,
  3815						   std::move(__init), std::move(__f)).value;
  3816	      }
  3817	
  3818	    template<input_range _Range, typename _Tp,
  3819		     __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
  3820	      constexpr auto
  3821	      operator()(_Range&& __r, _Tp __init, _Fp __f) const
  3822	      { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__init), std::move(__f)); }
  3823	  };
  3824	
  3825	  inline constexpr __fold_left_fn fold_left{};
  3826	
  3827	  template<typename _Iter, typename _Tp>
  3828	    using fold_left_first_with_iter_result = in_value_result<_Iter, _Tp>;
  3829	
  3830	  struct __fold_left_first_with_iter_fn
  3831	  {
  3832	    template<typename _Ret_iter, typename _Iter, typename _Sent, typename _Fp>
  3833	      static constexpr auto
  3834	      _S_impl(_Iter __first, _Sent __last, _Fp __f)
  3835	      {
  3836		using _Up = decltype(ranges::fold_left(std::move(__first), __last,
  3837						       iter_value_t<_Iter>(*__first), __f));
  3838		using _Ret = fold_left_first_with_iter_result<_Ret_iter, optional<_Up>>;
  3839	
  3840		if (__first == __last)
  3841		  return _Ret{std::move(__first), optional<_Up>()};
  3842	
  3843		optional<_Up> __init(in_place, *__first);
  3844		for (++__first; __first != __last; ++__first)
  3845		  *__init = std::__invoke(__f, std::move(*__init), *__first);
  3846		return _Ret{std::move(__first), std::move(__init)};
  3847	      }
  3848	
  3849	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
  3850		     __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
  3851	      requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
  3852	      constexpr auto
  3853	      operator()(_Iter __first, _Sent __last, _Fp __f) const
  3854	      {
  3855		using _Ret_iter = _Iter;
  3856		return _S_impl<_Ret_iter>(std::move(__first), __last, std::move(__f));
  3857	      }
  3858	
  3859	    template<input_range _Range,
  3860		     __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
  3861	      requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
  3862	      constexpr auto
  3863	      operator()(_Range&& __r, _Fp __f) const
  3864	      {
  3865		using _Ret_iter = borrowed_iterator_t<_Range>;
  3866		return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r), std::move(__f));
  3867	      }
  3868	  };
  3869	
  3870	  inline constexpr __fold_left_first_with_iter_fn fold_left_first_with_iter{};
  3871	
  3872	  struct __fold_left_first_fn
  3873	  {
  3874	    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
  3875		     __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
  3876	      requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
  3877	      constexpr auto
  3878	      operator()(_Iter __first, _Sent __last, _Fp __f) const
  3879	      {
  3880		return ranges::fold_left_first_with_iter(std::move(__first), __last,
  3881							 std::move(__f)).value;
  3882	      }
  3883	
  3884	    template<input_range _Range,
  3885		     __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
  3886	      requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
  3887	      constexpr auto
  3888	      operator()(_Range&& __r, _Fp __f) const
  3889	      { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__f)); }
  3890	  };
  3891	
  3892	  inline constexpr __fold_left_first_fn fold_left_first{};
  3893	
  3894	  struct __fold_right_fn
  3895	  {
  3896	    template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
  3897		     __detail::__indirectly_binary_right_foldable<_Tp, _Iter> _Fp>
  3898	      constexpr auto
  3899	      operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const
  3900	      {
  3901		using _Up = decay_t<invoke_result_t<_Fp&, iter_reference_t<_Iter>, _Tp>>;
  3902	
  3903		if (__first == __last)
  3904		  return _Up(std::move(__init));
  3905	
  3906		_Iter __tail = ranges::next(__first, __last);
  3907		_Up __accum = std::__invoke(__f, *--__tail, std::move(__init));
  3908		while (__first != __tail)
  3909		  __accum = std::__invoke(__f, *--__tail, std::move(__accum));
  3910		return __accum;
  3911	      }
  3912	
  3913	    template<bidirectional_range _Range, typename _Tp,
  3914		     __detail::__indirectly_binary_right_foldable<_Tp, iterator_t<_Range>> _Fp>
  3915	      constexpr auto
  3916	      operator()(_Range&& __r, _Tp __init, _Fp __f) const
  3917	      { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__init), std::move(__f)); }
  3918	  };
  3919	
  3920	  inline constexpr __fold_right_fn fold_right{};
  3921	
  3922	  struct __fold_right_last_fn
  3923	  {
  3924	    template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
  3925		     __detail::__indirectly_binary_right_foldable<iter_value_t<_Iter>, _Iter> _Fp>
  3926	      requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
  3927	      constexpr auto
  3928	      operator()(_Iter __first, _Sent __last, _Fp __f) const
  3929	      {
  3930		using _Up = decltype(ranges::fold_right(__first, __last,
  3931							iter_value_t<_Iter>(*__first), __f));
  3932	
  3933		if (__first == __last)
  3934		  return optional<_Up>();
  3935	
  3936		_Iter __tail = ranges::prev(ranges::next(__first, std::move(__last)));
  3937		return optional<_Up>(in_place,
  3938				     ranges::fold_right(std::move(__first), __tail,
  3939							iter_value_t<_Iter>(*__tail),
  3940							std::move(__f)));
  3941	      }
  3942	
  3943	    template<bidirectional_range _Range,
  3944		     __detail::__indirectly_binary_right_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
  3945	      requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
  3946	      constexpr auto
  3947	      operator()(_Range&& __r, _Fp __f) const
  3948	      { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__f)); }
  3949	  };
  3950	
  3951	  inline constexpr __fold_right_last_fn fold_right_last{};
  3952	#endif // C++23
  3953	} // namespace ranges
  3954	
  3955	#define __cpp_lib_shift 201806L
  3956	  template<typename _ForwardIterator>
  3957	    constexpr _ForwardIterator
  3958	    shift_left(_ForwardIterator __first, _ForwardIterator __last,
  3959		       typename iterator_traits<_ForwardIterator>::difference_type __n)
  3960	    {
  3961	      __glibcxx_assert(__n >= 0);
  3962	      if (__n == 0)
  3963		return __last;
  3964	
  3965	      auto __mid = ranges::next(__first, __n, __last);
  3966	      if (__mid == __last)
  3967		return __first;
  3968	      return std::move(std::move(__mid), std::move(__last), std::move(__first));
  3969	    }
  3970	
  3971	  template<typename _ForwardIterator>
  3972	    constexpr _ForwardIterator
  3973	    shift_right(_ForwardIterator __first, _ForwardIterator __last,
  3974			typename iterator_traits<_ForwardIterator>::difference_type __n)
  3975	    {
  3976	      __glibcxx_assert(__n >= 0);
  3977	      if (__n == 0)
  3978		return __first;
  3979	
  3980	      using _Cat
  3981		= typename iterator_traits<_ForwardIterator>::iterator_category;
  3982	      if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
  3983		{
  3984		  auto __mid = ranges::next(__last, -__n, __first);
  3985		  if (__mid == __first)
  3986		    return __last;
  3987	
  3988		  return std::move_backward(std::move(__first), std::move(__mid),
  3989					    std::move(__last));
  3990		}
  3991	      else
  3992		{
  3993		  auto __result = ranges::next(__first, __n, __last);
  3994		  if (__result == __last)
  3995		    return __last;
  3996	
  3997		  auto __dest_head = __first, __dest_tail = __result;
  3998		  while (__dest_head != __result)
  3999		    {
  4000		      if (__dest_tail == __last)
  4001			{
  4002			  // If we get here, then we must have
  4003			  //     2*n >= distance(__first, __last)
  4004			  // i.e. we are shifting out at least half of the range.  In
  4005			  // this case we can safely perform the shift with a single
  4006			  // move.
  4007			  std::move(std::move(__first), std::move(__dest_head), __result);
  4008			  return __result;
  4009			}
  4010		      ++__dest_head;
  4011		      ++__dest_tail;
  4012		    }
  4013	
  4014		  for (;;)
  4015		    {
  4016		      // At the start of each iteration of this outer loop, the range
  4017		      // [__first, __result) contains those elements that after shifting
  4018		      // the whole range right by __n, should end up in
  4019		      // [__dest_head, __dest_tail) in order.
  4020	
  4021		      // The below inner loop swaps the elements of [__first, __result)
  4022		      // and [__dest_head, __dest_tail), while simultaneously shifting
  4023		      // the latter range by __n.
  4024		      auto __cursor = __first;
  4025		      while (__cursor != __result)
  4026			{
  4027			  if (__dest_tail == __last)
  4028			    {
  4029			      // At this point the ranges [__first, result) and
  4030			      // [__dest_head, dest_tail) are disjoint, so we can safely
  4031			      // move the remaining elements.
  4032			      __dest_head = std::move(__cursor, __result,
  4033						      std::move(__dest_head));
  4034			      std::move(std::move(__first), std::move(__cursor),
  4035					std::move(__dest_head));
  4036			      return __result;
  4037			    }
  4038			  std::iter_swap(__cursor, __dest_head);
  4039			  ++__dest_head;
  4040			  ++__dest_tail;
  4041			  ++__cursor;
  4042			}
  4043		    }
  4044		}
  4045	    }
  4046	
  4047	_GLIBCXX_END_NAMESPACE_VERSION
  4048	} // namespace std
  4049	#endif // concepts
  4050	#endif // C++20
  4051	#endif // _RANGES_ALGO_H