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