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