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 <bits/refwrap.h>
  42 #include <compare>
  43 #include <initializer_list>
  44 #include <iterator>
  45 #include <optional>
  46 #include <tuple>
  47
  48 /**
  49  * @defgroup ranges Ranges
  50  *
  51  * Components for dealing with ranges of elements.
  52  */
  53
  54 namespace std _GLIBCXX_VISIBILITY(default)
  55 {
  56 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  57 namespace ranges
  58 {
  59   // [range.range] The range concept.
  60   // [range.sized] The sized_range concept.
  61   // Defined in <bits/range_access.h>
  62
  63   // [range.refinements]
  64   // Defined in <bits/range_access.h>
  65
  66   struct view_base { };
  67
  68   template<typename _Tp>
  69     inline constexpr bool enable_view = derived_from<_Tp, view_base>;
  70
  71   template<typename _Tp>
  72     concept view
  73       = range<_Tp> && movable<_Tp> && default_initializable<_Tp>
  74         && enable_view<_Tp>;
  75
  76   /// A range which can be safely converted to a view.
  77   template<typename _Tp>
  78     concept viewable_range = range<_Tp>
  79       && (borrowed_range<_Tp> || view<remove_cvref_t<_Tp>>);
  80
  81   namespace __detail
  82   {
  83     template<typename _Range>
  84       concept __simple_view = view<_Range> && range<const _Range>
  85         && same_as<iterator_t<_Range>, iterator_t<const _Range>>
  86         && same_as<sentinel_t<_Range>, sentinel_t<const _Range>>;
  87
  88     template<typename _It>
  89       concept __has_arrow = input_iterator<_It>
  90         && (is_pointer_v<_It> || requires(_It __it) { __it.operator->(); });
  91
  92     template<typename _Tp, typename _Up>
  93       concept __not_same_as
  94         = !same_as<remove_cvref_t<_Tp>, remove_cvref_t<_Up>>;
  95   } // namespace __detail
  96
  97   template<typename _Derived>
  98     requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
  99     class view_interface : public view_base
 100     {
 101     private:
 102       constexpr _Derived& _M_derived() noexcept
 103       {
 104         static_assert(derived_from<_Derived, view_interface<_Derived>>);
 105         static_assert(view<_Derived>);
 106         return static_cast<_Derived&>(*this);
 107       }
 108
 109       constexpr const _Derived& _M_derived() const noexcept
 110       {
 111         static_assert(derived_from<_Derived, view_interface<_Derived>>);
 112         static_assert(view<_Derived>);
 113         return static_cast<const _Derived&>(*this);
 114       }
 115
 116     public:
 117       constexpr bool
 118       empty() requires forward_range<_Derived>
 119       { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }
 120
 121       constexpr bool
 122       empty() const requires forward_range<const _Derived>
 123       { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }
 124
 125       constexpr explicit
 126       operator bool() requires requires { ranges::empty(_M_derived()); }
 127       { return !ranges::empty(_M_derived()); }
 128
 129       constexpr explicit
 130       operator bool() const requires requires { ranges::empty(_M_derived()); }
 131       { return !ranges::empty(_M_derived()); }
 132
 133       constexpr auto
 134       data() requires contiguous_iterator<iterator_t<_Derived>>
 135       { return to_address(ranges::begin(_M_derived())); }
 136
 137       constexpr auto
 138       data() const
 139       requires range<const _Derived>
 140         && contiguous_iterator<iterator_t<const _Derived>>
 141       { return to_address(ranges::begin(_M_derived())); }
 142
 143       constexpr auto
 144       size()
 145       requires forward_range<_Derived>
 146         && sized_sentinel_for<sentinel_t<_Derived>, iterator_t<_Derived>>
 147       { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }
 148
 149       constexpr auto
 150       size() const
 151       requires forward_range<const _Derived>
 152         && sized_sentinel_for<sentinel_t<const _Derived>,
 153                               iterator_t<const _Derived>>
 154       { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }
 155
 156       constexpr decltype(auto)
 157       front() requires forward_range<_Derived>
 158       {
 159         __glibcxx_assert(!empty());
 160         return *ranges::begin(_M_derived());
 161       }
 162
 163       constexpr decltype(auto)
 164       front() const requires forward_range<const _Derived>
 165       {
 166         __glibcxx_assert(!empty());
 167         return *ranges::begin(_M_derived());
 168       }
 169
 170       constexpr decltype(auto)
 171       back()
 172       requires bidirectional_range<_Derived> && common_range<_Derived>
 173       {
 174         __glibcxx_assert(!empty());
 175         return *ranges::prev(ranges::end(_M_derived()));
 176       }
 177
 178       constexpr decltype(auto)
 179       back() const
 180       requires bidirectional_range<const _Derived>
 181         && common_range<const _Derived>
 182       {
 183         __glibcxx_assert(!empty());
 184         return *ranges::prev(ranges::end(_M_derived()));
 185       }
 186
 187       template<random_access_range _Range = _Derived>
 188         constexpr decltype(auto)
 189         operator[](range_difference_t<_Range> __n)
 190         { return ranges::begin(_M_derived())[__n]; }
 191
 192       template<random_access_range _Range = const _Derived>
 193         constexpr decltype(auto)
 194         operator[](range_difference_t<_Range> __n) const
 195         { return ranges::begin(_M_derived())[__n]; }
 196     };
 197
 198   namespace __detail
 199   {
 200     template<class _From, class _To>
 201       concept __convertible_to_non_slicing = convertible_to<_From, _To>
 202         && !(is_pointer_v<decay_t<_From>> && is_pointer_v<decay_t<_To>>
 203             && __not_same_as<remove_pointer_t<decay_t<_From>>,
 204                              remove_pointer_t<decay_t<_To>>>);
 205
 206     template<typename _Tp>
 207       concept __pair_like
 208         = !is_reference_v<_Tp> && requires(_Tp __t)
 209         {
 210           typename tuple_size<_Tp>::type;
 211           requires derived_from<tuple_size<_Tp>, integral_constant<size_t, 2>>;
 212           typename tuple_element_t<0, remove_const_t<_Tp>>;
 213           typename tuple_element_t<1, remove_const_t<_Tp>>;
 214           { get<0>(__t) } -> convertible_to<const tuple_element_t<0, _Tp>&>;
 215           { get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>;
 216         };
 217
 218     template<typename _Tp, typename _Up, typename _Vp>
 219       concept __pair_like_convertible_from
 220         = !range<_Tp> && __pair_like<_Tp>
 221         && constructible_from<_Tp, _Up, _Vp>
 222         && __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>>
 223         && convertible_to<_Vp, tuple_element_t<1, _Tp>>;
 224
 225     template<typename _Tp>
 226       concept __iterator_sentinel_pair
 227         = !range<_Tp> && __pair_like<_Tp>
 228         && sentinel_for<tuple_element_t<1, _Tp>, tuple_element_t<0, _Tp>>;
 229
 230   } // namespace __detail
 231
 232   enum class subrange_kind : bool { unsized, sized };
 233
 234   template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
 235            subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
 236              ? subrange_kind::sized : subrange_kind::unsized>
 237     requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>)
 238     class subrange : public view_interface<subrange<_It, _Sent, _Kind>>
 239     {
 240     private:
 241       // XXX: gcc complains when using constexpr here
 242       static const bool _S_store_size
 243         = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>;
 244
 245       _It _M_begin = _It();
 246       _Sent _M_end = _Sent();
 247
 248       template<typename, bool = _S_store_size>
 249         struct _Size
 250         { };
 251
 252       template<typename _Tp>
 253         struct _Size<_Tp, true>
 254         { __detail::__make_unsigned_like_t<_Tp> _M_size; };
 255
 256       [[no_unique_address]] _Size<iter_difference_t<_It>> _M_size = {};
 257
 258     public:
 259       subrange() = default;
 260
 261       constexpr
 262       subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s)
 263         requires (!_S_store_size)
 264       : _M_begin(std::move(__i)), _M_end(__s)
 265       { }
 266
 267       constexpr
 268       subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s,
 269                __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
 270         requires (_Kind == subrange_kind::sized)
 271       : _M_begin(std::move(__i)), _M_end(__s)
 272       {
 273         using __detail::__to_unsigned_like;
 274         __glibcxx_assert(__n == __to_unsigned_like(ranges::distance(__i, __s)));
 275         if constexpr (_S_store_size)
 276           _M_size._M_size = __n;
 277       }
 278
 279       template<__detail::__not_same_as<subrange> _Rng>
 280         requires borrowed_range<_Rng>
 281           && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
 282           && convertible_to<sentinel_t<_Rng>, _Sent>
 283         constexpr
 284         subrange(_Rng&& __r) requires (!_S_store_size || sized_range<_Rng>)
 285         : subrange{ranges::begin(__r), ranges::end(__r)}
 286         {
 287           if constexpr (_S_store_size)
 288             _M_size._M_size = ranges::size(__r);
 289         }
 290
 291       template<borrowed_range _Rng>
 292         requires __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
 293           && convertible_to<sentinel_t<_Rng>, _Sent>
 294         constexpr
 295         subrange(_Rng&& __r,
 296                  __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
 297         requires (_Kind == subrange_kind::sized)
 298         : subrange{ranges::begin(__r), ranges::end(__r), __n}
 299         { }
 300
 301       template<__detail::__not_same_as<subrange> _PairLike>
 302         requires __detail::__pair_like_convertible_from<_PairLike, const _It&,
 303                                                         const _Sent&>
 304       constexpr
 305       operator _PairLike() const
 306       { return _PairLike(_M_begin, _M_end); }
 307
 308       constexpr _It
 309       begin() const requires copyable<_It>
 310       { return _M_begin; }
 311
 312       [[nodiscard]] constexpr _It
 313       begin() requires (!copyable<_It>)
 314       { return std::move(_M_begin); }
 315
 316       constexpr _Sent end() const { return _M_end; }
 317
 318       constexpr bool empty() const { return _M_begin == _M_end; }
 319
 320       constexpr __detail::__make_unsigned_like_t<iter_difference_t<_It>>
 321       size() const requires (_Kind == subrange_kind::sized)
 322       {
 323         if constexpr (_S_store_size)
 324           return _M_size._M_size;
 325         else
 326           return __detail::__to_unsigned_like(_M_end - _M_begin);
 327       }
 328
 329       [[nodiscard]] constexpr subrange
 330       next(iter_difference_t<_It> __n = 1) const &
 331         requires forward_iterator<_It>
 332       {
 333         auto __tmp = *this;
 334         __tmp.advance(__n);
 335         return __tmp;
 336       }
 337
 338       [[nodiscard]] constexpr subrange
 339       next(iter_difference_t<_It> __n = 1) &&
 340       {
 341         advance(__n);
 342         return std::move(*this);
 343       }
 344
 345       [[nodiscard]] constexpr subrange
 346       prev(iter_difference_t<_It> __n = 1) const
 347         requires bidirectional_iterator<_It>
 348       {
 349         auto __tmp = *this;
 350         __tmp.advance(--__n);
 351         return __tmp;
 352       }
 353
 354       constexpr subrange&
 355       advance(iter_difference_t<_It> __n)
 356       {
 357         if constexpr (_S_store_size)
 358           {
 359             auto __d = __n - ranges::advance(_M_begin, __n, _M_end);
 360             if (__d >= 0)
 361               _M_size._M_size -= __detail::__to_unsigned_like(__d);
 362             else
 363               _M_size._M_size += __detail::__to_unsigned_like(-__d);
 364           }
 365         else
 366           ranges::advance(_M_begin, __n, _M_end);
 367         return *this;
 368       }
 369     };
 370
 371   template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
 372     subrange(_It, _Sent) -> subrange<_It, _Sent>;
 373
 374   template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
 375     subrange(_It, _Sent,
 376              __detail::__make_unsigned_like_t<iter_difference_t<_It>>)
 377       -> subrange<_It, _Sent, subrange_kind::sized>;
 378
 379   template<__detail::__iterator_sentinel_pair _Pr>
 380     subrange(_Pr)
 381       -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>>;
 382
 383   template<__detail::__iterator_sentinel_pair _Pr>
 384     subrange(_Pr, __detail::__make_unsigned_like_t<iter_difference_t<
 385                                                      tuple_element_t<0, _Pr>>>)
 386       -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>,
 387                   subrange_kind::sized>;
 388
 389   template<borrowed_range _Rng>
 390     subrange(_Rng&&)
 391       -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>,
 392                  (sized_range<_Rng>
 393                   || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>)
 394                  ? subrange_kind::sized : subrange_kind::unsized>;
 395
 396   template<borrowed_range _Rng>
 397     subrange(_Rng&&,
 398              __detail::__make_unsigned_like_t<range_difference_t<_Rng>>)
 399       -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>;
 400
 401   template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
 402     requires (_Num < 2)
 403     constexpr auto
 404     get(const subrange<_It, _Sent, _Kind>& __r)
 405     {
 406       if constexpr (_Num == 0)
 407         return __r.begin();
 408       else
 409         return __r.end();
 410     }
 411
 412   template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
 413     requires (_Num < 2)
 414     constexpr auto
 415     get(subrange<_It, _Sent, _Kind>&& __r)
 416     {
 417       if constexpr (_Num == 0)
 418         return __r.begin();
 419       else
 420         return __r.end();
 421     }
 422
 423   template<input_or_output_iterator _It, sentinel_for<_It> _Sent,
 424            subrange_kind _Kind>
 425     inline constexpr bool
 426       enable_borrowed_range<subrange<_It, _Sent, _Kind>> = true;
 427
 428 } // namespace ranges
 429
 430   using ranges::get;
 431
 432 namespace ranges
 433 {
 434   /// Type returned by algorithms instead of a dangling iterator or subrange.
 435   struct dangling
 436   {
 437     constexpr dangling() noexcept = default;
 438     template<typename... _Args>
 439       constexpr dangling(_Args&&...) noexcept { }
 440   };
 441
 442   template<range _Range>
 443     using borrowed_iterator_t = conditional_t<borrowed_range<_Range>,
 444                                               iterator_t<_Range>,
 445                                               dangling>;
 446
 447   template<range _Range>
 448     using borrowed_subrange_t = conditional_t<borrowed_range<_Range>,
 449                                               subrange<iterator_t<_Range>>,
 450                                               dangling>;
 451
 452   template<typename _Tp> requires is_object_v<_Tp>
 453     class empty_view
 454     : public view_interface<empty_view<_Tp>>
 455     {
 456     public:
 457       static constexpr _Tp* begin() noexcept { return nullptr; }
 458       static constexpr _Tp* end() noexcept { return nullptr; }
 459       static constexpr _Tp* data() noexcept { return nullptr; }
 460       static constexpr size_t size() noexcept { return 0; }
 461       static constexpr bool empty() noexcept { return true; }
 462     };
 463
 464   template<typename _Tp>
 465     inline constexpr bool enable_borrowed_range<empty_view<_Tp>> = true;
 466
 467   namespace __detail
 468   {
 469     template<copy_constructible _Tp> requires is_object_v<_Tp>
 470       struct __box : std::optional<_Tp>
 471       {
 472         using std::optional<_Tp>::optional;
 473
 474         constexpr
 475         __box()
 476         noexcept(is_nothrow_default_constructible_v<_Tp>)
 477         requires default_initializable<_Tp>
 478         : std::optional<_Tp>{std::in_place}
 479         { }
 480
 481         __box(const __box&) = default;
 482         __box(__box&&) = default;
 483
 484         using std::optional<_Tp>::operator=;
 485
 486         __box&
 487         operator=(const __box& __that)
 488         noexcept(is_nothrow_copy_constructible_v<_Tp>)
 489         requires (!assignable_from<_Tp&, const _Tp&>)
 490         {
 491           if ((bool)__that)
 492             this->emplace(*__that);
 493           else
 494             this->reset();
 495           return *this;
 496         }
 497
 498         __box&
 499         operator=(__box&& __that)
 500         noexcept(is_nothrow_move_constructible_v<_Tp>)
 501         requires (!assignable_from<_Tp&, _Tp>)
 502         {
 503           if ((bool)__that)
 504             this->emplace(std::move(*__that));
 505           else
 506             this->reset();
 507           return *this;
 508         }
 509       };
 510
 511   } // namespace __detail
 512
 513   /// A view that contains exactly one element.
 514   template<copy_constructible _Tp> requires is_object_v<_Tp>
 515     class single_view : public view_interface<single_view<_Tp>>
 516     {
 517     public:
 518       single_view() = default;
 519
 520       constexpr explicit
 521       single_view(const _Tp& __t)
 522       : _M_value(__t)
 523       { }
 524
 525       constexpr explicit
 526       single_view(_Tp&& __t)
 527       : _M_value(std::move(__t))
 528       { }
 529
 530       template<typename... _Args>
 531         requires constructible_from<_Tp, _Args...>
 532         constexpr
 533         single_view(in_place_t, _Args&&... __args)
 534         : _M_value{in_place, std::forward<_Args>(__args)...}
 535         { }
 536
 537       constexpr _Tp*
 538       begin() noexcept
 539       { return data(); }
 540
 541       constexpr const _Tp*
 542       begin() const noexcept
 543       { return data(); }
 544
 545       constexpr _Tp*
 546       end() noexcept
 547       { return data() + 1; }
 548
 549       constexpr const _Tp*
 550       end() const noexcept
 551       { return data() + 1; }
 552
 553       static constexpr size_t
 554       size() noexcept
 555       { return 1; }
 556
 557       constexpr _Tp*
 558       data() noexcept
 559       { return _M_value.operator->(); }
 560
 561       constexpr const _Tp*
 562       data() const noexcept
 563       { return _M_value.operator->(); }
 564
 565     private:
 566       __detail::__box<_Tp> _M_value;
 567     };
 568
 569   namespace __detail
 570   {
 571     template<typename _Wp>
 572       constexpr auto __to_signed_like(_Wp __w) noexcept
 573       {
 574         if constexpr (!integral<_Wp>)
 575           return iter_difference_t<_Wp>();
 576         else if constexpr (sizeof(iter_difference_t<_Wp>) > sizeof(_Wp))
 577           return iter_difference_t<_Wp>(__w);
 578         else if constexpr (sizeof(ptrdiff_t) > sizeof(_Wp))
 579           return ptrdiff_t(__w);
 580         else if constexpr (sizeof(long long) > sizeof(_Wp))
 581           return (long long)(__w);
 582 #ifdef __SIZEOF_INT128__
 583         else if constexpr (__SIZEOF_INT128__ > sizeof(_Wp))
 584           return __int128(__w);
 585 #endif
 586         else
 587           return __max_diff_type(__w);
 588       }
 589
 590     template<typename _Wp>
 591       using __iota_diff_t = decltype(__to_signed_like(std::declval<_Wp>()));
 592
 593     template<typename _It>
 594       concept __decrementable = incrementable<_It>
 595         && requires(_It __i)
 596         {
 597             { --__i } -> same_as<_It&>;
 598             { __i-- } -> same_as<_It>;
 599         };
 600
 601     template<typename _It>
 602       concept __advanceable = __decrementable<_It> && totally_ordered<_It>
 603         && requires( _It __i, const _It __j, const __iota_diff_t<_It> __n)
 604         {
 605           { __i += __n } -> same_as<_It&>;
 606           { __i -= __n } -> same_as<_It&>;
 607           _It(__j + __n);
 608           _It(__n + __j);
 609           _It(__j - __n);
 610           { __j - __j } -> convertible_to<__iota_diff_t<_It>>;
 611         };
 612
 613   } // namespace __detail
 614
 615   template<weakly_incrementable _Winc,
 616            semiregular _Bound = unreachable_sentinel_t>
 617     requires std::__detail::__weakly_eq_cmp_with<_Winc, _Bound>
 618       && semiregular<_Winc>
 619     class iota_view : public view_interface<iota_view<_Winc, _Bound>>
 620     {
 621     private:
 622       struct _Sentinel;
 623
 624       struct _Iterator
 625       {
 626       private:
 627         static auto
 628         _S_iter_cat()
 629         {
 630           using namespace __detail;
 631           if constexpr (__advanceable<_Winc>)
 632             return random_access_iterator_tag{};
 633           else if constexpr (__decrementable<_Winc>)
 634             return bidirectional_iterator_tag{};
 635           else if constexpr (incrementable<_Winc>)
 636             return forward_iterator_tag{};
 637           else
 638             return input_iterator_tag{};
 639         }
 640
 641       public:
 642         using iterator_category = decltype(_S_iter_cat());
 643         using value_type = _Winc;
 644         using difference_type = __detail::__iota_diff_t<_Winc>;
 645
 646         _Iterator() = default;
 647
 648         constexpr explicit
 649         _Iterator(_Winc __value)
 650         : _M_value(__value) { }
 651
 652         constexpr _Winc
 653         operator*() const noexcept(is_nothrow_copy_constructible_v<_Winc>)
 654         { return _M_value; }
 655
 656         constexpr _Iterator&
 657         operator++()
 658         {
 659           ++_M_value;
 660           return *this;
 661         }
 662
 663         constexpr void
 664         operator++(int)
 665         { ++*this; }
 666
 667         constexpr _Iterator
 668         operator++(int) requires incrementable<_Winc>
 669         {
 670           auto __tmp = *this;
 671           ++*this;
 672           return __tmp;
 673         }
 674
 675         constexpr _Iterator&
 676         operator--() requires __detail::__decrementable<_Winc>
 677         {
 678           --_M_value;
 679           return *this;
 680         }
 681
 682         constexpr _Iterator
 683         operator--(int) requires __detail::__decrementable<_Winc>
 684         {
 685           auto __tmp = *this;
 686           --*this;
 687           return __tmp;
 688         }
 689
 690         constexpr _Iterator&
 691         operator+=(difference_type __n) requires __detail::__advanceable<_Winc>
 692         {
 693           using __detail::__is_integer_like;
 694           using __detail::__is_signed_integer_like;
 695           if constexpr (__is_integer_like<_Winc>
 696               && !__is_signed_integer_like<_Winc>)
 697             {
 698               if (__n >= difference_type(0))
 699                 _M_value += static_cast<_Winc>(__n);
 700               else
 701                 _M_value -= static_cast<_Winc>(-__n);
 702             }
 703           else
 704             _M_value += __n;
 705           return *this;
 706         }
 707
 708         constexpr _Iterator&
 709         operator-=(difference_type __n) requires __detail::__advanceable<_Winc>
 710         {
 711           using __detail::__is_integer_like;
 712           using __detail::__is_signed_integer_like;
 713           if constexpr (__is_integer_like<_Winc>
 714               && !__is_signed_integer_like<_Winc>)
 715             {
 716               if (__n >= difference_type(0))
 717                 _M_value -= static_cast<_Winc>(__n);
 718               else
 719                 _M_value += static_cast<_Winc>(-__n);
 720             }
 721           else
 722             _M_value -= __n;
 723           return *this;
 724         }
 725
 726         constexpr _Winc
 727         operator[](difference_type __n) const
 728         requires __detail::__advanceable<_Winc>
 729         { return _Winc(_M_value + __n); }
 730
 731         friend constexpr bool
 732         operator==(const _Iterator& __x, const _Iterator& __y)
 733         requires equality_comparable<_Winc>
 734         { return __x._M_value == __y._M_value; }
 735
 736         friend constexpr bool
 737         operator<(const _Iterator& __x, const _Iterator& __y)
 738         requires totally_ordered<_Winc>
 739         { return __x._M_value < __y._M_value; }
 740
 741         friend constexpr bool
 742         operator>(const _Iterator& __x, const _Iterator& __y)
 743           requires totally_ordered<_Winc>
 744         { return __y < __x; }
 745
 746         friend constexpr bool
 747         operator<=(const _Iterator& __x, const _Iterator& __y)
 748           requires totally_ordered<_Winc>
 749         { return !(__y < __x); }
 750
 751         friend constexpr bool
 752         operator>=(const _Iterator& __x, const _Iterator& __y)
 753           requires totally_ordered<_Winc>
 754         { return !(__x < __y); }
 755
 756 #ifdef __cpp_lib_three_way_comparison
 757         friend constexpr auto
 758         operator<=>(const _Iterator& __x, const _Iterator& __y)
 759           requires totally_ordered<_Winc> && three_way_comparable<_Winc>
 760         { return __x._M_value <=> __y._M_value; }
 761 #endif
 762
 763         friend constexpr _Iterator
 764         operator+(_Iterator __i, difference_type __n)
 765           requires __detail::__advanceable<_Winc>
 766         { return __i += __n; }
 767
 768         friend constexpr _Iterator
 769         operator+(difference_type __n, _Iterator __i)
 770           requires __detail::__advanceable<_Winc>
 771         { return __i += __n; }
 772
 773         friend constexpr _Iterator
 774         operator-(_Iterator __i, difference_type __n)
 775           requires __detail::__advanceable<_Winc>
 776         { return __i -= __n; }
 777
 778         friend constexpr difference_type
 779         operator-(const _Iterator& __x, const _Iterator& __y)
 780           requires __detail::__advanceable<_Winc>
 781         {
 782           using __detail::__is_integer_like;
 783           using __detail::__is_signed_integer_like;
 784           using _Dt = difference_type;
 785           if constexpr (__is_integer_like<_Winc>)
 786             {
 787               if constexpr (__is_signed_integer_like<_Winc>)
 788                 return _Dt(_Dt(__x._M_value) - _Dt(__y._M_value));
 789               else
 790                 return (__y._M_value > __x._M_value)
 791                   ? _Dt(-_Dt(__y._M_value - __x._M_value))
 792                   : _Dt(__x._M_value - __y._M_value);
 793             }
 794           else
 795             return __x._M_value - __y._M_value;
 796         }
 797
 798       private:
 799         _Winc _M_value = _Winc();
 800
 801         friend _Sentinel;
 802       };
 803
 804       struct _Sentinel
 805       {
 806       private:
 807         constexpr bool
 808         _M_equal(const _Iterator& __x) const
 809         { return __x._M_value == _M_bound; }
 810
 811         _Bound _M_bound = _Bound();
 812
 813       public:
 814         _Sentinel() = default;
 815
 816         constexpr explicit
 817         _Sentinel(_Bound __bound)
 818         : _M_bound(__bound) { }
 819
 820         friend constexpr bool
 821         operator==(const _Iterator& __x, const _Sentinel& __y)
 822         { return __y._M_equal(__x); }
 823
 824         friend constexpr iter_difference_t<_Winc>
 825         operator-(const _Iterator& __x, const _Sentinel& __y)
 826           requires sized_sentinel_for<_Bound, _Winc>
 827         { return __x._M_value - __y._M_bound; }
 828
 829         friend constexpr iter_difference_t<_Winc>
 830         operator-(const _Sentinel& __x, const _Iterator& __y)
 831           requires sized_sentinel_for<_Bound, _Winc>
 832         { return -(__y - __x); }
 833       };
 834
 835       _Winc _M_value = _Winc();
 836       _Bound _M_bound = _Bound();
 837
 838     public:
 839       iota_view() = default;
 840
 841       constexpr explicit
 842       iota_view(_Winc __value)
 843       : _M_value(__value)
 844       { }
 845
 846       constexpr
 847       iota_view(type_identity_t<_Winc> __value,
 848                 type_identity_t<_Bound> __bound)
 849       : _M_value(__value), _M_bound(__bound)
 850       {
 851         if constexpr (totally_ordered_with<_Winc, _Bound>)
 852           {
 853             __glibcxx_assert( bool(__value <= __bound) );
 854           }
 855       }
 856
 857       constexpr _Iterator
 858       begin() const { return _Iterator{_M_value}; }
 859
 860       constexpr auto
 861       end() const
 862       {
 863         if constexpr (same_as<_Bound, unreachable_sentinel_t>)
 864           return unreachable_sentinel;
 865         else
 866           return _Sentinel{_M_bound};
 867       }
 868
 869       constexpr _Iterator
 870       end() const requires same_as<_Winc, _Bound>
 871       { return _Iterator{_M_bound}; }
 872
 873       constexpr auto
 874       size() const
 875       requires (same_as<_Winc, _Bound> && __detail::__advanceable<_Winc>)
 876       || (integral<_Winc> && integral<_Bound>)
 877       || sized_sentinel_for<_Bound, _Winc>
 878       {
 879         using __detail::__is_integer_like;
 880         using __detail::__to_unsigned_like;
 881         if constexpr (__is_integer_like<_Winc> && __is_integer_like<_Bound>)
 882           return (_M_value < 0)
 883             ? ((_M_bound < 0)
 884                 ? __to_unsigned_like(-_M_value) - __to_unsigned_like(-_M_bound)
 885                 : __to_unsigned_like(_M_bound) + __to_unsigned_like(-_M_value))
 886             : __to_unsigned_like(_M_bound) - __to_unsigned_like(_M_value);
 887         else
 888           return __to_unsigned_like(_M_bound - _M_value);
 889       }
 890     };
 891
 892   template<typename _Winc, typename _Bound>
 893     requires (!__detail::__is_integer_like<_Winc>
 894         || !__detail::__is_integer_like<_Bound>
 895         || (__detail::__is_signed_integer_like<_Winc>
 896             == __detail::__is_signed_integer_like<_Bound>))
 897     iota_view(_Winc, _Bound) -> iota_view<_Winc, _Bound>;
 898
 899   template<weakly_incrementable _Winc, semiregular _Bound>
 900     inline constexpr bool
 901       enable_borrowed_range<iota_view<_Winc, _Bound>> = true;
 902
 903 namespace views
 904 {
 905   template<typename _Tp>
 906     inline constexpr empty_view<_Tp> empty{};
 907
 908   struct _Single
 909   {
 910     template<typename _Tp>
 911       constexpr auto
 912       operator()(_Tp&& __e) const
 913       { return single_view{std::forward<_Tp>(__e)}; }
 914   };
 915
 916   inline constexpr _Single single{};
 917
 918   struct _Iota
 919   {
 920     template<typename _Tp>
 921       constexpr auto
 922       operator()(_Tp&& __e) const
 923       { return iota_view{std::forward<_Tp>(__e)}; }
 924
 925     template<typename _Tp, typename _Up>
 926       constexpr auto
 927       operator()(_Tp&& __e, _Up&& __f) const
 928       { return iota_view{std::forward<_Tp>(__e), std::forward<_Up>(__f)}; }
 929   };
 930
 931   inline constexpr _Iota iota{};
 932 } // namespace views
 933
 934   namespace __detail
 935   {
 936     template<typename _Val, typename _CharT, typename _Traits>
 937       concept __stream_extractable
 938         = requires(basic_istream<_CharT, _Traits>& is, _Val& t) { is >> t; };
 939   } // namespace __detail
 940
 941   template<movable _Val, typename _CharT, typename _Traits>
 942     requires default_initializable<_Val>
 943       && __detail::__stream_extractable<_Val, _CharT, _Traits>
 944     class basic_istream_view
 945     : public view_interface<basic_istream_view<_Val, _CharT, _Traits>>
 946     {
 947     public:
 948       basic_istream_view() = default;
 949
 950       constexpr explicit
 951       basic_istream_view(basic_istream<_CharT, _Traits>& __stream)
 952         : _M_stream(std::__addressof(__stream))
 953       { }
 954
 955       constexpr auto
 956       begin()
 957       {
 958         if (_M_stream != nullptr)
 959           *_M_stream >> _M_object;
 960         return _Iterator{*this};
 961       }
 962
 963       constexpr default_sentinel_t
 964       end() const noexcept
 965       { return default_sentinel; }
 966
 967     private:
 968       basic_istream<_CharT, _Traits>* _M_stream = nullptr;
 969       _Val _M_object = _Val();
 970
 971       struct _Iterator
 972       {
 973       public:
 974         using iterator_concept = input_iterator_tag;
 975         using difference_type = ptrdiff_t;
 976         using value_type = _Val;
 977
 978         _Iterator() = default;
 979
 980         constexpr explicit
 981         _Iterator(basic_istream_view& __parent) noexcept
 982           : _M_parent(std::__addressof(__parent))
 983         { }
 984
 985         _Iterator(const _Iterator&) = delete;
 986         _Iterator(_Iterator&&) = default;
 987         _Iterator& operator=(const _Iterator&) = delete;
 988         _Iterator& operator=(_Iterator&&) = default;
 989
 990         _Iterator&
 991         operator++()
 992         {
 993           __glibcxx_assert(_M_parent->_M_stream != nullptr);
 994           *_M_parent->_M_stream >> _M_parent->_M_object;
 995           return *this;
 996         }
 997
 998         void
 999         operator++(int)
1000         { ++*this; }
1001
1002         _Val&
1003         operator*() const
1004         {
1005           __glibcxx_assert(_M_parent->_M_stream != nullptr);
1006           return _M_parent->_M_object;
1007         }
1008
1009         friend bool
1010         operator==(const _Iterator& __x, default_sentinel_t)
1011         { return __x._M_at_end(); }
1012
1013       private:
1014         basic_istream_view* _M_parent = nullptr;
1015
1016         bool
1017         _M_at_end() const
1018         { return _M_parent == nullptr || !*_M_parent->_M_stream; }
1019       };
1020
1021       friend _Iterator;
1022     };
1023
1024   template<typename _Val, typename _CharT, typename _Traits>
1025     basic_istream_view<_Val, _CharT, _Traits>
1026     istream_view(basic_istream<_CharT, _Traits>& __s)
1027     { return basic_istream_view<_Val, _CharT, _Traits>{__s}; }
1028
1029 namespace __detail
1030 {
1031   struct _Empty { };
1032
1033   // Alias for a type that is conditionally present
1034   // (and is an empty type otherwise).
1035   // Data members using this alias should use [[no_unique_address]] so that
1036   // they take no space when not needed.
1037   template<bool _Present, typename _Tp>
1038     using __maybe_present_t = conditional_t<_Present, _Tp, _Empty>;
1039
1040   // Alias for a type that is conditionally const.
1041   template<bool _Const, typename _Tp>
1042     using __maybe_const_t = conditional_t<_Const, const _Tp, _Tp>;
1043
1044 } // namespace __detail
1045
1046 namespace views
1047 {
1048   namespace __adaptor
1049   {
1050     template<typename _Tp>
1051       inline constexpr auto
1052       __maybe_refwrap(_Tp& __arg)
1053       { return reference_wrapper<_Tp>{__arg}; }
1054
1055     template<typename _Tp>
1056       inline constexpr auto
1057       __maybe_refwrap(const _Tp& __arg)
1058       { return reference_wrapper<const _Tp>{__arg}; }
1059
1060     template<typename _Tp>
1061       inline constexpr decltype(auto)
1062       __maybe_refwrap(_Tp&& __arg)
1063       { return std::forward<_Tp>(__arg); }
1064
1065     template<typename _Callable>
1066       struct _RangeAdaptorClosure;
1067
1068     template<typename _Callable>
1069       struct _RangeAdaptor
1070       {
1071       protected:
1072         [[no_unique_address]]
1073           __detail::__maybe_present_t<!is_default_constructible_v<_Callable>,
1074                                       _Callable> _M_callable;
1075
1076       public:
1077         constexpr
1078         _RangeAdaptor(const _Callable& = {})
1079           requires is_default_constructible_v<_Callable>
1080         { }
1081
1082         constexpr
1083         _RangeAdaptor(_Callable __callable)
1084           requires (!is_default_constructible_v<_Callable>)
1085           : _M_callable(std::move(__callable))
1086         { }
1087
1088         template<typename... _Args>
1089           requires (sizeof...(_Args) >= 1)
1090           constexpr auto
1091           operator()(_Args&&... __args) const
1092           {
1093             // [range.adaptor.object]: If a range adaptor object accepts more
1094             // than one argument, then the following expressions are equivalent:
1095             //
1096             //   (1) adaptor(range, args...)
1097             //   (2) adaptor(args...)(range)
1098             //   (3) range | adaptor(args...)
1099             //
1100             // In this case, adaptor(args...) is a range adaptor closure object.
1101             //
1102             // We handle (1) and (2) here, and (3) is just a special case of a
1103             // more general case already handled by _RangeAdaptorClosure.
1104             if constexpr (is_invocable_v<_Callable, _Args...>)
1105               {
1106                 static_assert(sizeof...(_Args) != 1,
1107                               "a _RangeAdaptor that accepts only one argument "
1108                               "should be defined as a _RangeAdaptorClosure");
1109                 // Here we handle adaptor(range, args...) -- just forward all
1110                 // arguments to the underlying adaptor routine.
1111                 return _Callable{}(std::forward<_Args>(__args)...);
1112               }
1113             else
1114               {
1115                 // Here we handle adaptor(args...)(range).
1116                 // Given args..., we return a _RangeAdaptorClosure that takes a
1117                 // range argument, such that (2) is equivalent to (1).
1118                 //
1119                 // We need to be careful about how we capture args... in this
1120                 // closure.  By using __maybe_refwrap, we capture lvalue
1121                 // references by reference (through a reference_wrapper) and
1122                 // otherwise capture by value.
1123                 auto __closure
1124                   = [...__args(__maybe_refwrap(std::forward<_Args>(__args)))]
1125                     <typename _Range> (_Range&& __r) {
1126                       // This static_cast has two purposes: it forwards a
1127                       // reference_wrapper<T> capture as a T&, and otherwise
1128                       // forwards the captured argument as an rvalue.
1129                       return _Callable{}(std::forward<_Range>(__r),
1130                                (static_cast<unwrap_reference_t
1131                                             <remove_const_t<decltype(__args)>>>
1132                                 (__args))...);
1133                     };
1134                 using _ClosureType = decltype(__closure);
1135                 return _RangeAdaptorClosure<_ClosureType>(std::move(__closure));
1136               }
1137           }
1138       };
1139
1140     template<typename _Callable>
1141       _RangeAdaptor(_Callable) -> _RangeAdaptor<_Callable>;
1142
1143     template<typename _Callable>
1144       struct _RangeAdaptorClosure : public _RangeAdaptor<_Callable>
1145       {
1146         using _RangeAdaptor<_Callable>::_RangeAdaptor;
1147
1148         template<viewable_range _Range>
1149           requires requires { declval<_Callable>()(declval<_Range>()); }
1150           constexpr auto
1151           operator()(_Range&& __r) const
1152           {
1153             if constexpr (is_default_constructible_v<_Callable>)
1154               return _Callable{}(std::forward<_Range>(__r));
1155             else
1156               return this->_M_callable(std::forward<_Range>(__r));
1157           }
1158
1159         template<viewable_range _Range>
1160           requires requires { declval<_Callable>()(declval<_Range>()); }
1161           friend constexpr auto
1162           operator|(_Range&& __r, const _RangeAdaptorClosure& __o)
1163           { return __o(std::forward<_Range>(__r)); }
1164
1165         template<typename _Tp>
1166           friend constexpr auto
1167           operator|(const _RangeAdaptorClosure<_Tp>& __x,
1168                     const _RangeAdaptorClosure& __y)
1169           {
1170             if constexpr (is_default_constructible_v<_Tp>
1171                           && is_default_constructible_v<_Callable>)
1172               {
1173                 auto __closure = [] <typename _Up> (_Up&& __e) {
1174                   return std::forward<_Up>(__e) | decltype(__x){} | decltype(__y){};
1175                 };
1176                 return _RangeAdaptorClosure<decltype(__closure)>(__closure);
1177               }
1178             else if constexpr (is_default_constructible_v<_Tp>
1179                                && !is_default_constructible_v<_Callable>)
1180               {
1181                 auto __closure = [__y] <typename _Up> (_Up&& __e) {
1182                   return std::forward<_Up>(__e) | decltype(__x){} | __y;
1183                 };
1184                 return _RangeAdaptorClosure<decltype(__closure)>(__closure);
1185               }
1186             else if constexpr (!is_default_constructible_v<_Tp>
1187                                && is_default_constructible_v<_Callable>)
1188               {
1189                 auto __closure = [__x] <typename _Up> (_Up&& __e) {
1190                   return std::forward<_Up>(__e) | __x | decltype(__y){};
1191                 };
1192                 return _RangeAdaptorClosure<decltype(__closure)>(__closure);
1193               }
1194             else
1195               {
1196                 auto __closure = [__x, __y] <typename _Up> (_Up&& __e) {
1197                   return std::forward<_Up>(__e) | __x | __y;
1198                 };
1199                 return _RangeAdaptorClosure<decltype(__closure)>(__closure);
1200               }
1201           }
1202       };
1203
1204     template<typename _Callable>
1205       _RangeAdaptorClosure(_Callable) -> _RangeAdaptorClosure<_Callable>;
1206   } // namespace __adaptor
1207 } // namespace views
1208
1209   template<range _Range> requires is_object_v<_Range>
1210     class ref_view : public view_interface<ref_view<_Range>>
1211     {
1212     private:
1213       _Range* _M_r = nullptr;
1214
1215       static void _S_fun(_Range&); // not defined
1216       static void _S_fun(_Range&&) = delete;
1217
1218     public:
1219       constexpr
1220       ref_view() noexcept = default;
1221
1222       template<__detail::__not_same_as<ref_view> _Tp>
1223         requires convertible_to<_Tp, _Range&>
1224           && requires { _S_fun(declval<_Tp>()); }
1225         constexpr
1226         ref_view(_Tp&& __t)
1227           : _M_r(std::__addressof(static_cast<_Range&>(std::forward<_Tp>(__t))))
1228         { }
1229
1230       constexpr _Range&
1231       base() const
1232       { return *_M_r; }
1233
1234       constexpr iterator_t<_Range>
1235       begin() const
1236       { return ranges::begin(*_M_r); }
1237
1238       constexpr sentinel_t<_Range>
1239       end() const
1240       { return ranges::end(*_M_r); }
1241
1242       constexpr bool
1243       empty() const requires requires { ranges::empty(*_M_r); }
1244       { return ranges::empty(*_M_r); }
1245
1246       constexpr auto
1247       size() const requires sized_range<_Range>
1248       { return ranges::size(*_M_r); }
1249
1250       constexpr auto
1251       data() const requires contiguous_range<_Range>
1252       { return ranges::data(*_M_r); }
1253     };
1254
1255   template<typename _Range>
1256     ref_view(_Range&) -> ref_view<_Range>;
1257
1258   template<typename _Tp>
1259     inline constexpr bool enable_borrowed_range<ref_view<_Tp>> = true;
1260
1261   namespace views
1262   {
1263     inline constexpr __adaptor::_RangeAdaptorClosure all
1264       = [] <viewable_range _Range> (_Range&& __r)
1265       {
1266         if constexpr (view<decay_t<_Range>>)
1267           return std::forward<_Range>(__r);
1268         else if constexpr (requires { ref_view{std::forward<_Range>(__r)}; })
1269           return ref_view{std::forward<_Range>(__r)};
1270         else
1271           return subrange{std::forward<_Range>(__r)};
1272       };
1273
1274     template<viewable_range _Range>
1275       using all_t = decltype(all(std::declval<_Range>()));
1276
1277   } // namespace views
1278
1279   // XXX: the following algos are copied from ranges_algo.h to avoid a circular
1280   // dependency with that header.
1281   namespace __detail
1282   {
1283     template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1284              typename _Proj = identity,
1285              indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1286       constexpr _Iter
1287       find_if(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
1288       {
1289         while (__first != __last
1290             && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
1291           ++__first;
1292         return __first;
1293       }
1294
1295     template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1296              typename _Proj = identity,
1297              indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1298       constexpr _Iter
1299       find_if_not(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
1300       {
1301         while (__first != __last
1302             && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
1303           ++__first;
1304         return __first;
1305       }
1306
1307     template<typename _Tp, typename _Proj = identity,
1308              indirect_strict_weak_order<projected<const _Tp*, _Proj>>
1309                _Comp = ranges::less>
1310       constexpr const _Tp&
1311       min(const _Tp& __a, const _Tp& __b, _Comp __comp = {}, _Proj __proj = {})
1312       {
1313         if (std::__invoke(std::move(__comp),
1314                           std::__invoke(__proj, __b),
1315                           std::__invoke(__proj, __a)))
1316           return __b;
1317         else
1318           return __a;
1319       }
1320
1321     template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
1322              input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
1323              typename _Pred = ranges::equal_to,
1324              typename _Proj1 = identity, typename _Proj2 = identity>
1325       requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
1326       constexpr pair<_Iter1, _Iter2>
1327       mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
1328                _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
1329       {
1330         while (__first1 != __last1 && __first2 != __last2
1331                && (bool)std::__invoke(__pred,
1332                                       std::__invoke(__proj1, *__first1),
1333                                       std::__invoke(__proj2, *__first2)))
1334         {
1335           ++__first1;
1336           ++__first2;
1337         }
1338         return { std::move(__first1), std::move(__first2) };
1339       }
1340   } // namespace __detail
1341
1342   namespace __detail
1343   {
1344     template<range _Range>
1345       struct _CachedPosition
1346       {
1347         constexpr bool
1348         _M_has_value() const
1349         { return false; }
1350
1351         constexpr iterator_t<_Range>
1352         _M_get(const _Range&) const
1353         {
1354           __glibcxx_assert(false);
1355           return {};
1356         }
1357
1358         constexpr void
1359         _M_set(const _Range&, const iterator_t<_Range>&) const
1360         { }
1361       };
1362
1363     template<forward_range _Range>
1364       struct _CachedPosition<_Range>
1365       {
1366       private:
1367         iterator_t<_Range> _M_iter{};
1368
1369       public:
1370         constexpr bool
1371         _M_has_value() const
1372         { return _M_iter != iterator_t<_Range>{}; }
1373
1374         constexpr iterator_t<_Range>
1375         _M_get(const _Range&) const
1376         {
1377           __glibcxx_assert(_M_has_value());
1378           return _M_iter;
1379         }
1380
1381         constexpr void
1382         _M_set(const _Range&, const iterator_t<_Range>& __it)
1383         {
1384           __glibcxx_assert(!_M_has_value());
1385           _M_iter = __it;
1386         }
1387       };
1388
1389     template<random_access_range _Range>
1390       requires (sizeof(range_difference_t<_Range>)
1391                 <= sizeof(iterator_t<_Range>))
1392       struct _CachedPosition<_Range>
1393       {
1394       private:
1395         range_difference_t<_Range> _M_offset = -1;
1396
1397       public:
1398         constexpr bool
1399         _M_has_value() const
1400         { return _M_offset >= 0; }
1401
1402         constexpr iterator_t<_Range>
1403         _M_get(_Range& __r) const
1404         {
1405           __glibcxx_assert(_M_has_value());
1406           return ranges::begin(__r) + _M_offset;
1407         }
1408
1409         constexpr void
1410         _M_set(_Range& __r, const iterator_t<_Range>& __it)
1411         {
1412           __glibcxx_assert(!_M_has_value());
1413           _M_offset = __it - ranges::begin(__r);
1414         }
1415       };
1416
1417   } // namespace __detail
1418
1419   template<input_range _Vp,
1420            indirect_unary_predicate<iterator_t<_Vp>> _Pred>
1421     requires view<_Vp> && is_object_v<_Pred>
1422     class filter_view : public view_interface<filter_view<_Vp, _Pred>>
1423     {
1424     private:
1425       struct _Sentinel;
1426
1427       struct _Iterator
1428       {
1429       private:
1430         static constexpr auto
1431         _S_iter_concept()
1432         {
1433           if constexpr (bidirectional_range<_Vp>)
1434             return bidirectional_iterator_tag{};
1435           else if constexpr (forward_range<_Vp>)
1436             return forward_iterator_tag{};
1437           else
1438             return input_iterator_tag{};
1439         }
1440
1441         static constexpr auto
1442         _S_iter_cat()
1443         {
1444           using _Cat = typename iterator_traits<_Vp_iter>::iterator_category;
1445           if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
1446             return bidirectional_iterator_tag{};
1447           else if constexpr (derived_from<_Cat, forward_iterator_tag>)
1448             return forward_iterator_tag{};
1449           else
1450             return _Cat{};
1451         }
1452
1453         friend filter_view;
1454
1455         using _Vp_iter = iterator_t<_Vp>;
1456
1457         _Vp_iter _M_current = _Vp_iter();
1458         filter_view* _M_parent = nullptr;
1459
1460       public:
1461         using iterator_concept = decltype(_S_iter_concept());
1462         using iterator_category = decltype(_S_iter_cat());
1463         using value_type = range_value_t<_Vp>;
1464         using difference_type = range_difference_t<_Vp>;
1465
1466         _Iterator() = default;
1467
1468         constexpr
1469         _Iterator(filter_view& __parent, _Vp_iter __current)
1470           : _M_current(std::move(__current)),
1471             _M_parent(std::__addressof(__parent))
1472         { }
1473
1474         constexpr _Vp_iter
1475         base() const &
1476           requires copyable<_Vp_iter>
1477         { return _M_current; }
1478
1479         constexpr _Vp_iter
1480         base() &&
1481         { return std::move(_M_current); }
1482
1483         constexpr range_reference_t<_Vp>
1484         operator*() const
1485         { return *_M_current; }
1486
1487         constexpr _Vp_iter
1488         operator->() const
1489           requires __detail::__has_arrow<_Vp_iter>
1490             && copyable<_Vp_iter>
1491         { return _M_current; }
1492
1493         constexpr _Iterator&
1494         operator++()
1495         {
1496           _M_current = __detail::find_if(std::move(++_M_current),
1497                                          ranges::end(_M_parent->_M_base),
1498                                          std::ref(*_M_parent->_M_pred));
1499           return *this;
1500         }
1501
1502         constexpr void
1503         operator++(int)
1504         { ++*this; }
1505
1506         constexpr _Iterator
1507         operator++(int) requires forward_range<_Vp>
1508         {
1509           auto __tmp = *this;
1510           ++*this;
1511           return __tmp;
1512         }
1513
1514         constexpr _Iterator&
1515         operator--() requires bidirectional_range<_Vp>
1516         {
1517           do
1518             --_M_current;
1519           while (!std::__invoke(*_M_parent->_M_pred, *_M_current));
1520           return *this;
1521         }
1522
1523         constexpr _Iterator
1524         operator--(int) requires bidirectional_range<_Vp>
1525         {
1526           auto __tmp = *this;
1527           --*this;
1528           return __tmp;
1529         }
1530
1531         friend constexpr bool
1532         operator==(const _Iterator& __x, const _Iterator& __y)
1533           requires equality_comparable<_Vp_iter>
1534         { return __x._M_current == __y._M_current; }
1535
1536         friend constexpr range_rvalue_reference_t<_Vp>
1537         iter_move(const _Iterator& __i)
1538           noexcept(noexcept(ranges::iter_move(__i._M_current)))
1539         { return ranges::iter_move(__i._M_current); }
1540
1541         friend constexpr void
1542         iter_swap(const _Iterator& __x, const _Iterator& __y)
1543           noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1544           requires indirectly_swappable<_Vp_iter>
1545         { ranges::iter_swap(__x._M_current, __y._M_current); }
1546       };
1547
1548       struct _Sentinel
1549       {
1550       private:
1551         sentinel_t<_Vp> _M_end = sentinel_t<_Vp>();
1552
1553         constexpr bool
1554         __equal(const _Iterator& __i) const
1555         { return __i._M_current == _M_end; }
1556
1557       public:
1558         _Sentinel() = default;
1559
1560         constexpr explicit
1561         _Sentinel(filter_view& __parent)
1562           : _M_end(ranges::end(__parent._M_base))
1563         { }
1564
1565         constexpr sentinel_t<_Vp>
1566         base() const
1567         { return _M_end; }
1568
1569         friend constexpr bool
1570         operator==(const _Iterator& __x, const _Sentinel& __y)
1571         { return __y.__equal(__x); }
1572       };
1573
1574       _Vp _M_base = _Vp();
1575       __detail::__box<_Pred> _M_pred;
1576       [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
1577
1578     public:
1579       filter_view() = default;
1580
1581       constexpr
1582       filter_view(_Vp __base, _Pred __pred)
1583         : _M_base(std::move(__base)), _M_pred(std::move(__pred))
1584       { }
1585
1586       constexpr _Vp
1587       base() const& requires copy_constructible<_Vp>
1588       { return _M_base; }
1589
1590       constexpr _Vp
1591       base() &&
1592       { return std::move(_M_base); }
1593
1594       constexpr const _Pred&
1595       pred() const
1596       { return *_M_pred; }
1597
1598       constexpr _Iterator
1599       begin()
1600       {
1601         if (_M_cached_begin._M_has_value())
1602           return {*this, _M_cached_begin._M_get(_M_base)};
1603
1604         __glibcxx_assert(_M_pred.has_value());
1605         auto __it = __detail::find_if(ranges::begin(_M_base),
1606                                       ranges::end(_M_base),
1607                                       std::ref(*_M_pred));
1608         _M_cached_begin._M_set(_M_base, __it);
1609         return {*this, std::move(__it)};
1610       }
1611
1612       constexpr auto
1613       end()
1614       {
1615         if constexpr (common_range<_Vp>)
1616           return _Iterator{*this, ranges::end(_M_base)};
1617         else
1618           return _Sentinel{*this};
1619       }
1620     };
1621
1622   template<typename _Range, typename _Pred>
1623     filter_view(_Range&&, _Pred) -> filter_view<views::all_t<_Range>, _Pred>;
1624
1625   namespace views
1626   {
1627     inline constexpr __adaptor::_RangeAdaptor filter
1628       = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p)
1629       {
1630         return filter_view{std::forward<_Range>(__r), std::forward<_Pred>(__p)};
1631       };
1632   } // namespace views
1633
1634   template<input_range _Vp, copy_constructible _Fp>
1635     requires view<_Vp> && is_object_v<_Fp>
1636       && regular_invocable<_Fp&, range_reference_t<_Vp>>
1637       && std::__detail::__can_reference<invoke_result_t<_Fp&,
1638                                                         range_reference_t<_Vp>>>
1639     class transform_view : public view_interface<transform_view<_Vp, _Fp>>
1640     {
1641     private:
1642       template<bool _Const>
1643         struct _Sentinel;
1644
1645       template<bool _Const>
1646         struct _Iterator
1647         {
1648         private:
1649           using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1650           using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1651
1652           static constexpr auto
1653           _S_iter_concept()
1654           {
1655             if constexpr (random_access_range<_Vp>)
1656               return random_access_iterator_tag{};
1657             else if constexpr (bidirectional_range<_Vp>)
1658               return bidirectional_iterator_tag{};
1659             else if constexpr (forward_range<_Vp>)
1660               return forward_iterator_tag{};
1661             else
1662               return input_iterator_tag{};
1663           }
1664
1665           static constexpr auto
1666           _S_iter_cat()
1667           {
1668             using _Res = invoke_result_t<_Fp&, range_reference_t<_Base>>;
1669             if constexpr (is_lvalue_reference_v<_Res>)
1670               {
1671                 using _Cat
1672                   = typename iterator_traits<_Base_iter>::iterator_category;
1673                 if constexpr (derived_from<_Cat, contiguous_iterator_tag>)
1674                   return random_access_iterator_tag{};
1675                 else
1676                   return _Cat{};
1677               }
1678             else
1679               return input_iterator_tag{};
1680           }
1681
1682           static constexpr decltype(auto)
1683           __iter_move(const _Iterator& __i = {})
1684             noexcept(noexcept(std::__invoke(*__i._M_parent->_M_fun,
1685                                             *__i._M_current)))
1686           {
1687             if constexpr (is_lvalue_reference_v<decltype(*__i)>)
1688               return std::move(*__i);
1689             else
1690               return *__i;
1691           }
1692
1693           using _Base_iter = iterator_t<_Base>;
1694
1695           _Base_iter _M_current = _Base_iter();
1696           _Parent* _M_parent = nullptr;
1697
1698         public:
1699           using iterator_concept = decltype(_S_iter_concept());
1700           using iterator_category = decltype(_S_iter_cat());
1701           using value_type
1702             = remove_cvref_t<invoke_result_t<_Fp&, range_reference_t<_Base>>>;
1703           using difference_type = range_difference_t<_Base>;
1704
1705           _Iterator() = default;
1706
1707           constexpr
1708           _Iterator(_Parent& __parent, _Base_iter __current)
1709             : _M_current(std::move(__current)),
1710               _M_parent(std::__addressof(__parent))
1711           { }
1712
1713           constexpr
1714           _Iterator(_Iterator<!_Const> __i)
1715             requires _Const
1716               && convertible_to<iterator_t<_Vp>, _Base_iter>
1717             : _M_current(std::move(__i._M_current)), _M_parent(__i._M_parent)
1718           { }
1719
1720           constexpr _Base_iter
1721           base() const &
1722             requires copyable<_Base_iter>
1723           { return _M_current; }
1724
1725           constexpr _Base_iter
1726           base() &&
1727           { return std::move(_M_current); }
1728
1729           constexpr decltype(auto)
1730           operator*() const
1731           { return std::__invoke(*_M_parent->_M_fun, *_M_current); }
1732
1733           constexpr _Iterator&
1734           operator++()
1735           {
1736             ++_M_current;
1737             return *this;
1738           }
1739
1740           constexpr void
1741           operator++(int)
1742           { ++_M_current; }
1743
1744           constexpr _Iterator
1745           operator++(int) requires forward_range<_Base>
1746           {
1747             auto __tmp = *this;
1748             ++*this;
1749             return __tmp;
1750           }
1751
1752           constexpr _Iterator&
1753           operator--() requires bidirectional_range<_Base>
1754           {
1755             --_M_current;
1756             return *this;
1757           }
1758
1759           constexpr _Iterator
1760           operator--(int) requires bidirectional_range<_Base>
1761           {
1762             auto __tmp = *this;
1763             --*this;
1764             return __tmp;
1765           }
1766
1767           constexpr _Iterator&
1768           operator+=(difference_type __n) requires random_access_range<_Base>
1769           {
1770             _M_current += __n;
1771             return *this;
1772           }
1773
1774           constexpr _Iterator&
1775           operator-=(difference_type __n) requires random_access_range<_Base>
1776           {
1777             _M_current -= __n;
1778             return *this;
1779           }
1780
1781           constexpr decltype(auto)
1782           operator[](difference_type __n) const
1783             requires random_access_range<_Base>
1784           { return std::__invoke(*_M_parent->_M_fun, _M_current[__n]); }
1785
1786           friend constexpr bool
1787           operator==(const _Iterator& __x, const _Iterator& __y)
1788             requires equality_comparable<_Base_iter>
1789           { return __x._M_current == __y._M_current; }
1790
1791           friend constexpr bool
1792           operator<(const _Iterator& __x, const _Iterator& __y)
1793             requires random_access_range<_Base>
1794           { return __x._M_current < __y._M_current; }
1795
1796           friend constexpr bool
1797           operator>(const _Iterator& __x, const _Iterator& __y)
1798             requires random_access_range<_Base>
1799           { return __y < __x; }
1800
1801           friend constexpr bool
1802           operator<=(const _Iterator& __x, const _Iterator& __y)
1803             requires random_access_range<_Base>
1804           { return !(__y < __x); }
1805
1806           friend constexpr bool
1807           operator>=(const _Iterator& __x, const _Iterator& __y)
1808             requires random_access_range<_Base>
1809           { return !(__x < __y); }
1810
1811 #ifdef __cpp_lib_three_way_comparison
1812           friend constexpr auto
1813           operator<=>(const _Iterator& __x, const _Iterator& __y)
1814             requires random_access_range<_Base>
1815               && three_way_comparable<_Base_iter>
1816           { return __x._M_current <=> __y._M_current; }
1817 #endif
1818
1819           friend constexpr _Iterator
1820           operator+(_Iterator __i, difference_type __n)
1821             requires random_access_range<_Base>
1822           { return {*__i._M_parent, __i._M_current + __n}; }
1823
1824           friend constexpr _Iterator
1825           operator+(difference_type __n, _Iterator __i)
1826             requires random_access_range<_Base>
1827           { return {*__i._M_parent, __i._M_current + __n}; }
1828
1829           friend constexpr _Iterator
1830           operator-(_Iterator __i, difference_type __n)
1831             requires random_access_range<_Base>
1832           { return {*__i._M_parent, __i._M_current - __n}; }
1833
1834           friend constexpr difference_type
1835           operator-(const _Iterator& __x, const _Iterator& __y)
1836             requires random_access_range<_Base>
1837           { return __x._M_current - __y._M_current; }
1838
1839           friend constexpr decltype(auto)
1840           iter_move(const _Iterator& __i) noexcept(noexcept(__iter_move()))
1841           { return __iter_move(__i); }
1842
1843           friend constexpr void
1844           iter_swap(const _Iterator& __x, const _Iterator& __y)
1845             noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1846             requires indirectly_swappable<_Base_iter>
1847           { return ranges::iter_swap(__x._M_current, __y._M_current); }
1848
1849           friend _Iterator<!_Const>;
1850           friend _Sentinel<_Const>;
1851         };
1852
1853       template<bool _Const>
1854         struct _Sentinel
1855         {
1856         private:
1857           using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1858           using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1859
1860           constexpr range_difference_t<_Base>
1861           __distance_from(const _Iterator<_Const>& __i) const
1862           { return _M_end - __i._M_current; }
1863
1864           constexpr bool
1865           __equal(const _Iterator<_Const>& __i) const
1866           { return __i._M_current == _M_end; }
1867
1868           sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1869
1870         public:
1871           _Sentinel() = default;
1872
1873           constexpr explicit
1874           _Sentinel(sentinel_t<_Base> __end)
1875             : _M_end(__end)
1876           { }
1877
1878           constexpr
1879           _Sentinel(_Sentinel<!_Const> __i)
1880             requires _Const
1881               && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1882             : _M_end(std::move(__i._M_end))
1883           { }
1884
1885           constexpr sentinel_t<_Base>
1886           base() const
1887           { return _M_end; }
1888
1889           friend constexpr bool
1890           operator==(const _Iterator<_Const>& __x, const _Sentinel& __y)
1891           { return __y.__equal(__x); }
1892
1893           friend constexpr range_difference_t<_Base>
1894           operator-(const _Iterator<_Const>& __x, const _Sentinel& __y)
1895             requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
1896           { return -__y.__distance_from(__x); }
1897
1898           friend constexpr range_difference_t<_Base>
1899           operator-(const _Sentinel& __y, const _Iterator<_Const>& __x)
1900             requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
1901           { return __y.__distance_from(__x); }
1902
1903           friend _Sentinel<!_Const>;
1904         };
1905
1906       _Vp _M_base = _Vp();
1907       __detail::__box<_Fp> _M_fun;
1908
1909     public:
1910       transform_view() = default;
1911
1912       constexpr
1913       transform_view(_Vp __base, _Fp __fun)
1914         : _M_base(std::move(__base)), _M_fun(std::move(__fun))
1915       { }
1916
1917       constexpr _Vp
1918       base() const& requires copy_constructible<_Vp>
1919       { return _M_base ; }
1920
1921       constexpr _Vp
1922       base() &&
1923       { return std::move(_M_base); }
1924
1925       constexpr _Iterator<false>
1926       begin()
1927       { return _Iterator<false>{*this, ranges::begin(_M_base)}; }
1928
1929       constexpr _Iterator<true>
1930       begin() const
1931         requires range<const _Vp>
1932           && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1933       { return _Iterator<true>{*this, ranges::begin(_M_base)}; }
1934
1935       constexpr _Sentinel<false>
1936       end()
1937       { return _Sentinel<false>{ranges::end(_M_base)}; }
1938
1939       constexpr _Iterator<false>
1940       end() requires common_range<_Vp>
1941       { return _Iterator<false>{*this, ranges::end(_M_base)}; }
1942
1943       constexpr _Sentinel<true>
1944       end() const
1945         requires range<const _Vp>
1946           && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1947       { return _Sentinel<true>{ranges::end(_M_base)}; }
1948
1949       constexpr _Iterator<true>
1950       end() const
1951         requires common_range<const _Vp>
1952           && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1953       { return _Iterator<true>{*this, ranges::end(_M_base)}; }
1954
1955       constexpr auto
1956       size() requires sized_range<_Vp>
1957       { return ranges::size(_M_base); }
1958
1959       constexpr auto
1960       size() const requires sized_range<const _Vp>
1961       { return ranges::size(_M_base); }
1962     };
1963
1964   template<typename _Range, typename _Fp>
1965     transform_view(_Range&&, _Fp) -> transform_view<views::all_t<_Range>, _Fp>;
1966
1967   namespace views
1968   {
1969     inline constexpr __adaptor::_RangeAdaptor transform
1970       = [] <viewable_range _Range, typename _Fp> (_Range&& __r, _Fp&& __f)
1971       {
1972         return transform_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)};
1973       };
1974   } // namespace views
1975
1976   template<view _Vp>
1977     class take_view : public view_interface<take_view<_Vp>>
1978     {
1979     private:
1980       template<bool _Const>
1981         struct _Sentinel
1982         {
1983         private:
1984           using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1985           using _CI = counted_iterator<iterator_t<_Base>>;
1986
1987           sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1988
1989         public:
1990           _Sentinel() = default;
1991
1992           constexpr explicit
1993           _Sentinel(sentinel_t<_Base> __end)
1994             : _M_end(__end)
1995           { }
1996
1997           constexpr
1998           _Sentinel(_Sentinel<!_Const> __s)
1999             requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2000             : _M_end(std::move(__s._M_end))
2001           { }
2002
2003           constexpr sentinel_t<_Base>
2004           base() const
2005           { return _M_end; }
2006
2007           friend constexpr bool operator==(const _CI& __y, const _Sentinel& __x)
2008           { return __y.count() == 0 || __y.base() == __x._M_end; }
2009
2010           friend _Sentinel<!_Const>;
2011         };
2012
2013       _Vp _M_base = _Vp();
2014       range_difference_t<_Vp> _M_count = 0;
2015
2016     public:
2017       take_view() = default;
2018
2019       constexpr
2020       take_view(_Vp base, range_difference_t<_Vp> __count)
2021         : _M_base(std::move(base)), _M_count(std::move(__count))
2022       { }
2023
2024       constexpr _Vp
2025       base() const& requires copy_constructible<_Vp>
2026       { return _M_base; }
2027
2028       constexpr _Vp
2029       base() &&
2030       { return std::move(_M_base); }
2031
2032       constexpr auto
2033       begin() requires (!__detail::__simple_view<_Vp>)
2034       {
2035         if constexpr (sized_range<_Vp>)
2036           {
2037             if constexpr (random_access_range<_Vp>)
2038               return ranges::begin(_M_base);
2039             else
2040               return counted_iterator{ranges::begin(_M_base), size()};
2041           }
2042         else
2043           return counted_iterator{ranges::begin(_M_base), _M_count};
2044       }
2045
2046       constexpr auto
2047       begin() const requires range<const _Vp>
2048       {
2049         if constexpr (sized_range<const _Vp>)
2050           {
2051             if constexpr (random_access_range<const _Vp>)
2052               return ranges::begin(_M_base);
2053             else
2054               return counted_iterator{ranges::begin(_M_base), size()};
2055           }
2056         else
2057           return counted_iterator{ranges::begin(_M_base), _M_count};
2058       }
2059
2060       constexpr auto
2061       end() requires (!__detail::__simple_view<_Vp>)
2062       {
2063         if constexpr (sized_range<_Vp>)
2064           {
2065             if constexpr (random_access_range<_Vp>)
2066               return ranges::begin(_M_base) + size();
2067             else
2068               return default_sentinel;
2069           }
2070         else
2071           return _Sentinel<false>{ranges::end(_M_base)};
2072       }
2073
2074       constexpr auto
2075       end() const requires range<const _Vp>
2076       {
2077         if constexpr (sized_range<const _Vp>)
2078           {
2079             if constexpr (random_access_range<const _Vp>)
2080               return ranges::begin(_M_base) + size();
2081             else
2082               return default_sentinel;
2083           }
2084         else
2085           return _Sentinel<true>{ranges::end(_M_base)};
2086       }
2087
2088       constexpr auto
2089       size() requires sized_range<_Vp>
2090       {
2091         auto __n = ranges::size(_M_base);
2092         return __detail::min(__n, static_cast<decltype(__n)>(_M_count));
2093       }
2094
2095       constexpr auto
2096       size() const requires sized_range<const _Vp>
2097       {
2098         auto __n = ranges::size(_M_base);
2099         return __detail::min(__n, static_cast<decltype(__n)>(_M_count));
2100       }
2101     };
2102
2103   template<range _Range>
2104     take_view(_Range&&, range_difference_t<_Range>)
2105       -> take_view<views::all_t<_Range>>;
2106
2107   namespace views
2108   {
2109     inline constexpr __adaptor::_RangeAdaptor take
2110       = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n)
2111       {
2112         return take_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
2113       };
2114   } // namespace views
2115
2116   template<view _Vp, typename _Pred>
2117     requires input_range<_Vp> && is_object_v<_Pred>
2118       && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2119     class take_while_view : public view_interface<take_while_view<_Vp, _Pred>>
2120     {
2121       template<bool _Const>
2122         struct _Sentinel
2123         {
2124         private:
2125           using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2126
2127           sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2128           const _Pred* _M_pred = nullptr;
2129
2130         public:
2131           _Sentinel() = default;
2132
2133           constexpr explicit
2134           _Sentinel(sentinel_t<_Base> __end, const _Pred* __pred)
2135             : _M_end(__end), _M_pred(__pred)
2136           { }
2137
2138           constexpr
2139           _Sentinel(_Sentinel<!_Const> __s)
2140             requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2141             : _M_end(__s._M_end), _M_pred(__s._M_pred)
2142           { }
2143
2144           constexpr sentinel_t<_Base>
2145           base() const { return _M_end; }
2146
2147           friend constexpr bool
2148           operator==(const iterator_t<_Base>& __x, const _Sentinel& __y)
2149           { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
2150
2151           friend _Sentinel<!_Const>;
2152         };
2153
2154       _Vp _M_base = _Vp();
2155       __detail::__box<_Pred> _M_pred;
2156
2157     public:
2158       take_while_view() = default;
2159
2160       constexpr
2161       take_while_view(_Vp base, _Pred __pred)
2162         : _M_base(std::move(base)), _M_pred(std::move(__pred))
2163       {
2164       }
2165
2166       constexpr _Vp
2167       base() const& requires copy_constructible<_Vp>
2168       { return _M_base; }
2169
2170       constexpr _Vp
2171       base() &&
2172       { return std::move(_M_base); }
2173
2174       constexpr const _Pred&
2175       pred() const
2176       { return *_M_pred; }
2177
2178       constexpr auto
2179       begin() requires (!__detail::__simple_view<_Vp>)
2180       { return ranges::begin(_M_base); }
2181
2182       constexpr auto
2183       begin() const requires range<const _Vp>
2184       { return ranges::begin(_M_base); }
2185
2186       constexpr auto
2187       end() requires (!__detail::__simple_view<_Vp>)
2188       { return _Sentinel<false>(ranges::end(_M_base),
2189                                 std::__addressof(*_M_pred)); }
2190
2191       constexpr auto
2192       end() const requires range<const _Vp>
2193       { return _Sentinel<true>(ranges::end(_M_base),
2194                                std::__addressof(*_M_pred)); }
2195     };
2196
2197   template<typename _Range, typename _Pred>
2198     take_while_view(_Range&&, _Pred)
2199       -> take_while_view<views::all_t<_Range>, _Pred>;
2200
2201   namespace views
2202   {
2203     inline constexpr __adaptor::_RangeAdaptor take_while
2204       = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p)
2205       {
2206         return take_while_view{std::forward<_Range>(__r), std::forward<_Pred>(__p)};
2207       };
2208   } // namespace views
2209
2210   template<view _Vp>
2211     class drop_view : public view_interface<drop_view<_Vp>>
2212     {
2213     private:
2214       _Vp _M_base = _Vp();
2215       range_difference_t<_Vp> _M_count = 0;
2216
2217       static constexpr bool _S_needs_cached_begin = !random_access_range<_Vp>;
2218       [[no_unique_address]]
2219         __detail::__maybe_present_t<_S_needs_cached_begin,
2220                                     __detail::_CachedPosition<_Vp>>
2221                                       _M_cached_begin;
2222
2223     public:
2224       drop_view() = default;
2225
2226       constexpr
2227       drop_view(_Vp __base, range_difference_t<_Vp> __count)
2228         : _M_base(std::move(__base)), _M_count(__count)
2229       { __glibcxx_assert(__count >= 0); }
2230
2231       constexpr _Vp
2232       base() const& requires copy_constructible<_Vp>
2233       { return _M_base; }
2234
2235       constexpr _Vp
2236       base() &&
2237       { return std::move(_M_base); }
2238
2239       constexpr auto
2240       begin() requires (!(__detail::__simple_view<_Vp>
2241                           && random_access_range<_Vp>))
2242       {
2243         if constexpr (_S_needs_cached_begin)
2244           if (_M_cached_begin._M_has_value())
2245             return _M_cached_begin._M_get(_M_base);
2246
2247         auto __it = ranges::next(ranges::begin(_M_base),
2248                                  _M_count, ranges::end(_M_base));
2249         if constexpr (_S_needs_cached_begin)
2250           _M_cached_begin._M_set(_M_base, __it);
2251         return __it;
2252       }
2253
2254       constexpr auto
2255       begin() const requires random_access_range<const _Vp>
2256       {
2257         return ranges::next(ranges::begin(_M_base), _M_count,
2258                             ranges::end(_M_base));
2259       }
2260
2261       constexpr auto
2262       end() requires (!__detail::__simple_view<_Vp>)
2263       { return ranges::end(_M_base); }
2264
2265       constexpr auto
2266       end() const requires range<const _Vp>
2267       { return ranges::end(_M_base); }
2268
2269       constexpr auto
2270       size() requires sized_range<_Vp>
2271       {
2272         const auto __s = ranges::size(_M_base);
2273         const auto __c = static_cast<decltype(__s)>(_M_count);
2274         return __s < __c ? 0 : __s - __c;
2275       }
2276
2277       constexpr auto
2278       size() const requires sized_range<const _Vp>
2279       {
2280         const auto __s = ranges::size(_M_base);
2281         const auto __c = static_cast<decltype(__s)>(_M_count);
2282         return __s < __c ? 0 : __s - __c;
2283       }
2284     };
2285
2286   template<typename _Range>
2287     drop_view(_Range&&, range_difference_t<_Range>)
2288       -> drop_view<views::all_t<_Range>>;
2289
2290   namespace views
2291   {
2292     inline constexpr __adaptor::_RangeAdaptor drop
2293       = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n)
2294       {
2295         return drop_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
2296       };
2297   } // namespace views
2298
2299   template<view _Vp, typename _Pred>
2300     requires input_range<_Vp> && is_object_v<_Pred>
2301       && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2302     class drop_while_view : public view_interface<drop_while_view<_Vp, _Pred>>
2303     {
2304     private:
2305       _Vp _M_base = _Vp();
2306       __detail::__box<_Pred> _M_pred;
2307       [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
2308
2309     public:
2310       drop_while_view() = default;
2311
2312       constexpr
2313       drop_while_view(_Vp __base, _Pred __pred)
2314         : _M_base(std::move(__base)), _M_pred(std::move(__pred))
2315       { }
2316
2317       constexpr _Vp
2318       base() const& requires copy_constructible<_Vp>
2319       { return _M_base; }
2320
2321       constexpr _Vp
2322       base() &&
2323       { return std::move(_M_base); }
2324
2325       constexpr const _Pred&
2326       pred() const
2327       { return *_M_pred; }
2328
2329       constexpr auto
2330       begin()
2331       {
2332         if (_M_cached_begin._M_has_value())
2333           return _M_cached_begin._M_get(_M_base);
2334
2335         auto __it = __detail::find_if_not(ranges::begin(_M_base),
2336                                           ranges::end(_M_base),
2337                                           std::cref(*_M_pred));
2338         _M_cached_begin._M_set(_M_base, __it);
2339         return __it;
2340       }
2341
2342       constexpr auto
2343       end()
2344       { return ranges::end(_M_base); }
2345     };
2346
2347   template<typename _Range, typename _Pred>
2348     drop_while_view(_Range&&, _Pred)
2349       -> drop_while_view<views::all_t<_Range>, _Pred>;
2350
2351   namespace views
2352   {
2353     inline constexpr __adaptor::_RangeAdaptor drop_while
2354       = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p)
2355       {
2356         return drop_while_view{std::forward<_Range>(__r),
2357                                std::forward<_Pred>(__p)};
2358       };
2359   } // namespace views
2360
2361   template<input_range _Vp>
2362     requires view<_Vp> && input_range<range_reference_t<_Vp>>
2363       && (is_reference_v<range_reference_t<_Vp>>
2364           || view<range_value_t<_Vp>>)
2365     class join_view : public view_interface<join_view<_Vp>>
2366     {
2367     private:
2368       using _InnerRange = range_reference_t<_Vp>;
2369
2370       template<bool _Const>
2371         struct _Sentinel;
2372
2373       template<bool _Const>
2374         struct _Iterator
2375         {
2376         private:
2377           using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2378           using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2379
2380           static constexpr bool _S_ref_is_glvalue
2381             = is_reference_v<range_reference_t<_Base>>;
2382
2383           constexpr void
2384           _M_satisfy()
2385           {
2386             auto __update_inner = [this] (range_reference_t<_Base> __x) -> auto&
2387             {
2388               if constexpr (_S_ref_is_glvalue)
2389                 return __x;
2390               else
2391                 return (_M_parent->_M_inner = views::all(std::move(__x)));
2392             };
2393
2394             for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer)
2395               {
2396                 auto& inner = __update_inner(*_M_outer);
2397                 _M_inner = ranges::begin(inner);
2398                 if (_M_inner != ranges::end(inner))
2399                   return;
2400               }
2401
2402             if constexpr (_S_ref_is_glvalue)
2403               _M_inner = _Inner_iter();
2404           }
2405
2406           static constexpr auto
2407           _S_iter_concept()
2408           {
2409             if constexpr (_S_ref_is_glvalue
2410                           && bidirectional_range<_Base>
2411                           && bidirectional_range<range_reference_t<_Base>>)
2412               return bidirectional_iterator_tag{};
2413             else if constexpr (_S_ref_is_glvalue
2414                                && forward_range<_Base>
2415                                && forward_range<range_reference_t<_Base>>)
2416               return forward_iterator_tag{};
2417             else
2418               return input_iterator_tag{};
2419           }
2420
2421           static constexpr auto
2422           _S_iter_cat()
2423           {
2424             using _OuterCat
2425               = typename iterator_traits<_Outer_iter>::iterator_category;
2426             using _InnerCat
2427               = typename iterator_traits<_Inner_iter>::iterator_category;
2428             if constexpr (_S_ref_is_glvalue
2429                           && derived_from<_OuterCat, bidirectional_iterator_tag>
2430                           && derived_from<_InnerCat, bidirectional_iterator_tag>)
2431               return bidirectional_iterator_tag{};
2432             else if constexpr (_S_ref_is_glvalue
2433                                && derived_from<_OuterCat, forward_iterator_tag>
2434                                && derived_from<_InnerCat, forward_iterator_tag>)
2435               return forward_iterator_tag{};
2436             else if constexpr (derived_from<_OuterCat, input_iterator_tag>
2437                                && derived_from<_InnerCat, input_iterator_tag>)
2438               return input_iterator_tag{};
2439             else
2440               return output_iterator_tag{};
2441           }
2442
2443           using _Outer_iter = iterator_t<_Base>;
2444           using _Inner_iter = iterator_t<range_reference_t<_Base>>;
2445
2446           _Outer_iter _M_outer = _Outer_iter();
2447           _Inner_iter _M_inner = _Inner_iter();
2448           _Parent* _M_parent = nullptr;
2449
2450         public:
2451           using iterator_concept = decltype(_S_iter_concept());
2452           using iterator_category = decltype(_S_iter_cat());
2453           using value_type = range_value_t<range_reference_t<_Base>>;
2454           using difference_type
2455             = common_type_t<range_difference_t<_Base>,
2456                             range_difference_t<range_reference_t<_Base>>>;
2457
2458           _Iterator() = default;
2459
2460           constexpr
2461           _Iterator(_Parent& __parent, _Outer_iter __outer)
2462             : _M_outer(std::move(__outer)),
2463               _M_parent(std::__addressof(__parent))
2464           { _M_satisfy(); }
2465
2466           constexpr
2467           _Iterator(_Iterator<!_Const> __i)
2468             requires _Const
2469               && convertible_to<iterator_t<_Vp>, _Outer_iter>
2470               && convertible_to<iterator_t<_InnerRange>, _Inner_iter>
2471             : _M_outer(std::move(__i._M_outer)), _M_inner(__i._M_inner),
2472               _M_parent(__i._M_parent)
2473           { }
2474
2475           constexpr decltype(auto)
2476           operator*() const
2477           { return *_M_inner; }
2478
2479           constexpr _Outer_iter
2480           operator->() const
2481             requires __detail::__has_arrow<_Outer_iter>
2482               && copyable<_Outer_iter>
2483           { return _M_inner; }
2484
2485           constexpr _Iterator&
2486           operator++()
2487           {
2488             auto&& __inner_range = [this] () -> decltype(auto) {
2489               if constexpr (_S_ref_is_glvalue)
2490                 return *_M_outer;
2491               else
2492                 return _M_parent->_M_inner;
2493             }();
2494             if (++_M_inner == ranges::end(__inner_range))
2495               {
2496                 ++_M_outer;
2497                 _M_satisfy();
2498               }
2499             return *this;
2500           }
2501
2502           constexpr void
2503           operator++(int)
2504           { ++*this; }
2505
2506           constexpr _Iterator
2507           operator++(int)
2508             requires _S_ref_is_glvalue && forward_range<_Base>
2509               && forward_range<range_reference_t<_Base>>
2510           {
2511             auto __tmp = *this;
2512             ++*this;
2513             return __tmp;
2514           }
2515
2516           constexpr _Iterator&
2517           operator--()
2518             requires _S_ref_is_glvalue && bidirectional_range<_Base>
2519               && bidirectional_range<range_reference_t<_Base>>
2520               && common_range<range_reference_t<_Base>>
2521           {
2522             if (_M_outer == ranges::end(_M_parent->_M_base))
2523               _M_inner = ranges::end(*--_M_outer);
2524             while (_M_inner == ranges::begin(*_M_outer))
2525               _M_inner = ranges::end(*--_M_outer);
2526             --_M_inner;
2527             return *this;
2528           }
2529
2530           constexpr _Iterator
2531           operator--(int)
2532             requires _S_ref_is_glvalue && bidirectional_range<_Base>
2533               && bidirectional_range<range_reference_t<_Base>>
2534               && common_range<range_reference_t<_Base>>
2535           {
2536             auto __tmp = *this;
2537             --*this;
2538             return __tmp;
2539           }
2540
2541           friend constexpr bool
2542           operator==(const _Iterator& __x, const _Iterator& __y)
2543             requires _S_ref_is_glvalue
2544               && equality_comparable<_Outer_iter>
2545               && equality_comparable<_Inner_iter>
2546           {
2547             return (__x._M_outer == __y._M_outer
2548                     && __x._M_inner == __y._M_inner);
2549           }
2550
2551           friend constexpr decltype(auto)
2552           iter_move(const _Iterator& __i)
2553           noexcept(noexcept(ranges::iter_move(__i._M_inner)))
2554           { return ranges::iter_move(__i._M_inner); }
2555
2556           friend constexpr void
2557           iter_swap(const _Iterator& __x, const _Iterator& __y)
2558             noexcept(noexcept(ranges::iter_swap(__x._M_inner, __y._M_inner)))
2559           { return ranges::iter_swap(__x._M_inner, __y._M_inner); }
2560
2561           friend _Iterator<!_Const>;
2562           friend _Sentinel<_Const>;
2563         };
2564
2565       template<bool _Const>
2566         struct _Sentinel
2567         {
2568         private:
2569           using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2570           using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2571
2572           constexpr bool
2573           __equal(const _Iterator<_Const>& __i) const
2574           { return __i._M_outer == _M_end; }
2575
2576           sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2577
2578         public:
2579           _Sentinel() = default;
2580
2581           constexpr explicit
2582           _Sentinel(_Parent& __parent)
2583             : _M_end(ranges::end(__parent._M_base))
2584           { }
2585
2586           constexpr
2587           _Sentinel(_Sentinel<!_Const> __s)
2588             requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2589             : _M_end(std::move(__s._M_end))
2590           { }
2591
2592           friend constexpr bool
2593           operator==(const _Iterator<_Const>& __x, const _Sentinel& __y)
2594           { return __y.__equal(__x); }
2595
2596           friend _Sentinel<!_Const>;
2597         };
2598
2599       _Vp _M_base = _Vp();
2600
2601       // XXX: _M_inner is "present only when !is_reference_v<_InnerRange>"
2602       [[no_unique_address]]
2603         __detail::__maybe_present_t<!is_reference_v<_InnerRange>,
2604                                     views::all_t<_InnerRange>> _M_inner;
2605
2606     public:
2607       join_view() = default;
2608
2609       constexpr explicit
2610       join_view(_Vp __base)
2611         : _M_base(std::move(__base))
2612       { }
2613
2614       constexpr _Vp
2615       base() const& requires copy_constructible<_Vp>
2616       { return _M_base; }
2617
2618       constexpr _Vp
2619       base() &&
2620       { return std::move(_M_base); }
2621
2622       constexpr auto
2623       begin()
2624       {
2625         constexpr bool __use_const
2626           = (__detail::__simple_view<_Vp>
2627              && is_reference_v<range_reference_t<_Vp>>);
2628         return _Iterator<__use_const>{*this, ranges::begin(_M_base)};
2629       }
2630
2631       constexpr auto
2632       begin() const
2633         requires input_range<const _Vp>
2634           && is_reference_v<range_reference_t<const _Vp>>
2635       {
2636         return _Iterator<true>{*this, ranges::begin(_M_base)};
2637       }
2638
2639       constexpr auto
2640       end()
2641       {
2642         if constexpr (forward_range<_Vp> && is_reference_v<_InnerRange>
2643                       && forward_range<_InnerRange>
2644                       && common_range<_Vp> && common_range<_InnerRange>)
2645           return _Iterator<__detail::__simple_view<_Vp>>{*this,
2646                                                          ranges::end(_M_base)};
2647         else
2648           return _Sentinel<__detail::__simple_view<_Vp>>{*this};
2649       }
2650
2651       constexpr auto
2652       end() const
2653         requires input_range<const _Vp>
2654           && is_reference_v<range_reference_t<const _Vp>>
2655       {
2656         if constexpr (forward_range<const _Vp>
2657                       && is_reference_v<range_reference_t<const _Vp>>
2658                       && forward_range<range_reference_t<const _Vp>>
2659                       && common_range<const _Vp>
2660                       && common_range<range_reference_t<const _Vp>>)
2661           return _Iterator<true>{*this, ranges::end(_M_base)};
2662         else
2663           return _Sentinel<true>{*this};
2664       }
2665     };
2666
2667   template<typename _Range>
2668     explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;
2669
2670   namespace views
2671   {
2672     inline constexpr __adaptor::_RangeAdaptorClosure join
2673       = [] <viewable_range _Range> (_Range&& __r)
2674       {
2675         return join_view{std::forward<_Range>(__r)};
2676       };
2677   } // namespace views
2678
2679   namespace __detail
2680   {
2681     template<auto>
2682       struct __require_constant;
2683
2684     template<typename _Range>
2685       concept __tiny_range = sized_range<_Range>
2686         && requires
2687            { typename __require_constant<remove_reference_t<_Range>::size()>; }
2688         && (remove_reference_t<_Range>::size() <= 1);
2689   }
2690
2691   template<input_range _Vp, forward_range _Pattern>
2692     requires view<_Vp> && view<_Pattern>
2693       && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
2694                                ranges::equal_to>
2695       && (forward_range<_Vp> || __detail::__tiny_range<_Pattern>)
2696     class split_view : public view_interface<split_view<_Vp, _Pattern>>
2697     {
2698     private:
2699       template<bool _Const>
2700         struct _InnerIter;
2701
2702       template<bool _Const>
2703         struct _OuterIter
2704         {
2705         private:
2706           using _Parent = __detail::__maybe_const_t<_Const, split_view>;
2707           using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2708
2709           constexpr bool
2710           __at_end() const
2711           { return _M_current == ranges::end(_M_parent->_M_base); }
2712
2713           // XXX: [24.7.11.3.1]
2714           //  Many of the following specifications refer to the notional member
2715           //  current of outer-iterator.  current is equivalent to current_ if
2716           //  V models forward_range, and parent_->current_ otherwise.
2717           constexpr auto&
2718           __current()
2719           {
2720             if constexpr (forward_range<_Vp>)
2721               return _M_current;
2722             else
2723               return _M_parent->_M_current;
2724           }
2725
2726           constexpr auto&
2727           __current() const
2728           {
2729             if constexpr (forward_range<_Vp>)
2730               return _M_current;
2731             else
2732               return _M_parent->_M_current;
2733           }
2734
2735           _Parent* _M_parent = nullptr;
2736
2737           // XXX: _M_current is present only if "V models forward_range"
2738           [[no_unique_address]]
2739             __detail::__maybe_present_t<forward_range<_Vp>,
2740                                         iterator_t<_Base>> _M_current;
2741
2742         public:
2743           using iterator_concept = conditional_t<forward_range<_Base>,
2744                                                  forward_iterator_tag,
2745                                                  input_iterator_tag>;
2746           using iterator_category = input_iterator_tag;
2747           using difference_type = range_difference_t<_Base>;
2748
2749           struct value_type : view_interface<value_type>
2750           {
2751           private:
2752             _OuterIter _M_i = _OuterIter();
2753
2754           public:
2755             value_type() = default;
2756
2757             constexpr explicit
2758             value_type(_OuterIter __i)
2759               : _M_i(std::move(__i))
2760             { }
2761
2762             constexpr _InnerIter<_Const>
2763             begin() const
2764               requires copyable<_OuterIter>
2765             { return _InnerIter<_Const>{_M_i}; }
2766
2767             constexpr _InnerIter<_Const>
2768             begin()
2769               requires (!copyable<_OuterIter>)
2770             { return _InnerIter<_Const>{std::move(_M_i)}; }
2771
2772             constexpr default_sentinel_t
2773             end() const
2774             { return default_sentinel; }
2775           };
2776
2777           _OuterIter() = default;
2778
2779           constexpr explicit
2780           _OuterIter(_Parent& __parent) requires (!forward_range<_Base>)
2781             : _M_parent(address(__parent))
2782           { }
2783
2784           constexpr
2785           _OuterIter(_Parent& __parent, iterator_t<_Base> __current)
2786             requires forward_range<_Base>
2787             : _M_parent(std::__addressof(__parent)),
2788               _M_current(std::move(__current))
2789           { }
2790
2791           constexpr
2792           _OuterIter(_OuterIter<!_Const> __i)
2793             requires _Const
2794               && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
2795             : _M_parent(__i._M_parent), _M_current(std::move(__i._M_current))
2796           { }
2797
2798           constexpr value_type
2799           operator*() const
2800           { return value_type{*this}; }
2801
2802           constexpr _OuterIter&
2803           operator++()
2804           {
2805             const auto __end = ranges::end(_M_parent->_M_base);
2806             if (_M_current == __end)
2807               return *this;
2808             const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern};
2809             if (__pbegin == __pend)
2810               ++_M_current;
2811             else
2812               do
2813                 {
2814                   auto [__b, __p]
2815                     = __detail::mismatch(std::move(_M_current), __end,
2816                                          __pbegin, __pend);
2817                   _M_current = std::move(__b);
2818                   if (__p == __pend)
2819                     break;
2820                 } while (++_M_current != __end);
2821             return *this;
2822           }
2823
2824           constexpr decltype(auto)
2825           operator++(int)
2826           {
2827             if constexpr (forward_range<_Base>)
2828               {
2829                 auto __tmp = *this;
2830                 ++*this;
2831                 return __tmp;
2832               }
2833             else
2834               ++*this;
2835           }
2836
2837           friend constexpr bool
2838           operator==(const _OuterIter& __x, const _OuterIter& __y)
2839             requires forward_range<_Base>
2840           { return __x._M_current == __y._M_current; }
2841
2842           friend constexpr bool
2843           operator==(const _OuterIter& __x, default_sentinel_t)
2844           { return __x.__at_end(); };
2845
2846           friend _OuterIter<!_Const>;
2847           friend _InnerIter<_Const>;
2848         };
2849
2850       template<bool _Const>
2851         struct _InnerIter
2852         {
2853         private:
2854           using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2855
2856           constexpr bool
2857           __at_end() const
2858           {
2859             auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern};
2860             auto __end = ranges::end(_M_i._M_parent->_M_base);
2861             if constexpr (__detail::__tiny_range<_Pattern>)
2862               {
2863                 const auto& __cur = _M_i.__current();
2864                 if (__cur == __end)
2865                   return true;
2866                 if (__pcur == __pend)
2867                   return _M_incremented;
2868                 return *__cur == *__pcur;
2869               }
2870             else
2871               {
2872                 auto __cur = _M_i.__current();
2873                 if (__cur == __end)
2874                   return true;
2875                 if (__pcur == __pend)
2876                   return _M_incremented;
2877                 do
2878                   {
2879                     if (*__cur != *__pcur)
2880                       return false;
2881                     if (++__pcur == __pend)
2882                       return true;
2883                   } while (++__cur != __end);
2884                 return false;
2885               }
2886           }
2887
2888           static constexpr auto
2889           _S_iter_cat()
2890           {
2891             using _Cat
2892               = typename iterator_traits<iterator_t<_Base>>::iterator_category;
2893             if constexpr (derived_from<_Cat, forward_iterator_tag>)
2894               return forward_iterator_tag{};
2895             else
2896               return _Cat{};
2897           }
2898
2899           static constexpr decltype(auto)
2900           __iter_move(const _InnerIter& __i = {})
2901           noexcept(noexcept(ranges::iter_move(__i._M_i.__current())))
2902           { return ranges::iter_move(__i._M_i.__current()); }
2903
2904           static constexpr void
2905           __iter_swap(const _InnerIter& __x = {}, const _InnerIter& __y = {})
2906             noexcept(noexcept(ranges::iter_swap(__x._M_i.__current(),
2907                                                 __y._M_i.__current())))
2908           { ranges::iter_swap(__x._M_i.__current(), __y._M_i.__current()); }
2909
2910           _OuterIter<_Const> _M_i = _OuterIter<_Const>();
2911           bool _M_incremented = false;
2912
2913         public:
2914           using iterator_concept
2915             = typename _OuterIter<_Const>::iterator_concept;
2916           using iterator_category = decltype(_S_iter_cat());
2917           using value_type = range_value_t<_Base>;
2918           using difference_type = range_difference_t<_Base>;
2919
2920           _InnerIter() = default;
2921
2922           constexpr explicit
2923           _InnerIter(_OuterIter<_Const> __i)
2924             : _M_i(std::move(__i))
2925           { }
2926
2927           constexpr decltype(auto)
2928           operator*() const
2929           { return *_M_i._M_current; }
2930
2931           constexpr _InnerIter&
2932           operator++()
2933           {
2934             _M_incremented = true;
2935             if constexpr (!forward_range<_Base>)
2936               if constexpr (_Pattern::size() == 0)
2937                 return *this;
2938             ++_M_i.__current();
2939             return *this;
2940           }
2941
2942           constexpr decltype(auto)
2943           operator++(int)
2944           {
2945             if constexpr (forward_range<_Vp>)
2946               {
2947                 auto __tmp = *this;
2948                 ++*this;
2949                 return __tmp;
2950               }
2951             else
2952               ++*this;
2953           }
2954
2955           friend constexpr bool
2956           operator==(const _InnerIter& __x, const _InnerIter& __y)
2957             requires forward_range<_Base>
2958           { return __x._M_i == __y._M_i; }
2959
2960           friend constexpr bool
2961           operator==(const _InnerIter& __x, default_sentinel_t)
2962           { return __x.__at_end(); }
2963
2964           friend constexpr decltype(auto)
2965           iter_move(const _InnerIter& __i) noexcept(noexcept(__iter_move()))
2966           { return __iter_move(__i); }
2967
2968           friend constexpr void
2969           iter_swap(const _InnerIter& __x, const _InnerIter& __y)
2970             noexcept(noexcept(__iter_swap()))
2971             requires indirectly_swappable<iterator_t<_Base>>
2972           { __iter_swap(__x, __y); }
2973         };
2974
2975       _Vp _M_base = _Vp();
2976       _Pattern _M_pattern = _Pattern();
2977
2978       // XXX: _M_current is "present only if !forward_range<V>"
2979       [[no_unique_address]]
2980         __detail::__maybe_present_t<!forward_range<_Vp>, iterator_t<_Vp>>
2981           _M_current;
2982
2983
2984     public:
2985       split_view() = default;
2986
2987       constexpr
2988       split_view(_Vp __base, _Pattern __pattern)
2989         : _M_base(std::move(__base)), _M_pattern(std::move(__pattern))
2990       { }
2991
2992       template<input_range _Range>
2993         requires constructible_from<_Vp, views::all_t<_Range>>
2994           && constructible_from<_Pattern, single_view<range_value_t<_Range>>>
2995         constexpr
2996         split_view(_Range&& __r, range_value_t<_Range> __e)
2997           : _M_base(views::all(std::forward<_Range>(__r))),
2998             _M_pattern(std::move(__e))
2999         { }
3000
3001       constexpr _Vp
3002       base() const& requires copy_constructible<_Vp>
3003       { return _M_base; }
3004
3005       constexpr _Vp
3006       base() &&
3007       { return std::move(_M_base); }
3008
3009       constexpr auto
3010       begin()
3011       {
3012         if constexpr (forward_range<_Vp>)
3013           return _OuterIter<__detail::__simple_view<_Vp>>{*this,
3014                                                         ranges::begin(_M_base)};
3015         else
3016           {
3017             _M_current = ranges::begin(_M_base);
3018             return _OuterIter<false>{*this};
3019           }
3020       }
3021
3022       constexpr auto
3023       begin() const requires forward_range<_Vp> && forward_range<const _Vp>
3024       {
3025         return _OuterIter<true>{*this, ranges::begin(_M_base)};
3026       }
3027
3028       constexpr auto
3029       end() requires forward_range<_Vp> && common_range<_Vp>
3030       {
3031         return _OuterIter<__detail::__simple_view<_Vp>>{*this, ranges::end(_M_base)};
3032       }
3033
3034       constexpr auto
3035       end() const
3036       {
3037         if constexpr (forward_range<_Vp>
3038                       && forward_range<const _Vp>
3039                       && common_range<const _Vp>)
3040           return _OuterIter<true>{*this, ranges::end(_M_base)};
3041         else
3042           return default_sentinel;
3043       }
3044     };
3045
3046   template<typename _Range, typename _Pred>
3047     split_view(_Range&&, _Pred&&)
3048       -> split_view<views::all_t<_Range>, views::all_t<_Pred>>;
3049
3050   template<input_range _Range>
3051     split_view(_Range&&, range_value_t<_Range>)
3052       -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
3053
3054   namespace views
3055   {
3056     inline constexpr __adaptor::_RangeAdaptor split
3057       = [] <viewable_range _Range, typename _Fp> (_Range&& __r, _Fp&& __f)
3058       {
3059         return split_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)};
3060       };
3061   } // namespace views
3062
3063   namespace views
3064   {
3065     struct _Counted
3066     {
3067       template<input_or_output_iterator _Iter>
3068       constexpr auto
3069       operator()(_Iter __i, iter_difference_t<_Iter> __n) const
3070       {
3071         if constexpr (random_access_iterator<_Iter>)
3072           return subrange{__i, __i + __n};
3073         else
3074           return subrange{counted_iterator{std::move(__i), __n},
3075                           default_sentinel};
3076       }
3077     };
3078
3079     inline constexpr _Counted counted{};
3080   } // namespace views
3081
3082   template<view _Vp>
3083     requires (!common_range<_Vp>) && copyable<iterator_t<_Vp>>
3084     class common_view : public view_interface<common_view<_Vp>>
3085     {
3086     private:
3087       _Vp _M_base = _Vp();
3088
3089     public:
3090       common_view() = default;
3091
3092       constexpr explicit
3093       common_view(_Vp __r)
3094         : _M_base(std::move(__r))
3095       { }
3096
3097       /* XXX: LWG 3280 didn't remove this constructor, but I think it should?
3098       template<viewable_range _Range>
3099         requires (!common_range<_Range>)
3100           && constructible_from<_Vp, views::all_t<_Range>>
3101         constexpr explicit
3102         common_view(_Range&& __r)
3103           : _M_base(views::all(std::forward<_Range>(__r)))
3104         { }
3105       */
3106
3107       constexpr _Vp
3108       base() const& requires copy_constructible<_Vp>
3109       { return _M_base; }
3110
3111       constexpr _Vp
3112       base() &&
3113       { return std::move(_M_base); }
3114
3115       constexpr auto
3116       begin()
3117       {
3118         if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3119           return ranges::begin(_M_base);
3120         else
3121           return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3122                   (ranges::begin(_M_base));
3123       }
3124
3125       constexpr auto
3126       begin() const requires range<const _Vp>
3127       {
3128         if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3129           return ranges::begin(_M_base);
3130         else
3131           return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3132                   (ranges::begin(_M_base));
3133       }
3134
3135       constexpr auto
3136       end()
3137       {
3138         if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3139           return ranges::begin(_M_base) + ranges::size(_M_base);
3140         else
3141           return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3142                   (ranges::end(_M_base));
3143       }
3144
3145       constexpr auto
3146       end() const requires range<const _Vp>
3147       {
3148         if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3149           return ranges::begin(_M_base) + ranges::size(_M_base);
3150         else
3151           return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3152                   (ranges::end(_M_base));
3153       }
3154
3155       constexpr auto
3156       size() requires sized_range<_Vp>
3157       { return ranges::size(_M_base); }
3158
3159       constexpr auto
3160       size() const requires sized_range<const _Vp>
3161       { return ranges::size(_M_base); }
3162     };
3163
3164   template<typename _Range>
3165     common_view(_Range&&) -> common_view<views::all_t<_Range>>;
3166
3167   namespace views
3168   {
3169     inline constexpr __adaptor::_RangeAdaptorClosure common
3170       = [] <viewable_range _Range> (_Range&& __r)
3171       {
3172         if constexpr (common_range<_Range>
3173                       && requires { views::all(std::forward<_Range>(__r)); })
3174           return views::all(std::forward<_Range>(__r));
3175         else
3176           return common_view{std::forward<_Range>(__r)};
3177       };
3178
3179   } // namespace views
3180
3181   template<view _Vp>
3182     requires bidirectional_range<_Vp>
3183     class reverse_view : public view_interface<reverse_view<_Vp>>
3184     {
3185     private:
3186       _Vp _M_base = _Vp();
3187
3188       static constexpr bool _S_needs_cached_begin
3189         = !common_range<_Vp> && !random_access_range<_Vp>;
3190       [[no_unique_address]]
3191         __detail::__maybe_present_t<_S_needs_cached_begin,
3192                                     __detail::_CachedPosition<_Vp>>
3193                                       _M_cached_begin;
3194
3195     public:
3196       reverse_view() = default;
3197
3198       constexpr explicit
3199       reverse_view(_Vp __r)
3200         : _M_base(std::move(__r))
3201         { }
3202
3203       constexpr _Vp
3204       base() const& requires copy_constructible<_Vp>
3205       { return _M_base; }
3206
3207       constexpr _Vp
3208       base() &&
3209       { return std::move(_M_base); }
3210
3211       constexpr reverse_iterator<iterator_t<_Vp>>
3212       begin()
3213       {
3214         if constexpr (_S_needs_cached_begin)
3215           if (_M_cached_begin._M_has_value())
3216             return make_reverse_iterator(_M_cached_begin._M_get(_M_base));
3217
3218         auto __it = ranges::next(ranges::begin(_M_base), ranges::end(_M_base));
3219         if constexpr (_S_needs_cached_begin)
3220           _M_cached_begin._M_set(_M_base, __it);
3221         return make_reverse_iterator(std::move(__it));
3222       }
3223
3224       constexpr auto
3225       begin() requires common_range<_Vp>
3226       { return make_reverse_iterator(ranges::end(_M_base)); }
3227
3228       constexpr auto
3229       begin() const requires common_range<const _Vp>
3230       { return make_reverse_iterator(ranges::end(_M_base)); }
3231
3232       constexpr reverse_iterator<iterator_t<_Vp>>
3233       end()
3234       { return make_reverse_iterator(ranges::begin(_M_base)); }
3235
3236       constexpr auto
3237       end() const requires common_range<const _Vp>
3238       { return make_reverse_iterator(ranges::begin(_M_base)); }
3239
3240       constexpr auto
3241       size() requires sized_range<_Vp>
3242       { return ranges::size(_M_base); }
3243
3244       constexpr auto
3245       size() const requires sized_range<const _Vp>
3246       { return ranges::size(_M_base); }
3247     };
3248
3249   template<typename _Range>
3250     reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>;
3251
3252   namespace views
3253   {
3254     namespace __detail
3255     {
3256       template<typename>
3257         inline constexpr bool __is_reversible_subrange = false;
3258
3259       template<typename _Iter, subrange_kind _Kind>
3260         inline constexpr bool
3261           __is_reversible_subrange<subrange<reverse_iterator<_Iter>,
3262                                             reverse_iterator<_Iter>,
3263                                             _Kind>> = true;
3264
3265       template<typename>
3266         inline constexpr bool __is_reverse_view = false;
3267
3268       template<typename _Vp>
3269         inline constexpr bool __is_reverse_view<reverse_view<_Vp>> = true;
3270     }
3271
3272     inline constexpr __adaptor::_RangeAdaptorClosure reverse
3273       = [] <viewable_range _Range> (_Range&& __r)
3274       {
3275         using _Tp = remove_cvref_t<_Range>;
3276         if constexpr (__detail::__is_reverse_view<_Tp>)
3277           return std::forward<_Range>(__r).base();
3278         else if constexpr (__detail::__is_reversible_subrange<_Tp>)
3279           {
3280             using _Iter = decltype(ranges::begin(__r).base());
3281             if constexpr (sized_range<_Tp>)
3282               return subrange<_Iter, _Iter, subrange_kind::sized>
3283                       (__r.end().base(), __r.begin().base(), __r.size());
3284             else
3285               return subrange<_Iter, _Iter, subrange_kind::unsized>
3286                       (__r.end().base(), __r.begin().base());
3287           }
3288         else
3289           return reverse_view{std::forward<_Range>(__r)};
3290       };
3291   } // namespace views
3292
3293   namespace __detail
3294   {
3295     template<typename _Tp, size_t _Nm>
3296     concept __has_tuple_element = requires(_Tp __t)
3297       {
3298         typename tuple_size<_Tp>::type;
3299         requires _Nm < tuple_size_v<_Tp>;
3300         typename tuple_element_t<_Nm, _Tp>;
3301         { std::get<_Nm>(__t) }
3302           -> convertible_to<const tuple_element_t<_Nm, _Tp>&>;
3303       };
3304   }
3305
3306   template<input_range _Vp, size_t _Nm>
3307     requires view<_Vp>
3308       && __detail::__has_tuple_element<range_value_t<_Vp>, _Nm>
3309       && __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>,
3310                                        _Nm>
3311     class elements_view : public view_interface<elements_view<_Vp, _Nm>>
3312     {
3313     public:
3314       elements_view() = default;
3315
3316       constexpr explicit
3317       elements_view(_Vp base)
3318         : _M_base(std::move(base))
3319       { }
3320
3321       constexpr _Vp
3322       base() const& requires copy_constructible<_Vp>
3323       { return _M_base; }
3324
3325       constexpr _Vp
3326       base() &&
3327       { return std::move(_M_base); }
3328
3329       constexpr auto
3330       begin() requires (!__detail::__simple_view<_Vp>)
3331       { return _Iterator<false>(ranges::begin(_M_base)); }
3332
3333       constexpr auto
3334       begin() const requires __detail::__simple_view<_Vp>
3335       { return _Iterator<true>(ranges::begin(_M_base)); }
3336
3337       constexpr auto
3338       end() requires (!__detail::__simple_view<_Vp>)
3339       { return ranges::end(_M_base); }
3340
3341       constexpr auto
3342       end() const requires __detail::__simple_view<_Vp>
3343       { return ranges::end(_M_base); }
3344
3345       constexpr auto
3346       size() requires sized_range<_Vp>
3347       { return ranges::size(_M_base); }
3348
3349       constexpr auto
3350       size() const requires sized_range<const _Vp>
3351       { return ranges::size(_M_base); }
3352
3353     private:
3354       template<bool _Const>
3355         struct _Iterator
3356         {
3357           using _Base = __detail::__maybe_const_t<_Const, _Vp>;
3358
3359           iterator_t<_Base> _M_current = iterator_t<_Base>();
3360
3361           friend _Iterator<!_Const>;
3362
3363         public:
3364           using iterator_category
3365             = typename iterator_traits<iterator_t<_Base>>::iterator_category;
3366           using value_type
3367             = remove_cvref_t<tuple_element_t<_Nm, range_value_t<_Base>>>;
3368           using difference_type = range_difference_t<_Base>;
3369
3370           _Iterator() = default;
3371
3372           constexpr explicit
3373           _Iterator(iterator_t<_Base> current)
3374             : _M_current(std::move(current))
3375           { }
3376
3377           constexpr
3378           _Iterator(_Iterator<!_Const> i)
3379             requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
3380             : _M_current(std::move(i._M_current))
3381           { }
3382
3383           constexpr iterator_t<_Base>
3384           base() const&
3385             requires copyable<iterator_t<_Base>>
3386           { return _M_current; }
3387
3388           constexpr iterator_t<_Base>
3389           base() &&
3390           { return std::move(_M_current); }
3391
3392           constexpr decltype(auto)
3393             operator*() const
3394           { return std::get<_Nm>(*_M_current); }
3395
3396           constexpr _Iterator&
3397           operator++()
3398           {
3399             ++_M_current;
3400             return *this;
3401           }
3402
3403           constexpr void
3404           operator++(int) requires (!forward_range<_Base>)
3405           { ++_M_current; }
3406
3407           constexpr _Iterator
3408           operator++(int) requires forward_range<_Base>
3409           {
3410             auto __tmp = *this;
3411             ++_M_current;
3412             return __tmp;
3413           }
3414
3415           constexpr _Iterator&
3416           operator--() requires bidirectional_range<_Base>
3417           {
3418             --_M_current;
3419             return *this;
3420           }
3421
3422           constexpr _Iterator
3423           operator--(int) requires bidirectional_range<_Base>
3424           {
3425             auto __tmp = *this;
3426             --_M_current;
3427             return __tmp;
3428           }
3429
3430           constexpr _Iterator&
3431           operator+=(difference_type __n)
3432             requires random_access_range<_Base>
3433           {
3434             _M_current += __n;
3435             return *this;
3436           }
3437
3438           constexpr _Iterator&
3439           operator-=(difference_type __n)
3440             requires random_access_range<_Base>
3441           {
3442             _M_current -= __n;
3443             return *this;
3444           }
3445
3446           constexpr decltype(auto)
3447           operator[](difference_type __n) const
3448             requires random_access_range<_Base>
3449           { return std::get<_Nm>(*(_M_current + __n)); }
3450
3451           friend constexpr bool
3452           operator==(const _Iterator& __x, const _Iterator& __y)
3453             requires equality_comparable<iterator_t<_Base>>
3454           { return __x._M_current == __y._M_current; }
3455
3456           friend constexpr bool
3457           operator==(const _Iterator& __x, const sentinel_t<_Base>& __y)
3458           { return __x._M_current == __y; }
3459
3460           friend constexpr bool
3461           operator<(const _Iterator& __x, const _Iterator& __y)
3462             requires random_access_range<_Base>
3463           { return __x._M_current < __y._M_current; }
3464
3465           friend constexpr bool
3466           operator>(const _Iterator& __x, const _Iterator& __y)
3467             requires random_access_range<_Base>
3468           { return __y._M_current < __x._M_current; }
3469
3470           friend constexpr bool
3471           operator<=(const _Iterator& __x, const _Iterator& __y)
3472             requires random_access_range<_Base>
3473           { return !(__y._M_current > __x._M_current); }
3474
3475           friend constexpr bool
3476           operator>=(const _Iterator& __x, const _Iterator& __y)
3477             requires random_access_range<_Base>
3478           { return !(__x._M_current > __y._M_current); }
3479
3480 #ifdef __cpp_lib_three_way_comparison
3481           friend constexpr auto
3482           operator<=>(const _Iterator& __x, const _Iterator& __y)
3483             requires random_access_range<_Base>
3484               && three_way_comparable<iterator_t<_Base>>
3485           { return __x._M_current <=> __y._M_current; }
3486 #endif
3487
3488           friend constexpr _Iterator
3489           operator+(const _Iterator& __x, difference_type __y)
3490             requires random_access_range<_Base>
3491           { return _Iterator{__x} += __y; }
3492
3493           friend constexpr _Iterator
3494           operator+(difference_type __x, const _Iterator& __y)
3495             requires random_access_range<_Base>
3496           { return __y + __x; }
3497
3498           friend constexpr _Iterator
3499           operator-(const _Iterator& __x, difference_type __y)
3500             requires random_access_range<_Base>
3501           { return _Iterator{__x} -= __y; }
3502
3503           friend constexpr difference_type
3504           operator-(const _Iterator& __x, const _Iterator& __y)
3505             requires random_access_range<_Base>
3506           { return __x._M_current - __y._M_current; }
3507
3508           friend constexpr difference_type
3509           operator-(const _Iterator<_Const>& __x, const sentinel_t<_Base>& __y)
3510             requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
3511           { return __x._M_current - __y; }
3512
3513           friend constexpr difference_type
3514           operator-(const sentinel_t<_Base>& __x, const _Iterator<_Const>& __y)
3515             requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
3516           { return -(__y - __x); }
3517         };
3518
3519       _Vp _M_base = _Vp();
3520     };
3521
3522   template<typename _Range>
3523     using keys_view = elements_view<views::all_t<_Range>, 0>;
3524
3525   template<typename _Range>
3526     using values_view = elements_view<views::all_t<_Range>, 1>;
3527
3528   namespace views
3529   {
3530     template<size_t _Nm>
3531     inline constexpr __adaptor::_RangeAdaptorClosure elements
3532       = [] <viewable_range _Range> (_Range&& __r)
3533       {
3534         using _El = elements_view<views::all_t<_Range>, _Nm>;
3535         return _El{std::forward<_Range>(__r)};
3536       };
3537
3538     inline constexpr __adaptor::_RangeAdaptorClosure keys = elements<0>;
3539     inline constexpr __adaptor::_RangeAdaptorClosure values = elements<1>;
3540   } // namespace views
3541
3542 } // namespace ranges
3543
3544   namespace views = ranges::views;
3545
3546   template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
3547     struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>>
3548     : integral_constant<size_t, 2>
3549     { };
3550
3551   template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
3552     struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>>
3553     { using type = _Iter; };
3554
3555   template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
3556     struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>>
3557     { using type = _Sent; };
3558
3559   template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
3560     struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>>
3561     { using type = _Iter; };
3562
3563   template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
3564     struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>>
3565     { using type = _Sent; };
3566
3567 _GLIBCXX_END_NAMESPACE_VERSION
3568 } // namespace
3569 #endif // library concepts
3570 #endif // C++2a
3571 #endif /* _GLIBCXX_RANGES */