Where Online Learning is simpler!
The C and C++ Include Header Files
/usr/include/c++/13/bits/ranges_algobase.h
$ cat -n /usr/include/c++/13/bits/ranges_algobase.h 1 // Core algorithmic facilities -*- C++ -*- 2 3 // Copyright (C) 2020-2023 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 42 #if __cpp_lib_concepts 43 namespace std _GLIBCXX_VISIBILITY(default) 44 { 45 _GLIBCXX_BEGIN_NAMESPACE_VERSION 46 namespace ranges 47 { 48 namespace __detail 49 { 50 template<typename _Tp> 51 constexpr inline bool __is_normal_iterator = false; 52 53 template<typename _Iterator, typename _Container> 54 constexpr inline bool 55 __is_normal_iterator<__gnu_cxx::__normal_iterator<_Iterator, 56 _Container>> = true; 57 58 template<typename _Tp> 59 constexpr inline bool __is_reverse_iterator = false; 60 61 template<typename _Iterator> 62 constexpr inline bool 63 __is_reverse_iterator<reverse_iterator<_Iterator>> = true; 64 65 template<typename _Tp> 66 constexpr inline bool __is_move_iterator = false; 67 68 template<typename _Iterator> 69 constexpr inline bool 70 __is_move_iterator<move_iterator<_Iterator>> = true; 71 } // namespace __detail 72 73 struct __equal_fn 74 { 75 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 76 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, 77 typename _Pred = ranges::equal_to, 78 typename _Proj1 = identity, typename _Proj2 = identity> 79 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> 80 constexpr bool 81 operator()(_Iter1 __first1, _Sent1 __last1, 82 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, 83 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 84 { 85 // TODO: implement more specializations to at least have parity with 86 // std::equal. 87 if constexpr (__detail::__is_normal_iterator<_Iter1> 88 && same_as<_Iter1, _Sent1>) 89 return (*this)(__first1.base(), __last1.base(), 90 std::move(__first2), std::move(__last2), 91 std::move(__pred), 92 std::move(__proj1), std::move(__proj2)); 93 else if constexpr (__detail::__is_normal_iterator<_Iter2> 94 && same_as<_Iter2, _Sent2>) 95 return (*this)(std::move(__first1), std::move(__last1), 96 __first2.base(), __last2.base(), 97 std::move(__pred), 98 std::move(__proj1), std::move(__proj2)); 99 else if constexpr (sized_sentinel_for<_Sent1, _Iter1> 100 && sized_sentinel_for<_Sent2, _Iter2>) 101 { 102 auto __d1 = ranges::distance(__first1, __last1); 103 auto __d2 = ranges::distance(__first2, __last2); 104 if (__d1 != __d2) 105 return false; 106 107 using _ValueType1 = iter_value_t<_Iter1>; 108 constexpr bool __use_memcmp 109 = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>) 110 && __memcmpable<_Iter1, _Iter2>::__value 111 && is_same_v<_Pred, ranges::equal_to> 112 && is_same_v<_Proj1, identity> 113 && is_same_v<_Proj2, identity>); 114 if constexpr (__use_memcmp) 115 { 116 if (const size_t __len = (__last1 - __first1)) 117 return !std::__memcmp(__first1, __first2, __len); 118 return true; 119 } 120 else 121 { 122 for (; __first1 != __last1; ++__first1, (void)++__first2) 123 if (!(bool)std::__invoke(__pred, 124 std::__invoke(__proj1, *__first1), 125 std::__invoke(__proj2, *__first2))) 126 return false; 127 return true; 128 } 129 } 130 else 131 { 132 for (; __first1 != __last1 && __first2 != __last2; 133 ++__first1, (void)++__first2) 134 if (!(bool)std::__invoke(__pred, 135 std::__invoke(__proj1, *__first1), 136 std::__invoke(__proj2, *__first2))) 137 return false; 138 return __first1 == __last1 && __first2 == __last2; 139 } 140 } 141 142 template<input_range _Range1, input_range _Range2, 143 typename _Pred = ranges::equal_to, 144 typename _Proj1 = identity, typename _Proj2 = identity> 145 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, 146 _Pred, _Proj1, _Proj2> 147 constexpr bool 148 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, 149 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 150 { 151 return (*this)(ranges::begin(__r1), ranges::end(__r1), 152 ranges::begin(__r2), ranges::end(__r2), 153 std::move(__pred), 154 std::move(__proj1), std::move(__proj2)); 155 } 156 }; 157 158 inline constexpr __equal_fn equal{}; 159 160 template<typename _Iter, typename _Out> 161 struct in_out_result 162 { 163 [[no_unique_address]] _Iter in; 164 [[no_unique_address]] _Out out; 165 166 template<typename _Iter2, typename _Out2> 167 requires convertible_to<const _Iter&, _Iter2> 168 && convertible_to<const _Out&, _Out2> 169 constexpr 170 operator in_out_result<_Iter2, _Out2>() const & 171 { return {in, out}; } 172 173 template<typename _Iter2, typename _Out2> 174 requires convertible_to<_Iter, _Iter2> 175 && convertible_to<_Out, _Out2> 176 constexpr 177 operator in_out_result<_Iter2, _Out2>() && 178 { return {std::move(in), std::move(out)}; } 179 }; 180 181 template<typename _Iter, typename _Out> 182 using copy_result = in_out_result<_Iter, _Out>; 183 184 template<typename _Iter, typename _Out> 185 using move_result = in_out_result<_Iter, _Out>; 186 187 template<typename _Iter1, typename _Iter2> 188 using move_backward_result = in_out_result<_Iter1, _Iter2>; 189 190 template<typename _Iter1, typename _Iter2> 191 using copy_backward_result = in_out_result<_Iter1, _Iter2>; 192 193 template<bool _IsMove, 194 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, 195 bidirectional_iterator _Out> 196 requires (_IsMove 197 ? indirectly_movable<_Iter, _Out> 198 : indirectly_copyable<_Iter, _Out>) 199 constexpr __conditional_t<_IsMove, 200 move_backward_result<_Iter, _Out>, 201 copy_backward_result<_Iter, _Out>> 202 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result); 203 204 template<bool _IsMove, 205 input_iterator _Iter, sentinel_for<_Iter> _Sent, 206 weakly_incrementable _Out> 207 requires (_IsMove 208 ? indirectly_movable<_Iter, _Out> 209 : indirectly_copyable<_Iter, _Out>) 210 constexpr __conditional_t<_IsMove, 211 move_result<_Iter, _Out>, 212 copy_result<_Iter, _Out>> 213 __copy_or_move(_Iter __first, _Sent __last, _Out __result) 214 { 215 // TODO: implement more specializations to be at least on par with 216 // std::copy/std::move. 217 using __detail::__is_move_iterator; 218 using __detail::__is_reverse_iterator; 219 using __detail::__is_normal_iterator; 220 if constexpr (__is_move_iterator<_Iter> && same_as<_Iter, _Sent>) 221 { 222 auto [__in, __out] 223 = ranges::__copy_or_move<true>(std::move(__first).base(), 224 std::move(__last).base(), 225 std::move(__result)); 226 return {move_iterator{std::move(__in)}, std::move(__out)}; 227 } 228 else if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent> 229 && __is_reverse_iterator<_Out>) 230 { 231 auto [__in,__out] 232 = ranges::__copy_or_move_backward<_IsMove>(std::move(__last).base(), 233 std::move(__first).base(), 234 std::move(__result).base()); 235 return {reverse_iterator{std::move(__in)}, 236 reverse_iterator{std::move(__out)}}; 237 } 238 else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>) 239 { 240 auto [__in,__out] 241 = ranges::__copy_or_move<_IsMove>(__first.base(), __last.base(), 242 std::move(__result)); 243 return {decltype(__first){__in}, std::move(__out)}; 244 } 245 else if constexpr (__is_normal_iterator<_Out>) 246 { 247 auto [__in,__out] 248 = ranges::__copy_or_move<_IsMove>(std::move(__first), __last, __result.base()); 249 return {std::move(__in), decltype(__result){__out}}; 250 } 251 else if constexpr (sized_sentinel_for<_Sent, _Iter>) 252 { 253 if (!std::__is_constant_evaluated()) 254 { 255 if constexpr (__memcpyable<_Iter, _Out>::__value) 256 { 257 using _ValueTypeI = iter_value_t<_Iter>; 258 static_assert(_IsMove 259 ? is_move_assignable_v<_ValueTypeI> 260 : is_copy_assignable_v<_ValueTypeI>); 261 auto __num = __last - __first; 262 if (__num) 263 __builtin_memmove(__result, __first, 264 sizeof(_ValueTypeI) * __num); 265 return {__first + __num, __result + __num}; 266 } 267 } 268 269 for (auto __n = __last - __first; __n > 0; --__n) 270 { 271 if constexpr (_IsMove) 272 *__result = std::move(*__first); 273 else 274 *__result = *__first; 275 ++__first; 276 ++__result; 277 } 278 return {std::move(__first), std::move(__result)}; 279 } 280 else 281 { 282 while (__first != __last) 283 { 284 if constexpr (_IsMove) 285 *__result = std::move(*__first); 286 else 287 *__result = *__first; 288 ++__first; 289 ++__result; 290 } 291 return {std::move(__first), std::move(__result)}; 292 } 293 } 294 295 struct __copy_fn 296 { 297 template<input_iterator _Iter, sentinel_for<_Iter> _Sent, 298 weakly_incrementable _Out> 299 requires indirectly_copyable<_Iter, _Out> 300 constexpr copy_result<_Iter, _Out> 301 operator()(_Iter __first, _Sent __last, _Out __result) const 302 { 303 return ranges::__copy_or_move<false>(std::move(__first), 304 std::move(__last), 305 std::move(__result)); 306 } 307 308 template<input_range _Range, weakly_incrementable _Out> 309 requires indirectly_copyable<iterator_t<_Range>, _Out> 310 constexpr copy_result<borrowed_iterator_t<_Range>, _Out> 311 operator()(_Range&& __r, _Out __result) const 312 { 313 return (*this)(ranges::begin(__r), ranges::end(__r), 314 std::move(__result)); 315 } 316 }; 317 318 inline constexpr __copy_fn copy{}; 319 320 struct __move_fn 321 { 322 template<input_iterator _Iter, sentinel_for<_Iter> _Sent, 323 weakly_incrementable _Out> 324 requires indirectly_movable<_Iter, _Out> 325 constexpr move_result<_Iter, _Out> 326 operator()(_Iter __first, _Sent __last, _Out __result) const 327 { 328 return ranges::__copy_or_move<true>(std::move(__first), 329 std::move(__last), 330 std::move(__result)); 331 } 332 333 template<input_range _Range, weakly_incrementable _Out> 334 requires indirectly_movable<iterator_t<_Range>, _Out> 335 constexpr move_result<borrowed_iterator_t<_Range>, _Out> 336 operator()(_Range&& __r, _Out __result) const 337 { 338 return (*this)(ranges::begin(__r), ranges::end(__r), 339 std::move(__result)); 340 } 341 }; 342 343 inline constexpr __move_fn move{}; 344 345 template<bool _IsMove, 346 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, 347 bidirectional_iterator _Out> 348 requires (_IsMove 349 ? indirectly_movable<_Iter, _Out> 350 : indirectly_copyable<_Iter, _Out>) 351 constexpr __conditional_t<_IsMove, 352 move_backward_result<_Iter, _Out>, 353 copy_backward_result<_Iter, _Out>> 354 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result) 355 { 356 // TODO: implement more specializations to be at least on par with 357 // std::copy_backward/std::move_backward. 358 using __detail::__is_reverse_iterator; 359 using __detail::__is_normal_iterator; 360 if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent> 361 && __is_reverse_iterator<_Out>) 362 { 363 auto [__in,__out] 364 = ranges::__copy_or_move<_IsMove>(std::move(__last).base(), 365 std::move(__first).base(), 366 std::move(__result).base()); 367 return {reverse_iterator{std::move(__in)}, 368 reverse_iterator{std::move(__out)}}; 369 } 370 else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>) 371 { 372 auto [__in,__out] 373 = ranges::__copy_or_move_backward<_IsMove>(__first.base(), 374 __last.base(), 375 std::move(__result)); 376 return {decltype(__first){__in}, std::move(__out)}; 377 } 378 else if constexpr (__is_normal_iterator<_Out>) 379 { 380 auto [__in,__out] 381 = ranges::__copy_or_move_backward<_IsMove>(std::move(__first), 382 std::move(__last), 383 __result.base()); 384 return {std::move(__in), decltype(__result){__out}}; 385 } 386 else if constexpr (sized_sentinel_for<_Sent, _Iter>) 387 { 388 if (!std::__is_constant_evaluated()) 389 { 390 if constexpr (__memcpyable<_Out, _Iter>::__value) 391 { 392 using _ValueTypeI = iter_value_t<_Iter>; 393 static_assert(_IsMove 394 ? is_move_assignable_v<_ValueTypeI> 395 : is_copy_assignable_v<_ValueTypeI>); 396 auto __num = __last - __first; 397 if (__num) 398 __builtin_memmove(__result - __num, __first, 399 sizeof(_ValueTypeI) * __num); 400 return {__first + __num, __result - __num}; 401 } 402 } 403 404 auto __lasti = ranges::next(__first, __last); 405 auto __tail = __lasti; 406 407 for (auto __n = __last - __first; __n > 0; --__n) 408 { 409 --__tail; 410 --__result; 411 if constexpr (_IsMove) 412 *__result = std::move(*__tail); 413 else 414 *__result = *__tail; 415 } 416 return {std::move(__lasti), std::move(__result)}; 417 } 418 else 419 { 420 auto __lasti = ranges::next(__first, __last); 421 auto __tail = __lasti; 422 423 while (__first != __tail) 424 { 425 --__tail; 426 --__result; 427 if constexpr (_IsMove) 428 *__result = std::move(*__tail); 429 else 430 *__result = *__tail; 431 } 432 return {std::move(__lasti), std::move(__result)}; 433 } 434 } 435 436 struct __copy_backward_fn 437 { 438 template<bidirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 439 bidirectional_iterator _Iter2> 440 requires indirectly_copyable<_Iter1, _Iter2> 441 constexpr copy_backward_result<_Iter1, _Iter2> 442 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result) const 443 { 444 return ranges::__copy_or_move_backward<false>(std::move(__first), 445 std::move(__last), 446 std::move(__result)); 447 } 448 449 template<bidirectional_range _Range, bidirectional_iterator _Iter> 450 requires indirectly_copyable<iterator_t<_Range>, _Iter> 451 constexpr copy_backward_result<borrowed_iterator_t<_Range>, _Iter> 452 operator()(_Range&& __r, _Iter __result) const 453 { 454 return (*this)(ranges::begin(__r), ranges::end(__r), 455 std::move(__result)); 456 } 457 }; 458 459 inline constexpr __copy_backward_fn copy_backward{}; 460 461 struct __move_backward_fn 462 { 463 template<bidirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 464 bidirectional_iterator _Iter2> 465 requires indirectly_movable<_Iter1, _Iter2> 466 constexpr move_backward_result<_Iter1, _Iter2> 467 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result) const 468 { 469 return ranges::__copy_or_move_backward<true>(std::move(__first), 470 std::move(__last), 471 std::move(__result)); 472 } 473 474 template<bidirectional_range _Range, bidirectional_iterator _Iter> 475 requires indirectly_movable<iterator_t<_Range>, _Iter> 476 constexpr move_backward_result<borrowed_iterator_t<_Range>, _Iter> 477 operator()(_Range&& __r, _Iter __result) const 478 { 479 return (*this)(ranges::begin(__r), ranges::end(__r), 480 std::move(__result)); 481 } 482 }; 483 484 inline constexpr __move_backward_fn move_backward{}; 485 486 template<typename _Iter, typename _Out> 487 using copy_n_result = in_out_result<_Iter, _Out>; 488 489 struct __copy_n_fn 490 { 491 template<input_iterator _Iter, weakly_incrementable _Out> 492 requires indirectly_copyable<_Iter, _Out> 493 constexpr copy_n_result<_Iter, _Out> 494 operator()(_Iter __first, iter_difference_t<_Iter> __n, 495 _Out __result) const 496 { 497 if constexpr (random_access_iterator<_Iter>) 498 { 499 if (__n > 0) 500 return ranges::copy(__first, __first + __n, std::move(__result)); 501 } 502 else 503 { 504 for (; __n > 0; --__n, (void)++__result, (void)++__first) 505 *__result = *__first; 506 } 507 return {std::move(__first), std::move(__result)}; 508 } 509 }; 510 511 inline constexpr __copy_n_fn copy_n{}; 512 513 struct __fill_n_fn 514 { 515 template<typename _Tp, output_iterator<const _Tp&> _Out> 516 constexpr _Out 517 operator()(_Out __first, iter_difference_t<_Out> __n, 518 const _Tp& __value) const 519 { 520 // TODO: implement more specializations to be at least on par with 521 // std::fill_n 522 if (__n <= 0) 523 return __first; 524 525 if constexpr (is_scalar_v<_Tp>) 526 { 527 // TODO: Generalize this optimization to contiguous iterators. 528 if constexpr (is_pointer_v<_Out> 529 // Note that __is_byte already implies !is_volatile. 530 && __is_byte<remove_pointer_t<_Out>>::__value 531 && integral<_Tp>) 532 { 533 if (!std::__is_constant_evaluated()) 534 { 535 __builtin_memset(__first, 536 static_cast<unsigned char>(__value), 537 __n); 538 return __first + __n; 539 } 540 } 541 542 const auto __tmp = __value; 543 for (; __n > 0; --__n, (void)++__first) 544 *__first = __tmp; 545 return __first; 546 } 547 else 548 { 549 for (; __n > 0; --__n, (void)++__first) 550 *__first = __value; 551 return __first; 552 } 553 } 554 }; 555 556 inline constexpr __fill_n_fn fill_n{}; 557 558 struct __fill_fn 559 { 560 template<typename _Tp, 561 output_iterator<const _Tp&> _Out, sentinel_for<_Out> _Sent> 562 constexpr _Out 563 operator()(_Out __first, _Sent __last, const _Tp& __value) const 564 { 565 // TODO: implement more specializations to be at least on par with 566 // std::fill 567 if constexpr (sized_sentinel_for<_Sent, _Out>) 568 { 569 const auto __len = __last - __first; 570 return ranges::fill_n(__first, __len, __value); 571 } 572 else if constexpr (is_scalar_v<_Tp>) 573 { 574 const auto __tmp = __value; 575 for (; __first != __last; ++__first) 576 *__first = __tmp; 577 return __first; 578 } 579 else 580 { 581 for (; __first != __last; ++__first) 582 *__first = __value; 583 return __first; 584 } 585 } 586 587 template<typename _Tp, output_range<const _Tp&> _Range> 588 constexpr borrowed_iterator_t<_Range> 589 operator()(_Range&& __r, const _Tp& __value) const 590 { 591 return (*this)(ranges::begin(__r), ranges::end(__r), __value); 592 } 593 }; 594 595 inline constexpr __fill_fn fill{}; 596 } 597 _GLIBCXX_END_NAMESPACE_VERSION 598 } // namespace std 599 #endif // concepts 600 #endif // C++20 601 #endif // _RANGES_ALGOBASE_H
Contact us
|
About us
|
Term of use
|
Copyright © 2000-2025 MyWebUniversity.com ™
