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 39namespace std _GLIBCXX_VISIBILITY(default) 40{ 41_GLIBCXX_BEGIN_NAMESPACE_VERSION 42namespace 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) -> bool { 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) -> bool { 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) -> bool { 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 namespace __detail 1399 { 1400 template<typename _Out, typename _Tp> 1401 concept __can_reread_output = input_iterator<_Out> 1402 && same_as<_Tp, iter_value_t<_Out>>; 1403 } 1404 1405 template<typename _Iter, typename _Out> 1406 using unique_copy_result = in_out_result<_Iter, _Out>; 1407 1408 struct __unique_copy_fn 1409 { 1410 template<input_iterator _Iter, sentinel_for<_Iter> _Sent, 1411 weakly_incrementable _Out, typename _Proj = identity, 1412 indirect_equivalence_relation< 1413 projected<_Iter, _Proj>> _Comp = ranges::equal_to> 1414 requires indirectly_copyable<_Iter, _Out> 1415 && (forward_iterator<_Iter> 1416 || __detail::__can_reread_output<_Out, iter_value_t<_Iter>> 1417 || indirectly_copyable_storable<_Iter, _Out>) 1418 constexpr unique_copy_result<_Iter, _Out> 1419 operator()(_Iter __first, _Sent __last, _Out __result, 1420 _Comp __comp = {}, _Proj __proj = {}) const 1421 { 1422 if (__first == __last) 1423 return {std::move(__first), std::move(__result)}; 1424 1425 // TODO: perform a closer comparison with reference implementations 1426 if constexpr (forward_iterator<_Iter>) 1427 { 1428 auto __next = __first; 1429 *__result = *__next; 1430 while (++__next != __last) 1431 if (!std::__invoke(__comp, 1432 std::__invoke(__proj, *__first), 1433 std::__invoke(__proj, *__next))) 1434 { 1435 __first = __next; 1436 *++__result = *__first; 1437 } 1438 return {__next, std::move(++__result)}; 1439 } 1440 else if constexpr (__detail::__can_reread_output<_Out, iter_value_t<_Iter>>) 1441 { 1442 *__result = *__first; 1443 while (++__first != __last) 1444 if (!std::__invoke(__comp, 1445 std::__invoke(__proj, *__result), 1446 std::__invoke(__proj, *__first))) 1447 *++__result = *__first; 1448 return {std::move(__first), std::move(++__result)}; 1449 } 1450 else // indirectly_copyable_storable<_Iter, _Out> 1451 { 1452 auto __value = *__first; 1453 *__result = __value; 1454 while (++__first != __last) 1455 { 1456 if (!(bool)std::__invoke(__comp, 1457 std::__invoke(__proj, *__first), 1458 std::__invoke(__proj, __value))) 1459 { 1460 __value = *__first; 1461 *++__result = __value; 1462 } 1463 } 1464 return {std::move(__first), std::move(++__result)}; 1465 } 1466 } 1467 1468 template<input_range _Range, 1469 weakly_incrementable _Out, typename _Proj = identity, 1470 indirect_equivalence_relation< 1471 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to> 1472 requires indirectly_copyable<iterator_t<_Range>, _Out> 1473 && (forward_iterator<iterator_t<_Range>> 1474 || __detail::__can_reread_output<_Out, range_value_t<_Range>> 1475 || indirectly_copyable_storable<iterator_t<_Range>, _Out>) 1476 constexpr unique_copy_result<borrowed_iterator_t<_Range>, _Out> 1477 operator()(_Range&& __r, _Out __result, 1478 _Comp __comp = {}, _Proj __proj = {}) const 1479 { 1480 return (*this)(ranges::begin(__r), ranges::end(__r), 1481 std::move(__result), 1482 std::move(__comp), std::move(__proj)); 1483 } 1484 }; 1485 1486 inline constexpr __unique_copy_fn unique_copy{}; 1487 1488 struct __reverse_fn 1489 { 1490 template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent> 1491 requires permutable<_Iter> 1492 constexpr _Iter 1493 operator()(_Iter __first, _Sent __last) const 1494 { 1495 auto __i = ranges::next(__first, __last); 1496 auto __tail = __i; 1497 1498 if constexpr (random_access_iterator<_Iter>) 1499 { 1500 if (__first != __last) 1501 { 1502 --__tail; 1503 while (__first < __tail) 1504 { 1505 ranges::iter_swap(__first, __tail); 1506 ++__first; 1507 --__tail; 1508 } 1509 } 1510 return __i; 1511 } 1512 else 1513 { 1514 for (;;) 1515 if (__first == __tail || __first == --__tail) 1516 break; 1517 else 1518 { 1519 ranges::iter_swap(__first, __tail); 1520 ++__first; 1521 } 1522 return __i; 1523 } 1524 } 1525 1526 template<bidirectional_range _Range> 1527 requires permutable<iterator_t<_Range>> 1528 constexpr borrowed_iterator_t<_Range> 1529 operator()(_Range&& __r) const 1530 { 1531 return (*this)(ranges::begin(__r), ranges::end(__r)); 1532 } 1533 }; 1534 1535 inline constexpr __reverse_fn reverse{}; 1536 1537 template<typename _Iter, typename _Out> 1538 using reverse_copy_result = in_out_result<_Iter, _Out>; 1539 1540 struct __reverse_copy_fn 1541 { 1542 template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, 1543 weakly_incrementable _Out> 1544 requires indirectly_copyable<_Iter, _Out> 1545 constexpr reverse_copy_result<_Iter, _Out> 1546 operator()(_Iter __first, _Sent __last, _Out __result) const 1547 { 1548 auto __i = ranges::next(__first, __last); 1549 auto __tail = __i; 1550 while (__first != __tail) 1551 { 1552 --__tail; 1553 *__result = *__tail; 1554 ++__result; 1555 } 1556 return {__i, std::move(__result)}; 1557 } 1558 1559 template<bidirectional_range _Range, weakly_incrementable _Out> 1560 requires indirectly_copyable<iterator_t<_Range>, _Out> 1561 constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _Out> 1562 operator()(_Range&& __r, _Out __result) const 1563 { 1564 return (*this)(ranges::begin(__r), ranges::end(__r), 1565 std::move(__result)); 1566 } 1567 }; 1568 1569 inline constexpr __reverse_copy_fn reverse_copy{}; 1570 1571 struct __rotate_fn 1572 { 1573 template<permutable _Iter, sentinel_for<_Iter> _Sent> 1574 constexpr subrange<_Iter> 1575 operator()(_Iter __first, _Iter __middle, _Sent __last) const 1576 { 1577 auto __lasti = ranges::next(__first, __last); 1578 if (__first == __middle) 1579 return {__lasti, __lasti}; 1580 if (__last == __middle) 1581 return {std::move(__first), std::move(__lasti)}; 1582 1583 if constexpr (random_access_iterator<_Iter>) 1584 { 1585 auto __n = __lasti - __first; 1586 auto __k = __middle - __first; 1587 1588 if (__k == __n - __k) 1589 { 1590 ranges::swap_ranges(__first, __middle, __middle, __middle + __k); 1591 return {std::move(__middle), std::move(__lasti)}; 1592 } 1593 1594 auto __p = __first; 1595 auto __ret = __first + (__lasti - __middle); 1596 1597 for (;;) 1598 { 1599 if (__k < __n - __k) 1600 { 1601 // TODO: is_pod is deprecated, but this condition is 1602 // consistent with the STL implementation. 1603 if constexpr (__is_pod(iter_value_t<_Iter>)) 1604 if (__k == 1) 1605 { 1606 auto __t = std::move(*__p); 1607 ranges::move(__p + 1, __p + __n, __p); 1608 *(__p + __n - 1) = std::move(__t); 1609 return {std::move(__ret), std::move(__lasti)}; 1610 } 1611 auto __q = __p + __k; 1612 for (decltype(__n) __i = 0; __i < __n - __k; ++ __i) 1613 { 1614 ranges::iter_swap(__p, __q); 1615 ++__p; 1616 ++__q; 1617 } 1618 __n %= __k; 1619 if (__n == 0) 1620 return {std::move(__ret), std::move(__lasti)}; 1621 ranges::swap(__n, __k); 1622 __k = __n - __k; 1623 } 1624 else 1625 { 1626 __k = __n - __k; 1627 // TODO: is_pod is deprecated, but this condition is 1628 // consistent with the STL implementation. 1629 if constexpr (__is_pod(iter_value_t<_Iter>)) 1630 if (__k == 1) 1631 { 1632 auto __t = std::move(*(__p + __n - 1)); 1633 ranges::move_backward(__p, __p + __n - 1, __p + __n); 1634 *__p = std::move(__t); 1635 return {std::move(__ret), std::move(__lasti)}; 1636 } 1637 auto __q = __p + __n; 1638 __p = __q - __k; 1639 for (decltype(__n) __i = 0; __i < __n - __k; ++ __i) 1640 { 1641 --__p; 1642 --__q; 1643 ranges::iter_swap(__p, __q); 1644 } 1645 __n %= __k; 1646 if (__n == 0) 1647 return {std::move(__ret), std::move(__lasti)}; 1648 std::swap(__n, __k); 1649 } 1650 } 1651 } 1652 else if constexpr (bidirectional_iterator<_Iter>) 1653 { 1654 auto __tail = __lasti; 1655 1656 ranges::reverse(__first, __middle); 1657 ranges::reverse(__middle, __tail); 1658 1659 while (__first != __middle && __middle != __tail) 1660 { 1661 ranges::iter_swap(__first, --__tail); 1662 ++__first; 1663 } 1664 1665 if (__first == __middle) 1666 { 1667 ranges::reverse(__middle, __tail); 1668 return {std::move(__tail), std::move(__lasti)}; 1669 } 1670 else 1671 { 1672 ranges::reverse(__first, __middle); 1673 return {std::move(__first), std::move(__lasti)}; 1674 } 1675 } 1676 else 1677 { 1678 auto __first2 = __middle; 1679 do 1680 { 1681 ranges::iter_swap(__first, __first2); 1682 ++__first; 1683 ++__first2; 1684 if (__first == __middle) 1685 __middle = __first2; 1686 } while (__first2 != __last); 1687 1688 auto __ret = __first; 1689 1690 __first2 = __middle; 1691 1692 while (__first2 != __last) 1693 { 1694 ranges::iter_swap(__first, __first2); 1695 ++__first; 1696 ++__first2; 1697 if (__first == __middle) 1698 __middle = __first2; 1699 else if (__first2 == __last) 1700 __first2 = __middle; 1701 } 1702 return {std::move(__ret), std::move(__lasti)}; 1703 } 1704 } 1705 1706 template<forward_range _Range> 1707 requires permutable<iterator_t<_Range>> 1708 constexpr borrowed_subrange_t<_Range> 1709 operator()(_Range&& __r, iterator_t<_Range> __middle) const 1710 { 1711 return (*this)(ranges::begin(__r), std::move(__middle), 1712 ranges::end(__r)); 1713 } 1714 }; 1715 1716 inline constexpr __rotate_fn rotate{}; 1717 1718 template<typename _Iter, typename _Out> 1719 using rotate_copy_result = in_out_result<_Iter, _Out>; 1720 1721 struct __rotate_copy_fn 1722 { 1723 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, 1724 weakly_incrementable _Out> 1725 requires indirectly_copyable<_Iter, _Out> 1726 constexpr rotate_copy_result<_Iter, _Out> 1727 operator()(_Iter __first, _Iter __middle, _Sent __last, 1728 _Out __result) const 1729 { 1730 auto __copy1 = ranges::copy(__middle, 1731 std::move(__last), 1732 std::move(__result)); 1733 auto __copy2 = ranges::copy(std::move(__first), 1734 std::move(__middle), 1735 std::move(__copy1.out)); 1736 return { std::move(__copy1.in), std::move(__copy2.out) }; 1737 } 1738 1739 template<forward_range _Range, weakly_incrementable _Out> 1740 requires indirectly_copyable<iterator_t<_Range>, _Out> 1741 constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _Out> 1742 operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result) const 1743 { 1744 return (*this)(ranges::begin(__r), std::move(__middle), 1745 ranges::end(__r), std::move(__result)); 1746 } 1747 }; 1748 1749 inline constexpr __rotate_copy_fn rotate_copy{}; 1750 1751 struct __sample_fn 1752 { 1753 template<input_iterator _Iter, sentinel_for<_Iter> _Sent, 1754 weakly_incrementable _Out, typename _Gen> 1755 requires (forward_iterator<_Iter> || random_access_iterator<_Out>) 1756 && indirectly_copyable<_Iter, _Out> 1757 && uniform_random_bit_generator<remove_reference_t<_Gen>> 1758 _Out 1759 operator()(_Iter __first, _Sent __last, _Out __out, 1760 iter_difference_t<_Iter> __n, _Gen&& __g) const 1761 { 1762 if constexpr (forward_iterator<_Iter>) 1763 { 1764 // FIXME: Forwarding to std::sample here requires computing __lasti 1765 // which may take linear time. 1766 auto __lasti = ranges::next(__first, __last); 1767 return std::sample(std::move(__first), std::move(__lasti), 1768 std::move(__out), __n, std::forward<_Gen>(__g)); 1769 } 1770 else 1771 { 1772 using __distrib_type 1773 = uniform_int_distribution<iter_difference_t<_Iter>>; 1774 using __param_type = typename __distrib_type::param_type; 1775 __distrib_type __d{}; 1776 iter_difference_t<_Iter> __sample_sz = 0; 1777 while (__first != __last && __sample_sz != __n) 1778 { 1779 __out[__sample_sz++] = *__first; 1780 ++__first; 1781 } 1782 for (auto __pop_sz = __sample_sz; __first != __last; 1783 ++__first, (void) ++__pop_sz) 1784 { 1785 const auto __k = __d(__g, __param_type{0, __pop_sz}); 1786 if (__k < __n) 1787 __out[__k] = *__first; 1788 } 1789 return __out + __sample_sz; 1790 } 1791 } 1792 1793 template<input_range _Range, weakly_incrementable _Out, typename _Gen> 1794 requires (forward_range<_Range> || random_access_iterator<_Out>) 1795 && indirectly_copyable<iterator_t<_Range>, _Out> 1796 && uniform_random_bit_generator<remove_reference_t<_Gen>> 1797 _Out 1798 operator()(_Range&& __r, _Out __out, 1799 range_difference_t<_Range> __n, _Gen&& __g) const 1800 { 1801 return (*this)(ranges::begin(__r), ranges::end(__r), 1802 std::move(__out), __n, 1803 std::forward<_Gen>(__g)); 1804 } 1805 }; 1806 1807 inline constexpr __sample_fn sample{}; 1808 1809#ifdef _GLIBCXX_USE_C99_STDINT_TR1 1810 struct __shuffle_fn 1811 { 1812 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, 1813 typename _Gen> 1814 requires permutable<_Iter> 1815 && uniform_random_bit_generator<remove_reference_t<_Gen>> 1816 _Iter 1817 operator()(_Iter __first, _Sent __last, _Gen&& __g) const 1818 { 1819 auto __lasti = ranges::next(__first, __last); 1820 std::shuffle(std::move(__first), __lasti, std::forward<_Gen>(__g)); 1821 return __lasti; 1822 } 1823 1824 template<random_access_range _Range, typename _Gen> 1825 requires permutable<iterator_t<_Range>> 1826 && uniform_random_bit_generator<remove_reference_t<_Gen>> 1827 borrowed_iterator_t<_Range> 1828 operator()(_Range&& __r, _Gen&& __g) const 1829 { 1830 return (*this)(ranges::begin(__r), ranges::end(__r), 1831 std::forward<_Gen>(__g)); 1832 } 1833 }; 1834 1835 inline constexpr __shuffle_fn shuffle{}; 1836#endif 1837 1838 struct __push_heap_fn 1839 { 1840 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, 1841 typename _Comp = ranges::less, typename _Proj = identity> 1842 requires sortable<_Iter, _Comp, _Proj> 1843 constexpr _Iter 1844 operator()(_Iter __first, _Sent __last, 1845 _Comp __comp = {}, _Proj __proj = {}) const 1846 { 1847 auto __lasti = ranges::next(__first, __last); 1848 std::push_heap(__first, __lasti, 1849 __detail::__make_comp_proj(__comp, __proj)); 1850 return __lasti; 1851 } 1852 1853 template<random_access_range _Range, 1854 typename _Comp = ranges::less, typename _Proj = identity> 1855 requires sortable<iterator_t<_Range>, _Comp, _Proj> 1856 constexpr borrowed_iterator_t<_Range> 1857 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 1858 { 1859 return (*this)(ranges::begin(__r), ranges::end(__r), 1860 std::move(__comp), std::move(__proj)); 1861 } 1862 }; 1863 1864 inline constexpr __push_heap_fn push_heap{}; 1865 1866 struct __pop_heap_fn 1867 { 1868 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, 1869 typename _Comp = ranges::less, typename _Proj = identity> 1870 requires sortable<_Iter, _Comp, _Proj> 1871 constexpr _Iter 1872 operator()(_Iter __first, _Sent __last, 1873 _Comp __comp = {}, _Proj __proj = {}) const 1874 { 1875 auto __lasti = ranges::next(__first, __last); 1876 std::pop_heap(__first, __lasti, 1877 __detail::__make_comp_proj(__comp, __proj)); 1878 return __lasti; 1879 } 1880 1881 template<random_access_range _Range, 1882 typename _Comp = ranges::less, typename _Proj = identity> 1883 requires sortable<iterator_t<_Range>, _Comp, _Proj> 1884 constexpr borrowed_iterator_t<_Range> 1885 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 1886 { 1887 return (*this)(ranges::begin(__r), ranges::end(__r), 1888 std::move(__comp), std::move(__proj)); 1889 } 1890 }; 1891 1892 inline constexpr __pop_heap_fn pop_heap{}; 1893 1894 struct __make_heap_fn 1895 { 1896 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, 1897 typename _Comp = ranges::less, typename _Proj = identity> 1898 requires sortable<_Iter, _Comp, _Proj> 1899 constexpr _Iter 1900 operator()(_Iter __first, _Sent __last, 1901 _Comp __comp = {}, _Proj __proj = {}) const 1902 { 1903 auto __lasti = ranges::next(__first, __last); 1904 std::make_heap(__first, __lasti, 1905 __detail::__make_comp_proj(__comp, __proj)); 1906 return __lasti; 1907 } 1908 1909 template<random_access_range _Range, 1910 typename _Comp = ranges::less, typename _Proj = identity> 1911 requires sortable<iterator_t<_Range>, _Comp, _Proj> 1912 constexpr borrowed_iterator_t<_Range> 1913 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 1914 { 1915 return (*this)(ranges::begin(__r), ranges::end(__r), 1916 std::move(__comp), std::move(__proj)); 1917 } 1918 }; 1919 1920 inline constexpr __make_heap_fn make_heap{}; 1921 1922 struct __sort_heap_fn 1923 { 1924 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, 1925 typename _Comp = ranges::less, typename _Proj = identity> 1926 requires sortable<_Iter, _Comp, _Proj> 1927 constexpr _Iter 1928 operator()(_Iter __first, _Sent __last, 1929 _Comp __comp = {}, _Proj __proj = {}) const 1930 { 1931 auto __lasti = ranges::next(__first, __last); 1932 std::sort_heap(__first, __lasti, 1933 __detail::__make_comp_proj(__comp, __proj)); 1934 return __lasti; 1935 } 1936 1937 template<random_access_range _Range, 1938 typename _Comp = ranges::less, typename _Proj = identity> 1939 requires sortable<iterator_t<_Range>, _Comp, _Proj> 1940 constexpr borrowed_iterator_t<_Range> 1941 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 1942 { 1943 return (*this)(ranges::begin(__r), ranges::end(__r), 1944 std::move(__comp), std::move(__proj)); 1945 } 1946 }; 1947 1948 inline constexpr __sort_heap_fn sort_heap{}; 1949 1950 struct __is_heap_until_fn 1951 { 1952 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, 1953 typename _Proj = identity, 1954 indirect_strict_weak_order<projected<_Iter, _Proj>> 1955 _Comp = ranges::less> 1956 constexpr _Iter 1957 operator()(_Iter __first, _Sent __last, 1958 _Comp __comp = {}, _Proj __proj = {}) const 1959 { 1960 iter_difference_t<_Iter> __n = ranges::distance(__first, __last); 1961 iter_difference_t<_Iter> __parent = 0, __child = 1; 1962 for (; __child < __n; ++__child) 1963 if (std::__invoke(__comp, 1964 std::__invoke(__proj, *(__first + __parent)), 1965 std::__invoke(__proj, *(__first + __child)))) 1966 return __first + __child; 1967 else if ((__child & 1) == 0) 1968 ++__parent; 1969 1970 return __first + __n; 1971 } 1972 1973 template<random_access_range _Range, 1974 typename _Proj = identity, 1975 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> 1976 _Comp = ranges::less> 1977 constexpr borrowed_iterator_t<_Range> 1978 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 1979 { 1980 return (*this)(ranges::begin(__r), ranges::end(__r), 1981 std::move(__comp), std::move(__proj)); 1982 } 1983 }; 1984 1985 inline constexpr __is_heap_until_fn is_heap_until{}; 1986 1987 struct __is_heap_fn 1988 { 1989 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, 1990 typename _Proj = identity, 1991 indirect_strict_weak_order<projected<_Iter, _Proj>> 1992 _Comp = ranges::less> 1993 constexpr bool 1994 operator()(_Iter __first, _Sent __last, 1995 _Comp __comp = {}, _Proj __proj = {}) const 1996 { 1997 return (__last 1998 == ranges::is_heap_until(__first, __last, 1999 std::move(__comp), 2000 std::move(__proj))); 2001 } 2002 2003 template<random_access_range _Range, 2004 typename _Proj = identity, 2005 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> 2006 _Comp = ranges::less> 2007 constexpr bool 2008 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 2009 { 2010 return (*this)(ranges::begin(__r), ranges::end(__r), 2011 std::move(__comp), std::move(__proj)); 2012 } 2013 }; 2014 2015 inline constexpr __is_heap_fn is_heap{}; 2016 2017 struct __sort_fn 2018 { 2019 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, 2020 typename _Comp = ranges::less, typename _Proj = identity> 2021 requires sortable<_Iter, _Comp, _Proj> 2022 constexpr _Iter 2023 operator()(_Iter __first, _Sent __last, 2024 _Comp __comp = {}, _Proj __proj = {}) const 2025 { 2026 auto __lasti = ranges::next(__first, __last); 2027 std::sort(std::move(__first), __lasti, 2028 __detail::__make_comp_proj(__comp, __proj)); 2029 return __lasti; 2030 } 2031 2032 template<random_access_range _Range, 2033 typename _Comp = ranges::less, typename _Proj = identity> 2034 requires sortable<iterator_t<_Range>, _Comp, _Proj> 2035 constexpr borrowed_iterator_t<_Range> 2036 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 2037 { 2038 return (*this)(ranges::begin(__r), ranges::end(__r), 2039 std::move(__comp), std::move(__proj)); 2040 } 2041 }; 2042 2043 inline constexpr __sort_fn sort{}; 2044 2045 struct __stable_sort_fn 2046 { 2047 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, 2048 typename _Comp = ranges::less, typename _Proj = identity> 2049 requires sortable<_Iter, _Comp, _Proj> 2050 _Iter 2051 operator()(_Iter __first, _Sent __last, 2052 _Comp __comp = {}, _Proj __proj = {}) const 2053 { 2054 auto __lasti = ranges::next(__first, __last); 2055 std::stable_sort(std::move(__first), __lasti, 2056 __detail::__make_comp_proj(__comp, __proj)); 2057 return __lasti; 2058 } 2059 2060 template<random_access_range _Range, 2061 typename _Comp = ranges::less, typename _Proj = identity> 2062 requires sortable<iterator_t<_Range>, _Comp, _Proj> 2063 borrowed_iterator_t<_Range> 2064 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 2065 { 2066 return (*this)(ranges::begin(__r), ranges::end(__r), 2067 std::move(__comp), std::move(__proj)); 2068 } 2069 }; 2070 2071 inline constexpr __stable_sort_fn stable_sort{}; 2072 2073 struct __partial_sort_fn 2074 { 2075 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, 2076 typename _Comp = ranges::less, typename _Proj = identity> 2077 requires sortable<_Iter, _Comp, _Proj> 2078 constexpr _Iter 2079 operator()(_Iter __first, _Iter __middle, _Sent __last, 2080 _Comp __comp = {}, _Proj __proj = {}) const 2081 { 2082 if (__first == __middle) 2083 return ranges::next(__first, __last); 2084 2085 ranges::make_heap(__first, __middle, __comp, __proj); 2086 auto __i = __middle; 2087 for (; __i != __last; ++__i) 2088 if (std::__invoke(__comp, 2089 std::__invoke(__proj, *__i), 2090 std::__invoke(__proj, *__first))) 2091 { 2092 ranges::pop_heap(__first, __middle, __comp, __proj); 2093 ranges::iter_swap(__middle-1, __i); 2094 ranges::push_heap(__first, __middle, __comp, __proj); 2095 } 2096 ranges::sort_heap(__first, __middle, __comp, __proj); 2097 2098 return __i; 2099 } 2100 2101 template<random_access_range _Range, 2102 typename _Comp = ranges::less, typename _Proj = identity> 2103 requires sortable<iterator_t<_Range>, _Comp, _Proj> 2104 constexpr borrowed_iterator_t<_Range> 2105 operator()(_Range&& __r, iterator_t<_Range> __middle, 2106 _Comp __comp = {}, _Proj __proj = {}) const 2107 { 2108 return (*this)(ranges::begin(__r), std::move(__middle), 2109 ranges::end(__r), 2110 std::move(__comp), std::move(__proj)); 2111 } 2112 }; 2113 2114 inline constexpr __partial_sort_fn partial_sort{}; 2115 2116 template<typename _Iter, typename _Out> 2117 using partial_sort_copy_result = in_out_result<_Iter, _Out>; 2118 2119 struct __partial_sort_copy_fn 2120 { 2121 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 2122 random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2, 2123 typename _Comp = ranges::less, 2124 typename _Proj1 = identity, typename _Proj2 = identity> 2125 requires indirectly_copyable<_Iter1, _Iter2> 2126 && sortable<_Iter2, _Comp, _Proj2> 2127 && indirect_strict_weak_order<_Comp, 2128 projected<_Iter1, _Proj1>, 2129 projected<_Iter2, _Proj2>> 2130 constexpr partial_sort_copy_result<_Iter1, _Iter2> 2131 operator()(_Iter1 __first, _Sent1 __last, 2132 _Iter2 __result_first, _Sent2 __result_last, 2133 _Comp __comp = {}, 2134 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 2135 { 2136 if (__result_first == __result_last) 2137 { 2138 // TODO: Eliminating the variable __lasti triggers an ICE. 2139 auto __lasti = ranges::next(std::move(__first), 2140 std::move(__last)); 2141 return {std::move(__lasti), std::move(__result_first)}; 2142 } 2143 2144 auto __result_real_last = __result_first; 2145 while (__first != __last && __result_real_last != __result_last) 2146 { 2147 *__result_real_last = *__first; 2148 ++__result_real_last; 2149 ++__first; 2150 } 2151 2152 ranges::make_heap(__result_first, __result_real_last, __comp, __proj2); 2153 for (; __first != __last; ++__first) 2154 if (std::__invoke(__comp, 2155 std::__invoke(__proj1, *__first), 2156 std::__invoke(__proj2, *__result_first))) 2157 { 2158 ranges::pop_heap(__result_first, __result_real_last, 2159 __comp, __proj2); 2160 *(__result_real_last-1) = *__first; 2161 ranges::push_heap(__result_first, __result_real_last, 2162 __comp, __proj2); 2163 } 2164 ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2); 2165 2166 return {std::move(__first), std::move(__result_real_last)}; 2167 } 2168 2169 template<input_range _Range1, random_access_range _Range2, 2170 typename _Comp = ranges::less, 2171 typename _Proj1 = identity, typename _Proj2 = identity> 2172 requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>> 2173 && sortable<iterator_t<_Range2>, _Comp, _Proj2> 2174 && indirect_strict_weak_order<_Comp, 2175 projected<iterator_t<_Range1>, _Proj1>, 2176 projected<iterator_t<_Range2>, _Proj2>> 2177 constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>, 2178 borrowed_iterator_t<_Range2>> 2179 operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {}, 2180 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 2181 { 2182 return (*this)(ranges::begin(__r), ranges::end(__r), 2183 ranges::begin(__out), ranges::end(__out), 2184 std::move(__comp), 2185 std::move(__proj1), std::move(__proj2)); 2186 } 2187 }; 2188 2189 inline constexpr __partial_sort_copy_fn partial_sort_copy{}; 2190 2191 struct __is_sorted_until_fn 2192 { 2193 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, 2194 typename _Proj = identity, 2195 indirect_strict_weak_order<projected<_Iter, _Proj>> 2196 _Comp = ranges::less> 2197 constexpr _Iter 2198 operator()(_Iter __first, _Sent __last, 2199 _Comp __comp = {}, _Proj __proj = {}) const 2200 { 2201 if (__first == __last) 2202 return __first; 2203 2204 auto __next = __first; 2205 for (++__next; __next != __last; __first = __next, (void)++__next) 2206 if (std::__invoke(__comp, 2207 std::__invoke(__proj, *__next), 2208 std::__invoke(__proj, *__first))) 2209 return __next; 2210 return __next; 2211 } 2212 2213 template<forward_range _Range, typename _Proj = identity, 2214 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> 2215 _Comp = ranges::less> 2216 constexpr borrowed_iterator_t<_Range> 2217 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 2218 { 2219 return (*this)(ranges::begin(__r), ranges::end(__r), 2220 std::move(__comp), std::move(__proj)); 2221 } 2222 }; 2223 2224 inline constexpr __is_sorted_until_fn is_sorted_until{}; 2225 2226 struct __is_sorted_fn 2227 { 2228 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, 2229 typename _Proj = identity, 2230 indirect_strict_weak_order<projected<_Iter, _Proj>> 2231 _Comp = ranges::less> 2232 constexpr bool 2233 operator()(_Iter __first, _Sent __last, 2234 _Comp __comp = {}, _Proj __proj = {}) const 2235 { 2236 if (__first == __last) 2237 return true; 2238 2239 auto __next = __first; 2240 for (++__next; __next != __last; __first = __next, (void)++__next) 2241 if (std::__invoke(__comp, 2242 std::__invoke(__proj, *__next), 2243 std::__invoke(__proj, *__first))) 2244 return false; 2245 return true; 2246 } 2247 2248 template<forward_range _Range, typename _Proj = identity, 2249 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> 2250 _Comp = ranges::less> 2251 constexpr bool 2252 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 2253 { 2254 return (*this)(ranges::begin(__r), ranges::end(__r), 2255 std::move(__comp), std::move(__proj)); 2256 } 2257 }; 2258 2259 inline constexpr __is_sorted_fn is_sorted{}; 2260 2261 struct __nth_element_fn 2262 { 2263 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, 2264 typename _Comp = ranges::less, typename _Proj = identity> 2265 requires sortable<_Iter, _Comp, _Proj> 2266 constexpr _Iter 2267 operator()(_Iter __first, _Iter __nth, _Sent __last, 2268 _Comp __comp = {}, _Proj __proj = {}) const 2269 { 2270 auto __lasti = ranges::next(__first, __last); 2271 std::nth_element(std::move(__first), std::move(__nth), __lasti, 2272 __detail::__make_comp_proj(__comp, __proj)); 2273 return __lasti; 2274 } 2275 2276 template<random_access_range _Range, 2277 typename _Comp = ranges::less, typename _Proj = identity> 2278 requires sortable<iterator_t<_Range>, _Comp, _Proj> 2279 constexpr borrowed_iterator_t<_Range> 2280 operator()(_Range&& __r, iterator_t<_Range> __nth, 2281 _Comp __comp = {}, _Proj __proj = {}) const 2282 { 2283 return (*this)(ranges::begin(__r), std::move(__nth), 2284 ranges::end(__r), std::move(__comp), std::move(__proj)); 2285 } 2286 }; 2287 2288 inline constexpr __nth_element_fn nth_element{}; 2289 2290 struct __lower_bound_fn 2291 { 2292 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, 2293 typename _Tp, typename _Proj = identity, 2294 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>> 2295 _Comp = ranges::less> 2296 constexpr _Iter 2297 operator()(_Iter __first, _Sent __last, 2298 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const 2299 { 2300 auto __len = ranges::distance(__first, __last); 2301 2302 while (__len > 0) 2303 { 2304 auto __half = __len / 2; 2305 auto __middle = __first; 2306 ranges::advance(__middle, __half); 2307 if (std::__invoke(__comp, std::__invoke(__proj, *__middle), __value)) 2308 { 2309 __first = __middle; 2310 ++__first; 2311 __len = __len - __half - 1; 2312 } 2313 else 2314 __len = __half; 2315 } 2316 return __first; 2317 } 2318 2319 template<forward_range _Range, typename _Tp, typename _Proj = identity, 2320 indirect_strict_weak_order<const _Tp*, 2321 projected<iterator_t<_Range>, _Proj>> 2322 _Comp = ranges::less> 2323 constexpr borrowed_iterator_t<_Range> 2324 operator()(_Range&& __r, 2325 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const 2326 { 2327 return (*this)(ranges::begin(__r), ranges::end(__r), 2328 __value, std::move(__comp), std::move(__proj)); 2329 } 2330 }; 2331 2332 inline constexpr __lower_bound_fn lower_bound{}; 2333 2334 struct __upper_bound_fn 2335 { 2336 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, 2337 typename _Tp, typename _Proj = identity, 2338 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>> 2339 _Comp = ranges::less> 2340 constexpr _Iter 2341 operator()(_Iter __first, _Sent __last, 2342 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const 2343 { 2344 auto __len = ranges::distance(__first, __last); 2345 2346 while (__len > 0) 2347 { 2348 auto __half = __len / 2; 2349 auto __middle = __first; 2350 ranges::advance(__middle, __half); 2351 if (std::__invoke(__comp, __value, std::__invoke(__proj, *__middle))) 2352 __len = __half; 2353 else 2354 { 2355 __first = __middle; 2356 ++__first; 2357 __len = __len - __half - 1; 2358 } 2359 } 2360 return __first; 2361 } 2362 2363 template<forward_range _Range, typename _Tp, typename _Proj = identity, 2364 indirect_strict_weak_order<const _Tp*, 2365 projected<iterator_t<_Range>, _Proj>> 2366 _Comp = ranges::less> 2367 constexpr borrowed_iterator_t<_Range> 2368 operator()(_Range&& __r, 2369 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const 2370 { 2371 return (*this)(ranges::begin(__r), ranges::end(__r), 2372 __value, std::move(__comp), std::move(__proj)); 2373 } 2374 }; 2375 2376 inline constexpr __upper_bound_fn upper_bound{}; 2377 2378 struct __equal_range_fn 2379 { 2380 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, 2381 typename _Tp, typename _Proj = identity, 2382 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>> 2383 _Comp = ranges::less> 2384 constexpr subrange<_Iter> 2385 operator()(_Iter __first, _Sent __last, 2386 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const 2387 { 2388 auto __len = ranges::distance(__first, __last); 2389 2390 while (__len > 0) 2391 { 2392 auto __half = __len / 2; 2393 auto __middle = __first; 2394 ranges::advance(__middle, __half); 2395 if (std::__invoke(__comp, 2396 std::__invoke(__proj, *__middle), 2397 __value)) 2398 { 2399 __first = __middle; 2400 ++__first; 2401 __len = __len - __half - 1; 2402 } 2403 else if (std::__invoke(__comp, 2404 __value, 2405 std::__invoke(__proj, *__middle))) 2406 __len = __half; 2407 else 2408 { 2409 auto __left 2410 = ranges::lower_bound(__first, __middle, 2411 __value, __comp, __proj); 2412 ranges::advance(__first, __len); 2413 auto __right 2414 = ranges::upper_bound(++__middle, __first, 2415 __value, __comp, __proj); 2416 return {__left, __right}; 2417 } 2418 } 2419 return {__first, __first}; 2420 } 2421 2422 template<forward_range _Range, 2423 typename _Tp, typename _Proj = identity, 2424 indirect_strict_weak_order<const _Tp*, 2425 projected<iterator_t<_Range>, _Proj>> 2426 _Comp = ranges::less> 2427 constexpr borrowed_subrange_t<_Range> 2428 operator()(_Range&& __r, const _Tp& __value, 2429 _Comp __comp = {}, _Proj __proj = {}) const 2430 { 2431 return (*this)(ranges::begin(__r), ranges::end(__r), 2432 __value, std::move(__comp), std::move(__proj)); 2433 } 2434 }; 2435 2436 inline constexpr __equal_range_fn equal_range{}; 2437 2438 struct __binary_search_fn 2439 { 2440 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, 2441 typename _Tp, typename _Proj = identity, 2442 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>> 2443 _Comp = ranges::less> 2444 constexpr bool 2445 operator()(_Iter __first, _Sent __last, 2446 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const 2447 { 2448 auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj); 2449 if (__i == __last) 2450 return false; 2451 return !(bool)std::__invoke(__comp, __value, 2452 std::__invoke(__proj, *__i)); 2453 } 2454 2455 template<forward_range _Range, 2456 typename _Tp, typename _Proj = identity, 2457 indirect_strict_weak_order<const _Tp*, 2458 projected<iterator_t<_Range>, _Proj>> 2459 _Comp = ranges::less> 2460 constexpr bool 2461 operator()(_Range&& __r, const _Tp& __value, _Comp __comp = {}, 2462 _Proj __proj = {}) const 2463 { 2464 return (*this)(ranges::begin(__r), ranges::end(__r), 2465 __value, std::move(__comp), std::move(__proj)); 2466 } 2467 }; 2468 2469 inline constexpr __binary_search_fn binary_search{}; 2470 2471 struct __is_partitioned_fn 2472 { 2473 template<input_iterator _Iter, sentinel_for<_Iter> _Sent, 2474 typename _Proj = identity, 2475 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> 2476 constexpr bool 2477 operator()(_Iter __first, _Sent __last, 2478 _Pred __pred, _Proj __proj = {}) const 2479 { 2480 __first = ranges::find_if_not(std::move(__first), __last, 2481 __pred, __proj); 2482 if (__first == __last) 2483 return true; 2484 ++__first; 2485 return ranges::none_of(std::move(__first), std::move(__last), 2486 std::move(__pred), std::move(__proj)); 2487 } 2488 2489 template<input_range _Range, typename _Proj = identity, 2490 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> 2491 _Pred> 2492 constexpr bool 2493 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const 2494 { 2495 return (*this)(ranges::begin(__r), ranges::end(__r), 2496 std::move(__pred), std::move(__proj)); 2497 } 2498 }; 2499 2500 inline constexpr __is_partitioned_fn is_partitioned{}; 2501 2502 struct __partition_fn 2503 { 2504 template<permutable _Iter, sentinel_for<_Iter> _Sent, 2505 typename _Proj = identity, 2506 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> 2507 constexpr subrange<_Iter> 2508 operator()(_Iter __first, _Sent __last, 2509 _Pred __pred, _Proj __proj = {}) const 2510 { 2511 if constexpr (bidirectional_iterator<_Iter>) 2512 { 2513 auto __lasti = ranges::next(__first, __last); 2514 auto __tail = __lasti; 2515 for (;;) 2516 { 2517 for (;;) 2518 if (__first == __tail) 2519 return {std::move(__first), std::move(__lasti)}; 2520 else if (std::__invoke(__pred, 2521 std::__invoke(__proj, *__first))) 2522 ++__first; 2523 else 2524 break; 2525 --__tail; 2526 for (;;) 2527 if (__first == __tail) 2528 return {std::move(__first), std::move(__lasti)}; 2529 else if (!(bool)std::__invoke(__pred, 2530 std::__invoke(__proj, *__tail))) 2531 --__tail; 2532 else 2533 break; 2534 ranges::iter_swap(__first, __tail); 2535 ++__first; 2536 } 2537 } 2538 else 2539 { 2540 if (__first == __last) 2541 return {__first, __first}; 2542 2543 while (std::__invoke(__pred, std::__invoke(__proj, *__first))) 2544 if (++__first == __last) 2545 return {__first, __first}; 2546 2547 auto __next = __first; 2548 while (++__next != __last) 2549 if (std::__invoke(__pred, std::__invoke(__proj, *__next))) 2550 { 2551 ranges::iter_swap(__first, __next); 2552 ++__first; 2553 } 2554 2555 return {std::move(__first), std::move(__next)}; 2556 } 2557 } 2558 2559 template<forward_range _Range, typename _Proj = identity, 2560 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> 2561 _Pred> 2562 requires permutable<iterator_t<_Range>> 2563 constexpr borrowed_subrange_t<_Range> 2564 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const 2565 { 2566 return (*this)(ranges::begin(__r), ranges::end(__r), 2567 std::move(__pred), std::move(__proj)); 2568 } 2569 }; 2570 2571 inline constexpr __partition_fn partition{}; 2572 2573 struct __stable_partition_fn 2574 { 2575 template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, 2576 typename _Proj = identity, 2577 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> 2578 requires permutable<_Iter> 2579 subrange<_Iter> 2580 operator()(_Iter __first, _Sent __last, 2581 _Pred __pred, _Proj __proj = {}) const 2582 { 2583 auto __lasti = ranges::next(__first, __last); 2584 auto __middle 2585 = std::stable_partition(std::move(__first), __lasti, 2586 __detail::__make_pred_proj(__pred, __proj)); 2587 return {std::move(__middle), std::move(__lasti)}; 2588 } 2589 2590 template<bidirectional_range _Range, typename _Proj = identity, 2591 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> 2592 _Pred> 2593 requires permutable<iterator_t<_Range>> 2594 borrowed_subrange_t<_Range> 2595 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const 2596 { 2597 return (*this)(ranges::begin(__r), ranges::end(__r), 2598 std::move(__pred), std::move(__proj)); 2599 } 2600 }; 2601 2602 inline constexpr __stable_partition_fn stable_partition{}; 2603 2604 template<typename _Iter, typename _Out1, typename _Out2> 2605 struct in_out_out_result 2606 { 2607 [[no_unique_address]] _Iter in; 2608 [[no_unique_address]] _Out1 out1; 2609 [[no_unique_address]] _Out2 out2; 2610 2611 template<typename _IIter, typename _OOut1, typename _OOut2> 2612 requires convertible_to<const _Iter&, _IIter> 2613 && convertible_to<const _Out1&, _OOut1> 2614 && convertible_to<const _Out2&, _OOut2> 2615 constexpr 2616 operator in_out_out_result<_IIter, _OOut1, _OOut2>() const & 2617 { return {in, out1, out2}; } 2618 2619 template<typename _IIter, typename _OOut1, typename _OOut2> 2620 requires convertible_to<_Iter, _IIter> 2621 && convertible_to<_Out1, _OOut1> 2622 && convertible_to<_Out2, _OOut2> 2623 constexpr 2624 operator in_out_out_result<_IIter, _OOut1, _OOut2>() && 2625 { return {std::move(in), std::move(out1), std::move(out2)}; } 2626 }; 2627 2628 template<typename _Iter, typename _Out1, typename _Out2> 2629 using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>; 2630 2631 struct __partition_copy_fn 2632 { 2633 template<input_iterator _Iter, sentinel_for<_Iter> _Sent, 2634 weakly_incrementable _Out1, weakly_incrementable _Out2, 2635 typename _Proj = identity, 2636 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> 2637 requires indirectly_copyable<_Iter, _Out1> 2638 && indirectly_copyable<_Iter, _Out2> 2639 constexpr partition_copy_result<_Iter, _Out1, _Out2> 2640 operator()(_Iter __first, _Sent __last, 2641 _Out1 __out_true, _Out2 __out_false, 2642 _Pred __pred, _Proj __proj = {}) const 2643 { 2644 for (; __first != __last; ++__first) 2645 if (std::__invoke(__pred, std::__invoke(__proj, *__first))) 2646 { 2647 *__out_true = *__first; 2648 ++__out_true; 2649 } 2650 else 2651 { 2652 *__out_false = *__first; 2653 ++__out_false; 2654 } 2655 2656 return {std::move(__first), 2657 std::move(__out_true), std::move(__out_false)}; 2658 } 2659 2660 template<input_range _Range, weakly_incrementable _Out1, 2661 weakly_incrementable _Out2, 2662 typename _Proj = identity, 2663 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> 2664 _Pred> 2665 requires indirectly_copyable<iterator_t<_Range>, _Out1> 2666 && indirectly_copyable<iterator_t<_Range>, _Out2> 2667 constexpr partition_copy_result<borrowed_iterator_t<_Range>, _Out1, _Out2> 2668 operator()(_Range&& __r, _Out1 __out_true, _Out2 __out_false, 2669 _Pred __pred, _Proj __proj = {}) const 2670 { 2671 return (*this)(ranges::begin(__r), ranges::end(__r), 2672 std::move(__out_true), std::move(__out_false), 2673 std::move(__pred), std::move(__proj)); 2674 } 2675 }; 2676 2677 inline constexpr __partition_copy_fn partition_copy{}; 2678 2679 struct __partition_point_fn 2680 { 2681 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, 2682 typename _Proj = identity, 2683 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> 2684 constexpr _Iter 2685 operator()(_Iter __first, _Sent __last, 2686 _Pred __pred, _Proj __proj = {}) const 2687 { 2688 auto __len = ranges::distance(__first, __last); 2689 2690 while (__len > 0) 2691 { 2692 auto __half = __len / 2; 2693 auto __middle = __first; 2694 ranges::advance(__middle, __half); 2695 if (std::__invoke(__pred, std::__invoke(__proj, *__middle))) 2696 { 2697 __first = __middle; 2698 ++__first; 2699 __len = __len - __half - 1; 2700 } 2701 else 2702 __len = __half; 2703 } 2704 return __first; 2705 } 2706 2707 template<forward_range _Range, typename _Proj = identity, 2708 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> 2709 _Pred> 2710 constexpr borrowed_iterator_t<_Range> 2711 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const 2712 { 2713 return (*this)(ranges::begin(__r), ranges::end(__r), 2714 std::move(__pred), std::move(__proj)); 2715 } 2716 }; 2717 2718 inline constexpr __partition_point_fn partition_point{}; 2719 2720 template<typename _Iter1, typename _Iter2, typename _Out> 2721 using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>; 2722 2723 struct __merge_fn 2724 { 2725 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 2726 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, 2727 weakly_incrementable _Out, typename _Comp = ranges::less, 2728 typename _Proj1 = identity, typename _Proj2 = identity> 2729 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2> 2730 constexpr merge_result<_Iter1, _Iter2, _Out> 2731 operator()(_Iter1 __first1, _Sent1 __last1, 2732 _Iter2 __first2, _Sent2 __last2, _Out __result, 2733 _Comp __comp = {}, 2734 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 2735 { 2736 while (__first1 != __last1 && __first2 != __last2) 2737 { 2738 if (std::__invoke(__comp, 2739 std::__invoke(__proj2, *__first2), 2740 std::__invoke(__proj1, *__first1))) 2741 { 2742 *__result = *__first2; 2743 ++__first2; 2744 } 2745 else 2746 { 2747 *__result = *__first1; 2748 ++__first1; 2749 } 2750 ++__result; 2751 } 2752 auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1), 2753 std::move(__result)); 2754 auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2), 2755 std::move(__copy1.out)); 2756 return { std::move(__copy1.in), std::move(__copy2.in), 2757 std::move(__copy2.out) }; 2758 } 2759 2760 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out, 2761 typename _Comp = ranges::less, 2762 typename _Proj1 = identity, typename _Proj2 = identity> 2763 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out, 2764 _Comp, _Proj1, _Proj2> 2765 constexpr merge_result<borrowed_iterator_t<_Range1>, 2766 borrowed_iterator_t<_Range2>, 2767 _Out> 2768 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, 2769 _Comp __comp = {}, 2770 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 2771 { 2772 return (*this)(ranges::begin(__r1), ranges::end(__r1), 2773 ranges::begin(__r2), ranges::end(__r2), 2774 std::move(__result), std::move(__comp), 2775 std::move(__proj1), std::move(__proj2)); 2776 } 2777 }; 2778 2779 inline constexpr __merge_fn merge{}; 2780 2781 struct __inplace_merge_fn 2782 { 2783 template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, 2784 typename _Comp = ranges::less, 2785 typename _Proj = identity> 2786 requires sortable<_Iter, _Comp, _Proj> 2787 _Iter 2788 operator()(_Iter __first, _Iter __middle, _Sent __last, 2789 _Comp __comp = {}, _Proj __proj = {}) const 2790 { 2791 auto __lasti = ranges::next(__first, __last); 2792 std::inplace_merge(std::move(__first), std::move(__middle), __lasti, 2793 __detail::__make_comp_proj(__comp, __proj)); 2794 return __lasti; 2795 } 2796 2797 template<bidirectional_range _Range, 2798 typename _Comp = ranges::less, typename _Proj = identity> 2799 requires sortable<iterator_t<_Range>, _Comp, _Proj> 2800 borrowed_iterator_t<_Range> 2801 operator()(_Range&& __r, iterator_t<_Range> __middle, 2802 _Comp __comp = {}, _Proj __proj = {}) const 2803 { 2804 return (*this)(ranges::begin(__r), std::move(__middle), 2805 ranges::end(__r), 2806 std::move(__comp), std::move(__proj)); 2807 } 2808 }; 2809 2810 inline constexpr __inplace_merge_fn inplace_merge{}; 2811 2812 struct __includes_fn 2813 { 2814 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 2815 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, 2816 typename _Proj1 = identity, typename _Proj2 = identity, 2817 indirect_strict_weak_order<projected<_Iter1, _Proj1>, 2818 projected<_Iter2, _Proj2>> 2819 _Comp = ranges::less> 2820 constexpr bool 2821 operator()(_Iter1 __first1, _Sent1 __last1, 2822 _Iter2 __first2, _Sent2 __last2, 2823 _Comp __comp = {}, 2824 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 2825 { 2826 while (__first1 != __last1 && __first2 != __last2) 2827 if (std::__invoke(__comp, 2828 std::__invoke(__proj2, *__first2), 2829 std::__invoke(__proj1, *__first1))) 2830 return false; 2831 else if (std::__invoke(__comp, 2832 std::__invoke(__proj1, *__first1), 2833 std::__invoke(__proj2, *__first2))) 2834 ++__first1; 2835 else 2836 { 2837 ++__first1; 2838 ++__first2; 2839 } 2840 2841 return __first2 == __last2; 2842 } 2843 2844 template<input_range _Range1, input_range _Range2, 2845 typename _Proj1 = identity, typename _Proj2 = identity, 2846 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>, 2847 projected<iterator_t<_Range2>, _Proj2>> 2848 _Comp = ranges::less> 2849 constexpr bool 2850 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {}, 2851 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 2852 { 2853 return (*this)(ranges::begin(__r1), ranges::end(__r1), 2854 ranges::begin(__r2), ranges::end(__r2), 2855 std::move(__comp), 2856 std::move(__proj1), std::move(__proj2)); 2857 } 2858 }; 2859 2860 inline constexpr __includes_fn includes{}; 2861 2862 template<typename _Iter1, typename _Iter2, typename _Out> 2863 using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>; 2864 2865 struct __set_union_fn 2866 { 2867 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 2868 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, 2869 weakly_incrementable _Out, typename _Comp = ranges::less, 2870 typename _Proj1 = identity, typename _Proj2 = identity> 2871 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2> 2872 constexpr set_union_result<_Iter1, _Iter2, _Out> 2873 operator()(_Iter1 __first1, _Sent1 __last1, 2874 _Iter2 __first2, _Sent2 __last2, 2875 _Out __result, _Comp __comp = {}, 2876 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 2877 { 2878 while (__first1 != __last1 && __first2 != __last2) 2879 { 2880 if (std::__invoke(__comp, 2881 std::__invoke(__proj1, *__first1), 2882 std::__invoke(__proj2, *__first2))) 2883 { 2884 *__result = *__first1; 2885 ++__first1; 2886 } 2887 else if (std::__invoke(__comp, 2888 std::__invoke(__proj2, *__first2), 2889 std::__invoke(__proj1, *__first1))) 2890 { 2891 *__result = *__first2; 2892 ++__first2; 2893 } 2894 else 2895 { 2896 *__result = *__first1; 2897 ++__first1; 2898 ++__first2; 2899 } 2900 ++__result; 2901 } 2902 auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1), 2903 std::move(__result)); 2904 auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2), 2905 std::move(__copy1.out)); 2906 return {std::move(__copy1.in), std::move(__copy2.in), 2907 std::move(__copy2.out)}; 2908 } 2909 2910 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out, 2911 typename _Comp = ranges::less, 2912 typename _Proj1 = identity, typename _Proj2 = identity> 2913 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out, 2914 _Comp, _Proj1, _Proj2> 2915 constexpr set_union_result<borrowed_iterator_t<_Range1>, 2916 borrowed_iterator_t<_Range2>, _Out> 2917 operator()(_Range1&& __r1, _Range2&& __r2, 2918 _Out __result, _Comp __comp = {}, 2919 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 2920 { 2921 return (*this)(ranges::begin(__r1), ranges::end(__r1), 2922 ranges::begin(__r2), ranges::end(__r2), 2923 std::move(__result), std::move(__comp), 2924 std::move(__proj1), std::move(__proj2)); 2925 } 2926 }; 2927 2928 inline constexpr __set_union_fn set_union{}; 2929 2930 template<typename _Iter1, typename _Iter2, typename _Out> 2931 using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>; 2932 2933 struct __set_intersection_fn 2934 { 2935 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 2936 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, 2937 weakly_incrementable _Out, typename _Comp = ranges::less, 2938 typename _Proj1 = identity, typename _Proj2 = identity> 2939 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2> 2940 constexpr set_intersection_result<_Iter1, _Iter2, _Out> 2941 operator()(_Iter1 __first1, _Sent1 __last1, 2942 _Iter2 __first2, _Sent2 __last2, _Out __result, 2943 _Comp __comp = {}, 2944 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 2945 { 2946 while (__first1 != __last1 && __first2 != __last2) 2947 if (std::__invoke(__comp, 2948 std::__invoke(__proj1, *__first1), 2949 std::__invoke(__proj2, *__first2))) 2950 ++__first1; 2951 else if (std::__invoke(__comp, 2952 std::__invoke(__proj2, *__first2), 2953 std::__invoke(__proj1, *__first1))) 2954 ++__first2; 2955 else 2956 { 2957 *__result = *__first1; 2958 ++__first1; 2959 ++__first2; 2960 ++__result; 2961 } 2962 // TODO: Eliminating these variables triggers an ICE. 2963 auto __last1i = ranges::next(std::move(__first1), std::move(__last1)); 2964 auto __last2i = ranges::next(std::move(__first2), std::move(__last2)); 2965 return {std::move(__last1i), std::move(__last2i), std::move(__result)}; 2966 } 2967 2968 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out, 2969 typename _Comp = ranges::less, 2970 typename _Proj1 = identity, typename _Proj2 = identity> 2971 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out, 2972 _Comp, _Proj1, _Proj2> 2973 constexpr set_intersection_result<borrowed_iterator_t<_Range1>, 2974 borrowed_iterator_t<_Range2>, _Out> 2975 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, 2976 _Comp __comp = {}, 2977 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 2978 { 2979 return (*this)(ranges::begin(__r1), ranges::end(__r1), 2980 ranges::begin(__r2), ranges::end(__r2), 2981 std::move(__result), std::move(__comp), 2982 std::move(__proj1), std::move(__proj2)); 2983 } 2984 }; 2985 2986 inline constexpr __set_intersection_fn set_intersection{}; 2987 2988 template<typename _Iter, typename _Out> 2989 using set_difference_result = in_out_result<_Iter, _Out>; 2990 2991 struct __set_difference_fn 2992 { 2993 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 2994 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, 2995 weakly_incrementable _Out, typename _Comp = ranges::less, 2996 typename _Proj1 = identity, typename _Proj2 = identity> 2997 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2> 2998 constexpr set_difference_result<_Iter1, _Out> 2999 operator()(_Iter1 __first1, _Sent1 __last1, 3000 _Iter2 __first2, _Sent2 __last2, _Out __result, 3001 _Comp __comp = {}, 3002 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 3003 { 3004 while (__first1 != __last1 && __first2 != __last2) 3005 if (std::__invoke(__comp, 3006 std::__invoke(__proj1, *__first1), 3007 std::__invoke(__proj2, *__first2))) 3008 { 3009 *__result = *__first1; 3010 ++__first1; 3011 ++__result; 3012 } 3013 else if (std::__invoke(__comp, 3014 std::__invoke(__proj2, *__first2), 3015 std::__invoke(__proj1, *__first1))) 3016 ++__first2; 3017 else 3018 { 3019 ++__first1; 3020 ++__first2; 3021 } 3022 return ranges::copy(std::move(__first1), std::move(__last1), 3023 std::move(__result)); 3024 } 3025 3026 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out, 3027 typename _Comp = ranges::less, 3028 typename _Proj1 = identity, typename _Proj2 = identity> 3029 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out, 3030 _Comp, _Proj1, _Proj2> 3031 constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out> 3032 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, 3033 _Comp __comp = {}, 3034 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 3035 { 3036 return (*this)(ranges::begin(__r1), ranges::end(__r1), 3037 ranges::begin(__r2), ranges::end(__r2), 3038 std::move(__result), std::move(__comp), 3039 std::move(__proj1), std::move(__proj2)); 3040 } 3041 }; 3042 3043 inline constexpr __set_difference_fn set_difference{}; 3044 3045 template<typename _Iter1, typename _Iter2, typename _Out> 3046 using set_symmetric_difference_result 3047 = in_in_out_result<_Iter1, _Iter2, _Out>; 3048 3049 struct __set_symmetric_difference_fn 3050 { 3051 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 3052 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, 3053 weakly_incrementable _Out, typename _Comp = ranges::less, 3054 typename _Proj1 = identity, typename _Proj2 = identity> 3055 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2> 3056 constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out> 3057 operator()(_Iter1 __first1, _Sent1 __last1, 3058 _Iter2 __first2, _Sent2 __last2, 3059 _Out __result, _Comp __comp = {}, 3060 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 3061 { 3062 while (__first1 != __last1 && __first2 != __last2) 3063 if (std::__invoke(__comp, 3064 std::__invoke(__proj1, *__first1), 3065 std::__invoke(__proj2, *__first2))) 3066 { 3067 *__result = *__first1; 3068 ++__first1; 3069 ++__result; 3070 } 3071 else if (std::__invoke(__comp, 3072 std::__invoke(__proj2, *__first2), 3073 std::__invoke(__proj1, *__first1))) 3074 { 3075 *__result = *__first2; 3076 ++__first2; 3077 ++__result; 3078 } 3079 else 3080 { 3081 ++__first1; 3082 ++__first2; 3083 } 3084 auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1), 3085 std::move(__result)); 3086 auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2), 3087 std::move(__copy1.out)); 3088 return {std::move(__copy1.in), std::move(__copy2.in), 3089 std::move(__copy2.out)}; 3090 } 3091 3092 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out, 3093 typename _Comp = ranges::less, 3094 typename _Proj1 = identity, typename _Proj2 = identity> 3095 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out, 3096 _Comp, _Proj1, _Proj2> 3097 constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>, 3098 borrowed_iterator_t<_Range2>, 3099 _Out> 3100 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, 3101 _Comp __comp = {}, 3102 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 3103 { 3104 return (*this)(ranges::begin(__r1), ranges::end(__r1), 3105 ranges::begin(__r2), ranges::end(__r2), 3106 std::move(__result), std::move(__comp), 3107 std::move(__proj1), std::move(__proj2)); 3108 } 3109 }; 3110 3111 inline constexpr __set_symmetric_difference_fn set_symmetric_difference{}; 3112 3113 struct __min_fn 3114 { 3115 template<typename _Tp, typename _Proj = identity, 3116 indirect_strict_weak_order<projected<const _Tp*, _Proj>> 3117 _Comp = ranges::less> 3118 constexpr const _Tp& 3119 operator()(const _Tp& __a, const _Tp& __b, 3120 _Comp __comp = {}, _Proj __proj = {}) const 3121 { 3122 if (std::__invoke(__comp, 3123 std::__invoke(__proj, __b), 3124 std::__invoke(__proj, __a))) 3125 return __b; 3126 else 3127 return __a; 3128 } 3129 3130 template<input_range _Range, typename _Proj = identity, 3131 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> 3132 _Comp = ranges::less> 3133 requires indirectly_copyable_storable<iterator_t<_Range>, 3134 range_value_t<_Range>*> 3135 constexpr range_value_t<_Range> 3136 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 3137 { 3138 auto __first = ranges::begin(__r); 3139 auto __last = ranges::end(__r); 3140 __glibcxx_assert(__first != __last); 3141 auto __result = *__first; 3142 while (++__first != __last) 3143 { 3144 auto __tmp = *__first; 3145 if (std::__invoke(__comp, 3146 std::__invoke(__proj, __tmp), 3147 std::__invoke(__proj, __result))) 3148 __result = std::move(__tmp); 3149 } 3150 return __result; 3151 } 3152 3153 template<copyable _Tp, typename _Proj = identity, 3154 indirect_strict_weak_order<projected<const _Tp*, _Proj>> 3155 _Comp = ranges::less> 3156 constexpr _Tp 3157 operator()(initializer_list<_Tp> __r, 3158 _Comp __comp = {}, _Proj __proj = {}) const 3159 { 3160 return (*this)(ranges::subrange(__r), 3161 std::move(__comp), std::move(__proj)); 3162 } 3163 }; 3164 3165 inline constexpr __min_fn min{}; 3166 3167 struct __max_fn 3168 { 3169 template<typename _Tp, typename _Proj = identity, 3170 indirect_strict_weak_order<projected<const _Tp*, _Proj>> 3171 _Comp = ranges::less> 3172 constexpr const _Tp& 3173 operator()(const _Tp& __a, const _Tp& __b, 3174 _Comp __comp = {}, _Proj __proj = {}) const 3175 { 3176 if (std::__invoke(__comp, 3177 std::__invoke(__proj, __a), 3178 std::__invoke(__proj, __b))) 3179 return __b; 3180 else 3181 return __a; 3182 } 3183 3184 template<input_range _Range, typename _Proj = identity, 3185 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> 3186 _Comp = ranges::less> 3187 requires indirectly_copyable_storable<iterator_t<_Range>, 3188 range_value_t<_Range>*> 3189 constexpr range_value_t<_Range> 3190 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 3191 { 3192 auto __first = ranges::begin(__r); 3193 auto __last = ranges::end(__r); 3194 __glibcxx_assert(__first != __last); 3195 auto __result = *__first; 3196 while (++__first != __last) 3197 { 3198 auto __tmp = *__first; 3199 if (std::__invoke(__comp, 3200 std::__invoke(__proj, __result), 3201 std::__invoke(__proj, __tmp))) 3202 __result = std::move(__tmp); 3203 } 3204 return __result; 3205 } 3206 3207 template<copyable _Tp, typename _Proj = identity, 3208 indirect_strict_weak_order<projected<const _Tp*, _Proj>> 3209 _Comp = ranges::less> 3210 constexpr _Tp 3211 operator()(initializer_list<_Tp> __r, 3212 _Comp __comp = {}, _Proj __proj = {}) const 3213 { 3214 return (*this)(ranges::subrange(__r), 3215 std::move(__comp), std::move(__proj)); 3216 } 3217 }; 3218 3219 inline constexpr __max_fn max{}; 3220 3221 struct __clamp_fn 3222 { 3223 template<typename _Tp, typename _Proj = identity, 3224 indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp 3225 = ranges::less> 3226 constexpr const _Tp& 3227 operator()(const _Tp& __val, const _Tp& __lo, const _Tp& __hi, 3228 _Comp __comp = {}, _Proj __proj = {}) const 3229 { 3230 __glibcxx_assert(!(std::__invoke(__comp, 3231 std::__invoke(__proj, __hi), 3232 std::__invoke(__proj, __lo)))); 3233 auto&& __proj_val = std::__invoke(__proj, __val); 3234 if (std::__invoke(__comp, __proj_val, std::__invoke(__proj, __lo))) 3235 return __lo; 3236 else if (std::__invoke(__comp, std::__invoke(__proj, __hi), __proj_val)) 3237 return __hi; 3238 else 3239 return __val; 3240 } 3241 }; 3242 3243 inline constexpr __clamp_fn clamp{}; 3244 3245 template<typename _Tp> 3246 struct min_max_result 3247 { 3248 [[no_unique_address]] _Tp min; 3249 [[no_unique_address]] _Tp max; 3250 3251 template<typename _Tp2> 3252 requires convertible_to<const _Tp&, _Tp2> 3253 constexpr 3254 operator min_max_result<_Tp2>() const & 3255 { return {min, max}; } 3256 3257 template<typename _Tp2> 3258 requires convertible_to<_Tp, _Tp2> 3259 constexpr 3260 operator min_max_result<_Tp2>() && 3261 { return {std::move(min), std::move(max)}; } 3262 }; 3263 3264 template<typename _Tp> 3265 using minmax_result = min_max_result<_Tp>; 3266 3267 struct __minmax_fn 3268 { 3269 template<typename _Tp, typename _Proj = identity, 3270 indirect_strict_weak_order<projected<const _Tp*, _Proj>> 3271 _Comp = ranges::less> 3272 constexpr minmax_result<const _Tp&> 3273 operator()(const _Tp& __a, const _Tp& __b, 3274 _Comp __comp = {}, _Proj __proj = {}) const 3275 { 3276 if (std::__invoke(__comp, 3277 std::__invoke(__proj, __b), 3278 std::__invoke(__proj, __a))) 3279 return {__b, __a}; 3280 else 3281 return {__a, __b}; 3282 } 3283 3284 template<input_range _Range, typename _Proj = identity, 3285 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> 3286 _Comp = ranges::less> 3287 requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*> 3288 constexpr minmax_result<range_value_t<_Range>> 3289 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 3290 { 3291 auto __first = ranges::begin(__r); 3292 auto __last = ranges::end(__r); 3293 __glibcxx_assert(__first != __last); 3294 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj); 3295 minmax_result<range_value_t<_Range>> __result = {*__first, *__first}; 3296 if (++__first == __last) 3297 return __result; 3298 else 3299 { 3300 // At this point __result.min == __result.max, so a single 3301 // comparison with the next element suffices. 3302 auto&& __val = *__first; 3303 if (__comp_proj(__val, __result.min)) 3304 __result.min = std::forward<decltype(__val)>(__val); 3305 else 3306 __result.max = std::forward<decltype(__val)>(__val); 3307 } 3308 while (++__first != __last) 3309 { 3310 // Now process two elements at a time so that we perform at most 3311 // 1 + 3*(N-2)/2 comparisons in total (each of the (N-2)/2 3312 // iterations of this loop performs three comparisons). 3313 range_value_t<_Range> __val1 = *__first; 3314 if (++__first == __last) 3315 { 3316 // N is odd; in this final iteration, we perform at most two 3317 // comparisons, for a total of 1 + 3*(N-3)/2 + 2 comparisons, 3318 // which is not more than 3*N/2, as required. 3319 if (__comp_proj(__val1, __result.min)) 3320 __result.min = std::move(__val1); 3321 else if (!__comp_proj(__val1, __result.max)) 3322 __result.max = std::move(__val1); 3323 break; 3324 } 3325 auto&& __val2 = *__first; 3326 if (!__comp_proj(__val2, __val1)) 3327 { 3328 if (__comp_proj(__val1, __result.min)) 3329 __result.min = std::move(__val1); 3330 if (!__comp_proj(__val2, __result.max)) 3331 __result.max = std::forward<decltype(__val2)>(__val2); 3332 } 3333 else 3334 { 3335 if (__comp_proj(__val2, __result.min)) 3336 __result.min = std::forward<decltype(__val2)>(__val2); 3337 if (!__comp_proj(__val1, __result.max)) 3338 __result.max = std::move(__val1); 3339 } 3340 } 3341 return __result; 3342 } 3343 3344 template<copyable _Tp, typename _Proj = identity, 3345 indirect_strict_weak_order<projected<const _Tp*, _Proj>> 3346 _Comp = ranges::less> 3347 constexpr minmax_result<_Tp> 3348 operator()(initializer_list<_Tp> __r, 3349 _Comp __comp = {}, _Proj __proj = {}) const 3350 { 3351 return (*this)(ranges::subrange(__r), 3352 std::move(__comp), std::move(__proj)); 3353 } 3354 }; 3355 3356 inline constexpr __minmax_fn minmax{}; 3357 3358 struct __min_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, *__i), 3376 std::__invoke(__proj, *__first))) 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 __min_element_fn min_element{}; 3394 3395 struct __max_element_fn 3396 { 3397 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, 3398 typename _Proj = identity, 3399 indirect_strict_weak_order<projected<_Iter, _Proj>> 3400 _Comp = ranges::less> 3401 constexpr _Iter 3402 operator()(_Iter __first, _Sent __last, 3403 _Comp __comp = {}, _Proj __proj = {}) const 3404 { 3405 if (__first == __last) 3406 return __first; 3407 3408 auto __i = __first; 3409 while (++__i != __last) 3410 { 3411 if (std::__invoke(__comp, 3412 std::__invoke(__proj, *__first), 3413 std::__invoke(__proj, *__i))) 3414 __first = __i; 3415 } 3416 return __first; 3417 } 3418 3419 template<forward_range _Range, typename _Proj = identity, 3420 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> 3421 _Comp = ranges::less> 3422 constexpr borrowed_iterator_t<_Range> 3423 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 3424 { 3425 return (*this)(ranges::begin(__r), ranges::end(__r), 3426 std::move(__comp), std::move(__proj)); 3427 } 3428 }; 3429 3430 inline constexpr __max_element_fn max_element{}; 3431 3432 template<typename _Iter> 3433 using minmax_element_result = min_max_result<_Iter>; 3434 3435 struct __minmax_element_fn 3436 { 3437 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, 3438 typename _Proj = identity, 3439 indirect_strict_weak_order<projected<_Iter, _Proj>> 3440 _Comp = ranges::less> 3441 constexpr minmax_element_result<_Iter> 3442 operator()(_Iter __first, _Sent __last, 3443 _Comp __comp = {}, _Proj __proj = {}) const 3444 { 3445 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj); 3446 minmax_element_result<_Iter> __result = {__first, __first}; 3447 if (__first == __last || ++__first == __last) 3448 return __result; 3449 else 3450 { 3451 // At this point __result.min == __result.max, so a single 3452 // comparison with the next element suffices. 3453 if (__comp_proj(*__first, *__result.min)) 3454 __result.min = __first; 3455 else 3456 __result.max = __first; 3457 } 3458 while (++__first != __last) 3459 { 3460 // Now process two elements at a time so that we perform at most 3461 // 1 + 3*(N-2)/2 comparisons in total (each of the (N-2)/2 3462 // iterations of this loop performs three comparisons). 3463 auto __prev = __first; 3464 if (++__first == __last) 3465 { 3466 // N is odd; in this final iteration, we perform at most two 3467 // comparisons, for a total of 1 + 3*(N-3)/2 + 2 comparisons, 3468 // which is not more than 3*N/2, as required. 3469 if (__comp_proj(*__prev, *__result.min)) 3470 __result.min = __prev; 3471 else if (!__comp_proj(*__prev, *__result.max)) 3472 __result.max = __prev; 3473 break; 3474 } 3475 if (!__comp_proj(*__first, *__prev)) 3476 { 3477 if (__comp_proj(*__prev, *__result.min)) 3478 __result.min = __prev; 3479 if (!__comp_proj(*__first, *__result.max)) 3480 __result.max = __first; 3481 } 3482 else 3483 { 3484 if (__comp_proj(*__first, *__result.min)) 3485 __result.min = __first; 3486 if (!__comp_proj(*__prev, *__result.max)) 3487 __result.max = __prev; 3488 } 3489 } 3490 return __result; 3491 } 3492 3493 template<forward_range _Range, typename _Proj = identity, 3494 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> 3495 _Comp = ranges::less> 3496 constexpr minmax_element_result<borrowed_iterator_t<_Range>> 3497 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 3498 { 3499 return (*this)(ranges::begin(__r), ranges::end(__r), 3500 std::move(__comp), std::move(__proj)); 3501 } 3502 }; 3503 3504 inline constexpr __minmax_element_fn minmax_element{}; 3505 3506 struct __lexicographical_compare_fn 3507 { 3508 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 3509 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, 3510 typename _Proj1 = identity, typename _Proj2 = identity, 3511 indirect_strict_weak_order<projected<_Iter1, _Proj1>, 3512 projected<_Iter2, _Proj2>> 3513 _Comp = ranges::less> 3514 constexpr bool 3515 operator()(_Iter1 __first1, _Sent1 __last1, 3516 _Iter2 __first2, _Sent2 __last2, 3517 _Comp __comp = {}, 3518 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 3519 { 3520 if constexpr (__detail::__is_normal_iterator<_Iter1> 3521 && same_as<_Iter1, _Sent1>) 3522 return (*this)(__first1.base(), __last1.base(), 3523 std::move(__first2), std::move(__last2), 3524 std::move(__comp), 3525 std::move(__proj1), std::move(__proj2)); 3526 else if constexpr (__detail::__is_normal_iterator<_Iter2> 3527 && same_as<_Iter2, _Sent2>) 3528 return (*this)(std::move(__first1), std::move(__last1), 3529 __first2.base(), __last2.base(), 3530 std::move(__comp), 3531 std::move(__proj1), std::move(__proj2)); 3532 else 3533 { 3534 constexpr bool __sized_iters 3535 = (sized_sentinel_for<_Sent1, _Iter1> 3536 && sized_sentinel_for<_Sent2, _Iter2>); 3537 if constexpr (__sized_iters) 3538 { 3539 using _ValueType1 = iter_value_t<_Iter1>; 3540 using _ValueType2 = iter_value_t<_Iter2>; 3541 // This condition is consistent with the one in 3542 // __lexicographical_compare_aux in <bits/stl_algobase.h>. 3543 constexpr bool __use_memcmp 3544 = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value 3545 && __ptr_to_nonvolatile<_Iter1> 3546 && __ptr_to_nonvolatile<_Iter2> 3547 && (is_same_v<_Comp, ranges::less> 3548 || is_same_v<_Comp, ranges::greater>) 3549 && is_same_v<_Proj1, identity> 3550 && is_same_v<_Proj2, identity>); 3551 if constexpr (__use_memcmp) 3552 { 3553 const auto __d1 = __last1 - __first1; 3554 const auto __d2 = __last2 - __first2; 3555 3556 if (const auto __len = std::min(__d1, __d2)) 3557 { 3558 const auto __c 3559 = std::__memcmp(__first1, __first2, __len); 3560 if constexpr (is_same_v<_Comp, ranges::less>) 3561 { 3562 if (__c < 0) 3563 return true; 3564 if (__c > 0) 3565 return false; 3566 } 3567 else if constexpr (is_same_v<_Comp, ranges::greater>) 3568 { 3569 if (__c > 0) 3570 return true; 3571 if (__c < 0) 3572 return false; 3573 } 3574 } 3575 return __d1 < __d2; 3576 } 3577 } 3578 3579 for (; __first1 != __last1 && __first2 != __last2; 3580 ++__first1, (void) ++__first2) 3581 { 3582 if (std::__invoke(__comp, 3583 std::__invoke(__proj1, *__first1), 3584 std::__invoke(__proj2, *__first2))) 3585 return true; 3586 if (std::__invoke(__comp, 3587 std::__invoke(__proj2, *__first2), 3588 std::__invoke(__proj1, *__first1))) 3589 return false; 3590 } 3591 return __first1 == __last1 && __first2 != __last2; 3592 } 3593 } 3594 3595 template<input_range _Range1, input_range _Range2, 3596 typename _Proj1 = identity, typename _Proj2 = identity, 3597 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>, 3598 projected<iterator_t<_Range2>, _Proj2>> 3599 _Comp = ranges::less> 3600 constexpr bool 3601 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {}, 3602 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 3603 { 3604 return (*this)(ranges::begin(__r1), ranges::end(__r1), 3605 ranges::begin(__r2), ranges::end(__r2), 3606 std::move(__comp), 3607 std::move(__proj1), std::move(__proj2)); 3608 } 3609 3610 private: 3611 template<typename _Iter, typename _Ref = iter_reference_t<_Iter>> 3612 static constexpr bool __ptr_to_nonvolatile 3613 = is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>; 3614 }; 3615 3616 inline constexpr __lexicographical_compare_fn lexicographical_compare; 3617 3618 template<typename _Iter> 3619 struct in_found_result 3620 { 3621 [[no_unique_address]] _Iter in; 3622 bool found; 3623 3624 template<typename _Iter2> 3625 requires convertible_to<const _Iter&, _Iter2> 3626 constexpr 3627 operator in_found_result<_Iter2>() const & 3628 { return {in, found}; } 3629 3630 template<typename _Iter2> 3631 requires convertible_to<_Iter, _Iter2> 3632 constexpr 3633 operator in_found_result<_Iter2>() && 3634 { return {std::move(in), found}; } 3635 }; 3636 3637 template<typename _Iter> 3638 using next_permutation_result = in_found_result<_Iter>; 3639 3640 struct __next_permutation_fn 3641 { 3642 template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, 3643 typename _Comp = ranges::less, typename _Proj = identity> 3644 requires sortable<_Iter, _Comp, _Proj> 3645 constexpr next_permutation_result<_Iter> 3646 operator()(_Iter __first, _Sent __last, 3647 _Comp __comp = {}, _Proj __proj = {}) const 3648 { 3649 if (__first == __last) 3650 return {std::move(__first), false}; 3651 3652 auto __i = __first; 3653 ++__i; 3654 if (__i == __last) 3655 return {std::move(__i), false}; 3656 3657 auto __lasti = ranges::next(__first, __last); 3658 __i = __lasti; 3659 --__i; 3660 3661 for (;;) 3662 { 3663 auto __ii = __i; 3664 --__i; 3665 if (std::__invoke(__comp, 3666 std::__invoke(__proj, *__i), 3667 std::__invoke(__proj, *__ii))) 3668 { 3669 auto __j = __lasti; 3670 while (!(bool)std::__invoke(__comp, 3671 std::__invoke(__proj, *__i), 3672 std::__invoke(__proj, *--__j))) 3673 ; 3674 ranges::iter_swap(__i, __j); 3675 ranges::reverse(__ii, __last); 3676 return {std::move(__lasti), true}; 3677 } 3678 if (__i == __first) 3679 { 3680 ranges::reverse(__first, __last); 3681 return {std::move(__lasti), false}; 3682 } 3683 } 3684 } 3685 3686 template<bidirectional_range _Range, typename _Comp = ranges::less, 3687 typename _Proj = identity> 3688 requires sortable<iterator_t<_Range>, _Comp, _Proj> 3689 constexpr next_permutation_result<borrowed_iterator_t<_Range>> 3690 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 3691 { 3692 return (*this)(ranges::begin(__r), ranges::end(__r), 3693 std::move(__comp), std::move(__proj)); 3694 } 3695 }; 3696 3697 inline constexpr __next_permutation_fn next_permutation{}; 3698 3699 template<typename _Iter> 3700 using prev_permutation_result = in_found_result<_Iter>; 3701 3702 struct __prev_permutation_fn 3703 { 3704 template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, 3705 typename _Comp = ranges::less, typename _Proj = identity> 3706 requires sortable<_Iter, _Comp, _Proj> 3707 constexpr prev_permutation_result<_Iter> 3708 operator()(_Iter __first, _Sent __last, 3709 _Comp __comp = {}, _Proj __proj = {}) const 3710 { 3711 if (__first == __last) 3712 return {std::move(__first), false}; 3713 3714 auto __i = __first; 3715 ++__i; 3716 if (__i == __last) 3717 return {std::move(__i), false}; 3718 3719 auto __lasti = ranges::next(__first, __last); 3720 __i = __lasti; 3721 --__i; 3722 3723 for (;;) 3724 { 3725 auto __ii = __i; 3726 --__i; 3727 if (std::__invoke(__comp, 3728 std::__invoke(__proj, *__ii), 3729 std::__invoke(__proj, *__i))) 3730 { 3731 auto __j = __lasti; 3732 while (!(bool)std::__invoke(__comp, 3733 std::__invoke(__proj, *--__j), 3734 std::__invoke(__proj, *__i))) 3735 ; 3736 ranges::iter_swap(__i, __j); 3737 ranges::reverse(__ii, __last); 3738 return {std::move(__lasti), true}; 3739 } 3740 if (__i == __first) 3741 { 3742 ranges::reverse(__first, __last); 3743 return {std::move(__lasti), false}; 3744 } 3745 } 3746 } 3747 3748 template<bidirectional_range _Range, typename _Comp = ranges::less, 3749 typename _Proj = identity> 3750 requires sortable<iterator_t<_Range>, _Comp, _Proj> 3751 constexpr prev_permutation_result<borrowed_iterator_t<_Range>> 3752 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 3753 { 3754 return (*this)(ranges::begin(__r), ranges::end(__r), 3755 std::move(__comp), std::move(__proj)); 3756 } 3757 }; 3758 3759 inline constexpr __prev_permutation_fn prev_permutation{}; 3760 3761} // namespace ranges 3762 3763#define __cpp_lib_shift 201806L 3764 template<typename _ForwardIterator> 3765 constexpr _ForwardIterator 3766 shift_left(_ForwardIterator __first, _ForwardIterator __last, 3767 typename iterator_traits<_ForwardIterator>::difference_type __n) 3768 { 3769 __glibcxx_assert(__n >= 0); 3770 if (__n == 0) 3771 return __last; 3772 3773 auto __mid = ranges::next(__first, __n, __last); 3774 if (__mid == __last) 3775 return __first; 3776 return std::move(std::move(__mid), std::move(__last), std::move(__first)); 3777 } 3778 3779 template<typename _ForwardIterator> 3780 constexpr _ForwardIterator 3781 shift_right(_ForwardIterator __first, _ForwardIterator __last, 3782 typename iterator_traits<_ForwardIterator>::difference_type __n) 3783 { 3784 __glibcxx_assert(__n >= 0); 3785 if (__n == 0) 3786 return __first; 3787 3788 using _Cat 3789 = typename iterator_traits<_ForwardIterator>::iterator_category; 3790 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>) 3791 { 3792 auto __mid = ranges::next(__last, -__n, __first); 3793 if (__mid == __first) 3794 return __last; 3795 3796 return std::move_backward(std::move(__first), std::move(__mid), 3797 std::move(__last)); 3798 } 3799 else 3800 { 3801 auto __result = ranges::next(__first, __n, __last); 3802 if (__result == __last) 3803 return __last; 3804 3805 auto __dest_head = __first, __dest_tail = __result; 3806 while (__dest_head != __result) 3807 { 3808 if (__dest_tail == __last) 3809 { 3810 // If we get here, then we must have 3811 // 2*n >= distance(__first, __last) 3812 // i.e. we are shifting out at least half of the range. In 3813 // this case we can safely perform the shift with a single 3814 // move. 3815 std::move(std::move(__first), std::move(__dest_head), __result); 3816 return __result; 3817 } 3818 ++__dest_head; 3819 ++__dest_tail; 3820 } 3821 3822 for (;;) 3823 { 3824 // At the start of each iteration of this outer loop, the range 3825 // [__first, __result) contains those elements that after shifting 3826 // the whole range right by __n, should end up in 3827 // [__dest_head, __dest_tail) in order. 3828 3829 // The below inner loop swaps the elements of [__first, __result) 3830 // and [__dest_head, __dest_tail), while simultaneously shifting 3831 // the latter range by __n. 3832 auto __cursor = __first; 3833 while (__cursor != __result) 3834 { 3835 if (__dest_tail == __last) 3836 { 3837 // At this point the ranges [__first, result) and 3838 // [__dest_head, dest_tail) are disjoint, so we can safely 3839 // move the remaining elements. 3840 __dest_head = std::move(__cursor, __result, 3841 std::move(__dest_head)); 3842 std::move(std::move(__first), std::move(__cursor), 3843 std::move(__dest_head)); 3844 return __result; 3845 } 3846 std::iter_swap(__cursor, __dest_head); 3847 ++__dest_head; 3848 ++__dest_tail; 3849 ++__cursor; 3850 } 3851 } 3852 } 3853 } 3854 3855_GLIBCXX_END_NAMESPACE_VERSION 3856} // namespace std 3857#endif // concepts 3858#endif // C++20 3859#endif // _RANGES_ALGO_H 3860