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