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