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