libstdc++-v3/include/std/ranges

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