source: Daodan/MSYS2/mingw32/include/c++/11.2.0/bits/ranges_algo.h@ 1181

Last change on this file since 1181 was 1166, checked in by rossy, 3 years ago

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