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