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