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