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