Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/bits/ranges_algobase.h
1 // Core algorithmic facilities -*- C++ -*- 2 3 // Copyright (C) 2020-2025 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file bits/ranges_algobase.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_ALGOBASE_H 31 #define _RANGES_ALGOBASE_H 1 32 33 #if __cplusplus > 201703L 34 35 #include <compare> 36 #include <bits/stl_iterator_base_funcs.h> 37 #include <bits/stl_iterator.h> 38 #include <bits/ranges_base.h> // ranges::begin, ranges::range etc. 39 #include <bits/invoke.h> // __invoke 40 #include <bits/cpp_type_traits.h> // __is_byte 41 #include <bits/stl_algobase.h> // __memcmp 42 43 #if __cpp_lib_concepts 44 namespace std _GLIBCXX_VISIBILITY(default) 45 { 46 _GLIBCXX_BEGIN_NAMESPACE_VERSION 47 namespace ranges 48 { 49 namespace __detail 50 { 51 template<typename _Tp> 52 constexpr inline bool __is_normal_iterator = false; 53 54 template<typename _Iterator, typename _Container> 55 constexpr inline bool 56 __is_normal_iterator<__gnu_cxx::__normal_iterator<_Iterator, 57 _Container>> = true; 58 59 template<typename _Tp> 60 constexpr inline bool __is_reverse_iterator = false; 61 62 template<typename _Iterator> 63 constexpr inline bool 64 __is_reverse_iterator<reverse_iterator<_Iterator>> = true; 65 66 template<typename _Tp> 67 constexpr inline bool __is_move_iterator = false; 68 69 template<typename _Iterator> 70 constexpr inline bool 71 __is_move_iterator<move_iterator<_Iterator>> = true; 72 } // namespace __detail 73 74 #if __glibcxx_ranges_iota >= 202202L // C++ >= 23 75 template<typename _Out, typename _Tp> 76 struct out_value_result 77 { 78 [[no_unique_address]] _Out out; 79 [[no_unique_address]] _Tp value; 80 81 template<typename _Out2, typename _Tp2> 82 requires convertible_to<const _Out&, _Out2> 83 && convertible_to<const _Tp&, _Tp2> 84 constexpr 85 operator out_value_result<_Out2, _Tp2>() const & 86 { return {out, value}; } 87 88 template<typename _Out2, typename _Tp2> 89 requires convertible_to<_Out, _Out2> 90 && convertible_to<_Tp, _Tp2> 91 constexpr 92 operator out_value_result<_Out2, _Tp2>() && 93 { return {std::move(out), std::move(value)}; } 94 }; 95 #endif // __glibcxx_ranges_iota 96 97 struct __equal_fn 98 { 99 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 100 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, 101 typename _Pred = ranges::equal_to, 102 typename _Proj1 = identity, typename _Proj2 = identity> 103 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> 104 constexpr bool 105 operator()(_Iter1 __first1, _Sent1 __last1, 106 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, 107 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 108 { 109 // TODO: implement more specializations to at least have parity with 110 // std::equal. 111 if constexpr (__detail::__is_normal_iterator<_Iter1> 112 && same_as<_Iter1, _Sent1>) 113 return (*this)(__first1.base(), __last1.base(), 114 std::move(__first2), std::move(__last2), 115 std::move(__pred), 116 std::move(__proj1), std::move(__proj2)); 117 else if constexpr (__detail::__is_normal_iterator<_Iter2> 118 && same_as<_Iter2, _Sent2>) 119 return (*this)(std::move(__first1), std::move(__last1), 120 __first2.base(), __last2.base(), 121 std::move(__pred), 122 std::move(__proj1), std::move(__proj2)); 123 else if constexpr (sized_sentinel_for<_Sent1, _Iter1> 124 && sized_sentinel_for<_Sent2, _Iter2>) 125 { 126 auto __d1 = ranges::distance(__first1, __last1); 127 auto __d2 = ranges::distance(__first2, __last2); 128 if (__d1 != __d2) 129 return false; 130 131 using _ValueType1 = iter_value_t<_Iter1>; 132 constexpr bool __use_memcmp 133 = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>) 134 && __memcmpable<_Iter1, _Iter2>::__value 135 && is_same_v<_Pred, ranges::equal_to> 136 && is_same_v<_Proj1, identity> 137 && is_same_v<_Proj2, identity>); 138 if constexpr (__use_memcmp) 139 { 140 if (const size_t __len = (__last1 - __first1)) 141 return !std::__memcmp(__first1, __first2, __len); 142 return true; 143 } 144 else 145 { 146 for (; __first1 != __last1; ++__first1, (void)++__first2) 147 if (!(bool)std::__invoke(__pred, 148 std::__invoke(__proj1, *__first1), 149 std::__invoke(__proj2, *__first2))) 150 return false; 151 return true; 152 } 153 } 154 else 155 { 156 for (; __first1 != __last1 && __first2 != __last2; 157 ++__first1, (void)++__first2) 158 if (!(bool)std::__invoke(__pred, 159 std::__invoke(__proj1, *__first1), 160 std::__invoke(__proj2, *__first2))) 161 return false; 162 return __first1 == __last1 && __first2 == __last2; 163 } 164 } 165 166 template<input_range _Range1, input_range _Range2, 167 typename _Pred = ranges::equal_to, 168 typename _Proj1 = identity, typename _Proj2 = identity> 169 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, 170 _Pred, _Proj1, _Proj2> 171 constexpr bool 172 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, 173 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 174 { 175 // _GLIBCXX_RESOLVE_LIB_DEFECTS 176 // 3560. ranges::equal [...] should short-circuit for sized_ranges 177 if constexpr (sized_range<_Range1>) 178 if constexpr (sized_range<_Range2>) 179 if (ranges::distance(__r1) != ranges::distance(__r2)) 180 return false; 181 182 return (*this)(ranges::begin(__r1), ranges::end(__r1), 183 ranges::begin(__r2), ranges::end(__r2), 184 std::move(__pred), 185 std::move(__proj1), std::move(__proj2)); 186 } 187 }; 188 189 inline constexpr __equal_fn equal{}; 190 191 namespace __detail 192 { 193 template<bool _IsMove, typename _OutIter, typename _InIter> 194 [[__gnu__::__always_inline__]] 195 constexpr void 196 __assign_one(_OutIter& __out, _InIter& __in) 197 { 198 if constexpr (_IsMove) 199 *__out = ranges::iter_move(__in); 200 else 201 *__out = *__in; 202 } 203 } // namespace __detail 204 205 template<typename _Iter, typename _Out> 206 struct in_out_result 207 { 208 [[no_unique_address]] _Iter in; 209 [[no_unique_address]] _Out out; 210 211 template<typename _Iter2, typename _Out2> 212 requires convertible_to<const _Iter&, _Iter2> 213 && convertible_to<const _Out&, _Out2> 214 constexpr 215 operator in_out_result<_Iter2, _Out2>() const & 216 { return {in, out}; } 217 218 template<typename _Iter2, typename _Out2> 219 requires convertible_to<_Iter, _Iter2> 220 && convertible_to<_Out, _Out2> 221 constexpr 222 operator in_out_result<_Iter2, _Out2>() && 223 { return {std::move(in), std::move(out)}; } 224 }; 225 226 template<typename _Iter, typename _Out> 227 using copy_result = in_out_result<_Iter, _Out>; 228 229 template<typename _Iter, typename _Out> 230 using move_result = in_out_result<_Iter, _Out>; 231 232 template<typename _Iter1, typename _Iter2> 233 using move_backward_result = in_out_result<_Iter1, _Iter2>; 234 235 template<typename _Iter1, typename _Iter2> 236 using copy_backward_result = in_out_result<_Iter1, _Iter2>; 237 238 template<bool _IsMove, 239 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, 240 bidirectional_iterator _Out> 241 requires (_IsMove 242 ? indirectly_movable<_Iter, _Out> 243 : indirectly_copyable<_Iter, _Out>) 244 constexpr __conditional_t<_IsMove, 245 move_backward_result<_Iter, _Out>, 246 copy_backward_result<_Iter, _Out>> 247 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result); 248 249 template<bool _IsMove, 250 input_iterator _Iter, sentinel_for<_Iter> _Sent, 251 weakly_incrementable _Out> 252 requires (_IsMove 253 ? indirectly_movable<_Iter, _Out> 254 : indirectly_copyable<_Iter, _Out>) 255 constexpr __conditional_t<_IsMove, 256 move_result<_Iter, _Out>, 257 copy_result<_Iter, _Out>> 258 __copy_or_move(_Iter __first, _Sent __last, _Out __result) 259 { 260 // TODO: implement more specializations to be at least on par with 261 // std::copy/std::move. 262 using __detail::__is_move_iterator; 263 using __detail::__is_reverse_iterator; 264 using __detail::__is_normal_iterator; 265 if constexpr (__is_move_iterator<_Iter> && same_as<_Iter, _Sent>) 266 { 267 auto [__in, __out] 268 = ranges::__copy_or_move<true>(std::move(__first).base(), 269 std::move(__last).base(), 270 std::move(__result)); 271 return {move_iterator{std::move(__in)}, std::move(__out)}; 272 } 273 else if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent> 274 && __is_reverse_iterator<_Out>) 275 { 276 auto [__in,__out] 277 = ranges::__copy_or_move_backward<_IsMove>(std::move(__last).base(), 278 std::move(__first).base(), 279 std::move(__result).base()); 280 return {reverse_iterator{std::move(__in)}, 281 reverse_iterator{std::move(__out)}}; 282 } 283 else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>) 284 { 285 auto [__in,__out] 286 = ranges::__copy_or_move<_IsMove>(__first.base(), __last.base(), 287 std::move(__result)); 288 return {decltype(__first){__in}, std::move(__out)}; 289 } 290 else if constexpr (__is_normal_iterator<_Out>) 291 { 292 auto [__in,__out] 293 = ranges::__copy_or_move<_IsMove>(std::move(__first), __last, __result.base()); 294 return {std::move(__in), decltype(__result){__out}}; 295 } 296 else if constexpr (sized_sentinel_for<_Sent, _Iter>) 297 { 298 if (!std::__is_constant_evaluated()) 299 { 300 if constexpr (__memcpyable<_Out, _Iter>::__value) 301 { 302 using _ValueTypeI = iter_value_t<_Iter>; 303 auto __num = __last - __first; 304 if (__num > 1) [[likely]] 305 __builtin_memmove(__result, __first, 306 sizeof(_ValueTypeI) * __num); 307 else if (__num == 1) 308 __detail::__assign_one<_IsMove>(__result, __first); 309 return {__first + __num, __result + __num}; 310 } 311 } 312 313 for (auto __n = __last - __first; __n > 0; --__n) 314 { 315 __detail::__assign_one<_IsMove>(__result, __first); 316 ++__first; 317 ++__result; 318 } 319 return {std::move(__first), std::move(__result)}; 320 } 321 else 322 { 323 while (__first != __last) 324 { 325 __detail::__assign_one<_IsMove>(__result, __first); 326 ++__first; 327 ++__result; 328 } 329 return {std::move(__first), std::move(__result)}; 330 } 331 } 332 333 struct __copy_fn 334 { 335 template<input_iterator _Iter, sentinel_for<_Iter> _Sent, 336 weakly_incrementable _Out> 337 requires indirectly_copyable<_Iter, _Out> 338 constexpr copy_result<_Iter, _Out> 339 operator()(_Iter __first, _Sent __last, _Out __result) const 340 { 341 return ranges::__copy_or_move<false>(std::move(__first), 342 std::move(__last), 343 std::move(__result)); 344 } 345 346 template<input_range _Range, weakly_incrementable _Out> 347 requires indirectly_copyable<iterator_t<_Range>, _Out> 348 constexpr copy_result<borrowed_iterator_t<_Range>, _Out> 349 operator()(_Range&& __r, _Out __result) const 350 { 351 return (*this)(ranges::begin(__r), ranges::end(__r), 352 std::move(__result)); 353 } 354 }; 355 356 inline constexpr __copy_fn copy{}; 357 358 struct __move_fn 359 { 360 template<input_iterator _Iter, sentinel_for<_Iter> _Sent, 361 weakly_incrementable _Out> 362 requires indirectly_movable<_Iter, _Out> 363 constexpr move_result<_Iter, _Out> 364 operator()(_Iter __first, _Sent __last, _Out __result) const 365 { 366 return ranges::__copy_or_move<true>(std::move(__first), 367 std::move(__last), 368 std::move(__result)); 369 } 370 371 template<input_range _Range, weakly_incrementable _Out> 372 requires indirectly_movable<iterator_t<_Range>, _Out> 373 constexpr move_result<borrowed_iterator_t<_Range>, _Out> 374 operator()(_Range&& __r, _Out __result) const 375 { 376 return (*this)(ranges::begin(__r), ranges::end(__r), 377 std::move(__result)); 378 } 379 }; 380 381 inline constexpr __move_fn move{}; 382 383 template<bool _IsMove, 384 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, 385 bidirectional_iterator _Out> 386 requires (_IsMove 387 ? indirectly_movable<_Iter, _Out> 388 : indirectly_copyable<_Iter, _Out>) 389 constexpr __conditional_t<_IsMove, 390 move_backward_result<_Iter, _Out>, 391 copy_backward_result<_Iter, _Out>> 392 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result) 393 { 394 // TODO: implement more specializations to be at least on par with 395 // std::copy_backward/std::move_backward. 396 using __detail::__is_reverse_iterator; 397 using __detail::__is_normal_iterator; 398 if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent> 399 && __is_reverse_iterator<_Out>) 400 { 401 auto [__in,__out] 402 = ranges::__copy_or_move<_IsMove>(std::move(__last).base(), 403 std::move(__first).base(), 404 std::move(__result).base()); 405 return {reverse_iterator{std::move(__in)}, 406 reverse_iterator{std::move(__out)}}; 407 } 408 else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>) 409 { 410 auto [__in,__out] 411 = ranges::__copy_or_move_backward<_IsMove>(__first.base(), 412 __last.base(), 413 std::move(__result)); 414 return {decltype(__first){__in}, std::move(__out)}; 415 } 416 else if constexpr (__is_normal_iterator<_Out>) 417 { 418 auto [__in,__out] 419 = ranges::__copy_or_move_backward<_IsMove>(std::move(__first), 420 std::move(__last), 421 __result.base()); 422 return {std::move(__in), decltype(__result){__out}}; 423 } 424 else if constexpr (sized_sentinel_for<_Sent, _Iter>) 425 { 426 if (!std::__is_constant_evaluated()) 427 { 428 if constexpr (__memcpyable<_Out, _Iter>::__value) 429 { 430 using _ValueTypeI = iter_value_t<_Iter>; 431 auto __num = __last - __first; 432 __result -= __num; 433 if (__num > 1) [[likely]] 434 __builtin_memmove(__result, __first, 435 sizeof(_ValueTypeI) * __num); 436 else if (__num == 1) 437 __detail::__assign_one<_IsMove>(__result, __first); 438 return {__first + __num, __result}; 439 } 440 } 441 442 auto __lasti = ranges::next(__first, __last); 443 auto __tail = __lasti; 444 445 for (auto __n = __last - __first; __n > 0; --__n) 446 { 447 --__tail; 448 --__result; 449 __detail::__assign_one<_IsMove>(__result, __tail); 450 } 451 return {std::move(__lasti), std::move(__result)}; 452 } 453 else 454 { 455 auto __lasti = ranges::next(__first, __last); 456 auto __tail = __lasti; 457 458 while (__first != __tail) 459 { 460 --__tail; 461 --__result; 462 __detail::__assign_one<_IsMove>(__result, __tail); 463 } 464 return {std::move(__lasti), std::move(__result)}; 465 } 466 } 467 468 struct __copy_backward_fn 469 { 470 template<bidirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 471 bidirectional_iterator _Iter2> 472 requires indirectly_copyable<_Iter1, _Iter2> 473 constexpr copy_backward_result<_Iter1, _Iter2> 474 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result) const 475 { 476 return ranges::__copy_or_move_backward<false>(std::move(__first), 477 std::move(__last), 478 std::move(__result)); 479 } 480 481 template<bidirectional_range _Range, bidirectional_iterator _Iter> 482 requires indirectly_copyable<iterator_t<_Range>, _Iter> 483 constexpr copy_backward_result<borrowed_iterator_t<_Range>, _Iter> 484 operator()(_Range&& __r, _Iter __result) const 485 { 486 return (*this)(ranges::begin(__r), ranges::end(__r), 487 std::move(__result)); 488 } 489 }; 490 491 inline constexpr __copy_backward_fn copy_backward{}; 492 493 struct __move_backward_fn 494 { 495 template<bidirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 496 bidirectional_iterator _Iter2> 497 requires indirectly_movable<_Iter1, _Iter2> 498 constexpr move_backward_result<_Iter1, _Iter2> 499 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result) const 500 { 501 return ranges::__copy_or_move_backward<true>(std::move(__first), 502 std::move(__last), 503 std::move(__result)); 504 } 505 506 template<bidirectional_range _Range, bidirectional_iterator _Iter> 507 requires indirectly_movable<iterator_t<_Range>, _Iter> 508 constexpr move_backward_result<borrowed_iterator_t<_Range>, _Iter> 509 operator()(_Range&& __r, _Iter __result) const 510 { 511 return (*this)(ranges::begin(__r), ranges::end(__r), 512 std::move(__result)); 513 } 514 }; 515 516 inline constexpr __move_backward_fn move_backward{}; 517 518 template<typename _Iter, typename _Out> 519 using copy_n_result = in_out_result<_Iter, _Out>; 520 521 struct __copy_n_fn 522 { 523 template<input_iterator _Iter, weakly_incrementable _Out> 524 requires indirectly_copyable<_Iter, _Out> 525 constexpr copy_n_result<_Iter, _Out> 526 operator()(_Iter __first, iter_difference_t<_Iter> __n, 527 _Out __result) const 528 { 529 if constexpr (random_access_iterator<_Iter>) 530 { 531 if (__n > 0) 532 return ranges::copy(__first, __first + __n, std::move(__result)); 533 } 534 else 535 { 536 for (; __n > 0; --__n, (void)++__result, (void)++__first) 537 *__result = *__first; 538 } 539 return {std::move(__first), std::move(__result)}; 540 } 541 }; 542 543 inline constexpr __copy_n_fn copy_n{}; 544 545 struct __fill_n_fn 546 { 547 template<typename _Out, 548 typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>)> 549 requires output_iterator<_Out, const _Tp&> 550 constexpr _Out 551 operator()(_Out __first, iter_difference_t<_Out> __n, 552 const _Tp& __value) const 553 { 554 // TODO: implement more specializations to be at least on par with 555 // std::fill_n 556 if (__n <= 0) 557 return __first; 558 559 if constexpr (is_scalar_v<_Tp>) 560 { 561 // TODO: Generalize this optimization to contiguous iterators. 562 if constexpr (is_pointer_v<_Out> 563 // Note that __is_byte already implies !is_volatile. 564 && __is_byte<remove_pointer_t<_Out>>::__value 565 && integral<_Tp>) 566 { 567 if (!std::__is_constant_evaluated()) 568 { 569 __builtin_memset(__first, 570 static_cast<unsigned char>(__value), 571 __n); 572 return __first + __n; 573 } 574 } 575 576 const auto __tmp = __value; 577 for (; __n > 0; --__n, (void)++__first) 578 *__first = __tmp; 579 return __first; 580 } 581 else 582 { 583 for (; __n > 0; --__n, (void)++__first) 584 *__first = __value; 585 return __first; 586 } 587 } 588 }; 589 590 inline constexpr __fill_n_fn fill_n{}; 591 592 struct __fill_fn 593 { 594 template<typename _Out, 595 sentinel_for<_Out> _Sent, 596 typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>)> 597 requires output_iterator<_Out, const _Tp&> 598 constexpr _Out 599 operator()(_Out __first, _Sent __last, const _Tp& __value) const 600 { 601 // TODO: implement more specializations to be at least on par with 602 // std::fill 603 if constexpr (sized_sentinel_for<_Sent, _Out>) 604 { 605 const auto __len = __last - __first; 606 return ranges::fill_n(std::move(__first), __len, __value); 607 } 608 else if constexpr (is_scalar_v<_Tp>) 609 { 610 const auto __tmp = __value; 611 for (; __first != __last; ++__first) 612 *__first = __tmp; 613 return __first; 614 } 615 else 616 { 617 for (; __first != __last; ++__first) 618 *__first = __value; 619 return __first; 620 } 621 } 622 623 template<typename _Range, 624 typename _Tp _GLIBCXX26_DEF_VAL_T(range_value_t<_Range>)> 625 requires output_range<_Range, const _Tp&> 626 constexpr borrowed_iterator_t<_Range> 627 operator()(_Range&& __r, const _Tp& __value) const 628 { 629 return (*this)(ranges::begin(__r), ranges::end(__r), __value); 630 } 631 }; 632 633 inline constexpr __fill_fn fill{}; 634 } 635 _GLIBCXX_END_NAMESPACE_VERSION 636 } // namespace std 637 #endif // concepts 638 #endif // C++20 639 #endif // _RANGES_ALGOBASE_H
