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