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