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 _Sentinel<_Const>;
1763         };
1764
1765       template<bool _Const>
1766         struct _Sentinel
1767         {
1768         private:
1769           using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1770           using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1771
1772           constexpr range_difference_t<_Base>
1773           __distance_from(const _Iterator<_Const>& __i) const
1774           { return _M_end - __i._M_current; }
1775
1776           constexpr bool
1777           __equal(const _Iterator<_Const>& __i) const
1778           { return __i._M_current == _M_end; }
1779
1780           sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1781
1782         public:
1783           _Sentinel() = default;
1784
1785           constexpr explicit
1786           _Sentinel(sentinel_t<_Base> __end)
1787             : _M_end(__end)
1788           { }
1789
1790           constexpr
1791           _Sentinel(_Sentinel<!_Const> __i)
1792             requires _Const
1793               && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1794             : _M_end(std::move(__i._M_end))
1795           { }
1796
1797           constexpr sentinel_t<_Base>
1798           base() const
1799           { return _M_end; }
1800
1801           friend constexpr bool
1802           operator==(const _Iterator<_Const>& __x, const _Sentinel& __y)
1803           { return __y.__equal(__x); }
1804
1805           friend constexpr range_difference_t<_Base>
1806           operator-(const _Iterator<_Const>& __x, const _Sentinel& __y)
1807             requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
1808           { return -__y.__distance_from(__x); }
1809
1810           friend constexpr range_difference_t<_Base>
1811           operator-(const _Sentinel& __y, const _Iterator<_Const>& __x)
1812             requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
1813           { return __y.__distance_from(__x); }
1814         };
1815
1816       _Vp _M_base = _Vp();
1817       __detail::__box<_Fp> _M_fun;
1818
1819     public:
1820       transform_view() = default;
1821
1822       constexpr
1823       transform_view(_Vp __base, _Fp __fun)
1824         : _M_base(std::move(__base)), _M_fun(std::move(__fun))
1825       { }
1826
1827       constexpr _Vp
1828       base() const& requires copy_constructible<_Vp>
1829       { return _M_base ; }
1830
1831       constexpr _Vp
1832       base() &&
1833       { return std::move(_M_base); }
1834
1835       constexpr _Iterator<false>
1836       begin()
1837       { return _Iterator<false>{*this, ranges::begin(_M_base)}; }
1838
1839       constexpr _Iterator<true>
1840       begin() const
1841         requires range<const _Vp>
1842           && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1843       { return _Iterator<true>{*this, ranges::begin(_M_base)}; }
1844
1845       constexpr _Sentinel<false>
1846       end()
1847       { return _Sentinel<false>{ranges::end(_M_base)}; }
1848
1849       constexpr _Iterator<false>
1850       end() requires common_range<_Vp>
1851       { return _Iterator<false>{*this, ranges::end(_M_base)}; }
1852
1853       constexpr _Sentinel<true>
1854       end() const
1855         requires range<const _Vp>
1856           && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1857       { return _Sentinel<true>{ranges::end(_M_base)}; }
1858
1859       constexpr _Iterator<true>
1860       end() const
1861         requires common_range<const _Vp>
1862           && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1863       { return _Iterator<true>{*this, ranges::end(_M_base)}; }
1864
1865       constexpr auto
1866       size() requires sized_range<_Vp>
1867       { return ranges::size(_M_base); }
1868
1869       constexpr auto
1870       size() const requires sized_range<const _Vp>
1871       { return ranges::size(_M_base); }
1872     };
1873
1874   template<typename _Range, typename _Fp>
1875     transform_view(_Range&&, _Fp) -> transform_view<views::all_t<_Range>, _Fp>;
1876
1877   namespace views
1878   {
1879     inline constexpr __adaptor::_RangeAdaptor transform
1880       = [] <viewable_range _Range, typename _Fp> (_Range&& __r, _Fp&& __f)
1881       {
1882         return transform_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)};
1883       };
1884   } // namespace views
1885
1886   template<view _Vp>
1887     class take_view : public view_interface<take_view<_Vp>>
1888     {
1889     private:
1890       template<bool _Const>
1891         struct _Sentinel
1892         {
1893         private:
1894           using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1895           using _CI = counted_iterator<iterator_t<_Base>>;
1896
1897           sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1898
1899         public:
1900           _Sentinel() = default;
1901
1902           constexpr explicit
1903           _Sentinel(sentinel_t<_Base> __end)
1904             : _M_end(__end)
1905           { }
1906
1907           constexpr
1908           _Sentinel(_Sentinel<!_Const> __s)
1909             requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1910             : _M_end(std::move(__s._M_end))
1911           { }
1912
1913           constexpr sentinel_t<_Base>
1914           base() const
1915           { return _M_end; }
1916
1917           friend constexpr bool operator==(const _CI& __y, const _Sentinel& __x)
1918           { return __y.count() == 0 || __y.base() == __x._M_end; }
1919         };
1920
1921       _Vp _M_base = _Vp();
1922       range_difference_t<_Vp> _M_count = 0;
1923
1924     public:
1925       take_view() = default;
1926
1927       constexpr
1928       take_view(_Vp base, range_difference_t<_Vp> __count)
1929         : _M_base(std::move(base)), _M_count(std::move(__count))
1930       { }
1931
1932       constexpr _Vp
1933       base() const& requires copy_constructible<_Vp>
1934       { return _M_base; }
1935
1936       constexpr _Vp
1937       base() &&
1938       { return std::move(_M_base); }
1939
1940       constexpr auto
1941       begin() requires (!__detail::__simple_view<_Vp>)
1942       {
1943         if constexpr (sized_range<_Vp>)
1944           {
1945             if constexpr (random_access_range<_Vp>)
1946               return ranges::begin(_M_base);
1947             else
1948               return counted_iterator{ranges::begin(_M_base), size()};
1949           }
1950         else
1951           return counted_iterator{ranges::begin(_M_base), _M_count};
1952       }
1953
1954       constexpr auto
1955       begin() const requires range<const _Vp>
1956       {
1957         if constexpr (sized_range<const _Vp>)
1958           {
1959             if constexpr (random_access_range<const _Vp>)
1960               return ranges::begin(_M_base);
1961             else
1962               return counted_iterator{ranges::begin(_M_base), size()};
1963           }
1964         else
1965           return counted_iterator{ranges::begin(_M_base), _M_count};
1966       }
1967
1968       constexpr auto
1969       end() requires (!__detail::__simple_view<_Vp>)
1970       {
1971         if constexpr (sized_range<_Vp>)
1972           {
1973             if constexpr (random_access_range<_Vp>)
1974               return ranges::begin(_M_base) + size();
1975             else
1976               return default_sentinel;
1977           }
1978         else
1979           return _Sentinel<false>{ranges::end(_M_base)};
1980       }
1981
1982       constexpr auto
1983       end() const requires range<const _Vp>
1984       {
1985         if constexpr (sized_range<const _Vp>)
1986           {
1987             if constexpr (random_access_range<const _Vp>)
1988               return ranges::begin(_M_base) + size();
1989             else
1990               return default_sentinel;
1991           }
1992         else
1993           return _Sentinel<true>{ranges::end(_M_base)};
1994       }
1995
1996       constexpr auto
1997       size() requires sized_range<_Vp>
1998       {
1999         auto __n = ranges::size(_M_base);
2000         return __detail::min(__n, static_cast<decltype(__n)>(_M_count));
2001       }
2002
2003       constexpr auto
2004       size() const requires sized_range<const _Vp>
2005       {
2006         auto __n = ranges::size(_M_base);
2007         return __detail::min(__n, static_cast<decltype(__n)>(_M_count));
2008       }
2009     };
2010
2011   template<range _Range>
2012     take_view(_Range&&, range_difference_t<_Range>)
2013       -> take_view<views::all_t<_Range>>;
2014
2015   namespace views
2016   {
2017     inline constexpr __adaptor::_RangeAdaptor take
2018       = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n)
2019       {
2020         return take_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
2021       };
2022   } // namespace views
2023
2024   template<view _Vp, typename _Pred>
2025     requires input_range<_Vp> && is_object_v<_Pred>
2026       && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2027     class take_while_view : public view_interface<take_while_view<_Vp, _Pred>>
2028     {
2029       template<bool _Const>
2030         struct _Sentinel
2031         {
2032         private:
2033           using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2034
2035           sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2036           const _Pred* _M_pred = nullptr;
2037
2038         public:
2039           _Sentinel() = default;
2040
2041           constexpr explicit
2042           _Sentinel(sentinel_t<_Base> __end, const _Pred* __pred)
2043             : _M_end(__end), _M_pred(__pred)
2044           { }
2045
2046           constexpr
2047           _Sentinel(_Sentinel<!_Const> __s)
2048             requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2049             : _M_end(__s._M_end), _M_pred(__s._M_pred)
2050           { }
2051
2052           constexpr sentinel_t<_Base>
2053           base() const { return _M_end; }
2054
2055           friend constexpr bool
2056           operator==(const iterator_t<_Base>& __x, const _Sentinel& __y)
2057           { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
2058         };
2059
2060       _Vp _M_base = _Vp();
2061       __detail::__box<_Pred> _M_pred;
2062
2063     public:
2064       take_while_view() = default;
2065
2066       constexpr
2067       take_while_view(_Vp base, _Pred __pred)
2068         : _M_base(std::move(base)), _M_pred(std::move(__pred))
2069       {
2070       }
2071
2072       constexpr _Vp
2073       base() const& requires copy_constructible<_Vp>
2074       { return _M_base; }
2075
2076       constexpr _Vp
2077       base() &&
2078       { return std::move(_M_base); }
2079
2080       constexpr const _Pred&
2081       pred() const
2082       { return *_M_pred; }
2083
2084       constexpr auto
2085       begin() requires (!__detail::__simple_view<_Vp>)
2086       { return ranges::begin(_M_base); }
2087
2088       constexpr auto
2089       begin() const requires range<const _Vp>
2090       { return ranges::begin(_M_base); }
2091
2092       constexpr auto
2093       end() requires (!__detail::__simple_view<_Vp>)
2094       { return _Sentinel<false>(ranges::end(_M_base),
2095                                 std::__addressof(*_M_pred)); }
2096
2097       constexpr auto
2098       end() const requires range<const _Vp>
2099       { return _Sentinel<true>(ranges::end(_M_base),
2100                                std::__addressof(*_M_pred)); }
2101     };
2102
2103   template<typename _Range, typename _Pred>
2104     take_while_view(_Range&&, _Pred)
2105       -> take_while_view<views::all_t<_Range>, _Pred>;
2106
2107   namespace views
2108   {
2109     inline constexpr __adaptor::_RangeAdaptor take_while
2110       = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p)
2111       {
2112         return take_while_view{std::forward<_Range>(__r), std::forward<_Pred>(__p)};
2113       };
2114   } // namespace views
2115
2116   template<view _Vp>
2117     class drop_view : public view_interface<drop_view<_Vp>>
2118     {
2119     private:
2120       _Vp _M_base = _Vp();
2121       range_difference_t<_Vp> _M_count = 0;
2122
2123     public:
2124       drop_view() = default;
2125
2126       constexpr
2127       drop_view(_Vp __base, range_difference_t<_Vp> __count)
2128         : _M_base(std::move(__base)), _M_count(__count)
2129       { __glibcxx_assert(__count >= 0); }
2130
2131       constexpr _Vp
2132       base() const& requires copy_constructible<_Vp>
2133       { return _M_base; }
2134
2135       constexpr _Vp
2136       base() &&
2137       { return std::move(_M_base); }
2138
2139       constexpr auto
2140       begin() requires (!(__detail::__simple_view<_Vp>
2141                           && random_access_range<_Vp>))
2142       {
2143         // XXX: we need to cache the result here as per [range.drop.view]
2144         return ranges::next(ranges::begin(_M_base), _M_count,
2145                             ranges::end(_M_base));
2146       }
2147
2148       constexpr auto
2149       begin() const requires random_access_range<const _Vp>
2150       {
2151         return ranges::next(ranges::begin(_M_base), _M_count,
2152                             ranges::end(_M_base));
2153       }
2154
2155       constexpr auto
2156       end() requires (!__detail::__simple_view<_Vp>)
2157       { return ranges::end(_M_base); }
2158
2159       constexpr auto
2160       end() const requires range<const _Vp>
2161       { return ranges::end(_M_base); }
2162
2163       constexpr auto
2164       size() requires sized_range<_Vp>
2165       {
2166         const auto __s = ranges::size(_M_base);
2167         const auto __c = static_cast<decltype(__s)>(_M_count);
2168         return __s < __c ? 0 : __s - __c;
2169       }
2170
2171       constexpr auto
2172       size() const requires sized_range<const _Vp>
2173       {
2174         const auto __s = ranges::size(_M_base);
2175         const auto __c = static_cast<decltype(__s)>(_M_count);
2176         return __s < __c ? 0 : __s - __c;
2177       }
2178     };
2179
2180   template<typename _Range>
2181     drop_view(_Range&&, range_difference_t<_Range>)
2182       -> drop_view<views::all_t<_Range>>;
2183
2184   namespace views
2185   {
2186     inline constexpr __adaptor::_RangeAdaptor drop
2187       = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n)
2188       {
2189         return drop_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
2190       };
2191   } // namespace views
2192
2193   template<view _Vp, typename _Pred>
2194     requires input_range<_Vp> && is_object_v<_Pred>
2195       && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2196     class drop_while_view : public view_interface<drop_while_view<_Vp, _Pred>>
2197     {
2198     private:
2199       _Vp _M_base = _Vp();
2200       __detail::__box<_Pred> _M_pred;
2201
2202     public:
2203       drop_while_view() = default;
2204
2205       constexpr
2206       drop_while_view(_Vp __base, _Pred __pred)
2207         : _M_base(std::move(__base)), _M_pred(std::move(__pred))
2208       { }
2209
2210       constexpr _Vp
2211       base() const& requires copy_constructible<_Vp>
2212       { return _M_base; }
2213
2214       constexpr _Vp
2215       base() &&
2216       { return std::move(_M_base); }
2217
2218       constexpr const _Pred&
2219       pred() const
2220       { return *_M_pred; }
2221
2222       constexpr auto
2223       begin()
2224       {
2225         // XXX: we need to cache the result here as per [range.drop.while.view]
2226         return __detail::find_if_not(ranges::begin(_M_base),
2227                                      ranges::end(_M_base),
2228                                      std::cref(*_M_pred));
2229       }
2230
2231       constexpr auto
2232       end()
2233       { return ranges::end(_M_base); }
2234     };
2235
2236   template<typename _Range, typename _Pred>
2237     drop_while_view(_Range&&, _Pred)
2238       -> drop_while_view<views::all_t<_Range>, _Pred>;
2239
2240   namespace views
2241   {
2242     inline constexpr __adaptor::_RangeAdaptor drop_while
2243       = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p)
2244       {
2245         return drop_while_view{std::forward<_Range>(__r),
2246                                std::forward<_Pred>(__p)};
2247       };
2248   } // namespace views
2249
2250   template<input_range _Vp>
2251     requires view<_Vp> && input_range<range_reference_t<_Vp>>
2252       && (is_reference_v<range_reference_t<_Vp>>
2253           || view<range_value_t<_Vp>>)
2254     class join_view : public view_interface<join_view<_Vp>>
2255     {
2256     private:
2257       using _InnerRange = range_reference_t<_Vp>;
2258
2259       template<bool _Const>
2260         struct _Sentinel;
2261
2262       template<bool _Const>
2263         struct _Iterator
2264         {
2265         private:
2266           using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2267           using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2268
2269           static constexpr bool _S_ref_is_glvalue
2270             = is_reference_v<range_reference_t<_Base>>;
2271
2272           constexpr void
2273           _M_satisfy()
2274           {
2275             auto __update_inner = [this] (range_reference_t<_Base> __x) -> auto&
2276             {
2277               if constexpr (_S_ref_is_glvalue)
2278                 return __x;
2279               else
2280                 return (_M_parent->_M_inner = views::all(std::move(__x)));
2281             };
2282
2283             for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer)
2284               {
2285                 auto& inner = __update_inner(*_M_outer);
2286                 _M_inner = ranges::begin(inner);
2287                 if (_M_inner != ranges::end(inner))
2288                   return;
2289               }
2290
2291             if constexpr (_S_ref_is_glvalue)
2292               _M_inner = _Inner_iter();
2293           }
2294
2295           static constexpr auto
2296           _S_iter_concept()
2297           {
2298             if constexpr (_S_ref_is_glvalue
2299                           && bidirectional_range<_Base>
2300                           && bidirectional_range<range_reference_t<_Base>>)
2301               return bidirectional_iterator_tag{};
2302             else if constexpr (_S_ref_is_glvalue
2303                                && forward_range<_Base>
2304                                && forward_range<range_reference_t<_Base>>)
2305               return forward_iterator_tag{};
2306             else
2307               return input_iterator_tag{};
2308           }
2309
2310           static constexpr auto
2311           _S_iter_cat()
2312           {
2313             using _OuterCat
2314               = typename iterator_traits<_Outer_iter>::iterator_category;
2315             using _InnerCat
2316               = typename iterator_traits<_Inner_iter>::iterator_category;
2317             if constexpr (_S_ref_is_glvalue
2318                           && derived_from<_OuterCat, bidirectional_iterator_tag>
2319                           && derived_from<_InnerCat, bidirectional_iterator_tag>)
2320               return bidirectional_iterator_tag{};
2321             else if constexpr (_S_ref_is_glvalue
2322                                && derived_from<_OuterCat, forward_iterator_tag>
2323                                && derived_from<_InnerCat, forward_iterator_tag>)
2324               return forward_iterator_tag{};
2325             else if constexpr (derived_from<_OuterCat, input_iterator_tag>
2326                                && derived_from<_InnerCat, input_iterator_tag>)
2327               return input_iterator_tag{};
2328             else
2329               return output_iterator_tag{};
2330           }
2331
2332           using _Outer_iter = iterator_t<_Base>;
2333           using _Inner_iter = iterator_t<range_reference_t<_Base>>;
2334
2335           _Outer_iter _M_outer = _Outer_iter();
2336           _Inner_iter _M_inner = _Inner_iter();
2337           _Parent* _M_parent = nullptr;
2338
2339         public:
2340           using iterator_concept = decltype(_S_iter_concept());
2341           using iterator_category = decltype(_S_iter_cat());
2342           using value_type = range_value_t<range_reference_t<_Base>>;
2343           using difference_type
2344             = common_type_t<range_difference_t<_Base>,
2345                             range_difference_t<range_reference_t<_Base>>>;
2346
2347           _Iterator() = default;
2348
2349           constexpr
2350           _Iterator(_Parent& __parent, _Outer_iter __outer)
2351             : _M_outer(std::move(__outer)),
2352               _M_parent(std::__addressof(__parent))
2353           { _M_satisfy(); }
2354
2355           constexpr
2356           _Iterator(_Iterator<!_Const> __i)
2357             requires _Const
2358               && convertible_to<iterator_t<_Vp>, _Outer_iter>
2359               && convertible_to<iterator_t<_InnerRange>, _Inner_iter>
2360             : _M_outer(std::move(__i._M_outer)), _M_inner(__i._M_inner),
2361               _M_parent(__i._M_parent)
2362           { }
2363
2364           constexpr decltype(auto)
2365           operator*() const
2366           { return *_M_inner; }
2367
2368           constexpr _Outer_iter
2369           operator->() const
2370             requires __detail::__has_arrow<_Outer_iter>
2371               && copyable<_Outer_iter>
2372           { return _M_inner; }
2373
2374           constexpr _Iterator&
2375           operator++()
2376           {
2377             auto&& __inner_range = [this] () -> decltype(auto) {
2378               if constexpr (_S_ref_is_glvalue)
2379                 return *_M_outer;
2380               else
2381                 return _M_parent->_M_inner;
2382             }();
2383             if (++_M_inner == ranges::end(__inner_range))
2384               {
2385                 ++_M_outer;
2386                 _M_satisfy();
2387               }
2388             return *this;
2389           }
2390
2391           constexpr void
2392           operator++(int)
2393           { ++*this; }
2394
2395           constexpr _Iterator
2396           operator++(int)
2397             requires _S_ref_is_glvalue && forward_range<_Base>
2398               && forward_range<range_reference_t<_Base>>
2399           {
2400             auto __tmp = *this;
2401             ++*this;
2402             return __tmp;
2403           }
2404
2405           constexpr _Iterator&
2406           operator--()
2407             requires _S_ref_is_glvalue && bidirectional_range<_Base>
2408               && bidirectional_range<range_reference_t<_Base>>
2409               && common_range<range_reference_t<_Base>>
2410           {
2411             if (_M_outer == ranges::end(_M_parent->_M_base))
2412               _M_inner = ranges::end(*--_M_outer);
2413             while (_M_inner == ranges::begin(*_M_outer))
2414               _M_inner = ranges::end(*--_M_outer);
2415             --_M_inner;
2416             return *this;
2417           }
2418
2419           constexpr _Iterator
2420           operator--(int)
2421             requires _S_ref_is_glvalue && bidirectional_range<_Base>
2422               && bidirectional_range<range_reference_t<_Base>>
2423               && common_range<range_reference_t<_Base>>
2424           {
2425             auto __tmp = *this;
2426             --*this;
2427             return __tmp;
2428           }
2429
2430           friend constexpr bool
2431           operator==(const _Iterator& __x, const _Iterator& __y)
2432             requires _S_ref_is_glvalue
2433               && equality_comparable<_Outer_iter>
2434               && equality_comparable<_Inner_iter>
2435           {
2436             return (__x._M_outer == __y._M_outer
2437                     && __x._M_inner == __y._M_inner);
2438           }
2439
2440           friend constexpr decltype(auto)
2441           iter_move(const _Iterator& __i)
2442           noexcept(noexcept(ranges::iter_move(__i._M_inner)))
2443           { return ranges::iter_move(__i._M_inner); }
2444
2445           friend constexpr void
2446           iter_swap(const _Iterator& __x, const _Iterator& __y)
2447             noexcept(noexcept(ranges::iter_swap(__x._M_inner, __y._M_inner)))
2448           { return ranges::iter_swap(__x._M_inner, __y._M_inner); }
2449
2450           friend _Iterator<!_Const>;
2451           friend _Sentinel<_Const>;
2452         };
2453
2454       template<bool _Const>
2455         struct _Sentinel
2456         {
2457         private:
2458           using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2459           using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2460
2461           constexpr bool
2462           __equal(const _Iterator<_Const>& __i) const
2463           { return __i._M_outer == _M_end; }
2464
2465           sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2466
2467         public:
2468           _Sentinel() = default;
2469
2470           constexpr explicit
2471           _Sentinel(_Parent& __parent)
2472             : _M_end(ranges::end(__parent._M_base))
2473           { }
2474
2475           constexpr
2476           _Sentinel(_Sentinel<!_Const> __s)
2477             requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2478             : _M_end(std::move(__s._M_end))
2479           { }
2480
2481           friend constexpr bool
2482           operator==(const _Iterator<_Const>& __x, const _Sentinel& __y)
2483           { return __y.__equal(__x); }
2484         };
2485
2486       _Vp _M_base = _Vp();
2487
2488       // XXX: _M_inner is "present only when !is_reference_v<_InnerRange>"
2489       [[no_unique_address]]
2490         __detail::__maybe_empty_t<!is_reference_v<_InnerRange>,
2491                                   views::all_t<_InnerRange>> _M_inner;
2492
2493     public:
2494       join_view() = default;
2495
2496       constexpr explicit
2497       join_view(_Vp __base)
2498         : _M_base(std::move(__base))
2499       { }
2500
2501       constexpr _Vp
2502       base() const& requires copy_constructible<_Vp>
2503       { return _M_base; }
2504
2505       constexpr _Vp
2506       base() &&
2507       { return std::move(_M_base); }
2508
2509       constexpr auto
2510       begin()
2511       {
2512         constexpr bool __use_const
2513           = (__detail::__simple_view<_Vp>
2514              && is_reference_v<range_reference_t<_Vp>>);
2515         return _Iterator<__use_const>{*this, ranges::begin(_M_base)};
2516       }
2517
2518       constexpr auto
2519       begin() const
2520         requires input_range<const _Vp>
2521           && is_reference_v<range_reference_t<const _Vp>>
2522       {
2523         return _Iterator<true>{*this, ranges::begin(_M_base)};
2524       }
2525
2526       constexpr auto
2527       end()
2528       {
2529         if constexpr (forward_range<_Vp> && is_reference_v<_InnerRange>
2530                       && forward_range<_InnerRange>
2531                       && common_range<_Vp> && common_range<_InnerRange>)
2532           return _Iterator<__detail::__simple_view<_Vp>>{*this,
2533                                                          ranges::end(_M_base)};
2534         else
2535           return _Sentinel<__detail::__simple_view<_Vp>>{*this};
2536       }
2537
2538       constexpr auto
2539       end() const
2540         requires input_range<const _Vp>
2541           && is_reference_v<range_reference_t<const _Vp>>
2542       {
2543         if constexpr (forward_range<const _Vp>
2544                       && is_reference_v<range_reference_t<const _Vp>>
2545                       && forward_range<range_reference_t<const _Vp>>
2546                       && common_range<const _Vp>
2547                       && common_range<range_reference_t<const _Vp>>)
2548           return _Iterator<true>{*this, ranges::end(_M_base)};
2549         else
2550           return _Sentinel<true>{*this};
2551       }
2552     };
2553
2554   template<typename _Range>
2555     explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;
2556
2557   namespace views
2558   {
2559     inline constexpr __adaptor::_RangeAdaptorClosure join
2560       = [] <viewable_range _Range> (_Range&& __r)
2561       {
2562         return join_view{std::forward<_Range>(__r)};
2563       };
2564   } // namespace views
2565
2566   namespace __detail
2567   {
2568     template<auto>
2569       struct __require_constant;
2570
2571     template<typename _Range>
2572       concept __tiny_range = sized_range<_Range>
2573         && requires
2574            { typename __require_constant<remove_reference_t<_Range>::size()>; }
2575         && (remove_reference_t<_Range>::size() <= 1);
2576   }
2577
2578   template<input_range _Vp, forward_range _Pattern>
2579     requires view<_Vp> && view<_Pattern>
2580       && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
2581                                ranges::equal_to>
2582       && (forward_range<_Vp> || __detail::__tiny_range<_Pattern>)
2583     class split_view : public view_interface<split_view<_Vp, _Pattern>>
2584     {
2585     private:
2586       template<bool _Const>
2587         struct _InnerIter;
2588
2589       template<bool _Const>
2590         struct _OuterIter
2591         {
2592         private:
2593           using _Parent = __detail::__maybe_const_t<_Const, split_view>;
2594           using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2595
2596           constexpr bool
2597           __at_end() const
2598           { return _M_current == ranges::end(_M_parent->_M_base); }
2599
2600           // XXX: [24.7.11.3.1]
2601           //  Many of the following specifications refer to the notional member
2602           //  current of outer-iterator.  current is equivalent to current_ if
2603           //  V models forward_range, and parent_->current_ otherwise.
2604           constexpr auto&
2605           __current()
2606           {
2607             if constexpr (forward_range<_Vp>)
2608               return _M_current;
2609             else
2610               return _M_parent->_M_current;
2611           }
2612
2613           constexpr auto&
2614           __current() const
2615           {
2616             if constexpr (forward_range<_Vp>)
2617               return _M_current;
2618             else
2619               return _M_parent->_M_current;
2620           }
2621
2622           _Parent* _M_parent = nullptr;
2623
2624           // XXX: _M_current is present only if "V models forward_range"
2625           [[no_unique_address]]
2626             __detail::__maybe_empty_t<forward_range<_Vp>,
2627                                       iterator_t<_Base>> _M_current;
2628
2629         public:
2630           using iterator_concept = conditional_t<forward_range<_Base>,
2631                                                  forward_iterator_tag,
2632                                                  input_iterator_tag>;
2633           using iterator_category = input_iterator_tag;
2634           using difference_type = range_difference_t<_Base>;
2635
2636           struct value_type : view_interface<value_type>
2637           {
2638           private:
2639             _OuterIter _M_i = _OuterIter();
2640
2641           public:
2642             value_type() = default;
2643
2644             constexpr explicit
2645             value_type(_OuterIter __i)
2646               : _M_i(std::move(__i))
2647             { }
2648
2649             constexpr _InnerIter<_Const>
2650             begin() const
2651               requires copyable<_OuterIter>
2652             { return _InnerIter<_Const>{_M_i}; }
2653
2654             constexpr _InnerIter<_Const>
2655             begin()
2656               requires (!copyable<_OuterIter>)
2657             { return _InnerIter<_Const>{std::move(_M_i)}; }
2658
2659             constexpr default_sentinel_t
2660             end() const
2661             { return default_sentinel; }
2662           };
2663
2664           _OuterIter() = default;
2665
2666           constexpr explicit
2667           _OuterIter(_Parent& __parent) requires (!forward_range<_Base>)
2668             : _M_parent(address(__parent))
2669           { }
2670
2671           constexpr
2672           _OuterIter(_Parent& __parent, iterator_t<_Base> __current)
2673             requires forward_range<_Base>
2674             : _M_parent(std::__addressof(__parent)),
2675               _M_current(std::move(__current))
2676           { }
2677
2678           constexpr
2679           _OuterIter(_OuterIter<!_Const> __i)
2680             requires _Const
2681               && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
2682             : _M_parent(__i._M_parent), _M_current(std::move(__i._M_current))
2683           { }
2684
2685           constexpr value_type
2686           operator*() const
2687           { return value_type{*this}; }
2688
2689           constexpr _OuterIter&
2690           operator++()
2691           {
2692             const auto __end = ranges::end(_M_parent->_M_base);
2693             if (_M_current == __end)
2694               return *this;
2695             const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern};
2696             if (__pbegin == __pend)
2697               ++_M_current;
2698             else
2699               do
2700                 {
2701                   auto [__b, __p]
2702                     = __detail::mismatch(std::move(_M_current), __end,
2703                                          __pbegin, __pend);
2704                   _M_current = std::move(__b);
2705                   if (__p == __pend)
2706                     break;
2707                 } while (++_M_current != __end);
2708             return *this;
2709           }
2710
2711           constexpr decltype(auto)
2712           operator++(int)
2713           {
2714             if constexpr (forward_range<_Base>)
2715               {
2716                 auto __tmp = *this;
2717                 ++*this;
2718                 return __tmp;
2719               }
2720             else
2721               ++*this;
2722           }
2723
2724           friend constexpr bool
2725           operator==(const _OuterIter& __x, const _OuterIter& __y)
2726             requires forward_range<_Base>
2727           { return __x._M_current == __y._M_current; }
2728
2729           friend constexpr bool
2730           operator==(const _OuterIter& __x, default_sentinel_t)
2731           { return __x.__at_end(); };
2732
2733           friend _InnerIter<_Const>;
2734         };
2735
2736       template<bool _Const>
2737         struct _InnerIter
2738         {
2739         private:
2740           using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2741
2742           constexpr bool
2743           __at_end() const
2744           {
2745             auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern};
2746             auto __end = ranges::end(_M_i._M_parent->_M_base);
2747             if constexpr (__detail::__tiny_range<_Pattern>)
2748               {
2749                 const auto& __cur = _M_i.__current();
2750                 if (__cur == __end)
2751                   return true;
2752                 if (__pcur == __pend)
2753                   return _M_incremented;
2754                 return *__cur == *__pcur;
2755               }
2756             else
2757               {
2758                 auto __cur = _M_i.__current();
2759                 if (__cur == __end)
2760                   return true;
2761                 if (__pcur == __pend)
2762                   return _M_incremented;
2763                 do
2764                   {
2765                     if (*__cur != *__pcur)
2766                       return false;
2767                     if (++__pcur == __pend)
2768                       return true;
2769                   } while (++__cur != __end);
2770                 return false;
2771               }
2772           }
2773
2774           static constexpr auto
2775           _S_iter_cat()
2776           {
2777             using _Cat
2778               = typename iterator_traits<iterator_t<_Base>>::iterator_category;
2779             if constexpr (derived_from<_Cat, forward_iterator_tag>)
2780               return forward_iterator_tag{};
2781             else
2782               return _Cat{};
2783           }
2784
2785           static constexpr decltype(auto)
2786           __iter_move(const _InnerIter& __i = {})
2787           noexcept(noexcept(ranges::iter_move(__i._M_i.__current())))
2788           { return ranges::iter_move(__i._M_i.__current()); }
2789
2790           static constexpr void
2791           __iter_swap(const _InnerIter& __x = {}, const _InnerIter& __y = {})
2792             noexcept(noexcept(ranges::iter_swap(__x._M_i.__current(),
2793                                                 __y._M_i.__current())))
2794           { ranges::iter_swap(__x._M_i.__current(), __y._M_i.__current()); }
2795
2796           _OuterIter<_Const> _M_i = _OuterIter<_Const>();
2797           bool _M_incremented = false;
2798
2799         public:
2800           using iterator_concept
2801             = typename _OuterIter<_Const>::iterator_concept;
2802           using iterator_category = decltype(_S_iter_cat());
2803           using value_type = range_value_t<_Base>;
2804           using difference_type = range_difference_t<_Base>;
2805
2806           _InnerIter() = default;
2807
2808           constexpr explicit
2809           _InnerIter(_OuterIter<_Const> __i)
2810             : _M_i(std::move(__i))
2811           { }
2812
2813           constexpr decltype(auto)
2814           operator*() const
2815           { return *_M_i._M_current; }
2816
2817           constexpr _InnerIter&
2818           operator++()
2819           {
2820             _M_incremented = true;
2821             if constexpr (!forward_range<_Base>)
2822               if constexpr (_Pattern::size() == 0)
2823                 return *this;
2824             ++_M_i.__current();
2825             return *this;
2826           }
2827
2828           constexpr decltype(auto)
2829           operator++(int)
2830           {
2831             if constexpr (forward_range<_Vp>)
2832               {
2833                 auto __tmp = *this;
2834                 ++*this;
2835                 return __tmp;
2836               }
2837             else
2838               ++*this;
2839           }
2840
2841           friend constexpr bool
2842           operator==(const _InnerIter& __x, const _InnerIter& __y)
2843             requires forward_range<_Base>
2844           { return __x._M_i == __y._M_i; }
2845
2846           friend constexpr bool
2847           operator==(const _InnerIter& __x, default_sentinel_t)
2848           { return __x.__at_end(); }
2849
2850           friend constexpr decltype(auto)
2851           iter_move(const _InnerIter& __i) noexcept(noexcept(__iter_move()))
2852           { return __iter_move(__i); }
2853
2854           friend constexpr void
2855           iter_swap(const _InnerIter& __x, const _InnerIter& __y)
2856             noexcept(noexcept(__iter_swap()))
2857             requires indirectly_swappable<iterator_t<_Base>>
2858           { __iter_swap(__x, __y); }
2859         };
2860
2861       _Vp _M_base = _Vp();
2862       _Pattern _M_pattern = _Pattern();
2863
2864       // XXX: _M_current is "present only if !forward_range<V>"
2865       [[no_unique_address]]
2866         __detail::__maybe_empty_t<!forward_range<_Vp>, iterator_t<_Vp>>
2867           _M_current;
2868
2869
2870     public:
2871       split_view() = default;
2872
2873       constexpr
2874       split_view(_Vp __base, _Pattern __pattern)
2875         : _M_base(std::move(__base)), _M_pattern(std::move(__pattern))
2876       { }
2877
2878       template<input_range _Range>
2879         requires constructible_from<_Vp, views::all_t<_Range>>
2880           && constructible_from<_Pattern, single_view<range_value_t<_Range>>>
2881         constexpr
2882         split_view(_Range&& __r, range_value_t<_Range> __e)
2883           : _M_base(views::all(std::forward<_Range>(__r))),
2884             _M_pattern(std::move(__e))
2885         { }
2886
2887       constexpr _Vp
2888       base() const& requires copy_constructible<_Vp>
2889       { return _M_base; }
2890
2891       constexpr _Vp
2892       base() &&
2893       { return std::move(_M_base); }
2894
2895       constexpr auto
2896       begin()
2897       {
2898         if constexpr (forward_range<_Vp>)
2899           return _OuterIter<__detail::__simple_view<_Vp>>{*this,
2900                                                         ranges::begin(_M_base)};
2901         else
2902           {
2903             _M_current = ranges::begin(_M_base);
2904             return _OuterIter<false>{*this};
2905           }
2906       }
2907
2908       constexpr auto
2909       begin() const requires forward_range<_Vp> && forward_range<const _Vp>
2910       {
2911         return _OuterIter<true>{*this, ranges::begin(_M_base)};
2912       }
2913
2914       constexpr auto
2915       end() requires forward_range<_Vp> && common_range<_Vp>
2916       {
2917         return _OuterIter<__detail::__simple_view<_Vp>>{*this, ranges::end(_M_base)};
2918       }
2919
2920       constexpr auto
2921       end() const
2922       {
2923         if constexpr (forward_range<_Vp>
2924                       && forward_range<const _Vp>
2925                       && common_range<const _Vp>)
2926           return _OuterIter<true>{*this, ranges::end(_M_base)};
2927         else
2928           return default_sentinel;
2929       }
2930     };
2931
2932   template<typename _Range, typename _Pred>
2933     split_view(_Range&&, _Pred&&)
2934       -> split_view<views::all_t<_Range>, views::all_t<_Pred>>;
2935
2936   template<input_range _Range>
2937     split_view(_Range&&, range_value_t<_Range>)
2938       -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
2939
2940   namespace views
2941   {
2942     inline constexpr __adaptor::_RangeAdaptor split
2943       = [] <viewable_range _Range, typename _Fp> (_Range&& __r, _Fp&& __f)
2944       {
2945         return split_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)};
2946       };
2947   } // namespace views
2948
2949   namespace views
2950   {
2951     struct _Counted
2952     {
2953       template<input_or_output_iterator _Iter>
2954       constexpr auto
2955       operator()(_Iter __i, iter_difference_t<_Iter> __n) const
2956       {
2957         if constexpr (random_access_iterator<_Iter>)
2958           return subrange{__i, __i + __n};
2959         else
2960           return subrange{counted_iterator{std::move(__i), __n},
2961                           default_sentinel};
2962       }
2963     };
2964
2965     inline constexpr _Counted counted{};
2966   } // namespace views
2967
2968   template<view _Vp>
2969     requires (!common_range<_Vp>) && copyable<iterator_t<_Vp>>
2970     class common_view : public view_interface<common_view<_Vp>>
2971     {
2972     private:
2973       _Vp _M_base = _Vp();
2974
2975     public:
2976       common_view() = default;
2977
2978       constexpr explicit
2979       common_view(_Vp __r)
2980         : _M_base(std::move(__r))
2981       { }
2982
2983       /* XXX: LWG 3280 didn't remove this constructor, but I think it should?
2984       template<viewable_range _Range>
2985         requires (!common_range<_Range>)
2986           && constructible_from<_Vp, views::all_t<_Range>>
2987         constexpr explicit
2988         common_view(_Range&& __r)
2989           : _M_base(views::all(std::forward<_Range>(__r)))
2990         { }
2991       */
2992
2993       constexpr _Vp
2994       base() const& requires copy_constructible<_Vp>
2995       { return _M_base; }
2996
2997       constexpr _Vp
2998       base() &&
2999       { return std::move(_M_base); }
3000
3001       constexpr auto
3002       begin()
3003       {
3004         if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3005           return ranges::begin(_M_base);
3006         else
3007           return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3008                   (ranges::begin(_M_base));
3009       }
3010
3011       constexpr auto
3012       begin() const requires range<const _Vp>
3013       {
3014         if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3015           return ranges::begin(_M_base);
3016         else
3017           return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3018                   (ranges::begin(_M_base));
3019       }
3020
3021       constexpr auto
3022       end()
3023       {
3024         if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3025           return ranges::begin(_M_base) + ranges::size(_M_base);
3026         else
3027           return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3028                   (ranges::end(_M_base));
3029       }
3030
3031       constexpr auto
3032       end() const requires range<const _Vp>
3033       {
3034         if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3035           return ranges::begin(_M_base) + ranges::size(_M_base);
3036         else
3037           return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3038                   (ranges::end(_M_base));
3039       }
3040
3041       constexpr auto
3042       size() requires sized_range<_Vp>
3043       { return ranges::size(_M_base); }
3044
3045       constexpr auto
3046       size() const requires sized_range<const _Vp>
3047       { return ranges::size(_M_base); }
3048     };
3049
3050   template<typename _Range>
3051     common_view(_Range&&) -> common_view<views::all_t<_Range>>;
3052
3053   namespace views
3054   {
3055     inline constexpr __adaptor::_RangeAdaptorClosure common
3056       = [] <viewable_range _Range> (_Range&& __r)
3057       {
3058         if constexpr (common_range<_Range>
3059                       && requires { views::all(std::forward<_Range>(__r)); })
3060           return views::all(std::forward<_Range>(__r));
3061         else
3062           return common_view{std::forward<_Range>(__r)};
3063       };
3064
3065   } // namespace views
3066
3067   template<view _Vp>
3068     requires bidirectional_range<_Vp>
3069     class reverse_view : public view_interface<reverse_view<_Vp>>
3070     {
3071     private:
3072       _Vp _M_base = _Vp();
3073
3074     public:
3075       reverse_view() = default;
3076
3077       constexpr explicit
3078       reverse_view(_Vp __r)
3079         : _M_base(std::move(__r))
3080         { }
3081
3082       constexpr _Vp
3083       base() const& requires copy_constructible<_Vp>
3084       { return _M_base; }
3085
3086       constexpr _Vp
3087       base() &&
3088       { return std::move(_M_base); }
3089
3090       constexpr reverse_iterator<iterator_t<_Vp>>
3091       begin()
3092       {
3093         // XXX: we need to cache the result here as per [range.reverse.view]
3094         return make_reverse_iterator(ranges::next(ranges::begin(_M_base),
3095                                                   ranges::end(_M_base)));
3096       }
3097
3098       constexpr auto
3099       begin() requires common_range<_Vp>
3100       { return make_reverse_iterator(ranges::end(_M_base)); }
3101
3102       constexpr auto
3103       begin() const requires common_range<const _Vp>
3104       { return make_reverse_iterator(ranges::end(_M_base)); }
3105
3106       constexpr reverse_iterator<iterator_t<_Vp>>
3107       end()
3108       { return make_reverse_iterator(ranges::begin(_M_base)); }
3109
3110       constexpr auto
3111       end() const requires common_range<const _Vp>
3112       { return make_reverse_iterator(ranges::begin(_M_base)); }
3113
3114       constexpr auto
3115       size() requires sized_range<_Vp>
3116       { return ranges::size(_M_base); }
3117
3118       constexpr auto
3119       size() const requires sized_range<const _Vp>
3120       { return ranges::size(_M_base); }
3121     };
3122
3123   template<typename _Range>
3124     reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>;
3125
3126   namespace views
3127   {
3128     namespace __detail
3129     {
3130       template<typename>
3131         inline constexpr bool __is_reversible_subrange = false;
3132
3133       template<typename _Iter, subrange_kind _Kind>
3134         inline constexpr bool
3135           __is_reversible_subrange<subrange<reverse_iterator<_Iter>,
3136                                             reverse_iterator<_Iter>,
3137                                             _Kind>> = true;
3138
3139       template<typename>
3140         inline constexpr bool __is_reverse_view = false;
3141
3142       template<typename _Vp>
3143         inline constexpr bool __is_reverse_view<reverse_view<_Vp>> = true;
3144     }
3145
3146     inline constexpr __adaptor::_RangeAdaptorClosure reverse
3147       = [] <viewable_range _Range> (_Range&& __r)
3148       {
3149         using _Tp = remove_cvref_t<_Range>;
3150         if constexpr (__detail::__is_reverse_view<_Tp>)
3151           return std::forward<_Range>(__r).base();
3152         else if constexpr (__detail::__is_reversible_subrange<_Tp>)
3153           {
3154             using _Iter = decltype(ranges::begin(__r).base());
3155             if constexpr (sized_range<_Tp>)
3156               return subrange<_Iter, _Iter, subrange_kind::sized>
3157                       (__r.end().base(), __r.begin().base(), __r.size());
3158             else
3159               return subrange<_Iter, _Iter, subrange_kind::unsized>
3160                       (__r.end().base(), __r.begin().base());
3161           }
3162         else
3163           return reverse_view{std::forward<_Range>(__r)};
3164       };
3165   } // namespace views
3166
3167   namespace __detail
3168   {
3169     template<typename _Tp, size_t _Nm>
3170     concept __has_tuple_element = requires(_Tp __t)
3171       {
3172         typename tuple_size<_Tp>::type;
3173         requires _Nm < tuple_size_v<_Tp>;
3174         typename tuple_element_t<_Nm, _Tp>;
3175         { std::get<_Nm>(__t) }
3176           -> convertible_to<const tuple_element_t<_Nm, _Tp>&>;
3177       };
3178   }
3179
3180   template<input_range _Vp, size_t _Nm>
3181     requires view<_Vp>
3182       && __detail::__has_tuple_element<range_value_t<_Vp>, _Nm>
3183       && __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>,
3184                                        _Nm>
3185     class elements_view : public view_interface<elements_view<_Vp, _Nm>>
3186     {
3187     public:
3188       elements_view() = default;
3189
3190       constexpr explicit
3191       elements_view(_Vp base)
3192         : _M_base(std::move(base))
3193       { }
3194
3195       constexpr _Vp
3196       base() const& requires copy_constructible<_Vp>
3197       { return _M_base; }
3198
3199       constexpr _Vp
3200       base() &&
3201       { return std::move(_M_base); }
3202
3203       constexpr auto
3204       begin() requires (!__detail::__simple_view<_Vp>)
3205       { return _Iterator<false>(ranges::begin(_M_base)); }
3206
3207       constexpr auto
3208       begin() const requires __detail::__simple_view<_Vp>
3209       { return _Iterator<true>(ranges::begin(_M_base)); }
3210
3211       constexpr auto
3212       end() requires (!__detail::__simple_view<_Vp>)
3213       { return ranges::end(_M_base); }
3214
3215       constexpr auto
3216       end() const requires __detail::__simple_view<_Vp>
3217       { return ranges::end(_M_base); }
3218
3219       constexpr auto
3220       size() requires sized_range<_Vp>
3221       { return ranges::size(_M_base); }
3222
3223       constexpr auto
3224       size() const requires sized_range<const _Vp>
3225       { return ranges::size(_M_base); }
3226
3227     private:
3228       template<bool _Const>
3229         struct _Iterator
3230         {
3231           using _Base = __detail::__maybe_const_t<_Const, _Vp>;
3232
3233           iterator_t<_Base> _M_current = iterator_t<_Base>();
3234
3235           friend _Iterator<!_Const>;
3236
3237         public:
3238           using iterator_category
3239             = typename iterator_traits<iterator_t<_Base>>::iterator_category;
3240           using value_type
3241             = remove_cvref_t<tuple_element_t<_Nm, range_value_t<_Base>>>;
3242           using difference_type = range_difference_t<_Base>;
3243
3244           _Iterator() = default;
3245
3246           constexpr explicit
3247           _Iterator(iterator_t<_Base> current)
3248             : _M_current(std::move(current))
3249           { }
3250
3251           constexpr
3252           _Iterator(_Iterator<!_Const> i)
3253             requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
3254             : _M_current(std::move(i._M_current))
3255           { }
3256
3257           constexpr iterator_t<_Base>
3258           base() const&
3259             requires copyable<iterator_t<_Base>>
3260           { return _M_current; }
3261
3262           constexpr iterator_t<_Base>
3263           base() &&
3264           { return std::move(_M_current); }
3265
3266           constexpr decltype(auto)
3267             operator*() const
3268           { return std::get<_Nm>(*_M_current); }
3269
3270           constexpr _Iterator&
3271           operator++()
3272           {
3273             ++_M_current;
3274             return *this;
3275           }
3276
3277           constexpr void
3278           operator++(int) requires (!forward_range<_Base>)
3279           { ++_M_current; }
3280
3281           constexpr _Iterator
3282           operator++(int) requires forward_range<_Base>
3283           {
3284             auto __tmp = *this;
3285             ++_M_current;
3286             return __tmp;
3287           }
3288
3289           constexpr _Iterator&
3290           operator--() requires bidirectional_range<_Base>
3291           {
3292             --_M_current;
3293             return *this;
3294           }
3295
3296           constexpr _Iterator
3297           operator--(int) requires bidirectional_range<_Base>
3298           {
3299             auto __tmp = *this;
3300             --_M_current;
3301             return __tmp;
3302           }
3303
3304           constexpr _Iterator&
3305           operator+=(difference_type __n)
3306             requires random_access_range<_Base>
3307           {
3308             _M_current += __n;
3309             return *this;
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 decltype(auto)
3321           operator[](difference_type __n) const
3322             requires random_access_range<_Base>
3323           { return std::get<_Nm>(*(_M_current + __n)); }
3324
3325           friend constexpr bool
3326           operator==(const _Iterator& __x, const _Iterator& __y)
3327             requires equality_comparable<iterator_t<_Base>>
3328           { return __x._M_current == __y._M_current; }
3329
3330           friend constexpr bool
3331           operator==(const _Iterator& __x, const sentinel_t<_Base>& __y)
3332           { return __x._M_current == __y; }
3333
3334           friend constexpr bool
3335           operator<(const _Iterator& __x, const _Iterator& __y)
3336             requires random_access_range<_Base>
3337           { return __x._M_current < __y._M_current; }
3338
3339           friend constexpr bool
3340           operator>(const _Iterator& __x, const _Iterator& __y)
3341             requires random_access_range<_Base>
3342           { return __y._M_current < __x._M_current; }
3343
3344           friend constexpr bool
3345           operator<=(const _Iterator& __x, const _Iterator& __y)
3346             requires random_access_range<_Base>
3347           { return !(__y._M_current > __x._M_current); }
3348
3349           friend constexpr bool
3350           operator>=(const _Iterator& __x, const _Iterator& __y)
3351             requires random_access_range<_Base>
3352           { return !(__x._M_current > __y._M_current); }
3353
3354 #ifdef __cpp_lib_three_way_comparison
3355           friend constexpr auto
3356           operator<=>(const _Iterator& __x, const _Iterator& __y)
3357             requires random_access_range<_Base>
3358               && three_way_comparable<iterator_t<_Base>>
3359           { return __x._M_current <=> __y._M_current; }
3360 #endif
3361
3362           friend constexpr _Iterator
3363           operator+(const _Iterator& __x, difference_type __y)
3364             requires random_access_range<_Base>
3365           { return _Iterator{__x} += __y; }
3366
3367           friend constexpr _Iterator
3368           operator+(difference_type __x, const _Iterator& __y)
3369             requires random_access_range<_Base>
3370           { return __y + __x; }
3371
3372           friend constexpr _Iterator
3373           operator-(const _Iterator& __x, difference_type __y)
3374             requires random_access_range<_Base>
3375           { return _Iterator{__x} -= __y; }
3376
3377           friend constexpr difference_type
3378           operator-(const _Iterator& __x, const _Iterator& __y)
3379             requires random_access_range<_Base>
3380           { return __x._M_current - __y._M_current; }
3381
3382           friend constexpr difference_type
3383           operator-(const _Iterator<_Const>& __x, const sentinel_t<_Base>& __y)
3384             requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
3385           { return __x._M_current - __y; }
3386
3387           friend constexpr difference_type
3388           operator-(const sentinel_t<_Base>& __x, const _Iterator<_Const>& __y)
3389             requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
3390           { return -(__y - __x); }
3391         };
3392
3393       _Vp _M_base = _Vp();
3394     };
3395
3396   template<typename _Range>
3397     using keys_view = elements_view<views::all_t<_Range>, 0>;
3398
3399   template<typename _Range>
3400     using values_view = elements_view<views::all_t<_Range>, 1>;
3401
3402   namespace views
3403   {
3404     template<size_t _Nm>
3405     inline constexpr __adaptor::_RangeAdaptorClosure elements
3406       = [] <viewable_range _Range> (_Range&& __r)
3407       {
3408         using _El = elements_view<views::all_t<_Range>, _Nm>;
3409         return _El{std::forward<_Range>(__r)};
3410       };
3411
3412     inline constexpr __adaptor::_RangeAdaptorClosure keys = elements<0>;
3413     inline constexpr __adaptor::_RangeAdaptorClosure values = elements<1>;
3414   } // namespace views
3415
3416 } // namespace ranges
3417
3418   namespace views = ranges::views;
3419
3420   template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
3421     struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>>
3422     : integral_constant<size_t, 2>
3423     { };
3424
3425   template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
3426     struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>>
3427     { using type = _Iter; };
3428
3429   template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
3430     struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>>
3431     { using type = _Sent; };
3432
3433   template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
3434     struct tuple_element<0, const 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, const ranges::subrange<_Iter, _Sent, _Kind>>
3439     { using type = _Sent; };
3440
3441 _GLIBCXX_END_NAMESPACE_VERSION
3442 } // namespace
3443 #endif // library concepts
3444 #endif // C++2a
3445 #endif /* _GLIBCXX_RANGES */