Where Online Learning is simpler!
The C and C++ Include Header Files
/usr/include/c++/13/bits/iterator_concepts.h
$ cat -n /usr/include/c++/13/bits/iterator_concepts.h 1 // Concepts and traits for use with iterators -*- C++ -*- 2 3 // Copyright (C) 2019-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/iterator_concepts.h 26 * This is an internal header file, included by other library headers. 27 * Do not attempt to use it directly. @headername{iterator} 28 */ 29 30 #ifndef _ITERATOR_CONCEPTS_H 31 #define _ITERATOR_CONCEPTS_H 1 32 33 #pragma GCC system_header 34 35 #if __cplusplus >= 202002L 36 #include <concepts> 37 #include <bits/ptr_traits.h> // to_address 38 #include <bits/ranges_cmp.h> // identity, ranges::less 39 40 namespace std _GLIBCXX_VISIBILITY(default) 41 { 42 _GLIBCXX_BEGIN_NAMESPACE_VERSION 43 44 /** A sentinel type that can be used to check for the end of a range. 45 * 46 * For some iterator types the past-the-end sentinel value is independent 47 * of the underlying sequence, and a default sentinel can be used with them. 48 * For example, a `std::counted_iterator` keeps a count of how many elements 49 * remain, and so checking for the past-the-end value only requires checking 50 * if that count has reached zero. A past-the-end `std::istream_iterator` is 51 * equal to the default-constructed value, which can be easily checked. 52 * 53 * Comparing iterators of these types to `std::default_sentinel` is a 54 * convenient way to check if the end has been reached. 55 * 56 * @since C++20 57 */ 58 struct default_sentinel_t { }; 59 60 /// A default sentinel value. 61 inline constexpr default_sentinel_t default_sentinel{}; 62 63 #if __cpp_lib_concepts 64 struct input_iterator_tag; 65 struct output_iterator_tag; 66 struct forward_iterator_tag; 67 struct bidirectional_iterator_tag; 68 struct random_access_iterator_tag; 69 struct contiguous_iterator_tag; 70 71 template<typename _Iterator> 72 struct iterator_traits; 73 74 template<typename _Tp> requires is_object_v<_Tp> 75 struct iterator_traits<_Tp*>; 76 77 template<typename _Iterator, typename> 78 struct __iterator_traits; 79 80 namespace __detail 81 { 82 template<typename _Tp> 83 using __with_ref = _Tp&; 84 85 template<typename _Tp> 86 concept __can_reference = requires { typename __with_ref<_Tp>; }; 87 88 template<typename _Tp> 89 concept __dereferenceable = requires(_Tp& __t) 90 { 91 { *__t } -> __can_reference; 92 }; 93 } // namespace __detail 94 95 template<__detail::__dereferenceable _Tp> 96 using iter_reference_t = decltype(*std::declval<_Tp&>()); 97 98 namespace ranges 99 { 100 namespace __cust_imove 101 { 102 void iter_move(); 103 104 template<typename _Tp> 105 concept __adl_imove 106 = (std::__detail::__class_or_enum<remove_reference_t<_Tp>>) 107 && requires(_Tp&& __t) { iter_move(static_cast<_Tp&&>(__t)); }; 108 109 struct _IMove 110 { 111 private: 112 template<typename _Tp> 113 struct __result 114 { using type = iter_reference_t<_Tp>; }; 115 116 template<typename _Tp> 117 requires __adl_imove<_Tp> 118 struct __result<_Tp> 119 { using type = decltype(iter_move(std::declval<_Tp>())); }; 120 121 template<typename _Tp> 122 requires (!__adl_imove<_Tp>) 123 && is_lvalue_reference_v<iter_reference_t<_Tp>> 124 struct __result<_Tp> 125 { using type = remove_reference_t<iter_reference_t<_Tp>>&&; }; 126 127 template<typename _Tp> 128 static constexpr bool 129 _S_noexcept() 130 { 131 if constexpr (__adl_imove<_Tp>) 132 return noexcept(iter_move(std::declval<_Tp>())); 133 else 134 return noexcept(*std::declval<_Tp>()); 135 } 136 137 public: 138 // The result type of iter_move(std::declval<_Tp>()) 139 template<std::__detail::__dereferenceable _Tp> 140 using __type = typename __result<_Tp>::type; 141 142 template<std::__detail::__dereferenceable _Tp> 143 [[nodiscard]] 144 constexpr __type<_Tp> 145 operator()(_Tp&& __e) const 146 noexcept(_S_noexcept<_Tp>()) 147 { 148 if constexpr (__adl_imove<_Tp>) 149 return iter_move(static_cast<_Tp&&>(__e)); 150 else if constexpr (is_lvalue_reference_v<iter_reference_t<_Tp>>) 151 return static_cast<__type<_Tp>>(*__e); 152 else 153 return *__e; 154 } 155 }; 156 } // namespace __cust_imove 157 158 inline namespace __cust 159 { 160 inline constexpr __cust_imove::_IMove iter_move{}; 161 } // inline namespace __cust 162 } // namespace ranges 163 164 template<__detail::__dereferenceable _Tp> 165 requires __detail:: 166 __can_reference<ranges::__cust_imove::_IMove::__type<_Tp&>> 167 using iter_rvalue_reference_t 168 = ranges::__cust_imove::_IMove::__type<_Tp&>; 169 170 template<typename> struct incrementable_traits { }; 171 172 template<typename _Tp> requires is_object_v<_Tp> 173 struct incrementable_traits<_Tp*> 174 { using difference_type = ptrdiff_t; }; 175 176 template<typename _Iter> 177 struct incrementable_traits<const _Iter> 178 : incrementable_traits<_Iter> { }; 179 180 template<typename _Tp> requires requires { typename _Tp::difference_type; } 181 struct incrementable_traits<_Tp> 182 { using difference_type = typename _Tp::difference_type; }; 183 184 template<typename _Tp> 185 requires (!requires { typename _Tp::difference_type; } 186 && requires(const _Tp& __a, const _Tp& __b) 187 { { __a - __b } -> integral; }) 188 struct incrementable_traits<_Tp> 189 { 190 using difference_type 191 = make_signed_t<decltype(std::declval<_Tp>() - std::declval<_Tp>())>; 192 }; 193 194 #if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__ 195 // __int128 is incrementable even if !integral<__int128> 196 template<> 197 struct incrementable_traits<__int128> 198 { using difference_type = __int128; }; 199 200 template<> 201 struct incrementable_traits<unsigned __int128> 202 { using difference_type = __int128; }; 203 #endif 204 205 namespace __detail 206 { 207 // An iterator such that iterator_traits<_Iter> names a specialization 208 // generated from the primary template. 209 template<typename _Iter> 210 concept __primary_traits_iter 211 = __is_base_of(__iterator_traits<_Iter, void>, iterator_traits<_Iter>); 212 213 template<typename _Iter, typename _Tp> 214 struct __iter_traits_impl 215 { using type = iterator_traits<_Iter>; }; 216 217 template<typename _Iter, typename _Tp> 218 requires __primary_traits_iter<_Iter> 219 struct __iter_traits_impl<_Iter, _Tp> 220 { using type = _Tp; }; 221 222 // ITER_TRAITS 223 template<typename _Iter, typename _Tp = _Iter> 224 using __iter_traits = typename __iter_traits_impl<_Iter, _Tp>::type; 225 226 template<typename _Tp> 227 using __iter_diff_t = typename 228 __iter_traits<_Tp, incrementable_traits<_Tp>>::difference_type; 229 } // namespace __detail 230 231 template<typename _Tp> 232 using iter_difference_t = __detail::__iter_diff_t<remove_cvref_t<_Tp>>; 233 234 namespace __detail 235 { 236 template<typename> struct __cond_value_type { }; 237 238 template<typename _Tp> requires is_object_v<_Tp> 239 struct __cond_value_type<_Tp> 240 { using value_type = remove_cv_t<_Tp>; }; 241 242 template<typename _Tp> 243 concept __has_member_value_type 244 = requires { typename _Tp::value_type; }; 245 246 template<typename _Tp> 247 concept __has_member_element_type 248 = requires { typename _Tp::element_type; }; 249 250 } // namespace __detail 251 252 template<typename> struct indirectly_readable_traits { }; 253 254 template<typename _Tp> 255 struct indirectly_readable_traits<_Tp*> 256 : __detail::__cond_value_type<_Tp> 257 { }; 258 259 template<typename _Iter> requires is_array_v<_Iter> 260 struct indirectly_readable_traits<_Iter> 261 { using value_type = remove_cv_t<remove_extent_t<_Iter>>; }; 262 263 template<typename _Iter> 264 struct indirectly_readable_traits<const _Iter> 265 : indirectly_readable_traits<_Iter> 266 { }; 267 268 template<__detail::__has_member_value_type _Tp> 269 struct indirectly_readable_traits<_Tp> 270 : __detail::__cond_value_type<typename _Tp::value_type> 271 { }; 272 273 template<__detail::__has_member_element_type _Tp> 274 struct indirectly_readable_traits<_Tp> 275 : __detail::__cond_value_type<typename _Tp::element_type> 276 { }; 277 278 // _GLIBCXX_RESOLVE_LIB_DEFECTS 279 // 3446. indirectly_readable_traits ambiguity for types with both [...] 280 template<__detail::__has_member_value_type _Tp> 281 requires __detail::__has_member_element_type<_Tp> 282 && same_as<remove_cv_t<typename _Tp::element_type>, 283 remove_cv_t<typename _Tp::value_type>> 284 struct indirectly_readable_traits<_Tp> 285 : __detail::__cond_value_type<typename _Tp::value_type> 286 { }; 287 288 // _GLIBCXX_RESOLVE_LIB_DEFECTS 289 // 3541. indirectly_readable_traits should be SFINAE-friendly for all types 290 template<__detail::__has_member_value_type _Tp> 291 requires __detail::__has_member_element_type<_Tp> 292 struct indirectly_readable_traits<_Tp> 293 { }; 294 295 namespace __detail 296 { 297 template<typename _Tp> 298 using __iter_value_t = typename 299 __iter_traits<_Tp, indirectly_readable_traits<_Tp>>::value_type; 300 } // namespace __detail 301 302 template<typename _Tp> 303 using iter_value_t = __detail::__iter_value_t<remove_cvref_t<_Tp>>; 304 305 namespace __detail 306 { 307 // _GLIBCXX_RESOLVE_LIB_DEFECTS 308 // 3420. cpp17-iterator should check [type] looks like an iterator first 309 template<typename _Iter> 310 concept __cpp17_iterator = requires(_Iter __it) 311 { 312 { *__it } -> __can_reference; 313 { ++__it } -> same_as<_Iter&>; 314 { *__it++ } -> __can_reference; 315 } && copyable<_Iter>; 316 317 template<typename _Iter> 318 concept __cpp17_input_iterator = __cpp17_iterator<_Iter> 319 && equality_comparable<_Iter> 320 && requires(_Iter __it) 321 { 322 typename incrementable_traits<_Iter>::difference_type; 323 typename indirectly_readable_traits<_Iter>::value_type; 324 typename common_reference_t<iter_reference_t<_Iter>&&, 325 typename indirectly_readable_traits<_Iter>::value_type&>; 326 typename common_reference_t<decltype(*__it++)&&, 327 typename indirectly_readable_traits<_Iter>::value_type&>; 328 requires signed_integral< 329 typename incrementable_traits<_Iter>::difference_type>; 330 }; 331 332 template<typename _Iter> 333 concept __cpp17_fwd_iterator = __cpp17_input_iterator<_Iter> 334 && constructible_from<_Iter> 335 && is_lvalue_reference_v<iter_reference_t<_Iter>> 336 && same_as<remove_cvref_t<iter_reference_t<_Iter>>, 337 typename indirectly_readable_traits<_Iter>::value_type> 338 && requires(_Iter __it) 339 { 340 { __it++ } -> convertible_to<const _Iter&>; 341 { *__it++ } -> same_as<iter_reference_t<_Iter>>; 342 }; 343 344 template<typename _Iter> 345 concept __cpp17_bidi_iterator = __cpp17_fwd_iterator<_Iter> 346 && requires(_Iter __it) 347 { 348 { --__it } -> same_as<_Iter&>; 349 { __it-- } -> convertible_to<const _Iter&>; 350 { *__it-- } -> same_as<iter_reference_t<_Iter>>; 351 }; 352 353 template<typename _Iter> 354 concept __cpp17_randacc_iterator = __cpp17_bidi_iterator<_Iter> 355 && totally_ordered<_Iter> 356 && requires(_Iter __it, 357 typename incrementable_traits<_Iter>::difference_type __n) 358 { 359 { __it += __n } -> same_as<_Iter&>; 360 { __it -= __n } -> same_as<_Iter&>; 361 { __it + __n } -> same_as<_Iter>; 362 { __n + __it } -> same_as<_Iter>; 363 { __it - __n } -> same_as<_Iter>; 364 { __it - __it } -> same_as<decltype(__n)>; 365 { __it[__n] } -> convertible_to<iter_reference_t<_Iter>>; 366 }; 367 368 template<typename _Iter> 369 concept __iter_with_nested_types = requires { 370 typename _Iter::iterator_category; 371 typename _Iter::value_type; 372 typename _Iter::difference_type; 373 typename _Iter::reference; 374 }; 375 376 template<typename _Iter> 377 concept __iter_without_nested_types = !__iter_with_nested_types<_Iter>; 378 379 template<typename _Iter> 380 concept __iter_without_category 381 = !requires { typename _Iter::iterator_category; }; 382 383 } // namespace __detail 384 385 template<typename _Iterator> 386 requires __detail::__iter_with_nested_types<_Iterator> 387 struct __iterator_traits<_Iterator, void> 388 { 389 private: 390 template<typename _Iter> 391 struct __ptr 392 { using type = void; }; 393 394 template<typename _Iter> requires requires { typename _Iter::pointer; } 395 struct __ptr<_Iter> 396 { using type = typename _Iter::pointer; }; 397 398 public: 399 using iterator_category = typename _Iterator::iterator_category; 400 using value_type = typename _Iterator::value_type; 401 using difference_type = typename _Iterator::difference_type; 402 using pointer = typename __ptr<_Iterator>::type; 403 using reference = typename _Iterator::reference; 404 }; 405 406 template<typename _Iterator> 407 requires __detail::__iter_without_nested_types<_Iterator> 408 && __detail::__cpp17_input_iterator<_Iterator> 409 struct __iterator_traits<_Iterator, void> 410 { 411 private: 412 template<typename _Iter> 413 struct __cat 414 { using type = input_iterator_tag; }; 415 416 template<typename _Iter> 417 requires requires { typename _Iter::iterator_category; } 418 struct __cat<_Iter> 419 { using type = typename _Iter::iterator_category; }; 420 421 template<typename _Iter> 422 requires __detail::__iter_without_category<_Iter> 423 && __detail::__cpp17_randacc_iterator<_Iter> 424 struct __cat<_Iter> 425 { using type = random_access_iterator_tag; }; 426 427 template<typename _Iter> 428 requires __detail::__iter_without_category<_Iter> 429 && __detail::__cpp17_bidi_iterator<_Iter> 430 struct __cat<_Iter> 431 { using type = bidirectional_iterator_tag; }; 432 433 template<typename _Iter> 434 requires __detail::__iter_without_category<_Iter> 435 && __detail::__cpp17_fwd_iterator<_Iter> 436 struct __cat<_Iter> 437 { using type = forward_iterator_tag; }; 438 439 template<typename _Iter> 440 struct __ptr 441 { using type = void; }; 442 443 template<typename _Iter> requires requires { typename _Iter::pointer; } 444 struct __ptr<_Iter> 445 { using type = typename _Iter::pointer; }; 446 447 template<typename _Iter> 448 requires (!requires { typename _Iter::pointer; } 449 && requires(_Iter& __it) { __it.operator->(); }) 450 struct __ptr<_Iter> 451 { using type = decltype(std::declval<_Iter&>().operator->()); }; 452 453 template<typename _Iter> 454 struct __ref 455 { using type = iter_reference_t<_Iter>; }; 456 457 template<typename _Iter> requires requires { typename _Iter::reference; } 458 struct __ref<_Iter> 459 { using type = typename _Iter::reference; }; 460 461 public: 462 using iterator_category = typename __cat<_Iterator>::type; 463 using value_type 464 = typename indirectly_readable_traits<_Iterator>::value_type; 465 using difference_type 466 = typename incrementable_traits<_Iterator>::difference_type; 467 using pointer = typename __ptr<_Iterator>::type; 468 using reference = typename __ref<_Iterator>::type; 469 }; 470 471 template<typename _Iterator> 472 requires __detail::__iter_without_nested_types<_Iterator> 473 && __detail::__cpp17_iterator<_Iterator> 474 struct __iterator_traits<_Iterator, void> 475 { 476 private: 477 template<typename _Iter> 478 struct __diff 479 { using type = void; }; 480 481 template<typename _Iter> 482 requires requires 483 { typename incrementable_traits<_Iter>::difference_type; } 484 struct __diff<_Iter> 485 { 486 using type = typename incrementable_traits<_Iter>::difference_type; 487 }; 488 489 public: 490 using iterator_category = output_iterator_tag; 491 using value_type = void; 492 using difference_type = typename __diff<_Iterator>::type; 493 using pointer = void; 494 using reference = void; 495 }; 496 497 namespace __detail 498 { 499 template<typename _Iter> 500 struct __iter_concept_impl; 501 502 // ITER_CONCEPT(I) is ITER_TRAITS(I)::iterator_concept if that is valid. 503 template<typename _Iter> 504 requires requires { typename __iter_traits<_Iter>::iterator_concept; } 505 struct __iter_concept_impl<_Iter> 506 { using type = typename __iter_traits<_Iter>::iterator_concept; }; 507 508 // Otherwise, ITER_TRAITS(I)::iterator_category if that is valid. 509 template<typename _Iter> 510 requires (!requires { typename __iter_traits<_Iter>::iterator_concept; } 511 && requires { typename __iter_traits<_Iter>::iterator_category; }) 512 struct __iter_concept_impl<_Iter> 513 { using type = typename __iter_traits<_Iter>::iterator_category; }; 514 515 // Otherwise, random_access_tag if iterator_traits<I> is not specialized. 516 template<typename _Iter> 517 requires (!requires { typename __iter_traits<_Iter>::iterator_concept; } 518 && !requires { typename __iter_traits<_Iter>::iterator_category; } 519 && __primary_traits_iter<_Iter>) 520 struct __iter_concept_impl<_Iter> 521 { using type = random_access_iterator_tag; }; 522 523 // Otherwise, there is no ITER_CONCEPT(I) type. 524 template<typename _Iter> 525 struct __iter_concept_impl 526 { }; 527 528 // ITER_CONCEPT 529 template<typename _Iter> 530 using __iter_concept = typename __iter_concept_impl<_Iter>::type; 531 532 template<typename _In> 533 concept __indirectly_readable_impl = requires 534 { 535 typename iter_value_t<_In>; 536 typename iter_reference_t<_In>; 537 typename iter_rvalue_reference_t<_In>; 538 requires same_as<iter_reference_t<const _In>, 539 iter_reference_t<_In>>; 540 requires same_as<iter_rvalue_reference_t<const _In>, 541 iter_rvalue_reference_t<_In>>; 542 } 543 && common_reference_with<iter_reference_t<_In>&&, iter_value_t<_In>&> 544 && common_reference_with<iter_reference_t<_In>&&, 545 iter_rvalue_reference_t<_In>&&> 546 && common_reference_with<iter_rvalue_reference_t<_In>&&, 547 const iter_value_t<_In>&>; 548 549 } // namespace __detail 550 551 /// Requirements for types that are readable by applying operator*. 552 template<typename _In> 553 concept indirectly_readable 554 = __detail::__indirectly_readable_impl<remove_cvref_t<_In>>; 555 556 template<indirectly_readable _Tp> 557 using iter_common_reference_t 558 = common_reference_t<iter_reference_t<_Tp>, iter_value_t<_Tp>&>; 559 560 /// Requirements for writing a value into an iterator's referenced object. 561 template<typename _Out, typename _Tp> 562 concept indirectly_writable = requires(_Out&& __o, _Tp&& __t) 563 { 564 *__o = std::forward<_Tp>(__t); 565 *std::forward<_Out>(__o) = std::forward<_Tp>(__t); 566 const_cast<const iter_reference_t<_Out>&&>(*__o) 567 = std::forward<_Tp>(__t); 568 const_cast<const iter_reference_t<_Out>&&>(*std::forward<_Out>(__o)) 569 = std::forward<_Tp>(__t); 570 }; 571 572 namespace ranges::__detail 573 { 574 class __max_diff_type; 575 class __max_size_type; 576 577 __extension__ 578 template<typename _Tp> 579 concept __is_signed_int128 580 #if __SIZEOF_INT128__ 581 = same_as<_Tp, __int128>; 582 #else 583 = false; 584 #endif 585 586 __extension__ 587 template<typename _Tp> 588 concept __is_unsigned_int128 589 #if __SIZEOF_INT128__ 590 = same_as<_Tp, unsigned __int128>; 591 #else 592 = false; 593 #endif 594 595 template<typename _Tp> 596 concept __cv_bool = same_as<const volatile _Tp, const volatile bool>; 597 598 template<typename _Tp> 599 concept __integral_nonbool = integral<_Tp> && !__cv_bool<_Tp>; 600 601 template<typename _Tp> 602 concept __is_int128 = __is_signed_int128<_Tp> || __is_unsigned_int128<_Tp>; 603 604 template<typename _Tp> 605 concept __is_integer_like = __integral_nonbool<_Tp> 606 || __is_int128<_Tp> 607 || same_as<_Tp, __max_diff_type> || same_as<_Tp, __max_size_type>; 608 609 template<typename _Tp> 610 concept __is_signed_integer_like = signed_integral<_Tp> 611 || __is_signed_int128<_Tp> 612 || same_as<_Tp, __max_diff_type>; 613 614 } // namespace ranges::__detail 615 616 namespace __detail { using ranges::__detail::__is_signed_integer_like; } 617 618 /// Requirements on types that can be incremented with ++. 619 template<typename _Iter> 620 concept weakly_incrementable = movable<_Iter> 621 && requires(_Iter __i) 622 { 623 typename iter_difference_t<_Iter>; 624 requires __detail::__is_signed_integer_like<iter_difference_t<_Iter>>; 625 { ++__i } -> same_as<_Iter&>; 626 __i++; 627 }; 628 629 template<typename _Iter> 630 concept incrementable = regular<_Iter> && weakly_incrementable<_Iter> 631 && requires(_Iter __i) { { __i++ } -> same_as<_Iter>; }; 632 633 template<typename _Iter> 634 concept input_or_output_iterator 635 = requires(_Iter __i) { { *__i } -> __detail::__can_reference; } 636 && weakly_incrementable<_Iter>; 637 638 template<typename _Sent, typename _Iter> 639 concept sentinel_for = semiregular<_Sent> 640 && input_or_output_iterator<_Iter> 641 && __detail::__weakly_eq_cmp_with<_Sent, _Iter>; 642 643 template<typename _Sent, typename _Iter> 644 inline constexpr bool disable_sized_sentinel_for = false; 645 646 template<typename _Sent, typename _Iter> 647 concept sized_sentinel_for = sentinel_for<_Sent, _Iter> 648 && !disable_sized_sentinel_for<remove_cv_t<_Sent>, remove_cv_t<_Iter>> 649 && requires(const _Iter& __i, const _Sent& __s) 650 { 651 { __s - __i } -> same_as<iter_difference_t<_Iter>>; 652 { __i - __s } -> same_as<iter_difference_t<_Iter>>; 653 }; 654 655 template<typename _Iter> 656 concept input_iterator = input_or_output_iterator<_Iter> 657 && indirectly_readable<_Iter> 658 && requires { typename __detail::__iter_concept<_Iter>; } 659 && derived_from<__detail::__iter_concept<_Iter>, input_iterator_tag>; 660 661 template<typename _Iter, typename _Tp> 662 concept output_iterator = input_or_output_iterator<_Iter> 663 && indirectly_writable<_Iter, _Tp> 664 && requires(_Iter __i, _Tp&& __t) { *__i++ = std::forward<_Tp>(__t); }; 665 666 template<typename _Iter> 667 concept forward_iterator = input_iterator<_Iter> 668 && derived_from<__detail::__iter_concept<_Iter>, forward_iterator_tag> 669 && incrementable<_Iter> && sentinel_for<_Iter, _Iter>; 670 671 template<typename _Iter> 672 concept bidirectional_iterator = forward_iterator<_Iter> 673 && derived_from<__detail::__iter_concept<_Iter>, 674 bidirectional_iterator_tag> 675 && requires(_Iter __i) 676 { 677 { --__i } -> same_as<_Iter&>; 678 { __i-- } -> same_as<_Iter>; 679 }; 680 681 template<typename _Iter> 682 concept random_access_iterator = bidirectional_iterator<_Iter> 683 && derived_from<__detail::__iter_concept<_Iter>, 684 random_access_iterator_tag> 685 && totally_ordered<_Iter> && sized_sentinel_for<_Iter, _Iter> 686 && requires(_Iter __i, const _Iter __j, 687 const iter_difference_t<_Iter> __n) 688 { 689 { __i += __n } -> same_as<_Iter&>; 690 { __j + __n } -> same_as<_Iter>; 691 { __n + __j } -> same_as<_Iter>; 692 { __i -= __n } -> same_as<_Iter&>; 693 { __j - __n } -> same_as<_Iter>; 694 { __j[__n] } -> same_as<iter_reference_t<_Iter>>; 695 }; 696 697 template<typename _Iter> 698 concept contiguous_iterator = random_access_iterator<_Iter> 699 && derived_from<__detail::__iter_concept<_Iter>, contiguous_iterator_tag> 700 && is_lvalue_reference_v<iter_reference_t<_Iter>> 701 && same_as<iter_value_t<_Iter>, remove_cvref_t<iter_reference_t<_Iter>>> 702 && requires(const _Iter& __i) 703 { 704 { std::to_address(__i) } 705 -> same_as<add_pointer_t<iter_reference_t<_Iter>>>; 706 }; 707 708 // [indirectcallable], indirect callable requirements 709 710 // [indirectcallable.indirectinvocable], indirect callables 711 712 template<typename _Fn, typename _Iter> 713 concept indirectly_unary_invocable = indirectly_readable<_Iter> 714 && copy_constructible<_Fn> && invocable<_Fn&, iter_value_t<_Iter>&> 715 && invocable<_Fn&, iter_reference_t<_Iter>> 716 && invocable<_Fn&, iter_common_reference_t<_Iter>> 717 && common_reference_with<invoke_result_t<_Fn&, iter_value_t<_Iter>&>, 718 invoke_result_t<_Fn&, iter_reference_t<_Iter>>>; 719 720 template<typename _Fn, typename _Iter> 721 concept indirectly_regular_unary_invocable = indirectly_readable<_Iter> 722 && copy_constructible<_Fn> 723 && regular_invocable<_Fn&, iter_value_t<_Iter>&> 724 && regular_invocable<_Fn&, iter_reference_t<_Iter>> 725 && regular_invocable<_Fn&, iter_common_reference_t<_Iter>> 726 && common_reference_with<invoke_result_t<_Fn&, iter_value_t<_Iter>&>, 727 invoke_result_t<_Fn&, iter_reference_t<_Iter>>>; 728 729 template<typename _Fn, typename _Iter> 730 concept indirect_unary_predicate = indirectly_readable<_Iter> 731 && copy_constructible<_Fn> && predicate<_Fn&, iter_value_t<_Iter>&> 732 && predicate<_Fn&, iter_reference_t<_Iter>> 733 && predicate<_Fn&, iter_common_reference_t<_Iter>>; 734 735 template<typename _Fn, typename _I1, typename _I2> 736 concept indirect_binary_predicate 737 = indirectly_readable<_I1> && indirectly_readable<_I2> 738 && copy_constructible<_Fn> 739 && predicate<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&> 740 && predicate<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>> 741 && predicate<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&> 742 && predicate<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>> 743 && predicate<_Fn&, iter_common_reference_t<_I1>, 744 iter_common_reference_t<_I2>>; 745 746 template<typename _Fn, typename _I1, typename _I2 = _I1> 747 concept indirect_equivalence_relation 748 = indirectly_readable<_I1> && indirectly_readable<_I2> 749 && copy_constructible<_Fn> 750 && equivalence_relation<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&> 751 && equivalence_relation<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>> 752 && equivalence_relation<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&> 753 && equivalence_relation<_Fn&, iter_reference_t<_I1>, 754 iter_reference_t<_I2>> 755 && equivalence_relation<_Fn&, iter_common_reference_t<_I1>, 756 iter_common_reference_t<_I2>>; 757 758 template<typename _Fn, typename _I1, typename _I2 = _I1> 759 concept indirect_strict_weak_order 760 = indirectly_readable<_I1> && indirectly_readable<_I2> 761 && copy_constructible<_Fn> 762 && strict_weak_order<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&> 763 && strict_weak_order<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>> 764 && strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&> 765 && strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>> 766 && strict_weak_order<_Fn&, iter_common_reference_t<_I1>, 767 iter_common_reference_t<_I2>>; 768 769 template<typename _Fn, typename... _Is> 770 requires (indirectly_readable<_Is> && ...) 771 && invocable<_Fn, iter_reference_t<_Is>...> 772 using indirect_result_t = invoke_result_t<_Fn, iter_reference_t<_Is>...>; 773 774 namespace __detail 775 { 776 template<typename _Iter, typename _Proj> 777 struct __projected 778 { 779 struct __type 780 { 781 using value_type = remove_cvref_t<indirect_result_t<_Proj&, _Iter>>; 782 indirect_result_t<_Proj&, _Iter> operator*() const; // not defined 783 }; 784 }; 785 786 template<weakly_incrementable _Iter, typename _Proj> 787 struct __projected<_Iter, _Proj> 788 { 789 struct __type 790 { 791 using value_type = remove_cvref_t<indirect_result_t<_Proj&, _Iter>>; 792 using difference_type = iter_difference_t<_Iter>; 793 indirect_result_t<_Proj&, _Iter> operator*() const; // not defined 794 }; 795 }; 796 } // namespace __detail 797 798 /// [projected], projected 799 template<indirectly_readable _Iter, 800 indirectly_regular_unary_invocable<_Iter> _Proj> 801 using projected = typename __detail::__projected<_Iter, _Proj>::__type; 802 803 // [alg.req], common algorithm requirements 804 805 /// [alg.req.ind.move], concept `indirectly_movable` 806 807 template<typename _In, typename _Out> 808 concept indirectly_movable = indirectly_readable<_In> 809 && indirectly_writable<_Out, iter_rvalue_reference_t<_In>>; 810 811 template<typename _In, typename _Out> 812 concept indirectly_movable_storable = indirectly_movable<_In, _Out> 813 && indirectly_writable<_Out, iter_value_t<_In>> 814 && movable<iter_value_t<_In>> 815 && constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>> 816 && assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In>>; 817 818 /// [alg.req.ind.copy], concept `indirectly_copyable` 819 template<typename _In, typename _Out> 820 concept indirectly_copyable = indirectly_readable<_In> 821 && indirectly_writable<_Out, iter_reference_t<_In>>; 822 823 template<typename _In, typename _Out> 824 concept indirectly_copyable_storable = indirectly_copyable<_In, _Out> 825 && indirectly_writable<_Out, iter_value_t<_In>&> 826 && indirectly_writable<_Out, const iter_value_t<_In>&> 827 && indirectly_writable<_Out, iter_value_t<_In>&&> 828 && indirectly_writable<_Out, const iter_value_t<_In>&&> 829 && copyable<iter_value_t<_In>> 830 && constructible_from<iter_value_t<_In>, iter_reference_t<_In>> 831 && assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>; 832 833 namespace ranges 834 { 835 namespace __cust_iswap 836 { 837 template<typename _It1, typename _It2> 838 void iter_swap(_It1, _It2) = delete; 839 840 template<typename _Tp, typename _Up> 841 concept __adl_iswap 842 = (std::__detail::__class_or_enum<remove_reference_t<_Tp>> 843 || std::__detail::__class_or_enum<remove_reference_t<_Up>>) 844 && requires(_Tp&& __t, _Up&& __u) { 845 iter_swap(static_cast<_Tp&&>(__t), static_cast<_Up&&>(__u)); 846 }; 847 848 template<typename _Xp, typename _Yp> 849 constexpr iter_value_t<_Xp> 850 __iter_exchange_move(_Xp&& __x, _Yp&& __y) 851 noexcept(noexcept(iter_value_t<_Xp>(iter_move(__x))) 852 && noexcept(*__x = iter_move(__y))) 853 { 854 iter_value_t<_Xp> __old_value(iter_move(__x)); 855 *__x = iter_move(__y); 856 return __old_value; 857 } 858 859 struct _IterSwap 860 { 861 private: 862 template<typename _Tp, typename _Up> 863 static constexpr bool 864 _S_noexcept() 865 { 866 if constexpr (__adl_iswap<_Tp, _Up>) 867 return noexcept(iter_swap(std::declval<_Tp>(), 868 std::declval<_Up>())); 869 else if constexpr (indirectly_readable<_Tp> 870 && indirectly_readable<_Up> 871 && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>) 872 return noexcept(ranges::swap(*std::declval<_Tp>(), 873 *std::declval<_Up>())); 874 else 875 return noexcept(*std::declval<_Tp>() 876 = __iter_exchange_move(std::declval<_Up>(), 877 std::declval<_Tp>())); 878 } 879 880 public: 881 template<typename _Tp, typename _Up> 882 requires __adl_iswap<_Tp, _Up> 883 || (indirectly_readable<remove_reference_t<_Tp>> 884 && indirectly_readable<remove_reference_t<_Up>> 885 && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>) 886 || (indirectly_movable_storable<_Tp, _Up> 887 && indirectly_movable_storable<_Up, _Tp>) 888 constexpr void 889 operator()(_Tp&& __e1, _Up&& __e2) const 890 noexcept(_S_noexcept<_Tp, _Up>()) 891 { 892 if constexpr (__adl_iswap<_Tp, _Up>) 893 iter_swap(static_cast<_Tp&&>(__e1), static_cast<_Up&&>(__e2)); 894 else if constexpr (indirectly_readable<_Tp> 895 && indirectly_readable<_Up> 896 && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>) 897 ranges::swap(*__e1, *__e2); 898 else 899 *__e1 = __iter_exchange_move(__e2, __e1); 900 } 901 }; 902 } // namespace __cust_iswap 903 904 inline namespace __cust 905 { 906 inline constexpr __cust_iswap::_IterSwap iter_swap{}; 907 } // inline namespace __cust 908 909 } // namespace ranges 910 911 /// [alg.req.ind.swap], concept `indirectly_swappable` 912 template<typename _I1, typename _I2 = _I1> 913 concept indirectly_swappable 914 = indirectly_readable<_I1> && indirectly_readable<_I2> 915 && requires(const _I1 __i1, const _I2 __i2) 916 { 917 ranges::iter_swap(__i1, __i1); 918 ranges::iter_swap(__i2, __i2); 919 ranges::iter_swap(__i1, __i2); 920 ranges::iter_swap(__i2, __i1); 921 }; 922 923 /// [alg.req.ind.cmp], concept `indirectly_comparable` 924 template<typename _I1, typename _I2, typename _Rel, typename _P1 = identity, 925 typename _P2 = identity> 926 concept indirectly_comparable 927 = indirect_binary_predicate<_Rel, projected<_I1, _P1>, 928 projected<_I2, _P2>>; 929 930 /// [alg.req.permutable], concept `permutable` 931 template<typename _Iter> 932 concept permutable = forward_iterator<_Iter> 933 && indirectly_movable_storable<_Iter, _Iter> 934 && indirectly_swappable<_Iter, _Iter>; 935 936 /// [alg.req.mergeable], concept `mergeable` 937 template<typename _I1, typename _I2, typename _Out, 938 typename _Rel = ranges::less, typename _P1 = identity, 939 typename _P2 = identity> 940 concept mergeable = input_iterator<_I1> && input_iterator<_I2> 941 && weakly_incrementable<_Out> && indirectly_copyable<_I1, _Out> 942 && indirectly_copyable<_I2, _Out> 943 && indirect_strict_weak_order<_Rel, projected<_I1, _P1>, 944 projected<_I2, _P2>>; 945 946 /// [alg.req.sortable], concept `sortable` 947 template<typename _Iter, typename _Rel = ranges::less, 948 typename _Proj = identity> 949 concept sortable = permutable<_Iter> 950 && indirect_strict_weak_order<_Rel, projected<_Iter, _Proj>>; 951 952 struct unreachable_sentinel_t 953 { 954 template<weakly_incrementable _It> 955 friend constexpr bool 956 operator==(unreachable_sentinel_t, const _It&) noexcept 957 { return false; } 958 }; 959 960 inline constexpr unreachable_sentinel_t unreachable_sentinel{}; 961 962 // This is the namespace for [range.access] CPOs. 963 namespace ranges::__cust_access 964 { 965 using std::__detail::__class_or_enum; 966 967 struct _Decay_copy final 968 { 969 template<typename _Tp> 970 constexpr decay_t<_Tp> 971 operator()(_Tp&& __t) const 972 noexcept(is_nothrow_convertible_v<_Tp, decay_t<_Tp>>) 973 { return std::forward<_Tp>(__t); } 974 } inline constexpr __decay_copy{}; 975 976 template<typename _Tp> 977 concept __member_begin = requires(_Tp& __t) 978 { 979 { __decay_copy(__t.begin()) } -> input_or_output_iterator; 980 }; 981 982 // Poison pills so that unqualified lookup doesn't find std::begin. 983 void begin(auto&) = delete; 984 void begin(const auto&) = delete; 985 986 template<typename _Tp> 987 concept __adl_begin = __class_or_enum<remove_reference_t<_Tp>> 988 && requires(_Tp& __t) 989 { 990 { __decay_copy(begin(__t)) } -> input_or_output_iterator; 991 }; 992 993 // Simplified version of std::ranges::begin that only supports lvalues, 994 // for use by __range_iter_t below. 995 template<typename _Tp> 996 requires is_array_v<_Tp> || __member_begin<_Tp&> || __adl_begin<_Tp&> 997 auto 998 __begin(_Tp& __t) 999 { 1000 if constexpr (is_array_v<_Tp>) 1001 return __t + 0; 1002 else if constexpr (__member_begin<_Tp&>) 1003 return __t.begin(); 1004 else 1005 return begin(__t); 1006 } 1007 } // namespace ranges::__cust_access 1008 1009 namespace __detail 1010 { 1011 // Implementation of std::ranges::iterator_t, without using ranges::begin. 1012 template<typename _Tp> 1013 using __range_iter_t 1014 = decltype(ranges::__cust_access::__begin(std::declval<_Tp&>())); 1015 1016 } // namespace __detail 1017 1018 #endif // C++20 library concepts 1019 _GLIBCXX_END_NAMESPACE_VERSION 1020 } // namespace std 1021 #endif // C++20 1022 #endif // _ITERATOR_CONCEPTS_H
Contact us
|
About us
|
Term of use
|
Copyright © 2000-2025 MyWebUniversity.com ™
