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