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