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