libstdc++-v3/include/bits/iterator_concepts.h

   1 // Concepts and traits for use with iterators -*- C++ -*-
   2
   3 // Copyright (C) 2019 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
  74     // FIXME: needed due to PR c++/67704
  75     template<__detail::__dereferenceable _Tp>
  76       struct __iter_ref
  77       {
  78         using type = decltype(*std::declval<_Tp&>());
  79       };
  80   } // namespace __detail
  81
  82   template<typename _Tp>
  83     using iter_reference_t = typename __detail::__iter_ref<_Tp>::type;
  84
  85   namespace ranges
  86   {
  87     namespace __cust_imove
  88     {
  89       template<typename _Tp>
  90         concept __adl_imove
  91           = (std::__detail::__class_or_enum<remove_reference_t<_Tp>>)
  92           && requires(_Tp&& __t) { iter_move(static_cast<_Tp&&>(__t)); };
  93
  94       struct _IMove
  95       {
  96       private:
  97         template<typename _Tp>
  98           static constexpr bool
  99           _S_noexcept()
 100           {
 101             if constexpr (__adl_imove<_Tp>)
 102               return noexcept(iter_move(std::declval<_Tp>()));
 103             else
 104               return noexcept(*std::declval<_Tp>());
 105           }
 106
 107       public:
 108         template<typename _Tp>
 109           requires __adl_imove<_Tp> || requires(_Tp& __e) { *__e; }
 110           constexpr decltype(auto)
 111           operator()(_Tp&& __e) const
 112           noexcept(_S_noexcept<_Tp>())
 113           {
 114             if constexpr (__adl_imove<_Tp>)
 115               return iter_move(static_cast<_Tp&&>(__e));
 116             else if constexpr (is_reference_v<iter_reference_t<_Tp>>)
 117               return std::move(*__e);
 118             else
 119               return *__e;
 120           }
 121       };
 122     } // namespace __cust_imove
 123
 124     inline namespace __cust
 125     {
 126       inline constexpr __cust_imove::_IMove iter_move{};
 127     } // inline namespace __cust
 128   } // namespace ranges
 129
 130   namespace __detail
 131   {
 132     // FIXME: needed due to PR c++/67704
 133     template<__detail::__dereferenceable _Tp>
 134       struct __iter_rvalue_ref
 135       { };
 136
 137     template<__detail::__dereferenceable _Tp>
 138       requires requires(_Tp& __t)
 139       {
 140         { ranges::iter_move(__t) } -> __detail::__can_reference;
 141       }
 142       struct __iter_rvalue_ref<_Tp>
 143       { using type = decltype(ranges::iter_move(std::declval<_Tp&>())); };
 144
 145   } // namespace __detail
 146
 147   template<typename _Tp>
 148     using iter_rvalue_reference_t
 149       = typename __detail::__iter_rvalue_ref<_Tp>::type;
 150
 151   template<typename> struct incrementable_traits { };
 152
 153   template<typename _Tp> requires is_object_v<_Tp>
 154     struct incrementable_traits<_Tp*>
 155     { using difference_type = ptrdiff_t; };
 156
 157   template<typename _Iter>
 158     struct incrementable_traits<const _Iter>
 159     : incrementable_traits<_Iter> { };
 160
 161   template<typename _Tp> requires requires { typename _Tp::difference_type; }
 162     struct incrementable_traits<_Tp>
 163     { using difference_type = typename _Tp::difference_type; };
 164
 165   template<typename _Tp>
 166     requires (!requires { typename _Tp::difference_type; }
 167               && requires(const _Tp& __a, const _Tp& __b)
 168               {
 169                 requires (!is_void_v<remove_pointer_t<_Tp>>); // PR c++/78173
 170                 { __a - __b } -> integral;
 171               })
 172     struct incrementable_traits<_Tp>
 173     {
 174       using difference_type
 175         = make_signed_t<decltype(std::declval<_Tp>() - std::declval<_Tp>())>;
 176     };
 177
 178   namespace __detail
 179   {
 180     // An iterator such that iterator_traits<_Iter> names a specialization
 181     // generated from the primary template.
 182     template<typename _Iter>
 183       concept __primary_traits_iter
 184         = __is_base_of(__iterator_traits<_Iter, void>, iterator_traits<_Iter>);
 185
 186     template<typename _Iter, typename _Tp>
 187       struct __iter_traits_impl
 188       { using type = iterator_traits<_Iter>; };
 189
 190     template<typename _Iter, typename _Tp>
 191       requires __primary_traits_iter<_Iter>
 192       struct __iter_traits_impl<_Iter, _Tp>
 193       { using type = _Tp; };
 194
 195     // ITER_TRAITS
 196     template<typename _Iter, typename _Tp = _Iter>
 197       using __iter_traits = typename __iter_traits_impl<_Iter, _Tp>::type;
 198   } // namespace __detail
 199
 200   template<typename _Tp>
 201     using iter_difference_t = typename
 202       __detail::__iter_traits<_Tp, incrementable_traits<_Tp>>::difference_type;
 203
 204   namespace __detail
 205   {
 206     template<typename> struct __cond_value_type { };
 207
 208     template<typename _Tp> requires is_object_v<_Tp>
 209       struct __cond_value_type<_Tp>
 210       { using value_type = remove_cv_t<_Tp>; };
 211   } // namespace __detail
 212
 213   template<typename> struct readable_traits { };
 214
 215   template<typename _Tp>
 216     struct readable_traits<_Tp*>
 217     : __detail::__cond_value_type<_Tp>
 218     { };
 219
 220   template<typename _Iter> requires is_array_v<_Iter>
 221     struct readable_traits<_Iter>
 222     { using value_type = remove_cv_t<remove_extent_t<_Iter>>; };
 223
 224   template<typename _Iter>
 225     struct readable_traits<const _Iter>
 226     : readable_traits<_Iter>
 227     { };
 228
 229   template<typename _Tp> requires requires { typename _Tp::value_type; }
 230     struct readable_traits<_Tp>
 231     : __detail::__cond_value_type<typename _Tp::value_type>
 232     { };
 233
 234   template<typename _Tp> requires requires { typename _Tp::element_type; }
 235     struct readable_traits<_Tp>
 236     : __detail::__cond_value_type<typename _Tp::element_type>
 237     { };
 238
 239   template<typename _Tp>
 240     using iter_value_t = typename
 241       __detail::__iter_traits<_Tp, readable_traits<_Tp>>::value_type;
 242
 243   namespace __detail
 244   {
 245     template<typename _Iter>
 246       concept __cpp17_iterator = copyable<_Iter>
 247         && requires(_Iter __it)
 248         {
 249           { *__it } -> __can_reference;
 250           { ++__it } -> same_as<_Iter&>;
 251           { *__it++ } -> __can_reference;
 252         };
 253
 254     template<typename _Iter>
 255       concept __cpp17_input_iterator = __cpp17_iterator<_Iter>
 256         && equality_comparable<_Iter>
 257         && requires(_Iter __it)
 258         {
 259           typename incrementable_traits<_Iter>::difference_type;
 260           typename readable_traits<_Iter>::value_type;
 261           typename common_reference_t<iter_reference_t<_Iter>&&,
 262                    typename readable_traits<_Iter>::value_type&>;
 263           typename common_reference_t<decltype(*__it++)&&,
 264                    typename readable_traits<_Iter>::value_type&>;
 265           requires signed_integral<typename incrementable_traits<_Iter>::difference_type>;
 266         };
 267
 268     template<typename _Iter>
 269       concept __cpp17_fwd_iterator = __cpp17_input_iterator<_Iter>
 270         && constructible_from<_Iter>
 271         && is_lvalue_reference_v<iter_reference_t<_Iter>>
 272         && same_as<remove_cvref_t<iter_reference_t<_Iter>>,
 273                    typename readable_traits<_Iter>::value_type>
 274         && requires(_Iter __it)
 275         {
 276           {  __it++ } -> convertible_to<const _Iter&>;
 277           { *__it++ } -> same_as<iter_reference_t<_Iter>>;
 278         };
 279
 280     template<typename _Iter>
 281       concept __cpp17_bidi_iterator = __cpp17_fwd_iterator<_Iter>
 282         && requires(_Iter __it)
 283         {
 284           {  --__it } -> same_as<_Iter&>;
 285           {  __it-- } -> convertible_to<const _Iter&>;
 286           { *__it-- } -> same_as<iter_reference_t<_Iter>>;
 287         };
 288
 289     template<typename _Iter>
 290       concept __cpp17_randacc_iterator = __cpp17_bidi_iterator<_Iter>
 291         && totally_ordered<_Iter>
 292         && requires(_Iter __it,
 293                     typename incrementable_traits<_Iter>::difference_type __n)
 294         {
 295           { __it += __n } -> same_as<_Iter&>;
 296           { __it -= __n } -> same_as<_Iter&>;
 297           { __it +  __n } -> same_as<_Iter>;
 298           { __n +  __it } -> same_as<_Iter>;
 299           { __it -  __n } -> same_as<_Iter>;
 300           { __it -  __it } -> same_as<decltype(__n)>;
 301           {  __it[__n]  } -> convertible_to<iter_reference_t<_Iter>>;
 302         };
 303
 304     template<typename _Iter>
 305       concept __iter_with_nested_types = requires {
 306         typename _Iter::iterator_category;
 307         typename _Iter::value_type;
 308         typename _Iter::difference_type;
 309         typename _Iter::reference;
 310       };
 311
 312     // FIXME: needed due to PR c++/92102
 313     template<typename _Iter>
 314       concept __iter_without_nested_types = !__iter_with_nested_types<_Iter>;
 315
 316     template<typename _Iter, bool __use_arrow = false>
 317       struct __ptr
 318       { using type = void; };
 319
 320     template<typename _Iter> requires requires { typename _Iter::pointer; }
 321       struct __ptr<_Iter, true>
 322       { using type = typename _Iter::pointer; };
 323
 324     template<typename _Iter> requires requires { typename _Iter::pointer; }
 325       struct __ptr<_Iter, false>
 326       { using type = typename _Iter::pointer; };
 327
 328     template<typename _Iter>
 329       requires (!requires { typename _Iter::pointer; }
 330           && requires(_Iter& __it) { __it.operator->(); })
 331       struct __ptr<_Iter, true>
 332       { using type = decltype(std::declval<_Iter&>().operator->()); };
 333
 334     template<typename _Iter>
 335       struct __ref
 336       { using type = iter_reference_t<_Iter>; };
 337
 338     template<typename _Iter> requires requires { typename _Iter::reference; }
 339       struct __ref<_Iter>
 340       { using type = typename _Iter::reference; };
 341
 342     template<typename _Iter>
 343       struct __cat
 344       { using type = input_iterator_tag; };
 345
 346     template<typename _Iter>
 347       requires requires { typename _Iter::iterator_category; }
 348       struct __cat<_Iter>
 349       { using type = typename _Iter::iterator_category; };
 350
 351     template<typename _Iter>
 352       requires (!requires { typename _Iter::iterator_category; }
 353                 && __detail::__cpp17_randacc_iterator<_Iter>)
 354       struct __cat<_Iter>
 355       { using type = random_access_iterator_tag; };
 356
 357     template<typename _Iter>
 358       requires (!requires { typename _Iter::iterator_category; }
 359                 && __detail::__cpp17_bidi_iterator<_Iter>)
 360       struct __cat<_Iter>
 361       { using type = bidirectional_iterator_tag; };
 362
 363     template<typename _Iter>
 364       requires (!requires { typename _Iter::iterator_category; }
 365                 && __detail::__cpp17_fwd_iterator<_Iter>)
 366       struct __cat<_Iter>
 367       { using type = forward_iterator_tag; };
 368
 369     template<typename _Iter>
 370       struct __diff
 371       { using type = void; };
 372
 373     template<typename _Iter>
 374       requires requires {
 375         typename incrementable_traits<_Iter>::difference_type;
 376       }
 377       struct __diff<_Iter>
 378       {
 379         using type = typename incrementable_traits<_Iter>::difference_type;
 380       };
 381
 382   } // namespace __detail
 383
 384   template<typename _Iterator>
 385     requires __detail::__iter_with_nested_types<_Iterator>
 386     struct __iterator_traits<_Iterator, void>
 387     {
 388       using iterator_category = typename _Iterator::iterator_category;
 389       using value_type        = typename _Iterator::value_type;
 390       using difference_type   = typename _Iterator::difference_type;
 391       using pointer           = typename __detail::__ptr<_Iterator>::type;
 392       using reference         = typename _Iterator::reference;
 393     };
 394
 395   template<typename _Iterator>
 396     requires __detail::__iter_without_nested_types<_Iterator>
 397               && __detail::__cpp17_input_iterator<_Iterator>
 398     struct __iterator_traits<_Iterator, void>
 399     {
 400       using iterator_category = typename __detail::__cat<_Iterator>::type;
 401       using value_type
 402         = typename readable_traits<_Iterator>::value_type;
 403       using difference_type
 404         = typename incrementable_traits<_Iterator>::difference_type;
 405       using pointer           = typename __detail::__ptr<_Iterator, true>::type;
 406       using reference         = typename __detail::__ref<_Iterator>::type;
 407     };
 408
 409   template<typename _Iterator>
 410     requires __detail::__iter_without_nested_types<_Iterator>
 411               && __detail::__cpp17_iterator<_Iterator>
 412     struct __iterator_traits<_Iterator, void>
 413     {
 414       using iterator_category = output_iterator_tag;
 415       using value_type        = void;
 416       using difference_type   = typename __detail::__diff<_Iterator>::type;
 417       using pointer           = void;
 418       using reference         = void;
 419     };
 420
 421   namespace __detail
 422   {
 423     template<typename _Iter>
 424       struct __iter_concept_impl
 425       { };
 426
 427     template<typename _Iter>
 428       requires requires { typename __iter_traits<_Iter>::iterator_concept; }
 429       struct __iter_concept_impl<_Iter>
 430       { using type = typename __iter_traits<_Iter>::iterator_concept; };
 431
 432     template<typename _Iter>
 433       requires (!requires { typename __iter_traits<_Iter>::iterator_concept; }
 434           && requires { typename __iter_traits<_Iter>::iterator_category; })
 435       struct __iter_concept_impl<_Iter>
 436       { using type = typename __iter_traits<_Iter>::iterator_category; };
 437
 438     template<typename _Iter>
 439       requires (!requires { typename __iter_traits<_Iter>::iterator_concept; }
 440           && !requires { typename __iter_traits<_Iter>::iterator_category; }
 441           && __primary_traits_iter<_Iter>)
 442       struct __iter_concept_impl<_Iter>
 443       { using type = random_access_iterator_tag; };
 444
 445     // ITER_TRAITS
 446     template<typename _Iter>
 447       using __iter_concept = typename __iter_concept_impl<_Iter>::type;
 448   } // namespace __detail
 449
 450   /// Requirements for types that are readable by applying operator*.
 451   template<typename _In>
 452     concept readable = requires
 453       {
 454         typename iter_value_t<_In>;
 455         typename iter_reference_t<_In>;
 456         typename iter_rvalue_reference_t<_In>;
 457       }
 458       && common_reference_with<iter_reference_t<_In>&&, iter_value_t<_In>&>
 459       && common_reference_with<iter_reference_t<_In>&&,
 460                               iter_rvalue_reference_t<_In>&&>
 461       && common_reference_with<iter_rvalue_reference_t<_In>&&,
 462                                const iter_value_t<_In>&>;
 463
 464   namespace __detail
 465   {
 466     // FIXME: needed due to PR c++/67704
 467     template<readable _Tp>
 468       struct __iter_common_ref
 469       : common_reference<iter_reference_t<_Tp>, iter_value_t<_Tp>&>
 470       { };
 471
 472     // FIXME: needed due to PR c++/67704
 473     template<typename _Fn, typename... _Is>
 474       struct __indirect_result
 475       { };
 476
 477     template<typename _Fn, typename... _Is>
 478       requires (readable<_Is> && ...)
 479         && invocable<_Fn, iter_reference_t<_Is>...>
 480       struct __indirect_result<_Fn, _Is...>
 481       : invoke_result<_Fn, iter_reference_t<_Is>...>
 482       { };
 483   } // namespace __detail
 484
 485   template<typename _Tp>
 486     using iter_common_reference_t
 487       = typename __detail::__iter_common_ref<_Tp>::type;
 488
 489   /// Requirements for writing a value into an iterator's referenced object.
 490   template<typename _Out, typename _Tp>
 491     concept writable = requires(_Out&& __o, _Tp&& __t)
 492       {
 493         *__o = std::forward<_Tp>(__t);
 494         *std::forward<_Out>(__o) = std::forward<_Tp>(__t);
 495         const_cast<const iter_reference_t<_Out>&&>(*__o)
 496           = std::forward<_Tp>(__t);
 497         const_cast<const iter_reference_t<_Out>&&>(*std::forward<_Out>(__o))
 498           = std::forward<_Tp>(__t);
 499       };
 500
 501   /// Requirements on types that can be incremented with ++.
 502   template<typename _Iter>
 503     concept weakly_incrementable = default_constructible<_Iter>
 504       && movable<_Iter>
 505       && requires(_Iter __i)
 506       {
 507         typename iter_difference_t<_Iter>;
 508         requires signed_integral<iter_difference_t<_Iter>>;
 509         { ++__i } -> same_as<_Iter&>;
 510         __i++;
 511       };
 512
 513   template<typename _Iter>
 514     concept incrementable = regular<_Iter> && weakly_incrementable<_Iter>
 515       && requires(_Iter __i) { { __i++ } -> same_as<_Iter>; };
 516
 517   template<typename _Iter>
 518     concept input_or_output_iterator
 519       = requires(_Iter __i) { { *__i } -> __detail::__can_reference; }
 520         && weakly_incrementable<_Iter>;
 521
 522   template<typename _Sent, typename _Iter>
 523     concept sentinel_for = semiregular<_Sent>
 524       && input_or_output_iterator<_Iter>
 525       && __detail::__weakly_eq_cmp_with<_Sent, _Iter>;
 526
 527   template<typename _Sent, typename _Iter>
 528     inline constexpr bool disable_sized_sentinel = false;
 529
 530   template<typename _Sent, typename _Iter>
 531     concept sized_sentinel_for = sentinel_for<_Sent, _Iter>
 532     && !disable_sized_sentinel<remove_cv_t<_Sent>, remove_cv_t<_Iter>>
 533     && requires(const _Iter& __i, const _Sent& __s)
 534     {
 535       { __s - __i } -> same_as<iter_difference_t<_Iter>>;
 536       { __i - __s } -> same_as<iter_difference_t<_Iter>>;
 537     };
 538
 539   template<typename _Iter>
 540     concept input_iterator = input_or_output_iterator<_Iter>
 541       && readable<_Iter>
 542       && requires { typename __detail::__iter_concept<_Iter>; }
 543       && derived_from<__detail::__iter_concept<_Iter>, input_iterator_tag>;
 544
 545   template<typename _Iter, typename _Tp>
 546     concept output_iterator = input_or_output_iterator<_Iter>
 547       && writable<_Iter, _Tp>
 548       && requires(_Iter __i, _Tp&& __t) { *__i++ = std::forward<_Tp>(__t); };
 549
 550   template<typename _Iter>
 551     concept forward_iterator = input_iterator<_Iter>
 552       && derived_from<__detail::__iter_concept<_Iter>, forward_iterator_tag>
 553       && incrementable<_Iter> && sentinel_for<_Iter, _Iter>;
 554
 555   template<typename _Iter>
 556     concept bidirectional_iterator = forward_iterator<_Iter>
 557       && derived_from<__detail::__iter_concept<_Iter>,
 558                       bidirectional_iterator_tag>
 559       && requires(_Iter __i)
 560       {
 561         { --__i } -> same_as<_Iter&>;
 562         { __i-- } -> same_as<_Iter>;
 563       };
 564
 565   template<typename _Iter>
 566     concept random_access_iterator = bidirectional_iterator<_Iter>
 567       && derived_from<__detail::__iter_concept<_Iter>,
 568                       random_access_iterator_tag>
 569       && totally_ordered<_Iter> && sized_sentinel_for<_Iter, _Iter>
 570       && requires(_Iter __i, const _Iter __j,
 571                   const iter_difference_t<_Iter> __n)
 572       {
 573         { __i += __n } -> same_as<_Iter&>;
 574         { __j +  __n } -> same_as<_Iter>;
 575         { __n +  __j } -> same_as<_Iter>;
 576         { __i -= __n } -> same_as<_Iter&>;
 577         { __j -  __n } -> same_as<_Iter>;
 578         {  __j[__n]  } -> same_as<iter_reference_t<_Iter>>;
 579       };
 580
 581   template<typename _Iter>
 582     concept contiguous_iterator = random_access_iterator<_Iter>
 583       && derived_from<__detail::__iter_concept<_Iter>, contiguous_iterator_tag>
 584       && is_lvalue_reference_v<iter_reference_t<_Iter>>
 585       && same_as<iter_value_t<_Iter>, remove_cvref_t<iter_reference_t<_Iter>>>
 586       && requires(const _Iter& __i)
 587       {
 588         { std::to_address(__i) }
 589           -> same_as<add_pointer_t<iter_reference_t<_Iter>>>;
 590       };
 591
 592   // [indirectcallable], indirect callable requirements
 593
 594   // [indirectcallable.indirectinvocable], indirect callables
 595
 596   template<typename _Fn, typename _Iter>
 597     concept indirectly_unary_invocable = readable<_Iter>
 598       && copy_constructible<_Fn> && invocable<_Fn&, iter_value_t<_Iter>&>
 599       && invocable<_Fn&, iter_reference_t<_Iter>>
 600       && invocable<_Fn&, iter_common_reference_t<_Iter>>
 601       && common_reference_with<invoke_result_t<_Fn&, iter_value_t<_Iter>&>,
 602                                invoke_result_t<_Fn&, iter_reference_t<_Iter>>>;
 603
 604   template<typename _Fn, typename _Iter>
 605     concept indirectly_regular_unary_invocable = readable<_Iter>
 606       && copy_constructible<_Fn>
 607       && regular_invocable<_Fn&, iter_value_t<_Iter>&>
 608       && regular_invocable<_Fn&, iter_reference_t<_Iter>>
 609       && regular_invocable<_Fn&, iter_common_reference_t<_Iter>>
 610       && common_reference_with<invoke_result_t<_Fn&, iter_value_t<_Iter>&>,
 611                                invoke_result_t<_Fn&, iter_reference_t<_Iter>>>;
 612
 613   template<typename _Fn, typename _Iter>
 614     concept indirect_unary_predicate = readable<_Iter>
 615       && copy_constructible<_Fn> && predicate<_Fn&, iter_value_t<_Iter>&>
 616       && predicate<_Fn&, iter_reference_t<_Iter>>
 617       && predicate<_Fn&, iter_common_reference_t<_Iter>>;
 618
 619   template<typename _Fn, typename _I1, typename _I2 = _I1>
 620     concept indirect_relation = readable<_I1> && readable<_I2>
 621       && copy_constructible<_Fn>
 622       && relation<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&>
 623       && relation<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>>
 624       && relation<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&>
 625       && relation<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>>
 626       && relation<_Fn&, iter_common_reference_t<_I1>,
 627                   iter_common_reference_t<_I2>>;
 628
 629   template<typename _Fn, typename _I1, typename _I2 = _I1>
 630     concept indirect_strict_weak_order = readable<_I1> && readable<_I2>
 631       && copy_constructible<_Fn>
 632       && strict_weak_order<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&>
 633       && strict_weak_order<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>>
 634       && strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&>
 635       && strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>>
 636       && strict_weak_order<_Fn&, iter_common_reference_t<_I1>,
 637                            iter_common_reference_t<_I2>>;
 638
 639   template<typename _Fn, typename... _Is>
 640     using indirect_result_t = typename
 641       __detail::__indirect_result<_Fn, iter_reference_t<_Is>...>::type;
 642
 643   /// [projected], projected
 644   template<readable _Iter, indirectly_regular_unary_invocable<_Iter> _Proj>
 645     struct projected
 646     {
 647       using value_type = remove_cvref_t<indirect_result_t<_Proj&, _Iter>>;
 648       indirect_result_t<_Proj&, _Iter> operator*() const; // not defined
 649     };
 650
 651   template<weakly_incrementable _Iter, typename _Proj>
 652     struct incrementable_traits<projected<_Iter, _Proj>>
 653     { using difference_type = iter_difference_t<_Iter>; };
 654
 655   // [alg.req], common algorithm requirements
 656
 657   /// [alg.req.ind.move], concept `indirectly_movable`
 658
 659   template<typename _In, typename _Out>
 660     concept indirectly_movable = readable<_In>
 661       && writable<_Out, iter_rvalue_reference_t<_In>>;
 662
 663   template<typename _In, typename _Out>
 664     concept indirectly_movable_storable = indirectly_movable<_In, _Out>
 665       && writable<_Out, iter_value_t<_In>> && movable<iter_value_t<_In>>
 666       && constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>>
 667       && assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In>>;
 668
 669   /// [alg.req.ind.copy], concept `indirectly_copyable`
 670   template<typename _In, typename _Out>
 671     concept indirectly_copyable = readable<_In>
 672       && writable<_Out, iter_reference_t<_In>>;
 673
 674   template<typename _In, typename _Out>
 675     concept indirectly_copyable_storable = indirectly_copyable<_In, _Out>
 676       && writable<_Out, const iter_value_t<_In>&>
 677       && copyable<iter_value_t<_In>>
 678       && constructible_from<iter_value_t<_In>, iter_reference_t<_In>>
 679       && assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>;
 680
 681 namespace ranges
 682 {
 683   namespace __cust_iswap
 684   {
 685     template<typename _It1, typename _It2>
 686       void iter_swap(_It1&, _It2&) = delete;
 687
 688     template<typename _Tp, typename _Up>
 689       concept __adl_iswap
 690         = (std::__detail::__class_or_enum<remove_reference_t<_Tp>>
 691           || std::__detail::__class_or_enum<remove_reference_t<_Up>>)
 692         && requires(_Tp&& __t, _Up&& __u) {
 693           iter_swap(static_cast<_Tp&&>(__t), static_cast<_Up&&>(__u));
 694         };
 695
 696     template<typename _Xp, typename _Yp>
 697       constexpr iter_value_t<remove_reference_t<_Xp>>
 698       __iter_exchange_move(_Xp&& __x, _Yp&& __y)
 699       noexcept(noexcept(iter_value_t<remove_reference_t<_Xp>>(iter_move(__x)))
 700                && noexcept(*__x = iter_move(__y)))
 701       {
 702         iter_value_t<remove_reference_t<_Xp>> __old_value(iter_move(__x));
 703         *__x = iter_move(__y);
 704         return __old_value;
 705       }
 706
 707     struct _IterSwap
 708     {
 709     private:
 710       template<typename _Tp, typename _Up>
 711         static constexpr bool
 712         _S_noexcept()
 713         {
 714           if constexpr (__adl_iswap<_Tp, _Up>)
 715             return noexcept(iter_swap(std::declval<_Tp>(),
 716                                       std::declval<_Up>()));
 717           else if constexpr (readable<_Tp> && readable<_Up>
 718             && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>)
 719             return noexcept(ranges::swap(*std::declval<_Tp>(),
 720                                          *std::declval<_Up>()));
 721           else
 722             return noexcept(*std::declval<_Tp>()
 723                 = __iter_exchange_move(std::declval<_Up>(),
 724                                        std::declval<_Tp>()));
 725         }
 726
 727     public:
 728       template<typename _Tp, typename _Up>
 729         requires __adl_iswap<_Tp, _Up>
 730         || (readable<_Tp> && readable<_Up>
 731             && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>)
 732         || (indirectly_movable_storable<_Tp, _Up>
 733             && indirectly_movable_storable<_Up, _Tp>)
 734         constexpr void
 735         operator()(_Tp&& __e1, _Up&& __e2) const
 736         noexcept(_S_noexcept<_Tp, _Up>())
 737         {
 738           if constexpr (__adl_iswap<_Tp, _Up>)
 739             iter_swap(static_cast<_Tp&&>(__e1), static_cast<_Up&&>(__e2));
 740           else if constexpr (readable<_Tp> && readable<_Up>
 741             && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>)
 742             ranges::swap(*__e1, *__e2);
 743           else
 744             *__e1 = __iter_exchange_move(__e2, __e1);
 745         }
 746     };
 747   } // namespace __cust_iswap
 748
 749   inline namespace __cust
 750   {
 751     inline constexpr __cust_iswap::_IterSwap iter_swap{};
 752   } // inline namespace __cust
 753
 754 } // namespace ranges
 755
 756   /// [alg.req.ind.swap], concept `indirectly_swappable`
 757   template<typename _I1, typename _I2 = _I1>
 758     concept indirectly_swappable = readable<_I1> && readable<_I2>
 759       && requires(_I1& __i1, _I2& __i2)
 760       {
 761         ranges::iter_swap(__i1, __i1);
 762         ranges::iter_swap(__i2, __i2);
 763         ranges::iter_swap(__i1, __i2);
 764         ranges::iter_swap(__i2, __i1);
 765       };
 766
 767   /// [alg.req.ind.cmp], concept `indirectly_comparable`
 768   template<typename _I1, typename _I2, typename _Rel, typename _P1 = identity,
 769            typename _P2 = identity>
 770     concept indirectly_comparable
 771       = indirect_relation<_Rel, projected<_I1, _P1>, projected<_I2, _P2>>;
 772
 773   /// [alg.req.permutable], concept `permutable`
 774   template<typename _Iter>
 775     concept permutable = forward_iterator<_Iter>
 776       && indirectly_movable_storable<_Iter, _Iter>
 777       && indirectly_swappable<_Iter, _Iter>;
 778
 779   /// [alg.req.mergeable], concept `mergeable`
 780   template<typename _I1, typename _I2, typename _Out,
 781            typename _Rel = ranges::less, typename _P1 = identity,
 782            typename _P2 = identity>
 783     concept mergeable = input_iterator<_I1> && input_iterator<_I2>
 784       && weakly_incrementable<_Out> && indirectly_copyable<_I1, _Out>
 785       && indirectly_copyable<_I2, _Out>
 786       && indirect_strict_weak_order<_Rel, projected<_I1, _P1>,
 787                                     projected<_I2, _P2>>;
 788
 789   /// [alg.req.sortable], concept `sortable`
 790   template<typename _Iter, typename _Rel = ranges::less,
 791            typename _Proj = identity>
 792     concept sortable = permutable<_Iter>
 793       && indirect_strict_weak_order<_Rel, projected<_Iter, _Proj>>;
 794
 795   struct unreachable_sentinel_t
 796   {
 797     template<weakly_incrementable _It>
 798       friend constexpr bool
 799       operator==(unreachable_sentinel_t, const _It&) noexcept
 800       { return false; }
 801
 802 #ifndef __cpp_lib_three_way_comparison
 803     template<weakly_incrementable _It>
 804       friend constexpr bool
 805       operator!=(unreachable_sentinel_t, const _It&) noexcept
 806       { return true; }
 807
 808     template<weakly_incrementable _It>
 809       friend constexpr bool
 810       operator==(const _It&, unreachable_sentinel_t) noexcept
 811       { return false; }
 812
 813     template<weakly_incrementable _It>
 814       friend constexpr bool
 815       operator!=(const _It&, unreachable_sentinel_t) noexcept
 816       { return true; }
 817 #endif
 818   };
 819
 820   inline constexpr unreachable_sentinel_t unreachable_sentinel{};
 821
 822   struct default_sentinel_t { };
 823   inline constexpr default_sentinel_t default_sentinel{};
 824
 825 _GLIBCXX_END_NAMESPACE_VERSION
 826 } // namespace std
 827 #endif // C++20 library concepts
 828 #endif // _ITERATOR_CONCEPTS_H