libstdc++-v3/include/std/ranges

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