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