libstdc++-v3/include/std/ranges

   1 // <ranges> -*- C++ -*-
   2
   3 // Copyright (C) 2019-2020 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received __a copy of the GNU General Public License and
  21 // __a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file include/ranges
  26  *  This is a Standard C++ Library header.
  27  *  @ingroup concepts
  28  */
  29
  30 #ifndef _GLIBCXX_RANGES
  31 #define _GLIBCXX_RANGES 1
  32
  33 #if __cplusplus > 201703L
  34
  35 #pragma GCC system_header
  36
  37 #include <concepts>
  38
  39 #if __cpp_lib_concepts
  40
  41 #include <compare>
  42 #include <initializer_list>
  43 #include <iterator>
  44 #include <limits>
  45 #include <optional>
  46
  47 /**
  48  * @defgroup ranges Ranges
  49  *
  50  * Components for dealing with ranges of elements.
  51  */
  52
  53 namespace std _GLIBCXX_VISIBILITY(default)
  54 {
  55 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  56 namespace ranges
  57 {
  58   // [range.range] The range concept.
  59   // [range.sized] The sized_range concept.
  60   // Defined in <bits/range_access.h>
  61
  62   // [range.refinements]
  63   // Defined in <bits/range_access.h>
  64
  65   struct view_base { };
  66
  67   namespace __detail
  68   {
  69     template<typename _Tp>
  70       concept __deep_const_range = range<_Tp> && range<const _Tp>
  71         && same_as<range_reference_t<_Tp>, range_reference_t<const _Tp>>;
  72
  73     template<typename _Tp>
  74       inline constexpr bool __enable_view_impl
  75         = derived_from<_Tp, view_base> || (!__deep_const_range<_Tp>);
  76
  77     template<typename _Tp>
  78       inline constexpr bool __enable_view_impl<std::initializer_list<_Tp>>
  79         = false;
  80
  81   } // namespace __detail
  82
  83   template<typename _Tp>
  84     inline constexpr bool enable_view
  85       = __detail::__enable_view_impl<remove_cv_t<_Tp>>;
  86
  87   template<typename _Tp>
  88     concept view
  89       = range<_Tp> && movable<_Tp> && default_initializable<_Tp>
  90         && enable_view<_Tp>;
  91
  92   /// A range which can be safely converted to a view.
  93   template<typename _Tp>
  94     concept viewable_range = range<_Tp>
  95       && (safe_range<_Tp> || view<decay_t<_Tp>>);
  96
  97   namespace __detail
  98   {
  99     template<typename _Range>
 100       concept __simple_view = view<_Range> && range<const _Range>
 101         && same_as<iterator_t<_Range>, iterator_t<const _Range>>
 102         && same_as<sentinel_t<_Range>, sentinel_t<const _Range>>;
 103
 104     template<typename _It>
 105       concept __has_arrow = input_iterator<_It>
 106         && (is_pointer_v<_It> || requires(_It __it) { __it.operator->(); });
 107
 108     template<typename _Tp, typename _Up>
 109       concept __not_same_as
 110         = !same_as<remove_cvref_t<_Tp>, remove_cvref_t<_Up>>;
 111   } // namespace __detail
 112
 113   template<typename _Derived>
 114     requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
 115     class view_interface : public view_base
 116     {
 117     private:
 118       constexpr _Derived& _M_derived() noexcept
 119       {
 120         static_assert(derived_from<_Derived, view_interface<_Derived>>);
 121         static_assert(view<_Derived>);
 122         return static_cast<_Derived&>(*this);
 123       }
 124
 125       constexpr const _Derived& _M_derived() const noexcept
 126       {
 127         static_assert(derived_from<_Derived, view_interface<_Derived>>);
 128         static_assert(view<_Derived>);
 129         return static_cast<const _Derived&>(*this);
 130       }
 131
 132     public:
 133       constexpr bool
 134       empty() requires forward_range<_Derived>
 135       { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }
 136
 137       constexpr bool
 138       empty() const requires forward_range<const _Derived>
 139       { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }
 140
 141       constexpr explicit
 142       operator bool() requires requires { ranges::empty(_M_derived()); }
 143       { return !ranges::empty(_M_derived()); }
 144
 145       constexpr explicit
 146       operator bool() const requires requires { ranges::empty(_M_derived()); }
 147       { return !ranges::empty(_M_derived()); }
 148
 149       constexpr auto
 150       data() requires contiguous_iterator<iterator_t<_Derived>>
 151       { return to_address(ranges::begin(_M_derived())); }
 152
 153       constexpr auto
 154       data() const
 155       requires range<const _Derived>
 156         && contiguous_iterator<iterator_t<const _Derived>>
 157       { return to_address(ranges::begin(_M_derived())); }
 158
 159       constexpr auto
 160       size()
 161       requires forward_range<_Derived>
 162         && sized_sentinel_for<sentinel_t<_Derived>, iterator_t<_Derived>>
 163       { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }
 164
 165       constexpr auto
 166       size() const
 167       requires forward_range<const _Derived>
 168         && sized_sentinel_for<sentinel_t<const _Derived>,
 169                               iterator_t<const _Derived>>
 170       { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }
 171
 172       constexpr decltype(auto)
 173       front() requires forward_range<_Derived>
 174       {
 175         __glibcxx_assert(!empty());
 176         return *ranges::begin(_M_derived());
 177       }
 178
 179       constexpr decltype(auto)
 180       front() const requires forward_range<const _Derived>
 181       {
 182         __glibcxx_assert(!empty());
 183         return *ranges::begin(_M_derived());
 184       }
 185
 186       constexpr decltype(auto)
 187       back()
 188       requires bidirectional_range<_Derived> && common_range<_Derived>
 189       {
 190         __glibcxx_assert(!empty());
 191         return *ranges::prev(ranges::end(_M_derived()));
 192       }
 193
 194       constexpr decltype(auto)
 195       back() const
 196       requires bidirectional_range<const _Derived>
 197         && common_range<const _Derived>
 198       {
 199         __glibcxx_assert(!empty());
 200         return *ranges::prev(ranges::end(_M_derived()));
 201       }
 202
 203       template<random_access_range _Range = _Derived>
 204         constexpr decltype(auto)
 205         operator[](range_difference_t<_Range> __n)
 206         { return ranges::begin(_M_derived())[__n]; }
 207
 208       template<random_access_range _Range = const _Derived>
 209         constexpr decltype(auto)
 210         operator[](range_difference_t<_Range> __n) const
 211         { return ranges::begin(_M_derived())[__n]; }
 212     };
 213
 214   namespace __detail
 215   {
 216     template<typename _Tp>
 217       concept __pair_like
 218         = !is_reference_v<_Tp> && requires(_Tp __t)
 219         {
 220           typename tuple_size<_Tp>::type;
 221           requires derived_from<tuple_size<_Tp>, integral_constant<size_t, 2>>;
 222           typename tuple_element_t<0, remove_const_t<_Tp>>;
 223           typename tuple_element_t<1, remove_const_t<_Tp>>;
 224           { get<0>(__t) } -> convertible_to<const tuple_element_t<0, _Tp>&>;
 225           { get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>;
 226         };
 227
 228     template<typename _Tp, typename _Up, typename _Vp>
 229       concept __pair_like_convertible_to
 230         = !range<_Tp> && __pair_like<remove_reference_t<_Tp>>
 231         && requires(_Tp&& __t)
 232         {
 233           { get<0>(std::forward<_Tp>(__t)) } -> convertible_to<_Up>;
 234           { get<1>(std::forward<_Tp>(__t)) } -> convertible_to<_Vp>;
 235         };
 236
 237     template<typename _Tp, typename _Up, typename _Vp>
 238       concept __pair_like_convertible_from
 239         = !range<_Tp> && __pair_like<_Tp>
 240         && constructible_from<_Tp, _Up, _Vp>;
 241
 242     template<typename _Tp>
 243       concept __iterator_sentinel_pair
 244         = !range<_Tp> && __pair_like<_Tp>
 245         && sentinel_for<tuple_element_t<1, _Tp>, tuple_element_t<0, _Tp>>;
 246
 247   } // namespace __detail
 248
 249   enum class subrange_kind : bool { unsized, sized };
 250
 251   template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
 252            subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
 253              ? subrange_kind::sized : subrange_kind::unsized>
 254     requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>)
 255     class subrange : public view_interface<subrange<_It, _Sent, _Kind>>
 256     {
 257     private:
 258       static constexpr bool _S_store_size
 259         = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>;
 260
 261       _It _M_begin = _It();
 262       _Sent _M_end = _Sent();
 263
 264       template<typename, bool = _S_store_size>
 265         struct _Size
 266         { };
 267
 268       template<typename _Tp>
 269         struct _Size<_Tp, true>
 270         { __detail::__make_unsigned_like_t<_Tp> _M_size; };
 271
 272       [[no_unique_address]] _Size<iter_difference_t<_It>> _M_size = {};
 273
 274     public:
 275       subrange() = default;
 276
 277       constexpr
 278       subrange(_It __i, _Sent __s) requires (!_S_store_size)
 279       : _M_begin(std::move(__i)), _M_end(__s)
 280       { }
 281
 282       constexpr
 283       subrange(_It __i, _Sent __s,
 284                __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
 285         requires (_Kind == subrange_kind::sized)
 286       : _M_begin(std::move(__i)), _M_end(__s)
 287       {
 288         using __detail::__to_unsigned_like;
 289         __glibcxx_assert(__n == __to_unsigned_like(ranges::distance(__i, __s)));
 290         if constexpr (_S_store_size)
 291           _M_size._M_size = __n;
 292       }
 293
 294       template<__detail::__not_same_as<subrange> _Rng>
 295         requires safe_range<_Rng>
 296           && convertible_to<iterator_t<_Rng>, _It>
 297           && convertible_to<sentinel_t<_Rng>, _Sent>
 298         constexpr
 299         subrange(_Rng&& __r) requires (!_S_store_size || sized_range<_Rng>)
 300         : subrange{ranges::begin(__r), ranges::end(__r)}
 301         {
 302           if constexpr (_S_store_size)
 303             _M_size._M_size = ranges::size(__r);
 304         }
 305
 306       template<safe_range _Rng>
 307         requires convertible_to<iterator_t<_Rng>, _It>
 308           && convertible_to<sentinel_t<_Rng>, _Sent>
 309         constexpr
 310         subrange(_Rng&& __r,
 311                  __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
 312         requires (_Kind == subrange_kind::sized)
 313         : subrange{ranges::begin(__r), ranges::end(__r), __n}
 314         { }
 315
 316       template<__detail::__not_same_as<subrange> _PairLike>
 317         requires __detail::__pair_like_convertible_to<_PairLike, _It, _Sent>
 318         constexpr
 319         subrange(_PairLike&& __r) requires (!_S_store_size)
 320         : subrange{std::get<0>(std::forward<_PairLike>(__r)),
 321                    std::get<1>(std::forward<_PairLike>(__r))}
 322         { }
 323
 324       template<__detail::__pair_like_convertible_to<_It, _Sent> _PairLike>
 325         constexpr
 326         subrange(_PairLike&& __r,
 327                  __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
 328         requires (_Kind == subrange_kind::sized)
 329         : subrange{std::get<0>(std::forward<_PairLike>(__r)),
 330                    std::get<1>(std::forward<_PairLike>(__r)), __n}
 331         { }
 332
 333       template<__detail::__not_same_as<subrange> _PairLike>
 334         requires __detail::__pair_like_convertible_from<_PairLike, const _It&,
 335                                                         const _Sent&>
 336       constexpr
 337       operator _PairLike() const
 338       { return _PairLike(_M_begin, _M_end); }
 339
 340       constexpr _It
 341       begin() const requires copyable<_It>
 342       { return _M_begin; }
 343
 344       [[nodiscard]] constexpr _It
 345       begin() requires (!copyable<_It>)
 346       { return std::move(_M_begin); }
 347
 348       constexpr _Sent end() const { return _M_end; }
 349
 350       constexpr bool empty() const { return _M_begin == _M_end; }
 351
 352       constexpr __detail::__make_unsigned_like_t<iter_difference_t<_It>>
 353       size() const requires (_Kind == subrange_kind::sized)
 354       {
 355         if constexpr (_S_store_size)
 356           return _M_size._M_size;
 357         else
 358           return __detail::__to_unsigned_like(_M_end - _M_begin);
 359       }
 360
 361       [[nodiscard]] constexpr subrange
 362       next(iter_difference_t<_It> __n = 1) const &
 363         requires forward_iterator<_It>
 364       {
 365         auto __tmp = *this;
 366         __tmp.advance(__n);
 367         return __tmp;
 368       }
 369
 370       [[nodiscard]] constexpr subrange
 371       next(iter_difference_t<_It> __n = 1) &&
 372       {
 373         advance(__n);
 374         return std::move(*this);
 375       }
 376
 377       [[nodiscard]] constexpr subrange
 378       prev(iter_difference_t<_It> __n = 1) const
 379         requires bidirectional_iterator<_It>
 380       {
 381         auto __tmp = *this;
 382         __tmp.advance(--__n);
 383         return __tmp;
 384       }
 385
 386       constexpr subrange&
 387       advance(iter_difference_t<_It> __n)
 388       {
 389         if constexpr (_S_store_size)
 390           {
 391             auto __d = __n - ranges::advance(_M_begin, __n, _M_end);
 392             if (__d >= 0)
 393               _M_size._M_size -= __detail::__to_unsigned_like(__d);
 394             else
 395               _M_size._M_size += __detail::__to_unsigned_like(-__d);
 396           }
 397         else
 398           ranges::advance(_M_begin, __n, _M_end);
 399         return *this;
 400       }
 401     };
 402
 403   template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
 404     subrange(_It, _Sent,
 405              __detail::__make_unsigned_like_t<iter_difference_t<_It>>)
 406       -> subrange<_It, _Sent, subrange_kind::sized>;
 407
 408   template<__detail::__iterator_sentinel_pair _Pr>
 409     subrange(_Pr)
 410       -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>>;
 411
 412   template<__detail::__iterator_sentinel_pair _Pr>
 413     subrange(_Pr, __detail::__make_unsigned_like_t<iter_difference_t<
 414                                                      tuple_element_t<0, _Pr>>>)
 415       -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>,
 416                   subrange_kind::sized>;
 417
 418   template<safe_range _Rng>
 419     subrange(_Rng&&)
 420       -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>,
 421                  (sized_range<_Rng>
 422                   || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>)
 423                  ? subrange_kind::sized : subrange_kind::unsized>;
 424
 425   template<safe_range _Rng>
 426     subrange(_Rng&&,
 427              __detail::__make_unsigned_like_t<range_difference_t<_Rng>>)
 428       -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>;
 429
 430   template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
 431     requires (_Num < 2)
 432     constexpr auto
 433     get(const subrange<_It, _Sent, _Kind>& __r)
 434     {
 435       if constexpr (_Num == 0)
 436         return __r.begin();
 437       else
 438         return __r.end();
 439     }
 440
 441   template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
 442     requires (_Num < 2)
 443     constexpr auto
 444     get(subrange<_It, _Sent, _Kind>&& __r)
 445     {
 446       if constexpr (_Num == 0)
 447         return __r.begin();
 448       else
 449         return __r.end();
 450     }
 451
 452   template<input_or_output_iterator _It, sentinel_for<_It> _Sent,
 453            subrange_kind _Kind>
 454     inline constexpr bool
 455       enable_safe_range<subrange<_It, _Sent, _Kind>> = true;
 456
 457 } // namespace ranges
 458
 459   using ranges::get;
 460
 461 namespace ranges
 462 {
 463   /// Type returned by algorithms instead of a dangling iterator or subrange.
 464   struct dangling
 465   {
 466     constexpr dangling() noexcept = default;
 467     template<typename... _Args>
 468       constexpr dangling(_Args&&...) noexcept { }
 469   };
 470
 471   template<range _Range>
 472     using safe_iterator_t = conditional_t<safe_range<_Range>,
 473                                           iterator_t<_Range>,
 474                                           dangling>;
 475
 476   template<range _Range>
 477     using safe_subrange_t = conditional_t<safe_range<_Range>,
 478                                           subrange<iterator_t<_Range>>,
 479                                           dangling>;
 480
 481   template<typename _Tp> requires is_object_v<_Tp>
 482     class empty_view
 483     : public view_interface<empty_view<_Tp>>
 484     {
 485     public:
 486       static constexpr _Tp* begin() noexcept { return nullptr; }
 487       static constexpr _Tp* end() noexcept { return nullptr; }
 488       static constexpr _Tp* data() noexcept { return nullptr; }
 489       static constexpr size_t size() noexcept { return 0; }
 490       static constexpr bool empty() noexcept { return true; }
 491     };
 492
 493   template<typename _Tp>
 494     inline constexpr bool enable_safe_range<empty_view<_Tp>> = true;
 495
 496   namespace __detail
 497   {
 498     template<copy_constructible _Tp> requires is_object_v<_Tp>
 499       struct __box : std::optional<_Tp>
 500       {
 501         using std::optional<_Tp>::optional;
 502
 503         constexpr
 504         __box()
 505         noexcept(is_nothrow_default_constructible_v<_Tp>)
 506         requires default_initializable<_Tp>
 507         : std::optional<_Tp>{std::in_place}
 508         { }
 509
 510         using std::optional<_Tp>::operator=;
 511
 512         __box&
 513         operator=(const __box& __that)
 514         noexcept(is_nothrow_copy_constructible_v<_Tp>)
 515         requires (!assignable_from<_Tp&, const _Tp&>)
 516         {
 517           if ((bool)__that)
 518             this->emplace(*__that);
 519           else
 520             this->reset();
 521           return *this;
 522         }
 523
 524         __box&
 525         operator=(__box&& __that)
 526         noexcept(is_nothrow_move_constructible_v<_Tp>)
 527         requires (!assignable_from<_Tp&, _Tp>)
 528         {
 529           if ((bool)__that)
 530             this->emplace(std::move(*__that));
 531           else
 532             this->reset();
 533           return *this;
 534         }
 535       };
 536
 537   } // namespace __detail
 538
 539   /// A view that contains exactly one element.
 540   template<copy_constructible _Tp> requires is_object_v<_Tp>
 541     class single_view : public view_interface<single_view<_Tp>>
 542     {
 543     public:
 544       single_view() = default;
 545
 546       constexpr explicit
 547       single_view(const _Tp& __t)
 548       : _M_value(__t)
 549       { }
 550
 551       constexpr explicit
 552       single_view(_Tp&& __t)
 553       : _M_value(std::move(__t))
 554       { }
 555
 556       template<typename... _Args>
 557         requires constructible_from<_Tp, _Args...>
 558         constexpr
 559         single_view(in_place_t, _Args&&... __args)
 560         : _M_value{in_place, std::forward<_Args>(__args)...}
 561         { }
 562
 563       constexpr _Tp*
 564       begin() noexcept
 565       { return data(); }
 566
 567       constexpr const _Tp*
 568       begin() const noexcept
 569       { return data(); }
 570
 571       constexpr _Tp*
 572       end() noexcept
 573       { return data() + 1; }
 574
 575       constexpr const _Tp*
 576       end() const noexcept
 577       { return data() + 1; }
 578
 579       static constexpr size_t
 580       size() noexcept
 581       { return 1; }
 582
 583       constexpr _Tp*
 584       data() noexcept
 585       { return _M_value.operator->(); }
 586
 587       constexpr const _Tp*
 588       data() const noexcept
 589       { return _M_value.operator->(); }
 590
 591     private:
 592       __detail::__box<_Tp> _M_value;
 593     };
 594
 595   namespace __detail
 596   {
 597     template<typename _Wp>
 598       constexpr auto __to_signed_like(_Wp __w) noexcept
 599       {
 600         if constexpr (!integral<_Wp>)
 601           return iter_difference_t<_Wp>();
 602         else if constexpr (sizeof(iter_difference_t<_Wp>) > sizeof(_Wp))
 603           return iter_difference_t<_Wp>(__w);
 604         else if constexpr (sizeof(ptrdiff_t) > sizeof(_Wp))
 605           return ptrdiff_t(__w);
 606         else if constexpr (sizeof(long long) > sizeof(_Wp))
 607           return (long long)(__w);
 608 #ifdef __SIZEOF_INT128__
 609         else if constexpr (__SIZEOF_INT128__ > sizeof(_Wp))
 610           return __int128(__w);
 611 #endif
 612         else
 613           return __max_diff_type(__w);
 614       }
 615
 616     template<typename _Wp>
 617       using __iota_diff_t = decltype(__to_signed_like(std::declval<_Wp>()));
 618
 619     template<typename _It>
 620       concept __decrementable = incrementable<_It>
 621         && requires(_It __i)
 622         {
 623             { --__i } -> same_as<_It&>;
 624             { __i-- } -> same_as<_It>;
 625         };
 626
 627     template<typename _It>
 628       concept __advanceable = __decrementable<_It> && totally_ordered<_It>
 629         && requires( _It __i, const _It __j, const __iota_diff_t<_It> __n)
 630         {
 631           { __i += __n } -> same_as<_It&>;
 632           { __i -= __n } -> same_as<_It&>;
 633           _It(__j + __n);
 634           _It(__n + __j);
 635           _It(__j - __n);
 636           { __j - __j } -> convertible_to<__iota_diff_t<_It>>;
 637         };
 638
 639   } // namespace __detail
 640
 641   template<weakly_incrementable _Winc,
 642            semiregular _Bound = unreachable_sentinel_t>
 643     requires std::__detail::__weakly_eq_cmp_with<_Winc, _Bound>
 644     class iota_view : public view_interface<iota_view<_Winc, _Bound>>
 645     {
 646     private:
 647       struct _Iterator
 648       {
 649       private:
 650         static auto
 651         _S_iter_cat()
 652         {
 653           using namespace __detail;
 654           if constexpr (__advanceable<_Winc>)
 655             return random_access_iterator_tag{};
 656           else if constexpr (__decrementable<_Winc>)
 657             return bidirectional_iterator_tag{};
 658           else if constexpr (incrementable<_Winc>)
 659             return forward_iterator_tag{};
 660           else
 661             return input_iterator_tag{};
 662         }
 663
 664       public:
 665         using iterator_category = decltype(_S_iter_cat());
 666         using value_type = _Winc;
 667         using difference_type = __detail::__iota_diff_t<_Winc>;
 668
 669         _Iterator() = default;
 670
 671         constexpr explicit
 672         _Iterator(_Winc __value)
 673         : _M_value(__value) { }
 674
 675         constexpr _Winc
 676         operator*() const noexcept(is_nothrow_copy_constructible_v<_Winc>)
 677         { return _M_value; }
 678
 679         constexpr _Iterator&
 680         operator++()
 681         {
 682           ++_M_value;
 683           return *this;
 684         }
 685
 686         constexpr void
 687         operator++(int)
 688         { ++*this; }
 689
 690         constexpr _Iterator
 691         operator++(int) requires incrementable<_Winc>
 692         {
 693           auto __tmp = *this;
 694           ++*this;
 695           return __tmp;
 696         }
 697
 698         constexpr _Iterator&
 699         operator--() requires __detail::__decrementable<_Winc>
 700         {
 701           --_M_value;
 702           return *this;
 703         }
 704
 705         constexpr _Iterator
 706         operator--(int) requires __detail::__decrementable<_Winc>
 707         {
 708           auto __tmp = *this;
 709           --*this;
 710           return __tmp;
 711         }
 712
 713         constexpr _Iterator&
 714         operator+=(difference_type __n) requires __detail::__advanceable<_Winc>
 715         {
 716           using __detail::__is_integer_like;
 717           using __detail::__is_signed_integer_like;
 718           if constexpr (__is_integer_like<_Winc>
 719               && !__is_signed_integer_like<_Winc>)
 720             {
 721               if (__n >= difference_type(0))
 722                 _M_value += static_cast<_Winc>(__n);
 723               else
 724                 _M_value -= static_cast<_Winc>(-__n);
 725             }
 726           else
 727             _M_value += __n;
 728           return *this;
 729         }
 730
 731         constexpr _Iterator&
 732         operator-=(difference_type __n) requires __detail::__advanceable<_Winc>
 733         {
 734           using __detail::__is_integer_like;
 735           using __detail::__is_signed_integer_like;
 736           if constexpr (__is_integer_like<_Winc>
 737               && !__is_signed_integer_like<_Winc>)
 738             {
 739               if (__n >= difference_type(0))
 740                 _M_value -= static_cast<_Winc>(__n);
 741               else
 742                 _M_value += static_cast<_Winc>(-__n);
 743             }
 744           else
 745             _M_value -= __n;
 746           return *this;
 747         }
 748
 749         constexpr _Winc
 750         operator[](difference_type __n) const
 751         requires __detail::__advanceable<_Winc>
 752         { return _Winc(_M_value + __n); }
 753
 754         friend constexpr bool
 755         operator==(const _Iterator& __x, const _Iterator& __y)
 756         requires equality_comparable<_Winc>
 757         { return __x._M_value == __y._M_value; }
 758
 759         friend constexpr bool
 760         operator<(const _Iterator& __x, const _Iterator& __y)
 761         requires totally_ordered<_Winc>
 762         { return __x._M_value < __y._M_value; }
 763
 764         friend constexpr bool
 765         operator>(const _Iterator& __x, const _Iterator& __y)
 766           requires totally_ordered<_Winc>
 767         { return __y < __x; }
 768
 769         friend constexpr bool
 770         operator<=(const _Iterator& __x, const _Iterator& __y)
 771           requires totally_ordered<_Winc>
 772         { return !(__y < __x); }
 773
 774         friend constexpr bool
 775         operator>=(const _Iterator& __x, const _Iterator& __y)
 776           requires totally_ordered<_Winc>
 777         { return !(__x < __y); }
 778
 779 #ifdef __cpp_lib_threeway_comparison
 780         friend constexpr compare_three_way_result_t<_Winc>
 781         operator<=>(const _Iterator& __x, const _Iterator& __y)
 782           requires totally_ordered<_Winc> && three_way_comparable<_Winc>
 783         { return __x._M_value <=> __y._M_value; }
 784 #endif
 785
 786         friend constexpr _Iterator
 787         operator+(_Iterator __i, difference_type __n)
 788           requires __detail::__advanceable<_Winc>
 789         { return __i += __n; }
 790
 791         friend constexpr _Iterator
 792         operator+(difference_type __n, _Iterator __i)
 793           requires __detail::__advanceable<_Winc>
 794         { return __i += __n; }
 795
 796         friend constexpr _Iterator
 797         operator-(_Iterator __i, difference_type __n)
 798           requires __detail::__advanceable<_Winc>
 799         { return __i -= __n; }
 800
 801         friend constexpr difference_type
 802         operator-(const _Iterator& __x, const _Iterator& __y)
 803           requires __detail::__advanceable<_Winc>
 804         {
 805           using __detail::__is_integer_like;
 806           using __detail::__is_signed_integer_like;
 807           using _Dt = difference_type;
 808           if constexpr (__is_integer_like<_Winc>)
 809             {
 810               if constexpr (__is_signed_integer_like<_Winc>)
 811                 return _Dt(_Dt(__x._M_value) - _Dt(__y._M_value));
 812               else
 813                 return (__y._M_value > __x._M_value)
 814                   ? _Dt(-_Dt(__y._M_value - __x._M_value))
 815                   : _Dt(__x._M_value - __y._M_value);
 816             }
 817           else
 818             return __x._M_value - __y._M_value;
 819         }
 820
 821       private:
 822         _Winc _M_value = _Winc();
 823       };
 824
 825       struct _Sentinel
 826       {
 827       private:
 828         _Bound _M_bound = _Bound();
 829
 830       public:
 831         _Sentinel() = default;
 832
 833         constexpr explicit
 834         _Sentinel(_Bound __bound)
 835         : _M_bound(__bound) { }
 836
 837         friend constexpr bool
 838         operator==(const _Iterator& __x, const _Sentinel& __y)
 839         { return __x._M_value == __y._M_bound; }
 840
 841         friend constexpr iter_difference_t<_Winc>
 842         operator-(const _Iterator& __x, const _Sentinel& __y)
 843           requires sized_sentinel_for<_Bound, _Winc>
 844         { return __x._M_value - __y._M_bound; }
 845
 846         friend constexpr iter_difference_t<_Winc>
 847         operator-(const _Sentinel& __x, const _Iterator& __y)
 848           requires sized_sentinel_for<_Bound, _Winc>
 849         { return -(__y - __x); }
 850       };
 851
 852       _Winc _M_value = _Winc();
 853       _Bound _M_bound = _Bound();
 854
 855     public:
 856       iota_view() = default;
 857
 858       constexpr explicit
 859       iota_view(_Winc __value)
 860       : _M_value(__value)
 861       { }
 862
 863       constexpr
 864       iota_view(type_identity_t<_Winc> __value,
 865                 type_identity_t<_Bound> __bound)
 866       : _M_value(__value), _M_bound(__bound)
 867       {
 868         if constexpr (totally_ordered_with<_Winc, _Bound>)
 869           __glibcxx_assert( bool(__value <= __bound) );
 870       }
 871
 872       constexpr _Iterator
 873       begin() const { return _Iterator{_M_value}; }
 874
 875       constexpr auto
 876       end() const
 877       {
 878         if constexpr (same_as<_Bound, unreachable_sentinel_t>)
 879           return unreachable_sentinel;
 880         else
 881           return _Sentinel{_M_bound};
 882       }
 883
 884       constexpr _Iterator
 885       end() const requires same_as<_Winc, _Bound>
 886       { return _Iterator{_M_bound}; }
 887
 888       constexpr auto
 889       size() const
 890       requires (same_as<_Winc, _Bound> && __detail::__advanceable<_Winc>)
 891       || (integral<_Winc> && integral<_Bound>)
 892       || sized_sentinel_for<_Bound, _Winc>
 893       {
 894         using __detail::__is_integer_like;
 895         using __detail::__to_unsigned_like;
 896         if constexpr (__is_integer_like<_Winc> && __is_integer_like<_Bound>)
 897           return (_M_value < 0)
 898             ? ((_M_bound < 0)
 899                 ? __to_unsigned_like(-_M_value) - __to_unsigned_like(-_M_bound)
 900                 : __to_unsigned_like(_M_bound) + __to_unsigned_like(-_M_value))
 901             : __to_unsigned_like(_M_bound) - __to_unsigned_like(_M_value);
 902         else
 903           return __to_unsigned_like(_M_bound - _M_value);
 904       }
 905     };
 906
 907   template<typename _Winc, typename _Bound>
 908     requires (!__detail::__is_integer_like<_Winc>
 909         || !__detail::__is_integer_like<_Bound>
 910         || (__detail::__is_signed_integer_like<_Winc>
 911             == __detail::__is_signed_integer_like<_Bound>))
 912     iota_view(_Winc, _Bound) -> iota_view<_Winc, _Bound>;
 913
 914   template<weakly_incrementable _Winc, semiregular _Bound>
 915     inline constexpr bool enable_safe_range<iota_view<_Winc, _Bound>> = true;
 916
 917 namespace views
 918 {
 919   template<typename _Tp>
 920     inline constexpr empty_view<_Tp> empty{};
 921
 922   struct _Single
 923   {
 924     template<typename _Tp>
 925       auto
 926       operator()(_Tp&& __e) const
 927       { return single_view{std::forward<_Tp>(__e)}; }
 928   };
 929
 930   inline constexpr _Single single{};
 931
 932   struct _Iota
 933   {
 934     template<typename _Tp>
 935       auto
 936       operator()(_Tp&& __e) const
 937       { return iota_view{std::forward<_Tp>(__e)}; }
 938
 939     template<typename _Tp, typename _Up>
 940       auto
 941       operator()(_Tp&& __e, _Up&& __f) const
 942       { return iota_view{std::forward<_Tp>(__e), std::forward<_Tp>(__f)}; }
 943   };
 944
 945   inline constexpr _Iota iota{};
 946
 947 } // namespace views
 948 } // namespace ranges
 949 _GLIBCXX_END_NAMESPACE_VERSION
 950 } // namespace
 951 #endif // library concepts
 952 #endif // C++2a
 953 #endif /* _GLIBCXX_RANGES */