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