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