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