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     template<typename _Iter>
 313       concept __iter_without_nested_types = !__iter_with_nested_types<_Iter>;
 314
 315     template<typename _Iter, bool __use_arrow = false>
 316       struct __ptr
 317       { using type = void; };
 318
 319     template<typename _Iter> requires requires { typename _Iter::pointer; }
 320       struct __ptr<_Iter, true>
 321       { using type = typename _Iter::pointer; };
 322
 323     template<typename _Iter> requires requires { typename _Iter::pointer; }
 324       struct __ptr<_Iter, false>
 325       { using type = typename _Iter::pointer; };
 326
 327     template<typename _Iter>
 328       requires (!requires { typename _Iter::pointer; }
 329           && requires(_Iter& __it) { __it.operator->(); })
 330       struct __ptr<_Iter, true>
 331       { using type = decltype(std::declval<_Iter&>().operator->()); };
 332
 333     template<typename _Iter>
 334       struct __ref
 335       { using type = iter_reference_t<_Iter>; };
 336
 337     template<typename _Iter> requires requires { typename _Iter::reference; }
 338       struct __ref<_Iter>
 339       { using type = typename _Iter::reference; };
 340
 341     template<typename _Iter>
 342       struct __cat
 343       { using type = input_iterator_tag; };
 344
 345     template<typename _Iter>
 346       requires requires { typename _Iter::iterator_category; }
 347       struct __cat<_Iter>
 348       { using type = typename _Iter::iterator_category; };
 349
 350     template<typename _Iter>
 351       requires (!requires { typename _Iter::iterator_category; }
 352                 && __detail::__cpp17_randacc_iterator<_Iter>)
 353       struct __cat<_Iter>
 354       { using type = random_access_iterator_tag; };
 355
 356     template<typename _Iter>
 357       requires (!requires { typename _Iter::iterator_category; }
 358                 && __detail::__cpp17_bidi_iterator<_Iter>)
 359       struct __cat<_Iter>
 360       { using type = bidirectional_iterator_tag; };
 361
 362     template<typename _Iter>
 363       requires (!requires { typename _Iter::iterator_category; }
 364                 && __detail::__cpp17_fwd_iterator<_Iter>)
 365       struct __cat<_Iter>
 366       { using type = forward_iterator_tag; };
 367
 368     template<typename _Iter>
 369       struct __diff
 370       { using type = void; };
 371
 372     template<typename _Iter>
 373       requires requires {
 374         typename incrementable_traits<_Iter>::difference_type;
 375       }
 376       struct __diff<_Iter>
 377       {
 378         using type = typename incrementable_traits<_Iter>::difference_type;
 379       };
 380
 381   } // namespace __detail
 382
 383   template<typename _Iterator>
 384     requires __detail::__iter_with_nested_types<_Iterator>
 385     struct __iterator_traits<_Iterator, void>
 386     {
 387       using iterator_category = typename _Iterator::iterator_category;
 388       using value_type        = typename _Iterator::value_type;
 389       using difference_type   = typename _Iterator::difference_type;
 390       using pointer           = typename __detail::__ptr<_Iterator>::type;
 391       using reference         = typename _Iterator::reference;
 392     };
 393
 394   template<typename _Iterator>
 395     requires __detail::__iter_without_nested_types<_Iterator>
 396               && __detail::__cpp17_input_iterator<_Iterator>
 397     struct __iterator_traits<_Iterator, void>
 398     {
 399       using iterator_category = typename __detail::__cat<_Iterator>::type;
 400       using value_type
 401         = typename readable_traits<_Iterator>::value_type;
 402       using difference_type
 403         = typename incrementable_traits<_Iterator>::difference_type;
 404       using pointer           = typename __detail::__ptr<_Iterator, true>::type;
 405       using reference         = typename __detail::__ref<_Iterator>::type;
 406     };
 407
 408   template<typename _Iterator>
 409     requires __detail::__iter_without_nested_types<_Iterator>
 410               && __detail::__cpp17_iterator<_Iterator>
 411     struct __iterator_traits<_Iterator, void>
 412     {
 413       using iterator_category = output_iterator_tag;
 414       using value_type        = void;
 415       using difference_type   = typename __detail::__diff<_Iterator>::type;
 416       using pointer           = void;
 417       using reference         = void;
 418     };
 419
 420   namespace __detail
 421   {
 422     template<typename _Iter>
 423       struct __iter_concept_impl;
 424
 425     // ITER_CONCEPT(I) is ITER_TRAITS(I)::iterator_concept if that is valid.
 426     template<typename _Iter>
 427       requires requires { typename __iter_traits<_Iter>::iterator_concept; }
 428       struct __iter_concept_impl<_Iter>
 429       { using type = typename __iter_traits<_Iter>::iterator_concept; };
 430
 431     // Otherwise, ITER_TRAITS(I)::iterator_category if that is valid.
 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     // Otherwise, random_access_tag if iterator_traits<I> is not specialized.
 439     template<typename _Iter>
 440       requires (!requires { typename __iter_traits<_Iter>::iterator_concept; }
 441           && !requires { typename __iter_traits<_Iter>::iterator_category; }
 442           && __primary_traits_iter<_Iter>)
 443       struct __iter_concept_impl<_Iter>
 444       { using type = random_access_iterator_tag; };
 445
 446     // Otherwise, there is no ITER_CONCEPT(I) type.
 447     template<typename _Iter>
 448       struct __iter_concept_impl
 449       { };
 450
 451     // ITER_CONCEPT
 452     template<typename _Iter>
 453       using __iter_concept = typename __iter_concept_impl<_Iter>::type;
 454   } // namespace __detail
 455
 456   /// Requirements for types that are readable by applying operator*.
 457   template<typename _In>
 458     concept readable = requires
 459       {
 460         typename iter_value_t<_In>;
 461         typename iter_reference_t<_In>;
 462         typename iter_rvalue_reference_t<_In>;
 463       }
 464       && common_reference_with<iter_reference_t<_In>&&, iter_value_t<_In>&>
 465       && common_reference_with<iter_reference_t<_In>&&,
 466                               iter_rvalue_reference_t<_In>&&>
 467       && common_reference_with<iter_rvalue_reference_t<_In>&&,
 468                                const iter_value_t<_In>&>;
 469
 470   namespace __detail
 471   {
 472     // FIXME: needed due to PR c++/67704
 473     template<readable _Tp>
 474       struct __iter_common_ref
 475       : common_reference<iter_reference_t<_Tp>, iter_value_t<_Tp>&>
 476       { };
 477
 478     // FIXME: needed due to PR c++/67704
 479     template<typename _Fn, typename... _Is>
 480       struct __indirect_result
 481       { };
 482
 483     template<typename _Fn, typename... _Is>
 484       requires (readable<_Is> && ...)
 485         && invocable<_Fn, iter_reference_t<_Is>...>
 486       struct __indirect_result<_Fn, _Is...>
 487       : invoke_result<_Fn, iter_reference_t<_Is>...>
 488       { };
 489   } // namespace __detail
 490
 491   template<typename _Tp>
 492     using iter_common_reference_t
 493       = typename __detail::__iter_common_ref<_Tp>::type;
 494
 495   /// Requirements for writing a value into an iterator's referenced object.
 496   template<typename _Out, typename _Tp>
 497     concept writable = requires(_Out&& __o, _Tp&& __t)
 498       {
 499         *__o = std::forward<_Tp>(__t);
 500         *std::forward<_Out>(__o) = std::forward<_Tp>(__t);
 501         const_cast<const iter_reference_t<_Out>&&>(*__o)
 502           = std::forward<_Tp>(__t);
 503         const_cast<const iter_reference_t<_Out>&&>(*std::forward<_Out>(__o))
 504           = std::forward<_Tp>(__t);
 505       };
 506
 507   /// Requirements on types that can be incremented with ++.
 508   template<typename _Iter>
 509     concept weakly_incrementable = default_constructible<_Iter>
 510       && movable<_Iter>
 511       && requires(_Iter __i)
 512       {
 513         typename iter_difference_t<_Iter>;
 514         requires signed_integral<iter_difference_t<_Iter>>;
 515         { ++__i } -> same_as<_Iter&>;
 516         __i++;
 517       };
 518
 519   template<typename _Iter>
 520     concept incrementable = regular<_Iter> && weakly_incrementable<_Iter>
 521       && requires(_Iter __i) { { __i++ } -> same_as<_Iter>; };
 522
 523   template<typename _Iter>
 524     concept input_or_output_iterator
 525       = requires(_Iter __i) { { *__i } -> __detail::__can_reference; }
 526         && weakly_incrementable<_Iter>;
 527
 528   template<typename _Sent, typename _Iter>
 529     concept sentinel_for = semiregular<_Sent>
 530       && input_or_output_iterator<_Iter>
 531       && __detail::__weakly_eq_cmp_with<_Sent, _Iter>;
 532
 533   template<typename _Sent, typename _Iter>
 534     inline constexpr bool disable_sized_sentinel_for = false;
 535
 536   template<typename _Sent, typename _Iter>
 537     concept sized_sentinel_for = sentinel_for<_Sent, _Iter>
 538     && !disable_sized_sentinel_for<remove_cv_t<_Sent>, remove_cv_t<_Iter>>
 539     && requires(const _Iter& __i, const _Sent& __s)
 540     {
 541       { __s - __i } -> same_as<iter_difference_t<_Iter>>;
 542       { __i - __s } -> same_as<iter_difference_t<_Iter>>;
 543     };
 544
 545   template<typename _Iter>
 546     concept input_iterator = input_or_output_iterator<_Iter>
 547       && readable<_Iter>
 548       && requires { typename __detail::__iter_concept<_Iter>; }
 549       && derived_from<__detail::__iter_concept<_Iter>, input_iterator_tag>;
 550
 551   template<typename _Iter, typename _Tp>
 552     concept output_iterator = input_or_output_iterator<_Iter>
 553       && writable<_Iter, _Tp>
 554       && requires(_Iter __i, _Tp&& __t) { *__i++ = std::forward<_Tp>(__t); };
 555
 556   template<typename _Iter>
 557     concept forward_iterator = input_iterator<_Iter>
 558       && derived_from<__detail::__iter_concept<_Iter>, forward_iterator_tag>
 559       && incrementable<_Iter> && sentinel_for<_Iter, _Iter>;
 560
 561   template<typename _Iter>
 562     concept bidirectional_iterator = forward_iterator<_Iter>
 563       && derived_from<__detail::__iter_concept<_Iter>,
 564                       bidirectional_iterator_tag>
 565       && requires(_Iter __i)
 566       {
 567         { --__i } -> same_as<_Iter&>;
 568         { __i-- } -> same_as<_Iter>;
 569       };
 570
 571   template<typename _Iter>
 572     concept random_access_iterator = bidirectional_iterator<_Iter>
 573       && derived_from<__detail::__iter_concept<_Iter>,
 574                       random_access_iterator_tag>
 575       && totally_ordered<_Iter> && sized_sentinel_for<_Iter, _Iter>
 576       && requires(_Iter __i, const _Iter __j,
 577                   const iter_difference_t<_Iter> __n)
 578       {
 579         { __i += __n } -> same_as<_Iter&>;
 580         { __j +  __n } -> same_as<_Iter>;
 581         { __n +  __j } -> same_as<_Iter>;
 582         { __i -= __n } -> same_as<_Iter&>;
 583         { __j -  __n } -> same_as<_Iter>;
 584         {  __j[__n]  } -> same_as<iter_reference_t<_Iter>>;
 585       };
 586
 587   template<typename _Iter>
 588     concept contiguous_iterator = random_access_iterator<_Iter>
 589       && derived_from<__detail::__iter_concept<_Iter>, contiguous_iterator_tag>
 590       && is_lvalue_reference_v<iter_reference_t<_Iter>>
 591       && same_as<iter_value_t<_Iter>, remove_cvref_t<iter_reference_t<_Iter>>>
 592       && requires(const _Iter& __i)
 593       {
 594         { std::to_address(__i) }
 595           -> same_as<add_pointer_t<iter_reference_t<_Iter>>>;
 596       };
 597
 598   // [indirectcallable], indirect callable requirements
 599
 600   // [indirectcallable.indirectinvocable], indirect callables
 601
 602   template<typename _Fn, typename _Iter>
 603     concept indirectly_unary_invocable = readable<_Iter>
 604       && copy_constructible<_Fn> && invocable<_Fn&, iter_value_t<_Iter>&>
 605       && invocable<_Fn&, iter_reference_t<_Iter>>
 606       && invocable<_Fn&, iter_common_reference_t<_Iter>>
 607       && common_reference_with<invoke_result_t<_Fn&, iter_value_t<_Iter>&>,
 608                                invoke_result_t<_Fn&, iter_reference_t<_Iter>>>;
 609
 610   template<typename _Fn, typename _Iter>
 611     concept indirectly_regular_unary_invocable = readable<_Iter>
 612       && copy_constructible<_Fn>
 613       && regular_invocable<_Fn&, iter_value_t<_Iter>&>
 614       && regular_invocable<_Fn&, iter_reference_t<_Iter>>
 615       && regular_invocable<_Fn&, iter_common_reference_t<_Iter>>
 616       && common_reference_with<invoke_result_t<_Fn&, iter_value_t<_Iter>&>,
 617                                invoke_result_t<_Fn&, iter_reference_t<_Iter>>>;
 618
 619   template<typename _Fn, typename _Iter>
 620     concept indirect_unary_predicate = readable<_Iter>
 621       && copy_constructible<_Fn> && predicate<_Fn&, iter_value_t<_Iter>&>
 622       && predicate<_Fn&, iter_reference_t<_Iter>>
 623       && predicate<_Fn&, iter_common_reference_t<_Iter>>;
 624
 625   template<typename _Fn, typename _I1, typename _I2>
 626     concept indirect_binary_predicate = readable<_I1> && readable<_I2>
 627       && copy_constructible<_Fn>
 628       && predicate<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&>
 629       && predicate<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>>
 630       && predicate<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&>
 631       && predicate<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>>
 632       && predicate<_Fn&, iter_common_reference_t<_I1>,
 633                    iter_common_reference_t<_I2>>;
 634
 635   template<typename _Fn, typename _I1, typename _I2 = _I1>
 636     concept indirect_equivalence_relation = readable<_I1> && readable<_I2>
 637       && copy_constructible<_Fn>
 638       && equivalence_relation<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&>
 639       && equivalence_relation<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>>
 640       && equivalence_relation<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&>
 641       && equivalence_relation<_Fn&, iter_reference_t<_I1>,
 642                               iter_reference_t<_I2>>
 643       && equivalence_relation<_Fn&, iter_common_reference_t<_I1>,
 644                               iter_common_reference_t<_I2>>;
 645
 646   template<typename _Fn, typename _I1, typename _I2 = _I1>
 647     concept indirect_strict_weak_order = readable<_I1> && readable<_I2>
 648       && copy_constructible<_Fn>
 649       && strict_weak_order<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&>
 650       && strict_weak_order<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>>
 651       && strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&>
 652       && strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>>
 653       && strict_weak_order<_Fn&, iter_common_reference_t<_I1>,
 654                            iter_common_reference_t<_I2>>;
 655
 656   template<typename _Fn, typename... _Is>
 657     using indirect_result_t = typename
 658       __detail::__indirect_result<_Fn, iter_reference_t<_Is>...>::type;
 659
 660   /// [projected], projected
 661   template<readable _Iter, indirectly_regular_unary_invocable<_Iter> _Proj>
 662     struct projected
 663     {
 664       using value_type = remove_cvref_t<indirect_result_t<_Proj&, _Iter>>;
 665       indirect_result_t<_Proj&, _Iter> operator*() const; // not defined
 666     };
 667
 668   template<weakly_incrementable _Iter, typename _Proj>
 669     struct incrementable_traits<projected<_Iter, _Proj>>
 670     { using difference_type = iter_difference_t<_Iter>; };
 671
 672   // [alg.req], common algorithm requirements
 673
 674   /// [alg.req.ind.move], concept `indirectly_movable`
 675
 676   template<typename _In, typename _Out>
 677     concept indirectly_movable = readable<_In>
 678       && writable<_Out, iter_rvalue_reference_t<_In>>;
 679
 680   template<typename _In, typename _Out>
 681     concept indirectly_movable_storable = indirectly_movable<_In, _Out>
 682       && writable<_Out, iter_value_t<_In>> && movable<iter_value_t<_In>>
 683       && constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>>
 684       && assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In>>;
 685
 686   /// [alg.req.ind.copy], concept `indirectly_copyable`
 687   template<typename _In, typename _Out>
 688     concept indirectly_copyable = readable<_In>
 689       && writable<_Out, iter_reference_t<_In>>;
 690
 691   template<typename _In, typename _Out>
 692     concept indirectly_copyable_storable = indirectly_copyable<_In, _Out>
 693       && writable<_Out, const iter_value_t<_In>&>
 694       && copyable<iter_value_t<_In>>
 695       && constructible_from<iter_value_t<_In>, iter_reference_t<_In>>
 696       && assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>;
 697
 698 namespace ranges
 699 {
 700   namespace __cust_iswap
 701   {
 702     template<typename _It1, typename _It2>
 703       void iter_swap(_It1&, _It2&) = delete;
 704
 705     template<typename _Tp, typename _Up>
 706       concept __adl_iswap
 707         = (std::__detail::__class_or_enum<remove_reference_t<_Tp>>
 708           || std::__detail::__class_or_enum<remove_reference_t<_Up>>)
 709         && requires(_Tp&& __t, _Up&& __u) {
 710           iter_swap(static_cast<_Tp&&>(__t), static_cast<_Up&&>(__u));
 711         };
 712
 713     template<typename _Xp, typename _Yp>
 714       constexpr iter_value_t<remove_reference_t<_Xp>>
 715       __iter_exchange_move(_Xp&& __x, _Yp&& __y)
 716       noexcept(noexcept(iter_value_t<remove_reference_t<_Xp>>(iter_move(__x)))
 717                && noexcept(*__x = iter_move(__y)))
 718       {
 719         iter_value_t<remove_reference_t<_Xp>> __old_value(iter_move(__x));
 720         *__x = iter_move(__y);
 721         return __old_value;
 722       }
 723
 724     struct _IterSwap
 725     {
 726     private:
 727       template<typename _Tp, typename _Up>
 728         static constexpr bool
 729         _S_noexcept()
 730         {
 731           if constexpr (__adl_iswap<_Tp, _Up>)
 732             return noexcept(iter_swap(std::declval<_Tp>(),
 733                                       std::declval<_Up>()));
 734           else if constexpr (readable<_Tp> && readable<_Up>
 735             && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>)
 736             return noexcept(ranges::swap(*std::declval<_Tp>(),
 737                                          *std::declval<_Up>()));
 738           else
 739             return noexcept(*std::declval<_Tp>()
 740                 = __iter_exchange_move(std::declval<_Up>(),
 741                                        std::declval<_Tp>()));
 742         }
 743
 744     public:
 745       template<typename _Tp, typename _Up>
 746         requires __adl_iswap<_Tp, _Up>
 747         || (readable<_Tp> && readable<_Up>
 748             && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>)
 749         || (indirectly_movable_storable<_Tp, _Up>
 750             && indirectly_movable_storable<_Up, _Tp>)
 751         constexpr void
 752         operator()(_Tp&& __e1, _Up&& __e2) const
 753         noexcept(_S_noexcept<_Tp, _Up>())
 754         {
 755           if constexpr (__adl_iswap<_Tp, _Up>)
 756             iter_swap(static_cast<_Tp&&>(__e1), static_cast<_Up&&>(__e2));
 757           else if constexpr (readable<_Tp> && readable<_Up>
 758             && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>)
 759             ranges::swap(*__e1, *__e2);
 760           else
 761             *__e1 = __iter_exchange_move(__e2, __e1);
 762         }
 763     };
 764   } // namespace __cust_iswap
 765
 766   inline namespace __cust
 767   {
 768     inline constexpr __cust_iswap::_IterSwap iter_swap{};
 769   } // inline namespace __cust
 770
 771 } // namespace ranges
 772
 773   /// [alg.req.ind.swap], concept `indirectly_swappable`
 774   template<typename _I1, typename _I2 = _I1>
 775     concept indirectly_swappable = readable<_I1> && readable<_I2>
 776       && requires(_I1& __i1, _I2& __i2)
 777       {
 778         ranges::iter_swap(__i1, __i1);
 779         ranges::iter_swap(__i2, __i2);
 780         ranges::iter_swap(__i1, __i2);
 781         ranges::iter_swap(__i2, __i1);
 782       };
 783
 784   /// [alg.req.ind.cmp], concept `indirectly_comparable`
 785   template<typename _I1, typename _I2, typename _Rel, typename _P1 = identity,
 786            typename _P2 = identity>
 787     concept indirectly_comparable
 788       = indirect_binary_predicate<_Rel, projected<_I1, _P1>,
 789                                   projected<_I2, _P2>>;
 790
 791   /// [alg.req.permutable], concept `permutable`
 792   template<typename _Iter>
 793     concept permutable = forward_iterator<_Iter>
 794       && indirectly_movable_storable<_Iter, _Iter>
 795       && indirectly_swappable<_Iter, _Iter>;
 796
 797   /// [alg.req.mergeable], concept `mergeable`
 798   template<typename _I1, typename _I2, typename _Out,
 799            typename _Rel = ranges::less, typename _P1 = identity,
 800            typename _P2 = identity>
 801     concept mergeable = input_iterator<_I1> && input_iterator<_I2>
 802       && weakly_incrementable<_Out> && indirectly_copyable<_I1, _Out>
 803       && indirectly_copyable<_I2, _Out>
 804       && indirect_strict_weak_order<_Rel, projected<_I1, _P1>,
 805                                     projected<_I2, _P2>>;
 806
 807   /// [alg.req.sortable], concept `sortable`
 808   template<typename _Iter, typename _Rel = ranges::less,
 809            typename _Proj = identity>
 810     concept sortable = permutable<_Iter>
 811       && indirect_strict_weak_order<_Rel, projected<_Iter, _Proj>>;
 812
 813   struct unreachable_sentinel_t
 814   {
 815     template<weakly_incrementable _It>
 816       friend constexpr bool
 817       operator==(unreachable_sentinel_t, const _It&) noexcept
 818       { return false; }
 819   };
 820
 821   inline constexpr unreachable_sentinel_t unreachable_sentinel{};
 822
 823   struct default_sentinel_t { };
 824   inline constexpr default_sentinel_t default_sentinel{};
 825
 826 _GLIBCXX_END_NAMESPACE_VERSION
 827 } // namespace std
 828 #endif // C++20 library concepts
 829 #endif // _ITERATOR_CONCEPTS_H