libstdc++-v3/include/std/ranges

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