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