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