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