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