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