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