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