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) -> bool {
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) -> bool {
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) -> bool {
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  namespace __detail
1399  {
1400  template<typename _Out, typename _Tp>
1401  concept __can_reread_output = input_iterator<_Out>
1402  && same_as<_Tp, iter_value_t<_Out>>;
1403  }
1404 
1405  template<typename _Iter, typename _Out>
1406  using unique_copy_result = in_out_result<_Iter, _Out>;
1407 
1408  struct __unique_copy_fn
1409  {
1410  template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1411  weakly_incrementable _Out, typename _Proj = identity,
1412  indirect_equivalence_relation<
1413  projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1414  requires indirectly_copyable<_Iter, _Out>
1415  && (forward_iterator<_Iter>
1416  || __detail::__can_reread_output<_Out, iter_value_t<_Iter>>
1417  || indirectly_copyable_storable<_Iter, _Out>)
1418  constexpr unique_copy_result<_Iter, _Out>
1419  operator()(_Iter __first, _Sent __last, _Out __result,
1420  _Comp __comp = {}, _Proj __proj = {}) const
1421  {
1422  if (__first == __last)
1423  return {std::move(__first), std::move(__result)};
1424 
1425  // TODO: perform a closer comparison with reference implementations
1426  if constexpr (forward_iterator<_Iter>)
1427  {
1428  auto __next = __first;
1429  *__result = *__next;
1430  while (++__next != __last)
1431  if (!std::__invoke(__comp,
1432  std::__invoke(__proj, *__first),
1433  std::__invoke(__proj, *__next)))
1434  {
1435  __first = __next;
1436  *++__result = *__first;
1437  }
1438  return {__next, std::move(++__result)};
1439  }
1440  else if constexpr (__detail::__can_reread_output<_Out, iter_value_t<_Iter>>)
1441  {
1442  *__result = *__first;
1443  while (++__first != __last)
1444  if (!std::__invoke(__comp,
1445  std::__invoke(__proj, *__result),
1446  std::__invoke(__proj, *__first)))
1447  *++__result = *__first;
1448  return {std::move(__first), std::move(++__result)};
1449  }
1450  else // indirectly_copyable_storable<_Iter, _Out>
1451  {
1452  auto __value = *__first;
1453  *__result = __value;
1454  while (++__first != __last)
1455  {
1456  if (!(bool)std::__invoke(__comp,
1457  std::__invoke(__proj, *__first),
1458  std::__invoke(__proj, __value)))
1459  {
1460  __value = *__first;
1461  *++__result = __value;
1462  }
1463  }
1464  return {std::move(__first), std::move(++__result)};
1465  }
1466  }
1467 
1468  template<input_range _Range,
1469  weakly_incrementable _Out, typename _Proj = identity,
1470  indirect_equivalence_relation<
1471  projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1472  requires indirectly_copyable<iterator_t<_Range>, _Out>
1473  && (forward_iterator<iterator_t<_Range>>
1474  || __detail::__can_reread_output<_Out, range_value_t<_Range>>
1475  || indirectly_copyable_storable<iterator_t<_Range>, _Out>)
1476  constexpr unique_copy_result<borrowed_iterator_t<_Range>, _Out>
1477  operator()(_Range&& __r, _Out __result,
1478  _Comp __comp = {}, _Proj __proj = {}) const
1479  {
1480  return (*this)(ranges::begin(__r), ranges::end(__r),
1481  std::move(__result),
1482  std::move(__comp), std::move(__proj));
1483  }
1484  };
1485 
1486  inline constexpr __unique_copy_fn unique_copy{};
1487 
1488  struct __reverse_fn
1489  {
1490  template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
1491  requires permutable<_Iter>
1492  constexpr _Iter
1493  operator()(_Iter __first, _Sent __last) const
1494  {
1495  auto __i = ranges::next(__first, __last);
1496  auto __tail = __i;
1497 
1498  if constexpr (random_access_iterator<_Iter>)
1499  {
1500  if (__first != __last)
1501  {
1502  --__tail;
1503  while (__first < __tail)
1504  {
1505  ranges::iter_swap(__first, __tail);
1506  ++__first;
1507  --__tail;
1508  }
1509  }
1510  return __i;
1511  }
1512  else
1513  {
1514  for (;;)
1515  if (__first == __tail || __first == --__tail)
1516  break;
1517  else
1518  {
1519  ranges::iter_swap(__first, __tail);
1520  ++__first;
1521  }
1522  return __i;
1523  }
1524  }
1525 
1526  template<bidirectional_range _Range>
1527  requires permutable<iterator_t<_Range>>
1528  constexpr borrowed_iterator_t<_Range>
1529  operator()(_Range&& __r) const
1530  {
1531  return (*this)(ranges::begin(__r), ranges::end(__r));
1532  }
1533  };
1534 
1535  inline constexpr __reverse_fn reverse{};
1536 
1537  template<typename _Iter, typename _Out>
1538  using reverse_copy_result = in_out_result<_Iter, _Out>;
1539 
1540  struct __reverse_copy_fn
1541  {
1542  template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
1543  weakly_incrementable _Out>
1544  requires indirectly_copyable<_Iter, _Out>
1545  constexpr reverse_copy_result<_Iter, _Out>
1546  operator()(_Iter __first, _Sent __last, _Out __result) const
1547  {
1548  auto __i = ranges::next(__first, __last);
1549  auto __tail = __i;
1550  while (__first != __tail)
1551  {
1552  --__tail;
1553  *__result = *__tail;
1554  ++__result;
1555  }
1556  return {__i, std::move(__result)};
1557  }
1558 
1559  template<bidirectional_range _Range, weakly_incrementable _Out>
1560  requires indirectly_copyable<iterator_t<_Range>, _Out>
1561  constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _Out>
1562  operator()(_Range&& __r, _Out __result) const
1563  {
1564  return (*this)(ranges::begin(__r), ranges::end(__r),
1565  std::move(__result));
1566  }
1567  };
1568 
1569  inline constexpr __reverse_copy_fn reverse_copy{};
1570 
1571  struct __rotate_fn
1572  {
1573  template<permutable _Iter, sentinel_for<_Iter> _Sent>
1574  constexpr subrange<_Iter>
1575  operator()(_Iter __first, _Iter __middle, _Sent __last) const
1576  {
1577  auto __lasti = ranges::next(__first, __last);
1578  if (__first == __middle)
1579  return {__lasti, __lasti};
1580  if (__last == __middle)
1581  return {std::move(__first), std::move(__lasti)};
1582 
1583  if constexpr (random_access_iterator<_Iter>)
1584  {
1585  auto __n = __lasti - __first;
1586  auto __k = __middle - __first;
1587 
1588  if (__k == __n - __k)
1589  {
1590  ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
1591  return {std::move(__middle), std::move(__lasti)};
1592  }
1593 
1594  auto __p = __first;
1595  auto __ret = __first + (__lasti - __middle);
1596 
1597  for (;;)
1598  {
1599  if (__k < __n - __k)
1600  {
1601  // TODO: is_pod is deprecated, but this condition is
1602  // consistent with the STL implementation.
1603  if constexpr (__is_pod(iter_value_t<_Iter>))
1604  if (__k == 1)
1605  {
1606  auto __t = std::move(*__p);
1607  ranges::move(__p + 1, __p + __n, __p);
1608  *(__p + __n - 1) = std::move(__t);
1609  return {std::move(__ret), std::move(__lasti)};
1610  }
1611  auto __q = __p + __k;
1612  for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1613  {
1614  ranges::iter_swap(__p, __q);
1615  ++__p;
1616  ++__q;
1617  }
1618  __n %= __k;
1619  if (__n == 0)
1620  return {std::move(__ret), std::move(__lasti)};
1621  ranges::swap(__n, __k);
1622  __k = __n - __k;
1623  }
1624  else
1625  {
1626  __k = __n - __k;
1627  // TODO: is_pod is deprecated, but this condition is
1628  // consistent with the STL implementation.
1629  if constexpr (__is_pod(iter_value_t<_Iter>))
1630  if (__k == 1)
1631  {
1632  auto __t = std::move(*(__p + __n - 1));
1633  ranges::move_backward(__p, __p + __n - 1, __p + __n);
1634  *__p = std::move(__t);
1635  return {std::move(__ret), std::move(__lasti)};
1636  }
1637  auto __q = __p + __n;
1638  __p = __q - __k;
1639  for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1640  {
1641  --__p;
1642  --__q;
1643  ranges::iter_swap(__p, __q);
1644  }
1645  __n %= __k;
1646  if (__n == 0)
1647  return {std::move(__ret), std::move(__lasti)};
1648  std::swap(__n, __k);
1649  }
1650  }
1651  }
1652  else if constexpr (bidirectional_iterator<_Iter>)
1653  {
1654  auto __tail = __lasti;
1655 
1656  ranges::reverse(__first, __middle);
1657  ranges::reverse(__middle, __tail);
1658 
1659  while (__first != __middle && __middle != __tail)
1660  {
1661  ranges::iter_swap(__first, --__tail);
1662  ++__first;
1663  }
1664 
1665  if (__first == __middle)
1666  {
1667  ranges::reverse(__middle, __tail);
1668  return {std::move(__tail), std::move(__lasti)};
1669  }
1670  else
1671  {
1672  ranges::reverse(__first, __middle);
1673  return {std::move(__first), std::move(__lasti)};
1674  }
1675  }
1676  else
1677  {
1678  auto __first2 = __middle;
1679  do
1680  {
1681  ranges::iter_swap(__first, __first2);
1682  ++__first;
1683  ++__first2;
1684  if (__first == __middle)
1685  __middle = __first2;
1686  } while (__first2 != __last);
1687 
1688  auto __ret = __first;
1689 
1690  __first2 = __middle;
1691 
1692  while (__first2 != __last)
1693  {
1694  ranges::iter_swap(__first, __first2);
1695  ++__first;
1696  ++__first2;
1697  if (__first == __middle)
1698  __middle = __first2;
1699  else if (__first2 == __last)
1700  __first2 = __middle;
1701  }
1702  return {std::move(__ret), std::move(__lasti)};
1703  }
1704  }
1705 
1706  template<forward_range _Range>
1707  requires permutable<iterator_t<_Range>>
1708  constexpr borrowed_subrange_t<_Range>
1709  operator()(_Range&& __r, iterator_t<_Range> __middle) const
1710  {
1711  return (*this)(ranges::begin(__r), std::move(__middle),
1712  ranges::end(__r));
1713  }
1714  };
1715 
1716  inline constexpr __rotate_fn rotate{};
1717 
1718  template<typename _Iter, typename _Out>
1719  using rotate_copy_result = in_out_result<_Iter, _Out>;
1720 
1721  struct __rotate_copy_fn
1722  {
1723  template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1724  weakly_incrementable _Out>
1725  requires indirectly_copyable<_Iter, _Out>
1726  constexpr rotate_copy_result<_Iter, _Out>
1727  operator()(_Iter __first, _Iter __middle, _Sent __last,
1728  _Out __result) const
1729  {
1730  auto __copy1 = ranges::copy(__middle,
1731  std::move(__last),
1732  std::move(__result));
1733  auto __copy2 = ranges::copy(std::move(__first),
1734  std::move(__middle),
1735  std::move(__copy1.out));
1736  return { std::move(__copy1.in), std::move(__copy2.out) };
1737  }
1738 
1739  template<forward_range _Range, weakly_incrementable _Out>
1740  requires indirectly_copyable<iterator_t<_Range>, _Out>
1741  constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _Out>
1742  operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result) const
1743  {
1744  return (*this)(ranges::begin(__r), std::move(__middle),
1745  ranges::end(__r), std::move(__result));
1746  }
1747  };
1748 
1749  inline constexpr __rotate_copy_fn rotate_copy{};
1750 
1751  struct __sample_fn
1752  {
1753  template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1754  weakly_incrementable _Out, typename _Gen>
1755  requires (forward_iterator<_Iter> || random_access_iterator<_Out>)
1756  && indirectly_copyable<_Iter, _Out>
1757  && uniform_random_bit_generator<remove_reference_t<_Gen>>
1758  _Out
1759  operator()(_Iter __first, _Sent __last, _Out __out,
1760  iter_difference_t<_Iter> __n, _Gen&& __g) const
1761  {
1762  if constexpr (forward_iterator<_Iter>)
1763  {
1764  // FIXME: Forwarding to std::sample here requires computing __lasti
1765  // which may take linear time.
1766  auto __lasti = ranges::next(__first, __last);
1767  return std::sample(std::move(__first), std::move(__lasti),
1768  std::move(__out), __n, std::forward<_Gen>(__g));
1769  }
1770  else
1771  {
1772  using __distrib_type
1773  = uniform_int_distribution<iter_difference_t<_Iter>>;
1774  using __param_type = typename __distrib_type::param_type;
1775  __distrib_type __d{};
1776  iter_difference_t<_Iter> __sample_sz = 0;
1777  while (__first != __last && __sample_sz != __n)
1778  {
1779  __out[__sample_sz++] = *__first;
1780  ++__first;
1781  }
1782  for (auto __pop_sz = __sample_sz; __first != __last;
1783  ++__first, (void) ++__pop_sz)
1784  {
1785  const auto __k = __d(__g, __param_type{0, __pop_sz});
1786  if (__k < __n)
1787  __out[__k] = *__first;
1788  }
1789  return __out + __sample_sz;
1790  }
1791  }
1792 
1793  template<input_range _Range, weakly_incrementable _Out, typename _Gen>
1794  requires (forward_range<_Range> || random_access_iterator<_Out>)
1795  && indirectly_copyable<iterator_t<_Range>, _Out>
1796  && uniform_random_bit_generator<remove_reference_t<_Gen>>
1797  _Out
1798  operator()(_Range&& __r, _Out __out,
1799  range_difference_t<_Range> __n, _Gen&& __g) const
1800  {
1801  return (*this)(ranges::begin(__r), ranges::end(__r),
1802  std::move(__out), __n,
1803  std::forward<_Gen>(__g));
1804  }
1805  };
1806 
1807  inline constexpr __sample_fn sample{};
1808 
1809 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
1810  struct __shuffle_fn
1811  {
1812  template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1813  typename _Gen>
1814  requires permutable<_Iter>
1815  && uniform_random_bit_generator<remove_reference_t<_Gen>>
1816  _Iter
1817  operator()(_Iter __first, _Sent __last, _Gen&& __g) const
1818  {
1819  auto __lasti = ranges::next(__first, __last);
1820  std::shuffle(std::move(__first), __lasti, std::forward<_Gen>(__g));
1821  return __lasti;
1822  }
1823 
1824  template<random_access_range _Range, typename _Gen>
1825  requires permutable<iterator_t<_Range>>
1826  && uniform_random_bit_generator<remove_reference_t<_Gen>>
1827  borrowed_iterator_t<_Range>
1828  operator()(_Range&& __r, _Gen&& __g) const
1829  {
1830  return (*this)(ranges::begin(__r), ranges::end(__r),
1831  std::forward<_Gen>(__g));
1832  }
1833  };
1834 
1835  inline constexpr __shuffle_fn shuffle{};
1836 #endif
1837 
1838  struct __push_heap_fn
1839  {
1840  template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1841  typename _Comp = ranges::less, typename _Proj = identity>
1842  requires sortable<_Iter, _Comp, _Proj>
1843  constexpr _Iter
1844  operator()(_Iter __first, _Sent __last,
1845  _Comp __comp = {}, _Proj __proj = {}) const
1846  {
1847  auto __lasti = ranges::next(__first, __last);
1848  std::push_heap(__first, __lasti,
1849  __detail::__make_comp_proj(__comp, __proj));
1850  return __lasti;
1851  }
1852 
1853  template<random_access_range _Range,
1854  typename _Comp = ranges::less, typename _Proj = identity>
1855  requires sortable<iterator_t<_Range>, _Comp, _Proj>
1856  constexpr borrowed_iterator_t<_Range>
1857  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1858  {
1859  return (*this)(ranges::begin(__r), ranges::end(__r),
1860  std::move(__comp), std::move(__proj));
1861  }
1862  };
1863 
1864  inline constexpr __push_heap_fn push_heap{};
1865 
1866  struct __pop_heap_fn
1867  {
1868  template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1869  typename _Comp = ranges::less, typename _Proj = identity>
1870  requires sortable<_Iter, _Comp, _Proj>
1871  constexpr _Iter
1872  operator()(_Iter __first, _Sent __last,
1873  _Comp __comp = {}, _Proj __proj = {}) const
1874  {
1875  auto __lasti = ranges::next(__first, __last);
1876  std::pop_heap(__first, __lasti,
1877  __detail::__make_comp_proj(__comp, __proj));
1878  return __lasti;
1879  }
1880 
1881  template<random_access_range _Range,
1882  typename _Comp = ranges::less, typename _Proj = identity>
1883  requires sortable<iterator_t<_Range>, _Comp, _Proj>
1884  constexpr borrowed_iterator_t<_Range>
1885  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1886  {
1887  return (*this)(ranges::begin(__r), ranges::end(__r),
1888  std::move(__comp), std::move(__proj));
1889  }
1890  };
1891 
1892  inline constexpr __pop_heap_fn pop_heap{};
1893 
1894  struct __make_heap_fn
1895  {
1896  template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1897  typename _Comp = ranges::less, typename _Proj = identity>
1898  requires sortable<_Iter, _Comp, _Proj>
1899  constexpr _Iter
1900  operator()(_Iter __first, _Sent __last,
1901  _Comp __comp = {}, _Proj __proj = {}) const
1902  {
1903  auto __lasti = ranges::next(__first, __last);
1904  std::make_heap(__first, __lasti,
1905  __detail::__make_comp_proj(__comp, __proj));
1906  return __lasti;
1907  }
1908 
1909  template<random_access_range _Range,
1910  typename _Comp = ranges::less, typename _Proj = identity>
1911  requires sortable<iterator_t<_Range>, _Comp, _Proj>
1912  constexpr borrowed_iterator_t<_Range>
1913  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1914  {
1915  return (*this)(ranges::begin(__r), ranges::end(__r),
1916  std::move(__comp), std::move(__proj));
1917  }
1918  };
1919 
1920  inline constexpr __make_heap_fn make_heap{};
1921 
1922  struct __sort_heap_fn
1923  {
1924  template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1925  typename _Comp = ranges::less, typename _Proj = identity>
1926  requires sortable<_Iter, _Comp, _Proj>
1927  constexpr _Iter
1928  operator()(_Iter __first, _Sent __last,
1929  _Comp __comp = {}, _Proj __proj = {}) const
1930  {
1931  auto __lasti = ranges::next(__first, __last);
1932  std::sort_heap(__first, __lasti,
1933  __detail::__make_comp_proj(__comp, __proj));
1934  return __lasti;
1935  }
1936 
1937  template<random_access_range _Range,
1938  typename _Comp = ranges::less, typename _Proj = identity>
1939  requires sortable<iterator_t<_Range>, _Comp, _Proj>
1940  constexpr borrowed_iterator_t<_Range>
1941  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1942  {
1943  return (*this)(ranges::begin(__r), ranges::end(__r),
1944  std::move(__comp), std::move(__proj));
1945  }
1946  };
1947 
1948  inline constexpr __sort_heap_fn sort_heap{};
1949 
1950  struct __is_heap_until_fn
1951  {
1952  template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1953  typename _Proj = identity,
1954  indirect_strict_weak_order<projected<_Iter, _Proj>>
1955  _Comp = ranges::less>
1956  constexpr _Iter
1957  operator()(_Iter __first, _Sent __last,
1958  _Comp __comp = {}, _Proj __proj = {}) const
1959  {
1960  iter_difference_t<_Iter> __n = ranges::distance(__first, __last);
1961  iter_difference_t<_Iter> __parent = 0, __child = 1;
1962  for (; __child < __n; ++__child)
1963  if (std::__invoke(__comp,
1964  std::__invoke(__proj, *(__first + __parent)),
1965  std::__invoke(__proj, *(__first + __child))))
1966  return __first + __child;
1967  else if ((__child & 1) == 0)
1968  ++__parent;
1969 
1970  return __first + __n;
1971  }
1972 
1973  template<random_access_range _Range,
1974  typename _Proj = identity,
1975  indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1976  _Comp = ranges::less>
1977  constexpr borrowed_iterator_t<_Range>
1978  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1979  {
1980  return (*this)(ranges::begin(__r), ranges::end(__r),
1981  std::move(__comp), std::move(__proj));
1982  }
1983  };
1984 
1985  inline constexpr __is_heap_until_fn is_heap_until{};
1986 
1987  struct __is_heap_fn
1988  {
1989  template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1990  typename _Proj = identity,
1991  indirect_strict_weak_order<projected<_Iter, _Proj>>
1992  _Comp = ranges::less>
1993  constexpr bool
1994  operator()(_Iter __first, _Sent __last,
1995  _Comp __comp = {}, _Proj __proj = {}) const
1996  {
1997  return (__last
1998  == ranges::is_heap_until(__first, __last,
1999  std::move(__comp),
2000  std::move(__proj)));
2001  }
2002 
2003  template<random_access_range _Range,
2004  typename _Proj = identity,
2005  indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2006  _Comp = ranges::less>
2007  constexpr bool
2008  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2009  {
2010  return (*this)(ranges::begin(__r), ranges::end(__r),
2011  std::move(__comp), std::move(__proj));
2012  }
2013  };
2014 
2015  inline constexpr __is_heap_fn is_heap{};
2016 
2017  struct __sort_fn
2018  {
2019  template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2020  typename _Comp = ranges::less, typename _Proj = identity>
2021  requires sortable<_Iter, _Comp, _Proj>
2022  constexpr _Iter
2023  operator()(_Iter __first, _Sent __last,
2024  _Comp __comp = {}, _Proj __proj = {}) const
2025  {
2026  auto __lasti = ranges::next(__first, __last);
2027  std::sort(std::move(__first), __lasti,
2028  __detail::__make_comp_proj(__comp, __proj));
2029  return __lasti;
2030  }
2031 
2032  template<random_access_range _Range,
2033  typename _Comp = ranges::less, typename _Proj = identity>
2034  requires sortable<iterator_t<_Range>, _Comp, _Proj>
2035  constexpr borrowed_iterator_t<_Range>
2036  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2037  {
2038  return (*this)(ranges::begin(__r), ranges::end(__r),
2039  std::move(__comp), std::move(__proj));
2040  }
2041  };
2042 
2043  inline constexpr __sort_fn sort{};
2044 
2045  struct __stable_sort_fn
2046  {
2047  template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2048  typename _Comp = ranges::less, typename _Proj = identity>
2049  requires sortable<_Iter, _Comp, _Proj>
2050  _Iter
2051  operator()(_Iter __first, _Sent __last,
2052  _Comp __comp = {}, _Proj __proj = {}) const
2053  {
2054  auto __lasti = ranges::next(__first, __last);
2055  std::stable_sort(std::move(__first), __lasti,
2056  __detail::__make_comp_proj(__comp, __proj));
2057  return __lasti;
2058  }
2059 
2060  template<random_access_range _Range,
2061  typename _Comp = ranges::less, typename _Proj = identity>
2062  requires sortable<iterator_t<_Range>, _Comp, _Proj>
2063  borrowed_iterator_t<_Range>
2064  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2065  {
2066  return (*this)(ranges::begin(__r), ranges::end(__r),
2067  std::move(__comp), std::move(__proj));
2068  }
2069  };
2070 
2071  inline constexpr __stable_sort_fn stable_sort{};
2072 
2073  struct __partial_sort_fn
2074  {
2075  template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2076  typename _Comp = ranges::less, typename _Proj = identity>
2077  requires sortable<_Iter, _Comp, _Proj>
2078  constexpr _Iter
2079  operator()(_Iter __first, _Iter __middle, _Sent __last,
2080  _Comp __comp = {}, _Proj __proj = {}) const
2081  {
2082  if (__first == __middle)
2083  return ranges::next(__first, __last);
2084 
2085  ranges::make_heap(__first, __middle, __comp, __proj);
2086  auto __i = __middle;
2087  for (; __i != __last; ++__i)
2088  if (std::__invoke(__comp,
2089  std::__invoke(__proj, *__i),
2090  std::__invoke(__proj, *__first)))
2091  {
2092  ranges::pop_heap(__first, __middle, __comp, __proj);
2093  ranges::iter_swap(__middle-1, __i);
2094  ranges::push_heap(__first, __middle, __comp, __proj);
2095  }
2096  ranges::sort_heap(__first, __middle, __comp, __proj);
2097 
2098  return __i;
2099  }
2100 
2101  template<random_access_range _Range,
2102  typename _Comp = ranges::less, typename _Proj = identity>
2103  requires sortable<iterator_t<_Range>, _Comp, _Proj>
2104  constexpr borrowed_iterator_t<_Range>
2105  operator()(_Range&& __r, iterator_t<_Range> __middle,
2106  _Comp __comp = {}, _Proj __proj = {}) const
2107  {
2108  return (*this)(ranges::begin(__r), std::move(__middle),
2109  ranges::end(__r),
2110  std::move(__comp), std::move(__proj));
2111  }
2112  };
2113 
2114  inline constexpr __partial_sort_fn partial_sort{};
2115 
2116  template<typename _Iter, typename _Out>
2117  using partial_sort_copy_result = in_out_result<_Iter, _Out>;
2118 
2119  struct __partial_sort_copy_fn
2120  {
2121  template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2122  random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2123  typename _Comp = ranges::less,
2124  typename _Proj1 = identity, typename _Proj2 = identity>
2125  requires indirectly_copyable<_Iter1, _Iter2>
2126  && sortable<_Iter2, _Comp, _Proj2>
2127  && indirect_strict_weak_order<_Comp,
2128  projected<_Iter1, _Proj1>,
2129  projected<_Iter2, _Proj2>>
2130  constexpr partial_sort_copy_result<_Iter1, _Iter2>
2131  operator()(_Iter1 __first, _Sent1 __last,
2132  _Iter2 __result_first, _Sent2 __result_last,
2133  _Comp __comp = {},
2134  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2135  {
2136  if (__result_first == __result_last)
2137  {
2138  // TODO: Eliminating the variable __lasti triggers an ICE.
2139  auto __lasti = ranges::next(std::move(__first),
2140  std::move(__last));
2141  return {std::move(__lasti), std::move(__result_first)};
2142  }
2143 
2144  auto __result_real_last = __result_first;
2145  while (__first != __last && __result_real_last != __result_last)
2146  {
2147  *__result_real_last = *__first;
2148  ++__result_real_last;
2149  ++__first;
2150  }
2151 
2152  ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
2153  for (; __first != __last; ++__first)
2154  if (std::__invoke(__comp,
2155  std::__invoke(__proj1, *__first),
2156  std::__invoke(__proj2, *__result_first)))
2157  {
2158  ranges::pop_heap(__result_first, __result_real_last,
2159  __comp, __proj2);
2160  *(__result_real_last-1) = *__first;
2161  ranges::push_heap(__result_first, __result_real_last,
2162  __comp, __proj2);
2163  }
2164  ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
2165 
2166  return {std::move(__first), std::move(__result_real_last)};
2167  }
2168 
2169  template<input_range _Range1, random_access_range _Range2,
2170  typename _Comp = ranges::less,
2171  typename _Proj1 = identity, typename _Proj2 = identity>
2172  requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
2173  && sortable<iterator_t<_Range2>, _Comp, _Proj2>
2174  && indirect_strict_weak_order<_Comp,
2175  projected<iterator_t<_Range1>, _Proj1>,
2176  projected<iterator_t<_Range2>, _Proj2>>
2177  constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>,
2178  borrowed_iterator_t<_Range2>>
2179  operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
2180  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2181  {
2182  return (*this)(ranges::begin(__r), ranges::end(__r),
2183  ranges::begin(__out), ranges::end(__out),
2184  std::move(__comp),
2185  std::move(__proj1), std::move(__proj2));
2186  }
2187  };
2188 
2189  inline constexpr __partial_sort_copy_fn partial_sort_copy{};
2190 
2191  struct __is_sorted_until_fn
2192  {
2193  template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2194  typename _Proj = identity,
2195  indirect_strict_weak_order<projected<_Iter, _Proj>>
2196  _Comp = ranges::less>
2197  constexpr _Iter
2198  operator()(_Iter __first, _Sent __last,
2199  _Comp __comp = {}, _Proj __proj = {}) const
2200  {
2201  if (__first == __last)
2202  return __first;
2203 
2204  auto __next = __first;
2205  for (++__next; __next != __last; __first = __next, (void)++__next)
2206  if (std::__invoke(__comp,
2207  std::__invoke(__proj, *__next),
2208  std::__invoke(__proj, *__first)))
2209  return __next;
2210  return __next;
2211  }
2212 
2213  template<forward_range _Range, typename _Proj = identity,
2214  indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2215  _Comp = ranges::less>
2216  constexpr borrowed_iterator_t<_Range>
2217  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2218  {
2219  return (*this)(ranges::begin(__r), ranges::end(__r),
2220  std::move(__comp), std::move(__proj));
2221  }
2222  };
2223 
2224  inline constexpr __is_sorted_until_fn is_sorted_until{};
2225 
2226  struct __is_sorted_fn
2227  {
2228  template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2229  typename _Proj = identity,
2230  indirect_strict_weak_order<projected<_Iter, _Proj>>
2231  _Comp = ranges::less>
2232  constexpr bool
2233  operator()(_Iter __first, _Sent __last,
2234  _Comp __comp = {}, _Proj __proj = {}) const
2235  {
2236  if (__first == __last)
2237  return true;
2238 
2239  auto __next = __first;
2240  for (++__next; __next != __last; __first = __next, (void)++__next)
2241  if (std::__invoke(__comp,
2242  std::__invoke(__proj, *__next),
2243  std::__invoke(__proj, *__first)))
2244  return false;
2245  return true;
2246  }
2247 
2248  template<forward_range _Range, typename _Proj = identity,
2249  indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2250  _Comp = ranges::less>
2251  constexpr bool
2252  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2253  {
2254  return (*this)(ranges::begin(__r), ranges::end(__r),
2255  std::move(__comp), std::move(__proj));
2256  }
2257  };
2258 
2259  inline constexpr __is_sorted_fn is_sorted{};
2260 
2261  struct __nth_element_fn
2262  {
2263  template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2264  typename _Comp = ranges::less, typename _Proj = identity>
2265  requires sortable<_Iter, _Comp, _Proj>
2266  constexpr _Iter
2267  operator()(_Iter __first, _Iter __nth, _Sent __last,
2268  _Comp __comp = {}, _Proj __proj = {}) const
2269  {
2270  auto __lasti = ranges::next(__first, __last);
2271  std::nth_element(std::move(__first), std::move(__nth), __lasti,
2272  __detail::__make_comp_proj(__comp, __proj));
2273  return __lasti;
2274  }
2275 
2276  template<random_access_range _Range,
2277  typename _Comp = ranges::less, typename _Proj = identity>
2278  requires sortable<iterator_t<_Range>, _Comp, _Proj>
2279  constexpr borrowed_iterator_t<_Range>
2280  operator()(_Range&& __r, iterator_t<_Range> __nth,
2281  _Comp __comp = {}, _Proj __proj = {}) const
2282  {
2283  return (*this)(ranges::begin(__r), std::move(__nth),
2284  ranges::end(__r), std::move(__comp), std::move(__proj));
2285  }
2286  };
2287 
2288  inline constexpr __nth_element_fn nth_element{};
2289 
2290  struct __lower_bound_fn
2291  {
2292  template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2293  typename _Tp, typename _Proj = identity,
2294  indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2295  _Comp = ranges::less>
2296  constexpr _Iter
2297  operator()(_Iter __first, _Sent __last,
2298  const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2299  {
2300  auto __len = ranges::distance(__first, __last);
2301 
2302  while (__len > 0)
2303  {
2304  auto __half = __len / 2;
2305  auto __middle = __first;
2306  ranges::advance(__middle, __half);
2307  if (std::__invoke(__comp, std::__invoke(__proj, *__middle), __value))
2308  {
2309  __first = __middle;
2310  ++__first;
2311  __len = __len - __half - 1;
2312  }
2313  else
2314  __len = __half;
2315  }
2316  return __first;
2317  }
2318 
2319  template<forward_range _Range, typename _Tp, typename _Proj = identity,
2320  indirect_strict_weak_order<const _Tp*,
2321  projected<iterator_t<_Range>, _Proj>>
2322  _Comp = ranges::less>
2323  constexpr borrowed_iterator_t<_Range>
2324  operator()(_Range&& __r,
2325  const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2326  {
2327  return (*this)(ranges::begin(__r), ranges::end(__r),
2328  __value, std::move(__comp), std::move(__proj));
2329  }
2330  };
2331 
2332  inline constexpr __lower_bound_fn lower_bound{};
2333 
2334  struct __upper_bound_fn
2335  {
2336  template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2337  typename _Tp, typename _Proj = identity,
2338  indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2339  _Comp = ranges::less>
2340  constexpr _Iter
2341  operator()(_Iter __first, _Sent __last,
2342  const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2343  {
2344  auto __len = ranges::distance(__first, __last);
2345 
2346  while (__len > 0)
2347  {
2348  auto __half = __len / 2;
2349  auto __middle = __first;
2350  ranges::advance(__middle, __half);
2351  if (std::__invoke(__comp, __value, std::__invoke(__proj, *__middle)))
2352  __len = __half;
2353  else
2354  {
2355  __first = __middle;
2356  ++__first;
2357  __len = __len - __half - 1;
2358  }
2359  }
2360  return __first;
2361  }
2362 
2363  template<forward_range _Range, typename _Tp, typename _Proj = identity,
2364  indirect_strict_weak_order<const _Tp*,
2365  projected<iterator_t<_Range>, _Proj>>
2366  _Comp = ranges::less>
2367  constexpr borrowed_iterator_t<_Range>
2368  operator()(_Range&& __r,
2369  const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2370  {
2371  return (*this)(ranges::begin(__r), ranges::end(__r),
2372  __value, std::move(__comp), std::move(__proj));
2373  }
2374  };
2375 
2376  inline constexpr __upper_bound_fn upper_bound{};
2377 
2378  struct __equal_range_fn
2379  {
2380  template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2381  typename _Tp, typename _Proj = identity,
2382  indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2383  _Comp = ranges::less>
2384  constexpr subrange<_Iter>
2385  operator()(_Iter __first, _Sent __last,
2386  const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2387  {
2388  auto __len = ranges::distance(__first, __last);
2389 
2390  while (__len > 0)
2391  {
2392  auto __half = __len / 2;
2393  auto __middle = __first;
2394  ranges::advance(__middle, __half);
2395  if (std::__invoke(__comp,
2396  std::__invoke(__proj, *__middle),
2397  __value))
2398  {
2399  __first = __middle;
2400  ++__first;
2401  __len = __len - __half - 1;
2402  }
2403  else if (std::__invoke(__comp,
2404  __value,
2405  std::__invoke(__proj, *__middle)))
2406  __len = __half;
2407  else
2408  {
2409  auto __left
2410  = ranges::lower_bound(__first, __middle,
2411  __value, __comp, __proj);
2412  ranges::advance(__first, __len);
2413  auto __right
2414  = ranges::upper_bound(++__middle, __first,
2415  __value, __comp, __proj);
2416  return {__left, __right};
2417  }
2418  }
2419  return {__first, __first};
2420  }
2421 
2422  template<forward_range _Range,
2423  typename _Tp, typename _Proj = identity,
2424  indirect_strict_weak_order<const _Tp*,
2425  projected<iterator_t<_Range>, _Proj>>
2426  _Comp = ranges::less>
2427  constexpr borrowed_subrange_t<_Range>
2428  operator()(_Range&& __r, const _Tp& __value,
2429  _Comp __comp = {}, _Proj __proj = {}) const
2430  {
2431  return (*this)(ranges::begin(__r), ranges::end(__r),
2432  __value, std::move(__comp), std::move(__proj));
2433  }
2434  };
2435 
2436  inline constexpr __equal_range_fn equal_range{};
2437 
2438  struct __binary_search_fn
2439  {
2440  template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2441  typename _Tp, typename _Proj = identity,
2442  indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2443  _Comp = ranges::less>
2444  constexpr bool
2445  operator()(_Iter __first, _Sent __last,
2446  const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2447  {
2448  auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
2449  if (__i == __last)
2450  return false;
2451  return !(bool)std::__invoke(__comp, __value,
2452  std::__invoke(__proj, *__i));
2453  }
2454 
2455  template<forward_range _Range,
2456  typename _Tp, typename _Proj = identity,
2457  indirect_strict_weak_order<const _Tp*,
2458  projected<iterator_t<_Range>, _Proj>>
2459  _Comp = ranges::less>
2460  constexpr bool
2461  operator()(_Range&& __r, const _Tp& __value, _Comp __comp = {},
2462  _Proj __proj = {}) const
2463  {
2464  return (*this)(ranges::begin(__r), ranges::end(__r),
2465  __value, std::move(__comp), std::move(__proj));
2466  }
2467  };
2468 
2469  inline constexpr __binary_search_fn binary_search{};
2470 
2471  struct __is_partitioned_fn
2472  {
2473  template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2474  typename _Proj = identity,
2475  indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2476  constexpr bool
2477  operator()(_Iter __first, _Sent __last,
2478  _Pred __pred, _Proj __proj = {}) const
2479  {
2480  __first = ranges::find_if_not(std::move(__first), __last,
2481  __pred, __proj);
2482  if (__first == __last)
2483  return true;
2484  ++__first;
2485  return ranges::none_of(std::move(__first), std::move(__last),
2486  std::move(__pred), std::move(__proj));
2487  }
2488 
2489  template<input_range _Range, typename _Proj = identity,
2490  indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2491  _Pred>
2492  constexpr bool
2493  operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
2494  {
2495  return (*this)(ranges::begin(__r), ranges::end(__r),
2496  std::move(__pred), std::move(__proj));
2497  }
2498  };
2499 
2500  inline constexpr __is_partitioned_fn is_partitioned{};
2501 
2502  struct __partition_fn
2503  {
2504  template<permutable _Iter, sentinel_for<_Iter> _Sent,
2505  typename _Proj = identity,
2506  indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2507  constexpr subrange<_Iter>
2508  operator()(_Iter __first, _Sent __last,
2509  _Pred __pred, _Proj __proj = {}) const
2510  {
2511  if constexpr (bidirectional_iterator<_Iter>)
2512  {
2513  auto __lasti = ranges::next(__first, __last);
2514  auto __tail = __lasti;
2515  for (;;)
2516  {
2517  for (;;)
2518  if (__first == __tail)
2519  return {std::move(__first), std::move(__lasti)};
2520  else if (std::__invoke(__pred,
2521  std::__invoke(__proj, *__first)))
2522  ++__first;
2523  else
2524  break;
2525  --__tail;
2526  for (;;)
2527  if (__first == __tail)
2528  return {std::move(__first), std::move(__lasti)};
2529  else if (!(bool)std::__invoke(__pred,
2530  std::__invoke(__proj, *__tail)))
2531  --__tail;
2532  else
2533  break;
2534  ranges::iter_swap(__first, __tail);
2535  ++__first;
2536  }
2537  }
2538  else
2539  {
2540  if (__first == __last)
2541  return {__first, __first};
2542 
2543  while (std::__invoke(__pred, std::__invoke(__proj, *__first)))
2544  if (++__first == __last)
2545  return {__first, __first};
2546 
2547  auto __next = __first;
2548  while (++__next != __last)
2549  if (std::__invoke(__pred, std::__invoke(__proj, *__next)))
2550  {
2551  ranges::iter_swap(__first, __next);
2552  ++__first;
2553  }
2554 
2555  return {std::move(__first), std::move(__next)};
2556  }
2557  }
2558 
2559  template<forward_range _Range, typename _Proj = identity,
2560  indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2561  _Pred>
2562  requires permutable<iterator_t<_Range>>
2563  constexpr borrowed_subrange_t<_Range>
2564  operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
2565  {
2566  return (*this)(ranges::begin(__r), ranges::end(__r),
2567  std::move(__pred), std::move(__proj));
2568  }
2569  };
2570 
2571  inline constexpr __partition_fn partition{};
2572 
2573  struct __stable_partition_fn
2574  {
2575  template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2576  typename _Proj = identity,
2577  indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2578  requires permutable<_Iter>
2579  subrange<_Iter>
2580  operator()(_Iter __first, _Sent __last,
2581  _Pred __pred, _Proj __proj = {}) const
2582  {
2583  auto __lasti = ranges::next(__first, __last);
2584  auto __middle
2585  = std::stable_partition(std::move(__first), __lasti,
2586  __detail::__make_pred_proj(__pred, __proj));
2587  return {std::move(__middle), std::move(__lasti)};
2588  }
2589 
2590  template<bidirectional_range _Range, typename _Proj = identity,
2591  indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2592  _Pred>
2593  requires permutable<iterator_t<_Range>>
2594  borrowed_subrange_t<_Range>
2595  operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
2596  {
2597  return (*this)(ranges::begin(__r), ranges::end(__r),
2598  std::move(__pred), std::move(__proj));
2599  }
2600  };
2601 
2602  inline constexpr __stable_partition_fn stable_partition{};
2603 
2604  template<typename _Iter, typename _Out1, typename _Out2>
2605  struct in_out_out_result
2606  {
2607  [[no_unique_address]] _Iter in;
2608  [[no_unique_address]] _Out1 out1;
2609  [[no_unique_address]] _Out2 out2;
2610 
2611  template<typename _IIter, typename _OOut1, typename _OOut2>
2612  requires convertible_to<const _Iter&, _IIter>
2613  && convertible_to<const _Out1&, _OOut1>
2614  && convertible_to<const _Out2&, _OOut2>
2615  constexpr
2616  operator in_out_out_result<_IIter, _OOut1, _OOut2>() const &
2617  { return {in, out1, out2}; }
2618 
2619  template<typename _IIter, typename _OOut1, typename _OOut2>
2620  requires convertible_to<_Iter, _IIter>
2621  && convertible_to<_Out1, _OOut1>
2622  && convertible_to<_Out2, _OOut2>
2623  constexpr
2624  operator in_out_out_result<_IIter, _OOut1, _OOut2>() &&
2625  { return {std::move(in), std::move(out1), std::move(out2)}; }
2626  };
2627 
2628  template<typename _Iter, typename _Out1, typename _Out2>
2629  using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>;
2630 
2631  struct __partition_copy_fn
2632  {
2633  template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2634  weakly_incrementable _Out1, weakly_incrementable _Out2,
2635  typename _Proj = identity,
2636  indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2637  requires indirectly_copyable<_Iter, _Out1>
2638  && indirectly_copyable<_Iter, _Out2>
2639  constexpr partition_copy_result<_Iter, _Out1, _Out2>
2640  operator()(_Iter __first, _Sent __last,
2641  _Out1 __out_true, _Out2 __out_false,
2642  _Pred __pred, _Proj __proj = {}) const
2643  {
2644  for (; __first != __last; ++__first)
2645  if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
2646  {
2647  *__out_true = *__first;
2648  ++__out_true;
2649  }
2650  else
2651  {
2652  *__out_false = *__first;
2653  ++__out_false;
2654  }
2655 
2656  return {std::move(__first),
2657  std::move(__out_true), std::move(__out_false)};
2658  }
2659 
2660  template<input_range _Range, weakly_incrementable _Out1,
2661  weakly_incrementable _Out2,
2662  typename _Proj = identity,
2663  indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2664  _Pred>
2665  requires indirectly_copyable<iterator_t<_Range>, _Out1>
2666  && indirectly_copyable<iterator_t<_Range>, _Out2>
2667  constexpr partition_copy_result<borrowed_iterator_t<_Range>, _Out1, _Out2>
2668  operator()(_Range&& __r, _Out1 __out_true, _Out2 __out_false,
2669  _Pred __pred, _Proj __proj = {}) const
2670  {
2671  return (*this)(ranges::begin(__r), ranges::end(__r),
2672  std::move(__out_true), std::move(__out_false),
2673  std::move(__pred), std::move(__proj));
2674  }
2675  };
2676 
2677  inline constexpr __partition_copy_fn partition_copy{};
2678 
2679  struct __partition_point_fn
2680  {
2681  template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2682  typename _Proj = identity,
2683  indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2684  constexpr _Iter
2685  operator()(_Iter __first, _Sent __last,
2686  _Pred __pred, _Proj __proj = {}) const
2687  {
2688  auto __len = ranges::distance(__first, __last);
2689 
2690  while (__len > 0)
2691  {
2692  auto __half = __len / 2;
2693  auto __middle = __first;
2694  ranges::advance(__middle, __half);
2695  if (std::__invoke(__pred, std::__invoke(__proj, *__middle)))
2696  {
2697  __first = __middle;
2698  ++__first;
2699  __len = __len - __half - 1;
2700  }
2701  else
2702  __len = __half;
2703  }
2704  return __first;
2705  }
2706 
2707  template<forward_range _Range, typename _Proj = identity,
2708  indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2709  _Pred>
2710  constexpr borrowed_iterator_t<_Range>
2711  operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
2712  {
2713  return (*this)(ranges::begin(__r), ranges::end(__r),
2714  std::move(__pred), std::move(__proj));
2715  }
2716  };
2717 
2718  inline constexpr __partition_point_fn partition_point{};
2719 
2720  template<typename _Iter1, typename _Iter2, typename _Out>
2721  using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2722 
2723  struct __merge_fn
2724  {
2725  template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2726  input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2727  weakly_incrementable _Out, typename _Comp = ranges::less,
2728  typename _Proj1 = identity, typename _Proj2 = identity>
2729  requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2730  constexpr merge_result<_Iter1, _Iter2, _Out>
2731  operator()(_Iter1 __first1, _Sent1 __last1,
2732  _Iter2 __first2, _Sent2 __last2, _Out __result,
2733  _Comp __comp = {},
2734  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2735  {
2736  while (__first1 != __last1 && __first2 != __last2)
2737  {
2738  if (std::__invoke(__comp,
2739  std::__invoke(__proj2, *__first2),
2740  std::__invoke(__proj1, *__first1)))
2741  {
2742  *__result = *__first2;
2743  ++__first2;
2744  }
2745  else
2746  {
2747  *__result = *__first1;
2748  ++__first1;
2749  }
2750  ++__result;
2751  }
2752  auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
2753  std::move(__result));
2754  auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
2755  std::move(__copy1.out));
2756  return { std::move(__copy1.in), std::move(__copy2.in),
2757  std::move(__copy2.out) };
2758  }
2759 
2760  template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2761  typename _Comp = ranges::less,
2762  typename _Proj1 = identity, typename _Proj2 = identity>
2763  requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2764  _Comp, _Proj1, _Proj2>
2765  constexpr merge_result<borrowed_iterator_t<_Range1>,
2766  borrowed_iterator_t<_Range2>,
2767  _Out>
2768  operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2769  _Comp __comp = {},
2770  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2771  {
2772  return (*this)(ranges::begin(__r1), ranges::end(__r1),
2773  ranges::begin(__r2), ranges::end(__r2),
2774  std::move(__result), std::move(__comp),
2775  std::move(__proj1), std::move(__proj2));
2776  }
2777  };
2778 
2779  inline constexpr __merge_fn merge{};
2780 
2781  struct __inplace_merge_fn
2782  {
2783  template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2784  typename _Comp = ranges::less,
2785  typename _Proj = identity>
2786  requires sortable<_Iter, _Comp, _Proj>
2787  _Iter
2788  operator()(_Iter __first, _Iter __middle, _Sent __last,
2789  _Comp __comp = {}, _Proj __proj = {}) const
2790  {
2791  auto __lasti = ranges::next(__first, __last);
2792  std::inplace_merge(std::move(__first), std::move(__middle), __lasti,
2793  __detail::__make_comp_proj(__comp, __proj));
2794  return __lasti;
2795  }
2796 
2797  template<bidirectional_range _Range,
2798  typename _Comp = ranges::less, typename _Proj = identity>
2799  requires sortable<iterator_t<_Range>, _Comp, _Proj>
2800  borrowed_iterator_t<_Range>
2801  operator()(_Range&& __r, iterator_t<_Range> __middle,
2802  _Comp __comp = {}, _Proj __proj = {}) const
2803  {
2804  return (*this)(ranges::begin(__r), std::move(__middle),
2805  ranges::end(__r),
2806  std::move(__comp), std::move(__proj));
2807  }
2808  };
2809 
2810  inline constexpr __inplace_merge_fn inplace_merge{};
2811 
2812  struct __includes_fn
2813  {
2814  template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2815  input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2816  typename _Proj1 = identity, typename _Proj2 = identity,
2817  indirect_strict_weak_order<projected<_Iter1, _Proj1>,
2818  projected<_Iter2, _Proj2>>
2819  _Comp = ranges::less>
2820  constexpr bool
2821  operator()(_Iter1 __first1, _Sent1 __last1,
2822  _Iter2 __first2, _Sent2 __last2,
2823  _Comp __comp = {},
2824  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2825  {
2826  while (__first1 != __last1 && __first2 != __last2)
2827  if (std::__invoke(__comp,
2828  std::__invoke(__proj2, *__first2),
2829  std::__invoke(__proj1, *__first1)))
2830  return false;
2831  else if (std::__invoke(__comp,
2832  std::__invoke(__proj1, *__first1),
2833  std::__invoke(__proj2, *__first2)))
2834  ++__first1;
2835  else
2836  {
2837  ++__first1;
2838  ++__first2;
2839  }
2840 
2841  return __first2 == __last2;
2842  }
2843 
2844  template<input_range _Range1, input_range _Range2,
2845  typename _Proj1 = identity, typename _Proj2 = identity,
2846  indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
2847  projected<iterator_t<_Range2>, _Proj2>>
2848  _Comp = ranges::less>
2849  constexpr bool
2850  operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
2851  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2852  {
2853  return (*this)(ranges::begin(__r1), ranges::end(__r1),
2854  ranges::begin(__r2), ranges::end(__r2),
2855  std::move(__comp),
2856  std::move(__proj1), std::move(__proj2));
2857  }
2858  };
2859 
2860  inline constexpr __includes_fn includes{};
2861 
2862  template<typename _Iter1, typename _Iter2, typename _Out>
2863  using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2864 
2865  struct __set_union_fn
2866  {
2867  template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2868  input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2869  weakly_incrementable _Out, typename _Comp = ranges::less,
2870  typename _Proj1 = identity, typename _Proj2 = identity>
2871  requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2872  constexpr set_union_result<_Iter1, _Iter2, _Out>
2873  operator()(_Iter1 __first1, _Sent1 __last1,
2874  _Iter2 __first2, _Sent2 __last2,
2875  _Out __result, _Comp __comp = {},
2876  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2877  {
2878  while (__first1 != __last1 && __first2 != __last2)
2879  {
2880  if (std::__invoke(__comp,
2881  std::__invoke(__proj1, *__first1),
2882  std::__invoke(__proj2, *__first2)))
2883  {
2884  *__result = *__first1;
2885  ++__first1;
2886  }
2887  else if (std::__invoke(__comp,
2888  std::__invoke(__proj2, *__first2),
2889  std::__invoke(__proj1, *__first1)))
2890  {
2891  *__result = *__first2;
2892  ++__first2;
2893  }
2894  else
2895  {
2896  *__result = *__first1;
2897  ++__first1;
2898  ++__first2;
2899  }
2900  ++__result;
2901  }
2902  auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
2903  std::move(__result));
2904  auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
2905  std::move(__copy1.out));
2906  return {std::move(__copy1.in), std::move(__copy2.in),
2907  std::move(__copy2.out)};
2908  }
2909 
2910  template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2911  typename _Comp = ranges::less,
2912  typename _Proj1 = identity, typename _Proj2 = identity>
2913  requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2914  _Comp, _Proj1, _Proj2>
2915  constexpr set_union_result<borrowed_iterator_t<_Range1>,
2916  borrowed_iterator_t<_Range2>, _Out>
2917  operator()(_Range1&& __r1, _Range2&& __r2,
2918  _Out __result, _Comp __comp = {},
2919  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2920  {
2921  return (*this)(ranges::begin(__r1), ranges::end(__r1),
2922  ranges::begin(__r2), ranges::end(__r2),
2923  std::move(__result), std::move(__comp),
2924  std::move(__proj1), std::move(__proj2));
2925  }
2926  };
2927 
2928  inline constexpr __set_union_fn set_union{};
2929 
2930  template<typename _Iter1, typename _Iter2, typename _Out>
2931  using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2932 
2933  struct __set_intersection_fn
2934  {
2935  template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2936  input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2937  weakly_incrementable _Out, typename _Comp = ranges::less,
2938  typename _Proj1 = identity, typename _Proj2 = identity>
2939  requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2940  constexpr set_intersection_result<_Iter1, _Iter2, _Out>
2941  operator()(_Iter1 __first1, _Sent1 __last1,
2942  _Iter2 __first2, _Sent2 __last2, _Out __result,
2943  _Comp __comp = {},
2944  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2945  {
2946  while (__first1 != __last1 && __first2 != __last2)
2947  if (std::__invoke(__comp,
2948  std::__invoke(__proj1, *__first1),
2949  std::__invoke(__proj2, *__first2)))
2950  ++__first1;
2951  else if (std::__invoke(__comp,
2952  std::__invoke(__proj2, *__first2),
2953  std::__invoke(__proj1, *__first1)))
2954  ++__first2;
2955  else
2956  {
2957  *__result = *__first1;
2958  ++__first1;
2959  ++__first2;
2960  ++__result;
2961  }
2962  // TODO: Eliminating these variables triggers an ICE.
2963  auto __last1i = ranges::next(std::move(__first1), std::move(__last1));
2964  auto __last2i = ranges::next(std::move(__first2), std::move(__last2));
2965  return {std::move(__last1i), std::move(__last2i), std::move(__result)};
2966  }
2967 
2968  template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2969  typename _Comp = ranges::less,
2970  typename _Proj1 = identity, typename _Proj2 = identity>
2971  requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2972  _Comp, _Proj1, _Proj2>
2973  constexpr set_intersection_result<borrowed_iterator_t<_Range1>,
2974  borrowed_iterator_t<_Range2>, _Out>
2975  operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2976  _Comp __comp = {},
2977  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2978  {
2979  return (*this)(ranges::begin(__r1), ranges::end(__r1),
2980  ranges::begin(__r2), ranges::end(__r2),
2981  std::move(__result), std::move(__comp),
2982  std::move(__proj1), std::move(__proj2));
2983  }
2984  };
2985 
2986  inline constexpr __set_intersection_fn set_intersection{};
2987 
2988  template<typename _Iter, typename _Out>
2989  using set_difference_result = in_out_result<_Iter, _Out>;
2990 
2991  struct __set_difference_fn
2992  {
2993  template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2994  input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2995  weakly_incrementable _Out, typename _Comp = ranges::less,
2996  typename _Proj1 = identity, typename _Proj2 = identity>
2997  requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2998  constexpr set_difference_result<_Iter1, _Out>
2999  operator()(_Iter1 __first1, _Sent1 __last1,
3000  _Iter2 __first2, _Sent2 __last2, _Out __result,
3001  _Comp __comp = {},
3002  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3003  {
3004  while (__first1 != __last1 && __first2 != __last2)
3005  if (std::__invoke(__comp,
3006  std::__invoke(__proj1, *__first1),
3007  std::__invoke(__proj2, *__first2)))
3008  {
3009  *__result = *__first1;
3010  ++__first1;
3011  ++__result;
3012  }
3013  else if (std::__invoke(__comp,
3014  std::__invoke(__proj2, *__first2),
3015  std::__invoke(__proj1, *__first1)))
3016  ++__first2;
3017  else
3018  {
3019  ++__first1;
3020  ++__first2;
3021  }
3022  return ranges::copy(std::move(__first1), std::move(__last1),
3023  std::move(__result));
3024  }
3025 
3026  template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
3027  typename _Comp = ranges::less,
3028  typename _Proj1 = identity, typename _Proj2 = identity>
3029  requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
3030  _Comp, _Proj1, _Proj2>
3031  constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out>
3032  operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
3033  _Comp __comp = {},
3034  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3035  {
3036  return (*this)(ranges::begin(__r1), ranges::end(__r1),
3037  ranges::begin(__r2), ranges::end(__r2),
3038  std::move(__result), std::move(__comp),
3039  std::move(__proj1), std::move(__proj2));
3040  }
3041  };
3042 
3043  inline constexpr __set_difference_fn set_difference{};
3044 
3045  template<typename _Iter1, typename _Iter2, typename _Out>
3046  using set_symmetric_difference_result
3047  = in_in_out_result<_Iter1, _Iter2, _Out>;
3048 
3049  struct __set_symmetric_difference_fn
3050  {
3051  template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3052  input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3053  weakly_incrementable _Out, typename _Comp = ranges::less,
3054  typename _Proj1 = identity, typename _Proj2 = identity>
3055  requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
3056  constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out>
3057  operator()(_Iter1 __first1, _Sent1 __last1,
3058  _Iter2 __first2, _Sent2 __last2,
3059  _Out __result, _Comp __comp = {},
3060  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3061  {
3062  while (__first1 != __last1 && __first2 != __last2)
3063  if (std::__invoke(__comp,
3064  std::__invoke(__proj1, *__first1),
3065  std::__invoke(__proj2, *__first2)))
3066  {
3067  *__result = *__first1;
3068  ++__first1;
3069  ++__result;
3070  }
3071  else if (std::__invoke(__comp,
3072  std::__invoke(__proj2, *__first2),
3073  std::__invoke(__proj1, *__first1)))
3074  {
3075  *__result = *__first2;
3076  ++__first2;
3077  ++__result;
3078  }
3079  else
3080  {
3081  ++__first1;
3082  ++__first2;
3083  }
3084  auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
3085  std::move(__result));
3086  auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
3087  std::move(__copy1.out));
3088  return {std::move(__copy1.in), std::move(__copy2.in),
3089  std::move(__copy2.out)};
3090  }
3091 
3092  template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
3093  typename _Comp = ranges::less,
3094  typename _Proj1 = identity, typename _Proj2 = identity>
3095  requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
3096  _Comp, _Proj1, _Proj2>
3097  constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>,
3098  borrowed_iterator_t<_Range2>,
3099  _Out>
3100  operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
3101  _Comp __comp = {},
3102  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3103  {
3104  return (*this)(ranges::begin(__r1), ranges::end(__r1),
3105  ranges::begin(__r2), ranges::end(__r2),
3106  std::move(__result), std::move(__comp),
3107  std::move(__proj1), std::move(__proj2));
3108  }
3109  };
3110 
3111  inline constexpr __set_symmetric_difference_fn set_symmetric_difference{};
3112 
3113  struct __min_fn
3114  {
3115  template<typename _Tp, typename _Proj = identity,
3116  indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3117  _Comp = ranges::less>
3118  constexpr const _Tp&
3119  operator()(const _Tp& __a, const _Tp& __b,
3120  _Comp __comp = {}, _Proj __proj = {}) const
3121  {
3122  if (std::__invoke(__comp,
3123  std::__invoke(__proj, __b),
3124  std::__invoke(__proj, __a)))
3125  return __b;
3126  else
3127  return __a;
3128  }
3129 
3130  template<input_range _Range, typename _Proj = identity,
3131  indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3132  _Comp = ranges::less>
3133  requires indirectly_copyable_storable<iterator_t<_Range>,
3134  range_value_t<_Range>*>
3135  constexpr range_value_t<_Range>
3136  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3137  {
3138  auto __first = ranges::begin(__r);
3139  auto __last = ranges::end(__r);
3140  __glibcxx_assert(__first != __last);
3141  auto __result = *__first;
3142  while (++__first != __last)
3143  {
3144  auto __tmp = *__first;
3145  if (std::__invoke(__comp,
3146  std::__invoke(__proj, __tmp),
3147  std::__invoke(__proj, __result)))
3148  __result = std::move(__tmp);
3149  }
3150  return __result;
3151  }
3152 
3153  template<copyable _Tp, typename _Proj = identity,
3154  indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3155  _Comp = ranges::less>
3156  constexpr _Tp
3157  operator()(initializer_list<_Tp> __r,
3158  _Comp __comp = {}, _Proj __proj = {}) const
3159  {
3160  return (*this)(ranges::subrange(__r),
3161  std::move(__comp), std::move(__proj));
3162  }
3163  };
3164 
3165  inline constexpr __min_fn min{};
3166 
3167  struct __max_fn
3168  {
3169  template<typename _Tp, typename _Proj = identity,
3170  indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3171  _Comp = ranges::less>
3172  constexpr const _Tp&
3173  operator()(const _Tp& __a, const _Tp& __b,
3174  _Comp __comp = {}, _Proj __proj = {}) const
3175  {
3176  if (std::__invoke(__comp,
3177  std::__invoke(__proj, __a),
3178  std::__invoke(__proj, __b)))
3179  return __b;
3180  else
3181  return __a;
3182  }
3183 
3184  template<input_range _Range, typename _Proj = identity,
3185  indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3186  _Comp = ranges::less>
3187  requires indirectly_copyable_storable<iterator_t<_Range>,
3188  range_value_t<_Range>*>
3189  constexpr range_value_t<_Range>
3190  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3191  {
3192  auto __first = ranges::begin(__r);
3193  auto __last = ranges::end(__r);
3194  __glibcxx_assert(__first != __last);
3195  auto __result = *__first;
3196  while (++__first != __last)
3197  {
3198  auto __tmp = *__first;
3199  if (std::__invoke(__comp,
3200  std::__invoke(__proj, __result),
3201  std::__invoke(__proj, __tmp)))
3202  __result = std::move(__tmp);
3203  }
3204  return __result;
3205  }
3206 
3207  template<copyable _Tp, typename _Proj = identity,
3208  indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3209  _Comp = ranges::less>
3210  constexpr _Tp
3211  operator()(initializer_list<_Tp> __r,
3212  _Comp __comp = {}, _Proj __proj = {}) const
3213  {
3214  return (*this)(ranges::subrange(__r),
3215  std::move(__comp), std::move(__proj));
3216  }
3217  };
3218 
3219  inline constexpr __max_fn max{};
3220 
3221  struct __clamp_fn
3222  {
3223  template<typename _Tp, typename _Proj = identity,
3224  indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp
3225  = ranges::less>
3226  constexpr const _Tp&
3227  operator()(const _Tp& __val, const _Tp& __lo, const _Tp& __hi,
3228  _Comp __comp = {}, _Proj __proj = {}) const
3229  {
3230  __glibcxx_assert(!(std::__invoke(__comp,
3231  std::__invoke(__proj, __hi),
3232  std::__invoke(__proj, __lo))));
3233  auto&& __proj_val = std::__invoke(__proj, __val);
3234  if (std::__invoke(__comp, __proj_val, std::__invoke(__proj, __lo)))
3235  return __lo;
3236  else if (std::__invoke(__comp, std::__invoke(__proj, __hi), __proj_val))
3237  return __hi;
3238  else
3239  return __val;
3240  }
3241  };
3242 
3243  inline constexpr __clamp_fn clamp{};
3244 
3245  template<typename _Tp>
3246  struct min_max_result
3247  {
3248  [[no_unique_address]] _Tp min;
3249  [[no_unique_address]] _Tp max;
3250 
3251  template<typename _Tp2>
3252  requires convertible_to<const _Tp&, _Tp2>
3253  constexpr
3254  operator min_max_result<_Tp2>() const &
3255  { return {min, max}; }
3256 
3257  template<typename _Tp2>
3258  requires convertible_to<_Tp, _Tp2>
3259  constexpr
3260  operator min_max_result<_Tp2>() &&
3261  { return {std::move(min), std::move(max)}; }
3262  };
3263 
3264  template<typename _Tp>
3265  using minmax_result = min_max_result<_Tp>;
3266 
3267  struct __minmax_fn
3268  {
3269  template<typename _Tp, typename _Proj = identity,
3270  indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3271  _Comp = ranges::less>
3272  constexpr minmax_result<const _Tp&>
3273  operator()(const _Tp& __a, const _Tp& __b,
3274  _Comp __comp = {}, _Proj __proj = {}) const
3275  {
3276  if (std::__invoke(__comp,
3277  std::__invoke(__proj, __b),
3278  std::__invoke(__proj, __a)))
3279  return {__b, __a};
3280  else
3281  return {__a, __b};
3282  }
3283 
3284  template<input_range _Range, typename _Proj = identity,
3285  indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3286  _Comp = ranges::less>
3287  requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*>
3288  constexpr minmax_result<range_value_t<_Range>>
3289  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3290  {
3291  auto __first = ranges::begin(__r);
3292  auto __last = ranges::end(__r);
3293  __glibcxx_assert(__first != __last);
3294  auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3295  minmax_result<range_value_t<_Range>> __result = {*__first, *__first};
3296  if (++__first == __last)
3297  return __result;
3298  else
3299  {
3300  // At this point __result.min == __result.max, so a single
3301  // comparison with the next element suffices.
3302  auto&& __val = *__first;
3303  if (__comp_proj(__val, __result.min))
3304  __result.min = std::forward<decltype(__val)>(__val);
3305  else
3306  __result.max = std::forward<decltype(__val)>(__val);
3307  }
3308  while (++__first != __last)
3309  {
3310  // Now process two elements at a time so that we perform at most
3311  // 1 + 3*(N-2)/2 comparisons in total (each of the (N-2)/2
3312  // iterations of this loop performs three comparisons).
3313  range_value_t<_Range> __val1 = *__first;
3314  if (++__first == __last)
3315  {
3316  // N is odd; in this final iteration, we perform at most two
3317  // comparisons, for a total of 1 + 3*(N-3)/2 + 2 comparisons,
3318  // which is not more than 3*N/2, as required.
3319  if (__comp_proj(__val1, __result.min))
3320  __result.min = std::move(__val1);
3321  else if (!__comp_proj(__val1, __result.max))
3322  __result.max = std::move(__val1);
3323  break;
3324  }
3325  auto&& __val2 = *__first;
3326  if (!__comp_proj(__val2, __val1))
3327  {
3328  if (__comp_proj(__val1, __result.min))
3329  __result.min = std::move(__val1);
3330  if (!__comp_proj(__val2, __result.max))
3331  __result.max = std::forward<decltype(__val2)>(__val2);
3332  }
3333  else
3334  {
3335  if (__comp_proj(__val2, __result.min))
3336  __result.min = std::forward<decltype(__val2)>(__val2);
3337  if (!__comp_proj(__val1, __result.max))
3338  __result.max = std::move(__val1);
3339  }
3340  }
3341  return __result;
3342  }
3343 
3344  template<copyable _Tp, typename _Proj = identity,
3345  indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3346  _Comp = ranges::less>
3347  constexpr minmax_result<_Tp>
3348  operator()(initializer_list<_Tp> __r,
3349  _Comp __comp = {}, _Proj __proj = {}) const
3350  {
3351  return (*this)(ranges::subrange(__r),
3352  std::move(__comp), std::move(__proj));
3353  }
3354  };
3355 
3356  inline constexpr __minmax_fn minmax{};
3357 
3358  struct __min_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, *__i),
3376  std::__invoke(__proj, *__first)))
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 __min_element_fn min_element{};
3394 
3395  struct __max_element_fn
3396  {
3397  template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3398  typename _Proj = identity,
3399  indirect_strict_weak_order<projected<_Iter, _Proj>>
3400  _Comp = ranges::less>
3401  constexpr _Iter
3402  operator()(_Iter __first, _Sent __last,
3403  _Comp __comp = {}, _Proj __proj = {}) const
3404  {
3405  if (__first == __last)
3406  return __first;
3407 
3408  auto __i = __first;
3409  while (++__i != __last)
3410  {
3411  if (std::__invoke(__comp,
3412  std::__invoke(__proj, *__first),
3413  std::__invoke(__proj, *__i)))
3414  __first = __i;
3415  }
3416  return __first;
3417  }
3418 
3419  template<forward_range _Range, typename _Proj = identity,
3420  indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3421  _Comp = ranges::less>
3422  constexpr borrowed_iterator_t<_Range>
3423  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3424  {
3425  return (*this)(ranges::begin(__r), ranges::end(__r),
3426  std::move(__comp), std::move(__proj));
3427  }
3428  };
3429 
3430  inline constexpr __max_element_fn max_element{};
3431 
3432  template<typename _Iter>
3433  using minmax_element_result = min_max_result<_Iter>;
3434 
3435  struct __minmax_element_fn
3436  {
3437  template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3438  typename _Proj = identity,
3439  indirect_strict_weak_order<projected<_Iter, _Proj>>
3440  _Comp = ranges::less>
3441  constexpr minmax_element_result<_Iter>
3442  operator()(_Iter __first, _Sent __last,
3443  _Comp __comp = {}, _Proj __proj = {}) const
3444  {
3445  auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3446  minmax_element_result<_Iter> __result = {__first, __first};
3447  if (__first == __last || ++__first == __last)
3448  return __result;
3449  else
3450  {
3451  // At this point __result.min == __result.max, so a single
3452  // comparison with the next element suffices.
3453  if (__comp_proj(*__first, *__result.min))
3454  __result.min = __first;
3455  else
3456  __result.max = __first;
3457  }
3458  while (++__first != __last)
3459  {
3460  // Now process two elements at a time so that we perform at most
3461  // 1 + 3*(N-2)/2 comparisons in total (each of the (N-2)/2
3462  // iterations of this loop performs three comparisons).
3463  auto __prev = __first;
3464  if (++__first == __last)
3465  {
3466  // N is odd; in this final iteration, we perform at most two
3467  // comparisons, for a total of 1 + 3*(N-3)/2 + 2 comparisons,
3468  // which is not more than 3*N/2, as required.
3469  if (__comp_proj(*__prev, *__result.min))
3470  __result.min = __prev;
3471  else if (!__comp_proj(*__prev, *__result.max))
3472  __result.max = __prev;
3473  break;
3474  }
3475  if (!__comp_proj(*__first, *__prev))
3476  {
3477  if (__comp_proj(*__prev, *__result.min))
3478  __result.min = __prev;
3479  if (!__comp_proj(*__first, *__result.max))
3480  __result.max = __first;
3481  }
3482  else
3483  {
3484  if (__comp_proj(*__first, *__result.min))
3485  __result.min = __first;
3486  if (!__comp_proj(*__prev, *__result.max))
3487  __result.max = __prev;
3488  }
3489  }
3490  return __result;
3491  }
3492 
3493  template<forward_range _Range, typename _Proj = identity,
3494  indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3495  _Comp = ranges::less>
3496  constexpr minmax_element_result<borrowed_iterator_t<_Range>>
3497  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3498  {
3499  return (*this)(ranges::begin(__r), ranges::end(__r),
3500  std::move(__comp), std::move(__proj));
3501  }
3502  };
3503 
3504  inline constexpr __minmax_element_fn minmax_element{};
3505 
3506  struct __lexicographical_compare_fn
3507  {
3508  template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3509  input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3510  typename _Proj1 = identity, typename _Proj2 = identity,
3511  indirect_strict_weak_order<projected<_Iter1, _Proj1>,
3512  projected<_Iter2, _Proj2>>
3513  _Comp = ranges::less>
3514  constexpr bool
3515  operator()(_Iter1 __first1, _Sent1 __last1,
3516  _Iter2 __first2, _Sent2 __last2,
3517  _Comp __comp = {},
3518  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3519  {
3520  if constexpr (__detail::__is_normal_iterator<_Iter1>
3521  && same_as<_Iter1, _Sent1>)
3522  return (*this)(__first1.base(), __last1.base(),
3523  std::move(__first2), std::move(__last2),
3524  std::move(__comp),
3525  std::move(__proj1), std::move(__proj2));
3526  else if constexpr (__detail::__is_normal_iterator<_Iter2>
3527  && same_as<_Iter2, _Sent2>)
3528  return (*this)(std::move(__first1), std::move(__last1),
3529  __first2.base(), __last2.base(),
3530  std::move(__comp),
3531  std::move(__proj1), std::move(__proj2));
3532  else
3533  {
3534  constexpr bool __sized_iters
3535  = (sized_sentinel_for<_Sent1, _Iter1>
3536  && sized_sentinel_for<_Sent2, _Iter2>);
3537  if constexpr (__sized_iters)
3538  {
3539  using _ValueType1 = iter_value_t<_Iter1>;
3540  using _ValueType2 = iter_value_t<_Iter2>;
3541  // This condition is consistent with the one in
3542  // __lexicographical_compare_aux in <bits/stl_algobase.h>.
3543  constexpr bool __use_memcmp
3544  = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
3545  && __ptr_to_nonvolatile<_Iter1>
3546  && __ptr_to_nonvolatile<_Iter2>
3547  && (is_same_v<_Comp, ranges::less>
3548  || is_same_v<_Comp, ranges::greater>)
3549  && is_same_v<_Proj1, identity>
3550  && is_same_v<_Proj2, identity>);
3551  if constexpr (__use_memcmp)
3552  {
3553  const auto __d1 = __last1 - __first1;
3554  const auto __d2 = __last2 - __first2;
3555 
3556  if (const auto __len = std::min(__d1, __d2))
3557  {
3558  const auto __c
3559  = std::__memcmp(__first1, __first2, __len);
3560  if constexpr (is_same_v<_Comp, ranges::less>)
3561  {
3562  if (__c < 0)
3563  return true;
3564  if (__c > 0)
3565  return false;
3566  }
3567  else if constexpr (is_same_v<_Comp, ranges::greater>)
3568  {
3569  if (__c > 0)
3570  return true;
3571  if (__c < 0)
3572  return false;
3573  }
3574  }
3575  return __d1 < __d2;
3576  }
3577  }
3578 
3579  for (; __first1 != __last1 && __first2 != __last2;
3580  ++__first1, (void) ++__first2)
3581  {
3582  if (std::__invoke(__comp,
3583  std::__invoke(__proj1, *__first1),
3584  std::__invoke(__proj2, *__first2)))
3585  return true;
3586  if (std::__invoke(__comp,
3587  std::__invoke(__proj2, *__first2),
3588  std::__invoke(__proj1, *__first1)))
3589  return false;
3590  }
3591  return __first1 == __last1 && __first2 != __last2;
3592  }
3593  }
3594 
3595  template<input_range _Range1, input_range _Range2,
3596  typename _Proj1 = identity, typename _Proj2 = identity,
3597  indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
3598  projected<iterator_t<_Range2>, _Proj2>>
3599  _Comp = ranges::less>
3600  constexpr bool
3601  operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
3602  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3603  {
3604  return (*this)(ranges::begin(__r1), ranges::end(__r1),
3605  ranges::begin(__r2), ranges::end(__r2),
3606  std::move(__comp),
3607  std::move(__proj1), std::move(__proj2));
3608  }
3609 
3610  private:
3611  template<typename _Iter, typename _Ref = iter_reference_t<_Iter>>
3612  static constexpr bool __ptr_to_nonvolatile
3613  = is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>;
3614  };
3615 
3616  inline constexpr __lexicographical_compare_fn lexicographical_compare;
3617 
3618  template<typename _Iter>
3619  struct in_found_result
3620  {
3621  [[no_unique_address]] _Iter in;
3622  bool found;
3623 
3624  template<typename _Iter2>
3625  requires convertible_to<const _Iter&, _Iter2>
3626  constexpr
3627  operator in_found_result<_Iter2>() const &
3628  { return {in, found}; }
3629 
3630  template<typename _Iter2>
3631  requires convertible_to<_Iter, _Iter2>
3632  constexpr
3633  operator in_found_result<_Iter2>() &&
3634  { return {std::move(in), found}; }
3635  };
3636 
3637  template<typename _Iter>
3638  using next_permutation_result = in_found_result<_Iter>;
3639 
3640  struct __next_permutation_fn
3641  {
3642  template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3643  typename _Comp = ranges::less, typename _Proj = identity>
3644  requires sortable<_Iter, _Comp, _Proj>
3645  constexpr next_permutation_result<_Iter>
3646  operator()(_Iter __first, _Sent __last,
3647  _Comp __comp = {}, _Proj __proj = {}) const
3648  {
3649  if (__first == __last)
3650  return {std::move(__first), false};
3651 
3652  auto __i = __first;
3653  ++__i;
3654  if (__i == __last)
3655  return {std::move(__i), false};
3656 
3657  auto __lasti = ranges::next(__first, __last);
3658  __i = __lasti;
3659  --__i;
3660 
3661  for (;;)
3662  {
3663  auto __ii = __i;
3664  --__i;
3665  if (std::__invoke(__comp,
3666  std::__invoke(__proj, *__i),
3667  std::__invoke(__proj, *__ii)))
3668  {
3669  auto __j = __lasti;
3670  while (!(bool)std::__invoke(__comp,
3671  std::__invoke(__proj, *__i),
3672  std::__invoke(__proj, *--__j)))
3673  ;
3674  ranges::iter_swap(__i, __j);
3675  ranges::reverse(__ii, __last);
3676  return {std::move(__lasti), true};
3677  }
3678  if (__i == __first)
3679  {
3680  ranges::reverse(__first, __last);
3681  return {std::move(__lasti), false};
3682  }
3683  }
3684  }
3685 
3686  template<bidirectional_range _Range, typename _Comp = ranges::less,
3687  typename _Proj = identity>
3688  requires sortable<iterator_t<_Range>, _Comp, _Proj>
3689  constexpr next_permutation_result<borrowed_iterator_t<_Range>>
3690  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3691  {
3692  return (*this)(ranges::begin(__r), ranges::end(__r),
3693  std::move(__comp), std::move(__proj));
3694  }
3695  };
3696 
3697  inline constexpr __next_permutation_fn next_permutation{};
3698 
3699  template<typename _Iter>
3700  using prev_permutation_result = in_found_result<_Iter>;
3701 
3702  struct __prev_permutation_fn
3703  {
3704  template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3705  typename _Comp = ranges::less, typename _Proj = identity>
3706  requires sortable<_Iter, _Comp, _Proj>
3707  constexpr prev_permutation_result<_Iter>
3708  operator()(_Iter __first, _Sent __last,
3709  _Comp __comp = {}, _Proj __proj = {}) const
3710  {
3711  if (__first == __last)
3712  return {std::move(__first), false};
3713 
3714  auto __i = __first;
3715  ++__i;
3716  if (__i == __last)
3717  return {std::move(__i), false};
3718 
3719  auto __lasti = ranges::next(__first, __last);
3720  __i = __lasti;
3721  --__i;
3722 
3723  for (;;)
3724  {
3725  auto __ii = __i;
3726  --__i;
3727  if (std::__invoke(__comp,
3728  std::__invoke(__proj, *__ii),
3729  std::__invoke(__proj, *__i)))
3730  {
3731  auto __j = __lasti;
3732  while (!(bool)std::__invoke(__comp,
3733  std::__invoke(__proj, *--__j),
3734  std::__invoke(__proj, *__i)))
3735  ;
3736  ranges::iter_swap(__i, __j);
3737  ranges::reverse(__ii, __last);
3738  return {std::move(__lasti), true};
3739  }
3740  if (__i == __first)
3741  {
3742  ranges::reverse(__first, __last);
3743  return {std::move(__lasti), false};
3744  }
3745  }
3746  }
3747 
3748  template<bidirectional_range _Range, typename _Comp = ranges::less,
3749  typename _Proj = identity>
3750  requires sortable<iterator_t<_Range>, _Comp, _Proj>
3751  constexpr prev_permutation_result<borrowed_iterator_t<_Range>>
3752  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3753  {
3754  return (*this)(ranges::begin(__r), ranges::end(__r),
3755  std::move(__comp), std::move(__proj));
3756  }
3757  };
3758 
3759  inline constexpr __prev_permutation_fn prev_permutation{};
3760 
3761 } // namespace ranges
3762 
3763 #define __cpp_lib_shift 201806L
3764  template<typename _ForwardIterator>
3765  constexpr _ForwardIterator
3766  shift_left(_ForwardIterator __first, _ForwardIterator __last,
3767  typename iterator_traits<_ForwardIterator>::difference_type __n)
3768  {
3769  __glibcxx_assert(__n >= 0);
3770  if (__n == 0)
3771  return __last;
3772 
3773  auto __mid = ranges::next(__first, __n, __last);
3774  if (__mid == __last)
3775  return __first;
3776  return std::move(std::move(__mid), std::move(__last), std::move(__first));
3777  }
3778 
3779  template<typename _ForwardIterator>
3780  constexpr _ForwardIterator
3781  shift_right(_ForwardIterator __first, _ForwardIterator __last,
3782  typename iterator_traits<_ForwardIterator>::difference_type __n)
3783  {
3784  __glibcxx_assert(__n >= 0);
3785  if (__n == 0)
3786  return __first;
3787 
3788  using _Cat
3789  = typename iterator_traits<_ForwardIterator>::iterator_category;
3790  if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
3791  {
3792  auto __mid = ranges::next(__last, -__n, __first);
3793  if (__mid == __first)
3794  return __last;
3795 
3796  return std::move_backward(std::move(__first), std::move(__mid),
3797  std::move(__last));
3798  }
3799  else
3800  {
3801  auto __result = ranges::next(__first, __n, __last);
3802  if (__result == __last)
3803  return __last;
3804 
3805  auto __dest_head = __first, __dest_tail = __result;
3806  while (__dest_head != __result)
3807  {
3808  if (__dest_tail == __last)
3809  {
3810  // If we get here, then we must have
3811  // 2*n >= distance(__first, __last)
3812  // i.e. we are shifting out at least half of the range. In
3813  // this case we can safely perform the shift with a single
3814  // move.
3815  std::move(std::move(__first), std::move(__dest_head), __result);
3816  return __result;
3817  }
3818  ++__dest_head;
3819  ++__dest_tail;
3820  }
3821 
3822  for (;;)
3823  {
3824  // At the start of each iteration of this outer loop, the range
3825  // [__first, __result) contains those elements that after shifting
3826  // the whole range right by __n, should end up in
3827  // [__dest_head, __dest_tail) in order.
3828 
3829  // The below inner loop swaps the elements of [__first, __result)
3830  // and [__dest_head, __dest_tail), while simultaneously shifting
3831  // the latter range by __n.
3832  auto __cursor = __first;
3833  while (__cursor != __result)
3834  {
3835  if (__dest_tail == __last)
3836  {
3837  // At this point the ranges [__first, result) and
3838  // [__dest_head, dest_tail) are disjoint, so we can safely
3839  // move the remaining elements.
3840  __dest_head = std::move(__cursor, __result,
3841  std::move(__dest_head));
3842  std::move(std::move(__first), std::move(__cursor),
3843  std::move(__dest_head));
3844  return __result;
3845  }
3846  std::iter_swap(__cursor, __dest_head);
3847  ++__dest_head;
3848  ++__dest_tail;
3849  ++__cursor;
3850  }
3851  }
3852  }
3853  }
3854 
3855 _GLIBCXX_END_NAMESPACE_VERSION
3856 } // namespace std
3857 #endif // concepts
3858 #endif // C++20
3859 #endif // _RANGES_ALGO_H
std::__invoke
constexpr __invoke_result< _Callable, _Args... >::type __invoke(_Callable &&__fn, _Args &&... __args) noexcept(__is_nothrow_invocable< _Callable, _Args... >::value)
Invoke a callable object.
Definition: invoke.h:89
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
std::end
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1234
std::begin
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1214
std::move_backward
constexpr _BI2 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Moves the range [first,last) into result.
Definition: stl_algobase.h:833
std::max
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:254
std::minmax
constexpr pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
Definition: stl_algo.h:3325
std::min
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:230
std
ISO C++ entities toplevel namespace is std.
std::distance
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:138
std::advance
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:202
std::experimental::fundamentals_v2::sample
_SampleIterator sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator __out, _Distance __n, _UniformRandomNumberGenerator &&__g)
Take a random sample from a population.
Definition: experimental/algorithm:61