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