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  // The following simple algos are transcribed from ranges_algo.h to avoid
1103  // having to include that entire header.
1104  namespace __detail
1105  {
1106  template<typename _Iter, typename _Sent, typename _Tp>
1107  constexpr _Iter
1108  find(_Iter __first, _Sent __last, const _Tp& __value)
1109  {
1110  while (__first != __last
1111  && !(bool)(*__first == __value))
1112  ++__first;
1113  return __first;
1114  }
1115 
1116  template<typename _Iter, typename _Sent, typename _Pred>
1117  constexpr _Iter
1118  find_if(_Iter __first, _Sent __last, _Pred __pred)
1119  {
1120  while (__first != __last
1121  && !(bool)std::__invoke(__pred, *__first))
1122  ++__first;
1123  return __first;
1124  }
1125 
1126  template<typename _Iter, typename _Sent, typename _Pred>
1127  constexpr _Iter
1128  find_if_not(_Iter __first, _Sent __last, _Pred __pred)
1129  {
1130  while (__first != __last
1131  && (bool)std::__invoke(__pred, *__first))
1132  ++__first;
1133  return __first;
1134  }
1135 
1136  template<typename _Iter1, typename _Sent1, typename _Iter2, typename _Sent2>
1137  constexpr pair<_Iter1, _Iter2>
1138  mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2)
1139  {
1140  while (__first1 != __last1 && __first2 != __last2
1141  && (bool)ranges::equal_to{}(*__first1, *__first2))
1142  {
1143  ++__first1;
1144  ++__first2;
1145  }
1146  return { std::move(__first1), std::move(__first2) };
1147  }
1148  } // namespace __detail
1149 
1150  namespace __detail
1151  {
1152  template<typename _Tp>
1153  struct __non_propagating_cache
1154  {
1155  // When _Tp is not an object type (e.g. is a reference type), we make
1156  // __non_propagating_cache<_Tp> empty rather than ill-formed so that
1157  // users can easily conditionally declare data members with this type
1158  // (such as join_view::_M_inner).
1159  };
1160 
1161  template<typename _Tp>
1162  requires is_object_v<_Tp>
1163  struct __non_propagating_cache<_Tp> : protected _Optional_base<_Tp>
1164  {
1165  __non_propagating_cache() = default;
1166 
1167  constexpr
1168  __non_propagating_cache(const __non_propagating_cache&) noexcept
1169  { }
1170 
1171  constexpr
1172  __non_propagating_cache(__non_propagating_cache&& __other) noexcept
1173  { __other._M_reset(); }
1174 
1175  constexpr __non_propagating_cache&
1176  operator=(const __non_propagating_cache& __other) noexcept
1177  {
1178  if (std::__addressof(__other) != this)
1179  this->_M_reset();
1180  return *this;
1181  }
1182 
1183  constexpr __non_propagating_cache&
1184  operator=(__non_propagating_cache&& __other) noexcept
1185  {
1186  this->_M_reset();
1187  __other._M_reset();
1188  return *this;
1189  }
1190 
1191  constexpr _Tp&
1192  operator*() noexcept
1193  { return this->_M_get(); }
1194 
1195  constexpr const _Tp&
1196  operator*() const noexcept
1197  { return this->_M_get(); }
1198 
1199  template<typename _Iter>
1200  _Tp&
1201  _M_emplace_deref(const _Iter& __i)
1202  {
1203  this->_M_reset();
1204  // Using _Optional_base::_M_construct to initialize from '*__i'
1205  // would incur an extra move due to the indirection, so we instead
1206  // use placement new directly.
1207  ::new ((void *) std::__addressof(this->_M_payload._M_payload)) _Tp(*__i);
1208  this->_M_payload._M_engaged = true;
1209  return this->_M_get();
1210  }
1211  };
1212 
1213  template<range _Range>
1214  struct _CachedPosition
1215  {
1216  constexpr bool
1217  _M_has_value() const
1218  { return false; }
1219 
1220  constexpr iterator_t<_Range>
1221  _M_get(const _Range&) const
1222  {
1223  __glibcxx_assert(false);
1224  return {};
1225  }
1226 
1227  constexpr void
1228  _M_set(const _Range&, const iterator_t<_Range>&) const
1229  { }
1230  };
1231 
1232  template<forward_range _Range>
1233  struct _CachedPosition<_Range>
1234  : protected __non_propagating_cache<iterator_t<_Range>>
1235  {
1236  constexpr bool
1237  _M_has_value() const
1238  { return this->_M_is_engaged(); }
1239 
1240  constexpr iterator_t<_Range>
1241  _M_get(const _Range&) const
1242  {
1243  __glibcxx_assert(_M_has_value());
1244  return **this;
1245  }
1246 
1247  constexpr void
1248  _M_set(const _Range&, const iterator_t<_Range>& __it)
1249  {
1250  __glibcxx_assert(!_M_has_value());
1251  std::construct_at(std::__addressof(this->_M_payload._M_payload),
1252  in_place, __it);
1253  this->_M_payload._M_engaged = true;
1254  }
1255  };
1256 
1257  template<random_access_range _Range>
1258  requires (sizeof(range_difference_t<_Range>)
1259  <= sizeof(iterator_t<_Range>))
1260  struct _CachedPosition<_Range>
1261  {
1262  private:
1263  range_difference_t<_Range> _M_offset = -1;
1264 
1265  public:
1266  _CachedPosition() = default;
1267 
1268  constexpr
1269  _CachedPosition(const _CachedPosition&) = default;
1270 
1271  constexpr
1272  _CachedPosition(_CachedPosition&& __other) noexcept
1273  { *this = std::move(__other); }
1274 
1275  constexpr _CachedPosition&
1276  operator=(const _CachedPosition&) = default;
1277 
1278  constexpr _CachedPosition&
1279  operator=(_CachedPosition&& __other) noexcept
1280  {
1281  // Propagate the cached offset, but invalidate the source.
1282  _M_offset = __other._M_offset;
1283  __other._M_offset = -1;
1284  return *this;
1285  }
1286 
1287  constexpr bool
1288  _M_has_value() const
1289  { return _M_offset >= 0; }
1290 
1291  constexpr iterator_t<_Range>
1292  _M_get(_Range& __r) const
1293  {
1294  __glibcxx_assert(_M_has_value());
1295  return ranges::begin(__r) + _M_offset;
1296  }
1297 
1298  constexpr void
1299  _M_set(_Range& __r, const iterator_t<_Range>& __it)
1300  {
1301  __glibcxx_assert(!_M_has_value());
1302  _M_offset = __it - ranges::begin(__r);
1303  }
1304  };
1305  } // namespace __detail
1306 
1307  namespace __detail
1308  {
1309  template<typename _Base>
1310  struct __filter_view_iter_cat
1311  { };
1312 
1313  template<forward_range _Base>
1314  struct __filter_view_iter_cat<_Base>
1315  {
1316  private:
1317  static auto
1318  _S_iter_cat()
1319  {
1320  using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
1321  if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
1322  return bidirectional_iterator_tag{};
1323  else if constexpr (derived_from<_Cat, forward_iterator_tag>)
1324  return forward_iterator_tag{};
1325  else
1326  return _Cat{};
1327  }
1328  public:
1329  using iterator_category = decltype(_S_iter_cat());
1330  };
1331  } // namespace __detail
1332 
1333  template<input_range _Vp,
1334  indirect_unary_predicate<iterator_t<_Vp>> _Pred>
1335  requires view<_Vp> && is_object_v<_Pred>
1336  class filter_view : public view_interface<filter_view<_Vp, _Pred>>
1337  {
1338  private:
1339  struct _Sentinel;
1340 
1341  struct _Iterator : __detail::__filter_view_iter_cat<_Vp>
1342  {
1343  private:
1344  static constexpr auto
1345  _S_iter_concept()
1346  {
1347  if constexpr (bidirectional_range<_Vp>)
1348  return bidirectional_iterator_tag{};
1349  else if constexpr (forward_range<_Vp>)
1350  return forward_iterator_tag{};
1351  else
1352  return input_iterator_tag{};
1353  }
1354 
1355  friend filter_view;
1356 
1357  using _Vp_iter = iterator_t<_Vp>;
1358 
1359  _Vp_iter _M_current = _Vp_iter();
1360  filter_view* _M_parent = nullptr;
1361 
1362  public:
1363  using iterator_concept = decltype(_S_iter_concept());
1364  // iterator_category defined in __filter_view_iter_cat
1365  using value_type = range_value_t<_Vp>;
1366  using difference_type = range_difference_t<_Vp>;
1367 
1368  _Iterator() = default;
1369 
1370  constexpr
1371  _Iterator(filter_view* __parent, _Vp_iter __current)
1372  : _M_current(std::move(__current)),
1373  _M_parent(__parent)
1374  { }
1375 
1376  constexpr const _Vp_iter&
1377  base() const & noexcept
1378  { return _M_current; }
1379 
1380  constexpr _Vp_iter
1381  base() &&
1382  { return std::move(_M_current); }
1383 
1384  constexpr range_reference_t<_Vp>
1385  operator*() const
1386  { return *_M_current; }
1387 
1388  constexpr _Vp_iter
1389  operator->() const
1390  requires __detail::__has_arrow<_Vp_iter>
1391  && copyable<_Vp_iter>
1392  { return _M_current; }
1393 
1394  constexpr _Iterator&
1395  operator++()
1396  {
1397  _M_current = __detail::find_if(std::move(++_M_current),
1398  ranges::end(_M_parent->_M_base),
1399  std::ref(*_M_parent->_M_pred));
1400  return *this;
1401  }
1402 
1403  constexpr void
1404  operator++(int)
1405  { ++*this; }
1406 
1407  constexpr _Iterator
1408  operator++(int) requires forward_range<_Vp>
1409  {
1410  auto __tmp = *this;
1411  ++*this;
1412  return __tmp;
1413  }
1414 
1415  constexpr _Iterator&
1416  operator--() requires bidirectional_range<_Vp>
1417  {
1418  do
1419  --_M_current;
1420  while (!std::__invoke(*_M_parent->_M_pred, *_M_current));
1421  return *this;
1422  }
1423 
1424  constexpr _Iterator
1425  operator--(int) requires bidirectional_range<_Vp>
1426  {
1427  auto __tmp = *this;
1428  --*this;
1429  return __tmp;
1430  }
1431 
1432  friend constexpr bool
1433  operator==(const _Iterator& __x, const _Iterator& __y)
1434  requires equality_comparable<_Vp_iter>
1435  { return __x._M_current == __y._M_current; }
1436 
1437  friend constexpr range_rvalue_reference_t<_Vp>
1438  iter_move(const _Iterator& __i)
1439  noexcept(noexcept(ranges::iter_move(__i._M_current)))
1440  { return ranges::iter_move(__i._M_current); }
1441 
1442  friend constexpr void
1443  iter_swap(const _Iterator& __x, const _Iterator& __y)
1444  noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1445  requires indirectly_swappable<_Vp_iter>
1446  { ranges::iter_swap(__x._M_current, __y._M_current); }
1447  };
1448 
1449  struct _Sentinel
1450  {
1451  private:
1452  sentinel_t<_Vp> _M_end = sentinel_t<_Vp>();
1453 
1454  constexpr bool
1455  __equal(const _Iterator& __i) const
1456  { return __i._M_current == _M_end; }
1457 
1458  public:
1459  _Sentinel() = default;
1460 
1461  constexpr explicit
1462  _Sentinel(filter_view* __parent)
1463  : _M_end(ranges::end(__parent->_M_base))
1464  { }
1465 
1466  constexpr sentinel_t<_Vp>
1467  base() const
1468  { return _M_end; }
1469 
1470  friend constexpr bool
1471  operator==(const _Iterator& __x, const _Sentinel& __y)
1472  { return __y.__equal(__x); }
1473  };
1474 
1475  [[no_unique_address]] __detail::__box<_Pred> _M_pred;
1476  [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
1477  _Vp _M_base = _Vp();
1478 
1479  public:
1480  filter_view() = default;
1481 
1482  constexpr
1483  filter_view(_Vp __base, _Pred __pred)
1484  : _M_pred(std::move(__pred)), _M_base(std::move(__base))
1485  { }
1486 
1487  constexpr _Vp
1488  base() const& requires copy_constructible<_Vp>
1489  { return _M_base; }
1490 
1491  constexpr _Vp
1492  base() &&
1493  { return std::move(_M_base); }
1494 
1495  constexpr const _Pred&
1496  pred() const
1497  { return *_M_pred; }
1498 
1499  constexpr _Iterator
1500  begin()
1501  {
1502  if (_M_cached_begin._M_has_value())
1503  return {this, _M_cached_begin._M_get(_M_base)};
1504 
1505  __glibcxx_assert(_M_pred.has_value());
1506  auto __it = __detail::find_if(ranges::begin(_M_base),
1507  ranges::end(_M_base),
1508  std::ref(*_M_pred));
1509  _M_cached_begin._M_set(_M_base, __it);
1510  return {this, std::move(__it)};
1511  }
1512 
1513  constexpr auto
1514  end()
1515  {
1516  if constexpr (common_range<_Vp>)
1517  return _Iterator{this, ranges::end(_M_base)};
1518  else
1519  return _Sentinel{this};
1520  }
1521  };
1522 
1523  template<typename _Range, typename _Pred>
1524  filter_view(_Range&&, _Pred) -> filter_view<views::all_t<_Range>, _Pred>;
1525 
1526  namespace views
1527  {
1528  namespace __detail
1529  {
1530  template<typename _Range, typename _Pred>
1531  concept __can_filter_view
1532  = requires { filter_view(std::declval<_Range>(), std::declval<_Pred>()); };
1533  } // namespace __detail
1534 
1535  struct _Filter : __adaptor::_RangeAdaptor<_Filter>
1536  {
1537  template<viewable_range _Range, typename _Pred>
1538  requires __detail::__can_filter_view<_Range, _Pred>
1539  constexpr auto
1540  operator()(_Range&& __r, _Pred&& __p) const
1541  {
1542  return filter_view(std::forward<_Range>(__r), std::forward<_Pred>(__p));
1543  }
1544 
1545  using _RangeAdaptor<_Filter>::operator();
1546  static constexpr int _S_arity = 2;
1547  static constexpr bool _S_has_simple_extra_args = true;
1548  };
1549 
1550  inline constexpr _Filter filter;
1551  } // namespace views
1552 
1553  template<input_range _Vp, copy_constructible _Fp>
1554  requires view<_Vp> && is_object_v<_Fp>
1555  && regular_invocable<_Fp&, range_reference_t<_Vp>>
1556  && std::__detail::__can_reference<invoke_result_t<_Fp&,
1557  range_reference_t<_Vp>>>
1558  class transform_view : public view_interface<transform_view<_Vp, _Fp>>
1559  {
1560  private:
1561  template<bool _Const>
1562  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1563 
1564  template<bool _Const>
1565  struct __iter_cat
1566  { };
1567 
1568  template<bool _Const>
1569  requires forward_range<_Base<_Const>>
1570  struct __iter_cat<_Const>
1571  {
1572  private:
1573  static auto
1574  _S_iter_cat()
1575  {
1576  using _Base = transform_view::_Base<_Const>;
1577  using _Res = invoke_result_t<_Fp&, range_reference_t<_Base>>;
1578  if constexpr (is_lvalue_reference_v<_Res>)
1579  {
1580  using _Cat
1581  = typename iterator_traits<iterator_t<_Base>>::iterator_category;
1582  if constexpr (derived_from<_Cat, contiguous_iterator_tag>)
1583  return random_access_iterator_tag{};
1584  else
1585  return _Cat{};
1586  }
1587  else
1588  return input_iterator_tag{};
1589  }
1590  public:
1591  using iterator_category = decltype(_S_iter_cat());
1592  };
1593 
1594  template<bool _Const>
1595  struct _Sentinel;
1596 
1597  template<bool _Const>
1598  struct _Iterator : __iter_cat<_Const>
1599  {
1600  private:
1601  using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1602  using _Base = transform_view::_Base<_Const>;
1603 
1604  static auto
1605  _S_iter_concept()
1606  {
1607  if constexpr (random_access_range<_Vp>)
1608  return random_access_iterator_tag{};
1609  else if constexpr (bidirectional_range<_Vp>)
1610  return bidirectional_iterator_tag{};
1611  else if constexpr (forward_range<_Vp>)
1612  return forward_iterator_tag{};
1613  else
1614  return input_iterator_tag{};
1615  }
1616 
1617  using _Base_iter = iterator_t<_Base>;
1618 
1619  _Base_iter _M_current = _Base_iter();
1620  _Parent* _M_parent = nullptr;
1621 
1622  public:
1623  using iterator_concept = decltype(_S_iter_concept());
1624  // iterator_category defined in __transform_view_iter_cat
1625  using value_type
1626  = remove_cvref_t<invoke_result_t<_Fp&, range_reference_t<_Base>>>;
1627  using difference_type = range_difference_t<_Base>;
1628 
1629  _Iterator() = default;
1630 
1631  constexpr
1632  _Iterator(_Parent* __parent, _Base_iter __current)
1633  : _M_current(std::move(__current)),
1634  _M_parent(__parent)
1635  { }
1636 
1637  constexpr
1638  _Iterator(_Iterator<!_Const> __i)
1639  requires _Const
1640  && convertible_to<iterator_t<_Vp>, _Base_iter>
1641  : _M_current(std::move(__i._M_current)), _M_parent(__i._M_parent)
1642  { }
1643 
1644  constexpr const _Base_iter&
1645  base() const & noexcept
1646  { return _M_current; }
1647 
1648  constexpr _Base_iter
1649  base() &&
1650  { return std::move(_M_current); }
1651 
1652  constexpr decltype(auto)
1653  operator*() const
1654  noexcept(noexcept(std::__invoke(*_M_parent->_M_fun, *_M_current)))
1655  { return std::__invoke(*_M_parent->_M_fun, *_M_current); }
1656 
1657  constexpr _Iterator&
1658  operator++()
1659  {
1660  ++_M_current;
1661  return *this;
1662  }
1663 
1664  constexpr void
1665  operator++(int)
1666  { ++_M_current; }
1667 
1668  constexpr _Iterator
1669  operator++(int) requires forward_range<_Base>
1670  {
1671  auto __tmp = *this;
1672  ++*this;
1673  return __tmp;
1674  }
1675 
1676  constexpr _Iterator&
1677  operator--() requires bidirectional_range<_Base>
1678  {
1679  --_M_current;
1680  return *this;
1681  }
1682 
1683  constexpr _Iterator
1684  operator--(int) requires bidirectional_range<_Base>
1685  {
1686  auto __tmp = *this;
1687  --*this;
1688  return __tmp;
1689  }
1690 
1691  constexpr _Iterator&
1692  operator+=(difference_type __n) requires random_access_range<_Base>
1693  {
1694  _M_current += __n;
1695  return *this;
1696  }
1697 
1698  constexpr _Iterator&
1699  operator-=(difference_type __n) requires random_access_range<_Base>
1700  {
1701  _M_current -= __n;
1702  return *this;
1703  }
1704 
1705  constexpr decltype(auto)
1706  operator[](difference_type __n) const
1707  requires random_access_range<_Base>
1708  { return std::__invoke(*_M_parent->_M_fun, _M_current[__n]); }
1709 
1710  friend constexpr bool
1711  operator==(const _Iterator& __x, const _Iterator& __y)
1712  requires equality_comparable<_Base_iter>
1713  { return __x._M_current == __y._M_current; }
1714 
1715  friend constexpr bool
1716  operator<(const _Iterator& __x, const _Iterator& __y)
1717  requires random_access_range<_Base>
1718  { return __x._M_current < __y._M_current; }
1719 
1720  friend constexpr bool
1721  operator>(const _Iterator& __x, const _Iterator& __y)
1722  requires random_access_range<_Base>
1723  { return __y < __x; }
1724 
1725  friend constexpr bool
1726  operator<=(const _Iterator& __x, const _Iterator& __y)
1727  requires random_access_range<_Base>
1728  { return !(__y < __x); }
1729 
1730  friend constexpr bool
1731  operator>=(const _Iterator& __x, const _Iterator& __y)
1732  requires random_access_range<_Base>
1733  { return !(__x < __y); }
1734 
1735 #ifdef __cpp_lib_three_way_comparison
1736  friend constexpr auto
1737  operator<=>(const _Iterator& __x, const _Iterator& __y)
1738  requires random_access_range<_Base>
1739  && three_way_comparable<_Base_iter>
1740  { return __x._M_current <=> __y._M_current; }
1741 #endif
1742 
1743  friend constexpr _Iterator
1744  operator+(_Iterator __i, difference_type __n)
1745  requires random_access_range<_Base>
1746  { return {__i._M_parent, __i._M_current + __n}; }
1747 
1748  friend constexpr _Iterator
1749  operator+(difference_type __n, _Iterator __i)
1750  requires random_access_range<_Base>
1751  { return {__i._M_parent, __i._M_current + __n}; }
1752 
1753  friend constexpr _Iterator
1754  operator-(_Iterator __i, difference_type __n)
1755  requires random_access_range<_Base>
1756  { return {__i._M_parent, __i._M_current - __n}; }
1757 
1758  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1759  // 3483. transform_view::iterator's difference is overconstrained
1760  friend constexpr difference_type
1761  operator-(const _Iterator& __x, const _Iterator& __y)
1762  requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
1763  { return __x._M_current - __y._M_current; }
1764 
1765  friend constexpr decltype(auto)
1766  iter_move(const _Iterator& __i) noexcept(noexcept(*__i))
1767  {
1768  if constexpr (is_lvalue_reference_v<decltype(*__i)>)
1769  return std::move(*__i);
1770  else
1771  return *__i;
1772  }
1773 
1774  friend _Iterator<!_Const>;
1775  template<bool> friend struct _Sentinel;
1776  };
1777 
1778  template<bool _Const>
1779  struct _Sentinel
1780  {
1781  private:
1782  using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1783  using _Base = transform_view::_Base<_Const>;
1784 
1785  template<bool _Const2>
1786  constexpr auto
1787  __distance_from(const _Iterator<_Const2>& __i) const
1788  { return _M_end - __i._M_current; }
1789 
1790  template<bool _Const2>
1791  constexpr bool
1792  __equal(const _Iterator<_Const2>& __i) const
1793  { return __i._M_current == _M_end; }
1794 
1795  sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1796 
1797  public:
1798  _Sentinel() = default;
1799 
1800  constexpr explicit
1801  _Sentinel(sentinel_t<_Base> __end)
1802  : _M_end(__end)
1803  { }
1804 
1805  constexpr
1806  _Sentinel(_Sentinel<!_Const> __i)
1807  requires _Const
1808  && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1809  : _M_end(std::move(__i._M_end))
1810  { }
1811 
1812  constexpr sentinel_t<_Base>
1813  base() const
1814  { return _M_end; }
1815 
1816  template<bool _Const2>
1817  requires sentinel_for<sentinel_t<_Base>,
1818  iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
1819  friend constexpr bool
1820  operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
1821  { return __y.__equal(__x); }
1822 
1823  template<bool _Const2,
1824  typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
1825  requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1826  friend constexpr range_difference_t<_Base2>
1827  operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
1828  { return -__y.__distance_from(__x); }
1829 
1830  template<bool _Const2,
1831  typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
1832  requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1833  friend constexpr range_difference_t<_Base2>
1834  operator-(const _Sentinel& __y, const _Iterator<_Const2>& __x)
1835  { return __y.__distance_from(__x); }
1836 
1837  friend _Sentinel<!_Const>;
1838  };
1839 
1840  [[no_unique_address]] __detail::__box<_Fp> _M_fun;
1841  _Vp _M_base = _Vp();
1842 
1843  public:
1844  transform_view() = default;
1845 
1846  constexpr
1847  transform_view(_Vp __base, _Fp __fun)
1848  : _M_fun(std::move(__fun)), _M_base(std::move(__base))
1849  { }
1850 
1851  constexpr _Vp
1852  base() const& requires copy_constructible<_Vp>
1853  { return _M_base ; }
1854 
1855  constexpr _Vp
1856  base() &&
1857  { return std::move(_M_base); }
1858 
1859  constexpr _Iterator<false>
1860  begin()
1861  { return _Iterator<false>{this, ranges::begin(_M_base)}; }
1862 
1863  constexpr _Iterator<true>
1864  begin() const
1865  requires range<const _Vp>
1866  && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1867  { return _Iterator<true>{this, ranges::begin(_M_base)}; }
1868 
1869  constexpr _Sentinel<false>
1870  end()
1871  { return _Sentinel<false>{ranges::end(_M_base)}; }
1872 
1873  constexpr _Iterator<false>
1874  end() requires common_range<_Vp>
1875  { return _Iterator<false>{this, ranges::end(_M_base)}; }
1876 
1877  constexpr _Sentinel<true>
1878  end() const
1879  requires range<const _Vp>
1880  && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1881  { return _Sentinel<true>{ranges::end(_M_base)}; }
1882 
1883  constexpr _Iterator<true>
1884  end() const
1885  requires common_range<const _Vp>
1886  && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1887  { return _Iterator<true>{this, ranges::end(_M_base)}; }
1888 
1889  constexpr auto
1890  size() requires sized_range<_Vp>
1891  { return ranges::size(_M_base); }
1892 
1893  constexpr auto
1894  size() const requires sized_range<const _Vp>
1895  { return ranges::size(_M_base); }
1896  };
1897 
1898  template<typename _Range, typename _Fp>
1899  transform_view(_Range&&, _Fp) -> transform_view<views::all_t<_Range>, _Fp>;
1900 
1901  namespace views
1902  {
1903  namespace __detail
1904  {
1905  template<typename _Range, typename _Fp>
1906  concept __can_transform_view
1907  = requires { transform_view(std::declval<_Range>(), std::declval<_Fp>()); };
1908  } // namespace __detail
1909 
1910  struct _Transform : __adaptor::_RangeAdaptor<_Transform>
1911  {
1912  template<viewable_range _Range, typename _Fp>
1913  requires __detail::__can_transform_view<_Range, _Fp>
1914  constexpr auto
1915  operator()(_Range&& __r, _Fp&& __f) const
1916  {
1917  return transform_view(std::forward<_Range>(__r), std::forward<_Fp>(__f));
1918  }
1919 
1920  using _RangeAdaptor<_Transform>::operator();
1921  static constexpr int _S_arity = 2;
1922  static constexpr bool _S_has_simple_extra_args = true;
1923  };
1924 
1925  inline constexpr _Transform transform;
1926  } // namespace views
1927 
1928  template<view _Vp>
1929  class take_view : public view_interface<take_view<_Vp>>
1930  {
1931  private:
1932  template<bool _Const>
1933  using _CI = counted_iterator<
1934  iterator_t<__detail::__maybe_const_t<_Const, _Vp>>>;
1935 
1936  template<bool _Const>
1937  struct _Sentinel
1938  {
1939  private:
1940  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1941  sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1942 
1943  public:
1944  _Sentinel() = default;
1945 
1946  constexpr explicit
1947  _Sentinel(sentinel_t<_Base> __end)
1948  : _M_end(__end)
1949  { }
1950 
1951  constexpr
1952  _Sentinel(_Sentinel<!_Const> __s)
1953  requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1954  : _M_end(std::move(__s._M_end))
1955  { }
1956 
1957  constexpr sentinel_t<_Base>
1958  base() const
1959  { return _M_end; }
1960 
1961  friend constexpr bool
1962  operator==(const _CI<_Const>& __y, const _Sentinel& __x)
1963  { return __y.count() == 0 || __y.base() == __x._M_end; }
1964 
1965  template<bool _OtherConst = !_Const,
1966  typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
1967  requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1968  friend constexpr bool
1969  operator==(const _CI<_OtherConst>& __y, const _Sentinel& __x)
1970  { return __y.count() == 0 || __y.base() == __x._M_end; }
1971 
1972  friend _Sentinel<!_Const>;
1973  };
1974 
1975  range_difference_t<_Vp> _M_count = 0;
1976  _Vp _M_base = _Vp();
1977 
1978  public:
1979  take_view() = default;
1980 
1981  constexpr
1982  take_view(_Vp base, range_difference_t<_Vp> __count)
1983  : _M_count(std::move(__count)), _M_base(std::move(base))
1984  { }
1985 
1986  constexpr _Vp
1987  base() const& requires copy_constructible<_Vp>
1988  { return _M_base; }
1989 
1990  constexpr _Vp
1991  base() &&
1992  { return std::move(_M_base); }
1993 
1994  constexpr auto
1995  begin() requires (!__detail::__simple_view<_Vp>)
1996  {
1997  if constexpr (sized_range<_Vp>)
1998  {
1999  if constexpr (random_access_range<_Vp>)
2000  return ranges::begin(_M_base);
2001  else
2002  {
2003  auto __sz = size();
2004  return counted_iterator(ranges::begin(_M_base), __sz);
2005  }
2006  }
2007  else
2008  return counted_iterator(ranges::begin(_M_base), _M_count);
2009  }
2010 
2011  constexpr auto
2012  begin() const requires range<const _Vp>
2013  {
2014  if constexpr (sized_range<const _Vp>)
2015  {
2016  if constexpr (random_access_range<const _Vp>)
2017  return ranges::begin(_M_base);
2018  else
2019  {
2020  auto __sz = size();
2021  return counted_iterator(ranges::begin(_M_base), __sz);
2022  }
2023  }
2024  else
2025  return counted_iterator(ranges::begin(_M_base), _M_count);
2026  }
2027 
2028  constexpr auto
2029  end() requires (!__detail::__simple_view<_Vp>)
2030  {
2031  if constexpr (sized_range<_Vp>)
2032  {
2033  if constexpr (random_access_range<_Vp>)
2034  return ranges::begin(_M_base) + size();
2035  else
2036  return default_sentinel;
2037  }
2038  else
2039  return _Sentinel<false>{ranges::end(_M_base)};
2040  }
2041 
2042  constexpr auto
2043  end() const requires range<const _Vp>
2044  {
2045  if constexpr (sized_range<const _Vp>)
2046  {
2047  if constexpr (random_access_range<const _Vp>)
2048  return ranges::begin(_M_base) + size();
2049  else
2050  return default_sentinel;
2051  }
2052  else
2053  return _Sentinel<true>{ranges::end(_M_base)};
2054  }
2055 
2056  constexpr auto
2057  size() requires sized_range<_Vp>
2058  {
2059  auto __n = ranges::size(_M_base);
2060  return std::min(__n, static_cast<decltype(__n)>(_M_count));
2061  }
2062 
2063  constexpr auto
2064  size() const requires sized_range<const _Vp>
2065  {
2066  auto __n = ranges::size(_M_base);
2067  return std::min(__n, static_cast<decltype(__n)>(_M_count));
2068  }
2069  };
2070 
2071  // _GLIBCXX_RESOLVE_LIB_DEFECTS
2072  // 3447. Deduction guides for take_view and drop_view have different
2073  // constraints
2074  template<typename _Range>
2075  take_view(_Range&&, range_difference_t<_Range>)
2076  -> take_view<views::all_t<_Range>>;
2077 
2078  template<typename _Tp>
2079  inline constexpr bool enable_borrowed_range<take_view<_Tp>>
2080  = enable_borrowed_range<_Tp>;
2081 
2082  namespace views
2083  {
2084  namespace __detail
2085  {
2086  template<typename _Range, typename _Tp>
2087  concept __can_take_view
2088  = requires { take_view(std::declval<_Range>(), std::declval<_Tp>()); };
2089  } // namespace __detail
2090 
2091  struct _Take : __adaptor::_RangeAdaptor<_Take>
2092  {
2093  template<viewable_range _Range, typename _Tp>
2094  requires __detail::__can_take_view<_Range, _Tp>
2095  constexpr auto
2096  operator()(_Range&& __r, _Tp&& __n) const
2097  {
2098  return take_view(std::forward<_Range>(__r), std::forward<_Tp>(__n));
2099  }
2100 
2101  using _RangeAdaptor<_Take>::operator();
2102  static constexpr int _S_arity = 2;
2103  // The count argument of views::take is not always simple -- it can be
2104  // e.g. a move-only class that's implicitly convertible to the difference
2105  // type. But an integer-like count argument is surely simple.
2106  template<typename _Tp>
2107  static constexpr bool _S_has_simple_extra_args
2108  = ranges::__detail::__is_integer_like<_Tp>;
2109  };
2110 
2111  inline constexpr _Take take;
2112  } // namespace views
2113 
2114  template<view _Vp, typename _Pred>
2115  requires input_range<_Vp> && is_object_v<_Pred>
2116  && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2117  class take_while_view : public view_interface<take_while_view<_Vp, _Pred>>
2118  {
2119  template<bool _Const>
2120  struct _Sentinel
2121  {
2122  private:
2123  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2124 
2125  sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2126  const _Pred* _M_pred = nullptr;
2127 
2128  public:
2129  _Sentinel() = default;
2130 
2131  constexpr explicit
2132  _Sentinel(sentinel_t<_Base> __end, const _Pred* __pred)
2133  : _M_end(__end), _M_pred(__pred)
2134  { }
2135 
2136  constexpr
2137  _Sentinel(_Sentinel<!_Const> __s)
2138  requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2139  : _M_end(__s._M_end), _M_pred(__s._M_pred)
2140  { }
2141 
2142  constexpr sentinel_t<_Base>
2143  base() const { return _M_end; }
2144 
2145  friend constexpr bool
2146  operator==(const iterator_t<_Base>& __x, const _Sentinel& __y)
2147  { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
2148 
2149  template<bool _OtherConst = !_Const,
2150  typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
2151  requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
2152  friend constexpr bool
2153  operator==(const iterator_t<_Base2>& __x, const _Sentinel& __y)
2154  { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
2155 
2156  friend _Sentinel<!_Const>;
2157  };
2158 
2159  [[no_unique_address]] __detail::__box<_Pred> _M_pred;
2160  _Vp _M_base = _Vp();
2161 
2162  public:
2163  take_while_view() = default;
2164 
2165  constexpr
2166  take_while_view(_Vp base, _Pred __pred)
2167  : _M_pred(std::move(__pred)), _M_base(std::move(base))
2168  { }
2169 
2170  constexpr _Vp
2171  base() const& requires copy_constructible<_Vp>
2172  { return _M_base; }
2173 
2174  constexpr _Vp
2175  base() &&
2176  { return std::move(_M_base); }
2177 
2178  constexpr const _Pred&
2179  pred() const
2180  { return *_M_pred; }
2181 
2182  constexpr auto
2183  begin() requires (!__detail::__simple_view<_Vp>)
2184  { return ranges::begin(_M_base); }
2185 
2186  constexpr auto
2187  begin() const requires range<const _Vp>
2188  && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
2189  { return ranges::begin(_M_base); }
2190 
2191  constexpr auto
2192  end() requires (!__detail::__simple_view<_Vp>)
2193  { return _Sentinel<false>(ranges::end(_M_base),
2194  std::__addressof(*_M_pred)); }
2195 
2196  constexpr auto
2197  end() const requires range<const _Vp>
2198  && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
2199  { return _Sentinel<true>(ranges::end(_M_base),
2200  std::__addressof(*_M_pred)); }
2201  };
2202 
2203  template<typename _Range, typename _Pred>
2204  take_while_view(_Range&&, _Pred)
2205  -> take_while_view<views::all_t<_Range>, _Pred>;
2206 
2207  namespace views
2208  {
2209  namespace __detail
2210  {
2211  template<typename _Range, typename _Pred>
2212  concept __can_take_while_view
2213  = requires { take_while_view(std::declval<_Range>(), std::declval<_Pred>()); };
2214  } // namespace __detail
2215 
2216  struct _TakeWhile : __adaptor::_RangeAdaptor<_TakeWhile>
2217  {
2218  template<viewable_range _Range, typename _Pred>
2219  requires __detail::__can_take_while_view<_Range, _Pred>
2220  constexpr auto
2221  operator()(_Range&& __r, _Pred&& __p) const
2222  {
2223  return take_while_view(std::forward<_Range>(__r), std::forward<_Pred>(__p));
2224  }
2225 
2226  using _RangeAdaptor<_TakeWhile>::operator();
2227  static constexpr int _S_arity = 2;
2228  static constexpr bool _S_has_simple_extra_args = true;
2229  };
2230 
2231  inline constexpr _TakeWhile take_while;
2232  } // namespace views
2233 
2234  template<view _Vp>
2235  class drop_view : public view_interface<drop_view<_Vp>>
2236  {
2237  private:
2238  range_difference_t<_Vp> _M_count = 0;
2239  _Vp _M_base = _Vp();
2240 
2241  // ranges::next(begin(base), count, end(base)) is O(1) if _Vp satisfies
2242  // both random_access_range and sized_range. Otherwise, cache its result.
2243  static constexpr bool _S_needs_cached_begin
2244  = !(random_access_range<const _Vp> && sized_range<const _Vp>);
2245  [[no_unique_address]]
2246  __detail::__maybe_present_t<_S_needs_cached_begin,
2247  __detail::_CachedPosition<_Vp>>
2248  _M_cached_begin;
2249 
2250  public:
2251  drop_view() = default;
2252 
2253  constexpr
2254  drop_view(_Vp __base, range_difference_t<_Vp> __count)
2255  : _M_count(__count), _M_base(std::move(__base))
2256  { __glibcxx_assert(__count >= 0); }
2257 
2258  constexpr _Vp
2259  base() const& requires copy_constructible<_Vp>
2260  { return _M_base; }
2261 
2262  constexpr _Vp
2263  base() &&
2264  { return std::move(_M_base); }
2265 
2266  // This overload is disabled for simple views with constant-time begin().
2267  constexpr auto
2268  begin()
2269  requires (!(__detail::__simple_view<_Vp>
2270  && random_access_range<const _Vp>
2271  && sized_range<const _Vp>))
2272  {
2273  if constexpr (_S_needs_cached_begin)
2274  if (_M_cached_begin._M_has_value())
2275  return _M_cached_begin._M_get(_M_base);
2276 
2277  auto __it = ranges::next(ranges::begin(_M_base),
2278  _M_count, ranges::end(_M_base));
2279  if constexpr (_S_needs_cached_begin)
2280  _M_cached_begin._M_set(_M_base, __it);
2281  return __it;
2282  }
2283 
2284  // _GLIBCXX_RESOLVE_LIB_DEFECTS
2285  // 3482. drop_view's const begin should additionally require sized_range
2286  constexpr auto
2287  begin() const
2288  requires random_access_range<const _Vp> && sized_range<const _Vp>
2289  {
2290  return ranges::next(ranges::begin(_M_base), _M_count,
2291  ranges::end(_M_base));
2292  }
2293 
2294  constexpr auto
2295  end() requires (!__detail::__simple_view<_Vp>)
2296  { return ranges::end(_M_base); }
2297 
2298  constexpr auto
2299  end() const requires range<const _Vp>
2300  { return ranges::end(_M_base); }
2301 
2302  constexpr auto
2303  size() requires sized_range<_Vp>
2304  {
2305  const auto __s = ranges::size(_M_base);
2306  const auto __c = static_cast<decltype(__s)>(_M_count);
2307  return __s < __c ? 0 : __s - __c;
2308  }
2309 
2310  constexpr auto
2311  size() const requires sized_range<const _Vp>
2312  {
2313  const auto __s = ranges::size(_M_base);
2314  const auto __c = static_cast<decltype(__s)>(_M_count);
2315  return __s < __c ? 0 : __s - __c;
2316  }
2317  };
2318 
2319  template<typename _Range>
2320  drop_view(_Range&&, range_difference_t<_Range>)
2321  -> drop_view<views::all_t<_Range>>;
2322 
2323  template<typename _Tp>
2324  inline constexpr bool enable_borrowed_range<drop_view<_Tp>>
2325  = enable_borrowed_range<_Tp>;
2326 
2327  namespace views
2328  {
2329  namespace __detail
2330  {
2331  template<typename _Range, typename _Tp>
2332  concept __can_drop_view
2333  = requires { drop_view(std::declval<_Range>(), std::declval<_Tp>()); };
2334  } // namespace __detail
2335 
2336  struct _Drop : __adaptor::_RangeAdaptor<_Drop>
2337  {
2338  template<viewable_range _Range, typename _Tp>
2339  requires __detail::__can_drop_view<_Range, _Tp>
2340  constexpr auto
2341  operator()(_Range&& __r, _Tp&& __n) const
2342  {
2343  return drop_view(std::forward<_Range>(__r), std::forward<_Tp>(__n));
2344  }
2345 
2346  using _RangeAdaptor<_Drop>::operator();
2347  static constexpr int _S_arity = 2;
2348  template<typename _Tp>
2349  static constexpr bool _S_has_simple_extra_args
2350  = _Take::_S_has_simple_extra_args<_Tp>;
2351  };
2352 
2353  inline constexpr _Drop drop;
2354  } // namespace views
2355 
2356  template<view _Vp, typename _Pred>
2357  requires input_range<_Vp> && is_object_v<_Pred>
2358  && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2359  class drop_while_view : public view_interface<drop_while_view<_Vp, _Pred>>
2360  {
2361  private:
2362  [[no_unique_address]] __detail::__box<_Pred> _M_pred;
2363  [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
2364  _Vp _M_base = _Vp();
2365 
2366  public:
2367  drop_while_view() = default;
2368 
2369  constexpr
2370  drop_while_view(_Vp __base, _Pred __pred)
2371  : _M_pred(std::move(__pred)), _M_base(std::move(__base))
2372  { }
2373 
2374  constexpr _Vp
2375  base() const& requires copy_constructible<_Vp>
2376  { return _M_base; }
2377 
2378  constexpr _Vp
2379  base() &&
2380  { return std::move(_M_base); }
2381 
2382  constexpr const _Pred&
2383  pred() const
2384  { return *_M_pred; }
2385 
2386  constexpr auto
2387  begin()
2388  {
2389  if (_M_cached_begin._M_has_value())
2390  return _M_cached_begin._M_get(_M_base);
2391 
2392  auto __it = __detail::find_if_not(ranges::begin(_M_base),
2393  ranges::end(_M_base),
2394  std::cref(*_M_pred));
2395  _M_cached_begin._M_set(_M_base, __it);
2396  return __it;
2397  }
2398 
2399  constexpr auto
2400  end()
2401  { return ranges::end(_M_base); }
2402  };
2403 
2404  template<typename _Range, typename _Pred>
2405  drop_while_view(_Range&&, _Pred)
2406  -> drop_while_view<views::all_t<_Range>, _Pred>;
2407 
2408  template<typename _Tp, typename _Pred>
2409  inline constexpr bool enable_borrowed_range<drop_while_view<_Tp, _Pred>>
2410  = enable_borrowed_range<_Tp>;
2411 
2412  namespace views
2413  {
2414  namespace __detail
2415  {
2416  template<typename _Range, typename _Pred>
2417  concept __can_drop_while_view
2418  = requires { drop_while_view(std::declval<_Range>(), std::declval<_Pred>()); };
2419  } // namespace __detail
2420 
2421  struct _DropWhile : __adaptor::_RangeAdaptor<_DropWhile>
2422  {
2423  template<viewable_range _Range, typename _Pred>
2424  requires __detail::__can_drop_while_view<_Range, _Pred>
2425  constexpr auto
2426  operator()(_Range&& __r, _Pred&& __p) const
2427  {
2428  return drop_while_view(std::forward<_Range>(__r),
2429  std::forward<_Pred>(__p));
2430  }
2431 
2432  using _RangeAdaptor<_DropWhile>::operator();
2433  static constexpr int _S_arity = 2;
2434  static constexpr bool _S_has_simple_extra_args = true;
2435  };
2436 
2437  inline constexpr _DropWhile drop_while;
2438  } // namespace views
2439 
2440  template<input_range _Vp>
2441  requires view<_Vp> && input_range<range_reference_t<_Vp>>
2442  class join_view : public view_interface<join_view<_Vp>>
2443  {
2444  private:
2445  using _InnerRange = range_reference_t<_Vp>;
2446 
2447  template<bool _Const>
2448  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2449 
2450  template<bool _Const>
2451  using _Outer_iter = iterator_t<_Base<_Const>>;
2452 
2453  template<bool _Const>
2454  using _Inner_iter = iterator_t<range_reference_t<_Base<_Const>>>;
2455 
2456  template<bool _Const>
2457  static constexpr bool _S_ref_is_glvalue
2458  = is_reference_v<range_reference_t<_Base<_Const>>>;
2459 
2460  template<bool _Const>
2461  struct __iter_cat
2462  { };
2463 
2464  template<bool _Const>
2465  requires _S_ref_is_glvalue<_Const>
2466  && forward_range<_Base<_Const>>
2467  && forward_range<range_reference_t<_Base<_Const>>>
2468  struct __iter_cat<_Const>
2469  {
2470  private:
2471  static constexpr auto
2472  _S_iter_cat()
2473  {
2474  using _Outer_iter = join_view::_Outer_iter<_Const>;
2475  using _Inner_iter = join_view::_Inner_iter<_Const>;
2476  using _OuterCat = typename iterator_traits<_Outer_iter>::iterator_category;
2477  using _InnerCat = typename iterator_traits<_Inner_iter>::iterator_category;
2478  if constexpr (derived_from<_OuterCat, bidirectional_iterator_tag>
2479  && derived_from<_InnerCat, bidirectional_iterator_tag>)
2480  return bidirectional_iterator_tag{};
2481  else if constexpr (derived_from<_OuterCat, forward_iterator_tag>
2482  && derived_from<_InnerCat, forward_iterator_tag>)
2483  return forward_iterator_tag{};
2484  else
2485  return input_iterator_tag{};
2486  }
2487  public:
2488  using iterator_category = decltype(_S_iter_cat());
2489  };
2490 
2491  template<bool _Const>
2492  struct _Sentinel;
2493 
2494  template<bool _Const>
2495  struct _Iterator : __iter_cat<_Const>
2496  {
2497  private:
2498  using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2499  using _Base = join_view::_Base<_Const>;
2500 
2501  static constexpr bool _S_ref_is_glvalue
2502  = join_view::_S_ref_is_glvalue<_Const>;
2503 
2504  constexpr void
2505  _M_satisfy()
2506  {
2507  auto __update_inner = [this] (const iterator_t<_Base>& __x) -> auto&& {
2508  if constexpr (_S_ref_is_glvalue)
2509  return *__x;
2510  else
2511  return _M_parent->_M_inner._M_emplace_deref(__x);
2512  };
2513 
2514  for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer)
2515  {
2516  auto&& __inner = __update_inner(_M_outer);
2517  _M_inner = ranges::begin(__inner);
2518  if (_M_inner != ranges::end(__inner))
2519  return;
2520  }
2521 
2522  if constexpr (_S_ref_is_glvalue)
2523  _M_inner = _Inner_iter();
2524  }
2525 
2526  static constexpr auto
2527  _S_iter_concept()
2528  {
2529  if constexpr (_S_ref_is_glvalue
2530  && bidirectional_range<_Base>
2531  && bidirectional_range<range_reference_t<_Base>>)
2532  return bidirectional_iterator_tag{};
2533  else if constexpr (_S_ref_is_glvalue
2534  && forward_range<_Base>
2535  && forward_range<range_reference_t<_Base>>)
2536  return forward_iterator_tag{};
2537  else
2538  return input_iterator_tag{};
2539  }
2540 
2541  using _Outer_iter = join_view::_Outer_iter<_Const>;
2542  using _Inner_iter = join_view::_Inner_iter<_Const>;
2543 
2544  _Outer_iter _M_outer = _Outer_iter();
2545  _Inner_iter _M_inner = _Inner_iter();
2546  _Parent* _M_parent = nullptr;
2547 
2548  public:
2549  using iterator_concept = decltype(_S_iter_concept());
2550  // iterator_category defined in __join_view_iter_cat
2551  using value_type = range_value_t<range_reference_t<_Base>>;
2552  using difference_type
2553  = common_type_t<range_difference_t<_Base>,
2554  range_difference_t<range_reference_t<_Base>>>;
2555 
2556  _Iterator() = default;
2557 
2558  constexpr
2559  _Iterator(_Parent* __parent, _Outer_iter __outer)
2560  : _M_outer(std::move(__outer)),
2561  _M_parent(__parent)
2562  { _M_satisfy(); }
2563 
2564  constexpr
2565  _Iterator(_Iterator<!_Const> __i)
2566  requires _Const
2567  && convertible_to<iterator_t<_Vp>, _Outer_iter>
2568  && convertible_to<iterator_t<_InnerRange>, _Inner_iter>
2569  : _M_outer(std::move(__i._M_outer)), _M_inner(__i._M_inner),
2570  _M_parent(__i._M_parent)
2571  { }
2572 
2573  constexpr decltype(auto)
2574  operator*() const
2575  { return *_M_inner; }
2576 
2577  // _GLIBCXX_RESOLVE_LIB_DEFECTS
2578  // 3500. join_view::iterator::operator->() is bogus
2579  constexpr _Inner_iter
2580  operator->() const
2581  requires __detail::__has_arrow<_Inner_iter>
2582  && copyable<_Inner_iter>
2583  { return _M_inner; }
2584 
2585  constexpr _Iterator&
2586  operator++()
2587  {
2588  auto&& __inner_range = [this] () -> auto&& {
2589  if constexpr (_S_ref_is_glvalue)
2590  return *_M_outer;
2591  else
2592  return *_M_parent->_M_inner;
2593  }();
2594  if (++_M_inner == ranges::end(__inner_range))
2595  {
2596  ++_M_outer;
2597  _M_satisfy();
2598  }
2599  return *this;
2600  }
2601 
2602  constexpr void
2603  operator++(int)
2604  { ++*this; }
2605 
2606  constexpr _Iterator
2607  operator++(int)
2608  requires _S_ref_is_glvalue && forward_range<_Base>
2609  && forward_range<range_reference_t<_Base>>
2610  {
2611  auto __tmp = *this;
2612  ++*this;
2613  return __tmp;
2614  }
2615 
2616  constexpr _Iterator&
2617  operator--()
2618  requires _S_ref_is_glvalue && bidirectional_range<_Base>
2619  && bidirectional_range<range_reference_t<_Base>>
2620  && common_range<range_reference_t<_Base>>
2621  {
2622  if (_M_outer == ranges::end(_M_parent->_M_base))
2623  _M_inner = ranges::end(*--_M_outer);
2624  while (_M_inner == ranges::begin(*_M_outer))
2625  _M_inner = ranges::end(*--_M_outer);
2626  --_M_inner;
2627  return *this;
2628  }
2629 
2630  constexpr _Iterator
2631  operator--(int)
2632  requires _S_ref_is_glvalue && bidirectional_range<_Base>
2633  && bidirectional_range<range_reference_t<_Base>>
2634  && common_range<range_reference_t<_Base>>
2635  {
2636  auto __tmp = *this;
2637  --*this;
2638  return __tmp;
2639  }
2640 
2641  friend constexpr bool
2642  operator==(const _Iterator& __x, const _Iterator& __y)
2643  requires _S_ref_is_glvalue
2644  && equality_comparable<_Outer_iter>
2645  && equality_comparable<_Inner_iter>
2646  {
2647  return (__x._M_outer == __y._M_outer
2648  && __x._M_inner == __y._M_inner);
2649  }
2650 
2651  friend constexpr decltype(auto)
2652  iter_move(const _Iterator& __i)
2653  noexcept(noexcept(ranges::iter_move(__i._M_inner)))
2654  { return ranges::iter_move(__i._M_inner); }
2655 
2656  friend constexpr void
2657  iter_swap(const _Iterator& __x, const _Iterator& __y)
2658  noexcept(noexcept(ranges::iter_swap(__x._M_inner, __y._M_inner)))
2659  requires indirectly_swappable<_Inner_iter>
2660  { return ranges::iter_swap(__x._M_inner, __y._M_inner); }
2661 
2662  friend _Iterator<!_Const>;
2663  template<bool> friend struct _Sentinel;
2664  };
2665 
2666  template<bool _Const>
2667  struct _Sentinel
2668  {
2669  private:
2670  using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2671  using _Base = join_view::_Base<_Const>;
2672 
2673  template<bool _Const2>
2674  constexpr bool
2675  __equal(const _Iterator<_Const2>& __i) const
2676  { return __i._M_outer == _M_end; }
2677 
2678  sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2679 
2680  public:
2681  _Sentinel() = default;
2682 
2683  constexpr explicit
2684  _Sentinel(_Parent* __parent)
2685  : _M_end(ranges::end(__parent->_M_base))
2686  { }
2687 
2688  constexpr
2689  _Sentinel(_Sentinel<!_Const> __s)
2690  requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2691  : _M_end(std::move(__s._M_end))
2692  { }
2693 
2694  template<bool _Const2>
2695  requires sentinel_for<sentinel_t<_Base>,
2696  iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
2697  friend constexpr bool
2698  operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
2699  { return __y.__equal(__x); }
2700 
2701  friend _Sentinel<!_Const>;
2702  };
2703 
2704  [[no_unique_address]]
2705  __detail::__non_propagating_cache<remove_cv_t<_InnerRange>> _M_inner;
2706  _Vp _M_base = _Vp();
2707 
2708  public:
2709  join_view() = default;
2710 
2711  constexpr explicit
2712  join_view(_Vp __base)
2713  : _M_base(std::move(__base))
2714  { }
2715 
2716  constexpr _Vp
2717  base() const& requires copy_constructible<_Vp>
2718  { return _M_base; }
2719 
2720  constexpr _Vp
2721  base() &&
2722  { return std::move(_M_base); }
2723 
2724  constexpr auto
2725  begin()
2726  {
2727  constexpr bool __use_const
2728  = (__detail::__simple_view<_Vp>
2729  && is_reference_v<range_reference_t<_Vp>>);
2730  return _Iterator<__use_const>{this, ranges::begin(_M_base)};
2731  }
2732 
2733  constexpr auto
2734  begin() const
2735  requires input_range<const _Vp>
2736  && is_reference_v<range_reference_t<const _Vp>>
2737  {
2738  return _Iterator<true>{this, ranges::begin(_M_base)};
2739  }
2740 
2741  constexpr auto
2742  end()
2743  {
2744  if constexpr (forward_range<_Vp> && is_reference_v<_InnerRange>
2745  && forward_range<_InnerRange>
2746  && common_range<_Vp> && common_range<_InnerRange>)
2747  return _Iterator<__detail::__simple_view<_Vp>>{this,
2748  ranges::end(_M_base)};
2749  else
2750  return _Sentinel<__detail::__simple_view<_Vp>>{this};
2751  }
2752 
2753  constexpr auto
2754  end() const
2755  requires input_range<const _Vp>
2756  && is_reference_v<range_reference_t<const _Vp>>
2757  {
2758  if constexpr (forward_range<const _Vp>
2759  && is_reference_v<range_reference_t<const _Vp>>
2760  && forward_range<range_reference_t<const _Vp>>
2761  && common_range<const _Vp>
2762  && common_range<range_reference_t<const _Vp>>)
2763  return _Iterator<true>{this, ranges::end(_M_base)};
2764  else
2765  return _Sentinel<true>{this};
2766  }
2767  };
2768 
2769  template<typename _Range>
2770  explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;
2771 
2772  namespace views
2773  {
2774  namespace __detail
2775  {
2776  template<typename _Range>
2777  concept __can_join_view
2778  = requires { join_view<all_t<_Range>>{std::declval<_Range>()}; };
2779  } // namespace __detail
2780 
2781  struct _Join : __adaptor::_RangeAdaptorClosure
2782  {
2783  template<viewable_range _Range>
2784  requires __detail::__can_join_view<_Range>
2785  constexpr auto
2786  operator()(_Range&& __r) const
2787  {
2788  // _GLIBCXX_RESOLVE_LIB_DEFECTS
2789  // 3474. Nesting join_views is broken because of CTAD
2790  return join_view<all_t<_Range>>{std::forward<_Range>(__r)};
2791  }
2792 
2793  static constexpr bool _S_has_simple_call_op = true;
2794  };
2795 
2796  inline constexpr _Join join;
2797  } // namespace views
2798 
2799  namespace __detail
2800  {
2801  template<auto>
2802  struct __require_constant;
2803 
2804  template<typename _Range>
2805  concept __tiny_range = sized_range<_Range>
2806  && requires
2807  { typename __require_constant<remove_reference_t<_Range>::size()>; }
2808  && (remove_reference_t<_Range>::size() <= 1);
2809 
2810  template<typename _Base>
2811  struct __split_view_outer_iter_cat
2812  { };
2813 
2814  template<forward_range _Base>
2815  struct __split_view_outer_iter_cat<_Base>
2816  { using iterator_category = input_iterator_tag; };
2817 
2818  template<typename _Base>
2819  struct __split_view_inner_iter_cat
2820  { };
2821 
2822  template<forward_range _Base>
2823  struct __split_view_inner_iter_cat<_Base>
2824  {
2825  private:
2826  static constexpr auto
2827  _S_iter_cat()
2828  {
2829  using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
2830  if constexpr (derived_from<_Cat, forward_iterator_tag>)
2831  return forward_iterator_tag{};
2832  else
2833  return _Cat{};
2834  }
2835  public:
2836  using iterator_category = decltype(_S_iter_cat());
2837  };
2838  }
2839 
2840  template<input_range _Vp, forward_range _Pattern>
2841  requires view<_Vp> && view<_Pattern>
2842  && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
2843  ranges::equal_to>
2844  && (forward_range<_Vp> || __detail::__tiny_range<_Pattern>)
2845  class split_view : public view_interface<split_view<_Vp, _Pattern>>
2846  {
2847  private:
2848  template<bool _Const>
2849  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2850 
2851  template<bool _Const>
2852  struct _InnerIter;
2853 
2854  template<bool _Const>
2855  struct _OuterIter
2856  : __detail::__split_view_outer_iter_cat<_Base<_Const>>
2857  {
2858  private:
2859  using _Parent = __detail::__maybe_const_t<_Const, split_view>;
2860  using _Base = split_view::_Base<_Const>;
2861 
2862  constexpr bool
2863  __at_end() const
2864  { return __current() == ranges::end(_M_parent->_M_base); }
2865 
2866  // [range.split.outer] p1
2867  // Many of the following specifications refer to the notional member
2868  // current of outer-iterator. current is equivalent to current_ if
2869  // V models forward_range, and parent_->current_ otherwise.
2870  constexpr auto&
2871  __current() noexcept
2872  {
2873  if constexpr (forward_range<_Vp>)
2874  return _M_current;
2875  else
2876  return _M_parent->_M_current;
2877  }
2878 
2879  constexpr auto&
2880  __current() const noexcept
2881  {
2882  if constexpr (forward_range<_Vp>)
2883  return _M_current;
2884  else
2885  return _M_parent->_M_current;
2886  }
2887 
2888  _Parent* _M_parent = nullptr;
2889 
2890  // XXX: _M_current is present only if "V models forward_range"
2891  [[no_unique_address]]
2892  __detail::__maybe_present_t<forward_range<_Vp>,
2893  iterator_t<_Base>> _M_current;
2894 
2895  public:
2896  using iterator_concept = conditional_t<forward_range<_Base>,
2897  forward_iterator_tag,
2898  input_iterator_tag>;
2899  // iterator_category defined in __split_view_outer_iter_cat
2900  using difference_type = range_difference_t<_Base>;
2901 
2902  struct value_type : view_interface<value_type>
2903  {
2904  private:
2905  _OuterIter _M_i = _OuterIter();
2906 
2907  public:
2908  value_type() = default;
2909 
2910  constexpr explicit
2911  value_type(_OuterIter __i)
2912  : _M_i(std::move(__i))
2913  { }
2914 
2915  constexpr _InnerIter<_Const>
2916  begin() const
2917  requires copyable<_OuterIter>
2918  { return _InnerIter<_Const>{_M_i}; }
2919 
2920  constexpr _InnerIter<_Const>
2921  begin()
2922  requires (!copyable<_OuterIter>)
2923  { return _InnerIter<_Const>{std::move(_M_i)}; }
2924 
2925  constexpr default_sentinel_t
2926  end() const
2927  { return default_sentinel; }
2928  };
2929 
2930  _OuterIter() = default;
2931 
2932  constexpr explicit
2933  _OuterIter(_Parent* __parent) requires (!forward_range<_Base>)
2934  : _M_parent(__parent)
2935  { }
2936 
2937  constexpr
2938  _OuterIter(_Parent* __parent, iterator_t<_Base> __current)
2939  requires forward_range<_Base>
2940  : _M_parent(__parent),
2941  _M_current(std::move(__current))
2942  { }
2943 
2944  constexpr
2945  _OuterIter(_OuterIter<!_Const> __i)
2946  requires _Const
2947  && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
2948  : _M_parent(__i._M_parent), _M_current(std::move(__i._M_current))
2949  { }
2950 
2951  constexpr value_type
2952  operator*() const
2953  { return value_type{*this}; }
2954 
2955  constexpr _OuterIter&
2956  operator++()
2957  {
2958  // _GLIBCXX_RESOLVE_LIB_DEFECTS
2959  // 3505. split_view::outer-iterator::operator++ misspecified
2960  const auto __end = ranges::end(_M_parent->_M_base);
2961  if (__current() == __end)
2962  return *this;
2963  const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern};
2964  if (__pbegin == __pend)
2965  ++__current();
2966  else if constexpr (__detail::__tiny_range<_Pattern>)
2967  {
2968  __current() = __detail::find(std::move(__current()), __end,
2969  *__pbegin);
2970  if (__current() != __end)
2971  ++__current();
2972  }
2973  else
2974  do
2975  {
2976  auto [__b, __p]
2977  = __detail::mismatch(__current(), __end, __pbegin, __pend);
2978  if (__p == __pend)
2979  {
2980  __current() = __b;
2981  break;
2982  }
2983  } while (++__current() != __end);
2984  return *this;
2985  }
2986 
2987  constexpr decltype(auto)
2988  operator++(int)
2989  {
2990  if constexpr (forward_range<_Base>)
2991  {
2992  auto __tmp = *this;
2993  ++*this;
2994  return __tmp;
2995  }
2996  else
2997  ++*this;
2998  }
2999 
3000  friend constexpr bool
3001  operator==(const _OuterIter& __x, const _OuterIter& __y)
3002  requires forward_range<_Base>
3003  { return __x._M_current == __y._M_current; }
3004 
3005  friend constexpr bool
3006  operator==(const _OuterIter& __x, default_sentinel_t)
3007  { return __x.__at_end(); };
3008 
3009  friend _OuterIter<!_Const>;
3010  friend _InnerIter<_Const>;
3011  };
3012 
3013  template<bool _Const>
3014  struct _InnerIter
3015  : __detail::__split_view_inner_iter_cat<_Base<_Const>>
3016  {
3017  private:
3018  using _Base = split_view::_Base<_Const>;
3019 
3020  constexpr bool
3021  __at_end() const
3022  {
3023  auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern};
3024  auto __end = ranges::end(_M_i._M_parent->_M_base);
3025  if constexpr (__detail::__tiny_range<_Pattern>)
3026  {
3027  const auto& __cur = _M_i_current();
3028  if (__cur == __end)
3029  return true;
3030  if (__pcur == __pend)
3031  return _M_incremented;
3032  return *__cur == *__pcur;
3033  }
3034  else
3035  {
3036  auto __cur = _M_i_current();
3037  if (__cur == __end)
3038  return true;
3039  if (__pcur == __pend)
3040  return _M_incremented;
3041  do
3042  {
3043  if (*__cur != *__pcur)
3044  return false;
3045  if (++__pcur == __pend)
3046  return true;
3047  } while (++__cur != __end);
3048  return false;
3049  }
3050  }
3051 
3052  constexpr auto&
3053  _M_i_current() noexcept
3054  { return _M_i.__current(); }
3055 
3056  constexpr auto&
3057  _M_i_current() const noexcept
3058  { return _M_i.__current(); }
3059 
3060  _OuterIter<_Const> _M_i = _OuterIter<_Const>();
3061  bool _M_incremented = false;
3062 
3063  public:
3064  using iterator_concept
3065  = typename _OuterIter<_Const>::iterator_concept;
3066  // iterator_category defined in __split_view_inner_iter_cat
3067  using value_type = range_value_t<_Base>;
3068  using difference_type = range_difference_t<_Base>;
3069 
3070  _InnerIter() = default;
3071 
3072  constexpr explicit
3073  _InnerIter(_OuterIter<_Const> __i)
3074  : _M_i(std::move(__i))
3075  { }
3076 
3077  constexpr decltype(auto)
3078  operator*() const
3079  { return *_M_i_current(); }
3080 
3081  constexpr _InnerIter&
3082  operator++()
3083  {
3084  _M_incremented = true;
3085  if constexpr (!forward_range<_Base>)
3086  if constexpr (_Pattern::size() == 0)
3087  return *this;
3088  ++_M_i_current();
3089  return *this;
3090  }
3091 
3092  constexpr decltype(auto)
3093  operator++(int)
3094  {
3095  if constexpr (forward_range<_Base>)
3096  {
3097  auto __tmp = *this;
3098  ++*this;
3099  return __tmp;
3100  }
3101  else
3102  ++*this;
3103  }
3104 
3105  friend constexpr bool
3106  operator==(const _InnerIter& __x, const _InnerIter& __y)
3107  requires forward_range<_Base>
3108  { return __x._M_i == __y._M_i; }
3109 
3110  friend constexpr bool
3111  operator==(const _InnerIter& __x, default_sentinel_t)
3112  { return __x.__at_end(); }
3113 
3114  friend constexpr decltype(auto)
3115  iter_move(const _InnerIter& __i)
3116  noexcept(noexcept(ranges::iter_move(__i._M_i_current())))
3117  { return ranges::iter_move(__i._M_i_current()); }
3118 
3119  friend constexpr void
3120  iter_swap(const _InnerIter& __x, const _InnerIter& __y)
3121  noexcept(noexcept(ranges::iter_swap(__x._M_i_current(),
3122  __y._M_i_current())))
3123  requires indirectly_swappable<iterator_t<_Base>>
3124  { ranges::iter_swap(__x._M_i_current(), __y._M_i_current()); }
3125  };
3126 
3127  _Pattern _M_pattern = _Pattern();
3128  // XXX: _M_current is "present only if !forward_range<V>"
3129  [[no_unique_address]]
3130  __detail::__maybe_present_t<!forward_range<_Vp>,
3131  iterator_t<_Vp>> _M_current;
3132  _Vp _M_base = _Vp();
3133 
3134 
3135  public:
3136  split_view() = default;
3137 
3138  constexpr
3139  split_view(_Vp __base, _Pattern __pattern)
3140  : _M_pattern(std::move(__pattern)), _M_base(std::move(__base))
3141  { }
3142 
3143  template<input_range _Range>
3144  requires constructible_from<_Vp, views::all_t<_Range>>
3145  && constructible_from<_Pattern, single_view<range_value_t<_Range>>>
3146  constexpr
3147  split_view(_Range&& __r, range_value_t<_Range> __e)
3148  : _M_pattern(views::single(std::move(__e))),
3149  _M_base(views::all(std::forward<_Range>(__r)))
3150  { }
3151 
3152  constexpr _Vp
3153  base() const& requires copy_constructible<_Vp>
3154  { return _M_base; }
3155 
3156  constexpr _Vp
3157  base() &&
3158  { return std::move(_M_base); }
3159 
3160  constexpr auto
3161  begin()
3162  {
3163  if constexpr (forward_range<_Vp>)
3164  return _OuterIter<__detail::__simple_view<_Vp>>{
3165  this, ranges::begin(_M_base)};
3166  else
3167  {
3168  _M_current = ranges::begin(_M_base);
3169  return _OuterIter<false>{this};
3170  }
3171  }
3172 
3173  constexpr auto
3174  begin() const requires forward_range<_Vp> && forward_range<const _Vp>
3175  {
3176  return _OuterIter<true>{this, ranges::begin(_M_base)};
3177  }
3178 
3179  constexpr auto
3180  end() requires forward_range<_Vp> && common_range<_Vp>
3181  {
3182  return _OuterIter<__detail::__simple_view<_Vp>>{
3183  this, ranges::end(_M_base)};
3184  }
3185 
3186  constexpr auto
3187  end() const
3188  {
3189  if constexpr (forward_range<_Vp>
3190  && forward_range<const _Vp>
3191  && common_range<const _Vp>)
3192  return _OuterIter<true>{this, ranges::end(_M_base)};
3193  else
3194  return default_sentinel;
3195  }
3196  };
3197 
3198  template<typename _Range, typename _Pattern>
3199  split_view(_Range&&, _Pattern&&)
3200  -> split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
3201 
3202  template<input_range _Range>
3203  split_view(_Range&&, range_value_t<_Range>)
3204  -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
3205 
3206  namespace views
3207  {
3208  namespace __detail
3209  {
3210  template<typename _Range, typename _Pattern>
3211  concept __can_split_view
3212  = requires { split_view(std::declval<_Range>(), std::declval<_Pattern>()); };
3213  } // namespace __detail
3214 
3215  struct _Split : __adaptor::_RangeAdaptor<_Split>
3216  {
3217  template<viewable_range _Range, typename _Pattern>
3218  requires __detail::__can_split_view<_Range, _Pattern>
3219  constexpr auto
3220  operator()(_Range&& __r, _Pattern&& __f) const
3221  {
3222  return split_view(std::forward<_Range>(__r), std::forward<_Pattern>(__f));
3223  }
3224 
3225  using _RangeAdaptor<_Split>::operator();
3226  static constexpr int _S_arity = 2;
3227  // The pattern argument of views::split is not always simple -- it can be
3228  // a non-view range, the value category of which affects whether the call
3229  // is well-formed. But a scalar or a view pattern argument is surely
3230  // simple.
3231  template<typename _Pattern>
3232  static constexpr bool _S_has_simple_extra_args
3233  = is_scalar_v<_Pattern> || (view<_Pattern>
3234  && copy_constructible<_Pattern>);
3235  };
3236 
3237  inline constexpr _Split split;
3238  } // namespace views
3239 
3240  namespace views
3241  {
3242  struct _Counted
3243  {
3244  template<input_or_output_iterator _Iter>
3245  constexpr auto
3246  operator()(_Iter __i, iter_difference_t<_Iter> __n) const
3247  {
3248  if constexpr (random_access_iterator<_Iter>)
3249  return subrange(__i, __i + __n);
3250  else
3251  return subrange(counted_iterator(std::move(__i), __n),
3252  default_sentinel);
3253  }
3254  };
3255 
3256  inline constexpr _Counted counted{};
3257  } // namespace views
3258 
3259  template<view _Vp>
3260  requires (!common_range<_Vp>) && copyable<iterator_t<_Vp>>
3261  class common_view : public view_interface<common_view<_Vp>>
3262  {
3263  private:
3264  _Vp _M_base = _Vp();
3265 
3266  public:
3267  common_view() = default;
3268 
3269  constexpr explicit
3270  common_view(_Vp __r)
3271  : _M_base(std::move(__r))
3272  { }
3273 
3274  /* XXX: LWG 3280 didn't remove this constructor, but I think it should?
3275  template<viewable_range _Range>
3276  requires (!common_range<_Range>)
3277  && constructible_from<_Vp, views::all_t<_Range>>
3278  constexpr explicit
3279  common_view(_Range&& __r)
3280  : _M_base(views::all(std::forward<_Range>(__r)))
3281  { }
3282  */
3283 
3284  constexpr _Vp
3285  base() const& requires copy_constructible<_Vp>
3286  { return _M_base; }
3287 
3288  constexpr _Vp
3289  base() &&
3290  { return std::move(_M_base); }
3291 
3292  constexpr auto
3293  begin()
3294  {
3295  if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3296  return ranges::begin(_M_base);
3297  else
3298  return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3299  (ranges::begin(_M_base));
3300  }
3301 
3302  constexpr auto
3303  begin() const requires range<const _Vp>
3304  {
3305  if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3306  return ranges::begin(_M_base);
3307  else
3308  return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3309  (ranges::begin(_M_base));
3310  }
3311 
3312  constexpr auto
3313  end()
3314  {
3315  if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3316  return ranges::begin(_M_base) + ranges::size(_M_base);
3317  else
3318  return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3319  (ranges::end(_M_base));
3320  }
3321 
3322  constexpr auto
3323  end() const requires range<const _Vp>
3324  {
3325  if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3326  return ranges::begin(_M_base) + ranges::size(_M_base);
3327  else
3328  return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3329  (ranges::end(_M_base));
3330  }
3331 
3332  constexpr auto
3333  size() requires sized_range<_Vp>
3334  { return ranges::size(_M_base); }
3335 
3336  constexpr auto
3337  size() const requires sized_range<const _Vp>
3338  { return ranges::size(_M_base); }
3339  };
3340 
3341  template<typename _Range>
3342  common_view(_Range&&) -> common_view<views::all_t<_Range>>;
3343 
3344  template<typename _Tp>
3345  inline constexpr bool enable_borrowed_range<common_view<_Tp>>
3346  = enable_borrowed_range<_Tp>;
3347 
3348  namespace views
3349  {
3350  namespace __detail
3351  {
3352  template<typename _Range>
3353  concept __already_common = common_range<_Range>
3354  && requires { views::all(std::declval<_Range>()); };
3355 
3356  template<typename _Range>
3357  concept __can_common_view
3358  = requires { common_view{std::declval<_Range>()}; };
3359  } // namespace __detail
3360 
3361  struct _Common : __adaptor::_RangeAdaptorClosure
3362  {
3363  template<viewable_range _Range>
3364  requires __detail::__already_common<_Range>
3365  || __detail::__can_common_view<_Range>
3366  constexpr auto
3367  operator()(_Range&& __r) const
3368  {
3369  if constexpr (__detail::__already_common<_Range>)
3370  return views::all(std::forward<_Range>(__r));
3371  else
3372  return common_view{std::forward<_Range>(__r)};
3373  }
3374 
3375  static constexpr bool _S_has_simple_call_op = true;
3376  };
3377 
3378  inline constexpr _Common common;
3379  } // namespace views
3380 
3381  template<view _Vp>
3382  requires bidirectional_range<_Vp>
3383  class reverse_view : public view_interface<reverse_view<_Vp>>
3384  {
3385  private:
3386  static constexpr bool _S_needs_cached_begin
3387  = !common_range<_Vp> && !random_access_range<_Vp>;
3388 
3389  [[no_unique_address]]
3390  __detail::__maybe_present_t<_S_needs_cached_begin,
3391  __detail::_CachedPosition<_Vp>>
3392  _M_cached_begin;
3393  _Vp _M_base = _Vp();
3394 
3395  public:
3396  reverse_view() = default;
3397 
3398  constexpr explicit
3399  reverse_view(_Vp __r)
3400  : _M_base(std::move(__r))
3401  { }
3402 
3403  constexpr _Vp
3404  base() const& requires copy_constructible<_Vp>
3405  { return _M_base; }
3406 
3407  constexpr _Vp
3408  base() &&
3409  { return std::move(_M_base); }
3410 
3411  constexpr reverse_iterator<iterator_t<_Vp>>
3412  begin()
3413  {
3414  if constexpr (_S_needs_cached_begin)
3415  if (_M_cached_begin._M_has_value())
3416  return std::make_reverse_iterator(_M_cached_begin._M_get(_M_base));
3417 
3418  auto __it = ranges::next(ranges::begin(_M_base), ranges::end(_M_base));
3419  if constexpr (_S_needs_cached_begin)
3420  _M_cached_begin._M_set(_M_base, __it);
3421  return std::make_reverse_iterator(std::move(__it));
3422  }
3423 
3424  constexpr auto
3425  begin() requires common_range<_Vp>
3426  { return std::make_reverse_iterator(ranges::end(_M_base)); }
3427 
3428  constexpr auto
3429  begin() const requires common_range<const _Vp>
3430  { return std::make_reverse_iterator(ranges::end(_M_base)); }
3431 
3432  constexpr reverse_iterator<iterator_t<_Vp>>
3433  end()
3434  { return std::make_reverse_iterator(ranges::begin(_M_base)); }
3435 
3436  constexpr auto
3437  end() const requires common_range<const _Vp>
3438  { return std::make_reverse_iterator(ranges::begin(_M_base)); }
3439 
3440  constexpr auto
3441  size() requires sized_range<_Vp>
3442  { return ranges::size(_M_base); }
3443 
3444  constexpr auto
3445  size() const requires sized_range<const _Vp>
3446  { return ranges::size(_M_base); }
3447  };
3448 
3449  template<typename _Range>
3450  reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>;
3451 
3452  template<typename _Tp>
3453  inline constexpr bool enable_borrowed_range<reverse_view<_Tp>>
3454  = enable_borrowed_range<_Tp>;
3455 
3456  namespace views
3457  {
3458  namespace __detail
3459  {
3460  template<typename>
3461  inline constexpr bool __is_reversible_subrange = false;
3462 
3463  template<typename _Iter, subrange_kind _Kind>
3464  inline constexpr bool
3465  __is_reversible_subrange<subrange<reverse_iterator<_Iter>,
3466  reverse_iterator<_Iter>,
3467  _Kind>> = true;
3468 
3469  template<typename>
3470  inline constexpr bool __is_reverse_view = false;
3471 
3472  template<typename _Vp>
3473  inline constexpr bool __is_reverse_view<reverse_view<_Vp>> = true;
3474 
3475  template<typename _Range>
3476  concept __can_reverse_view
3477  = requires { reverse_view{std::declval<_Range>()}; };
3478  } // namespace __detail
3479 
3480  struct _Reverse : __adaptor::_RangeAdaptorClosure
3481  {
3482  template<viewable_range _Range>
3483  requires __detail::__is_reverse_view<remove_cvref_t<_Range>>
3484  || __detail::__is_reversible_subrange<remove_cvref_t<_Range>>
3485  || __detail::__can_reverse_view<_Range>
3486  constexpr auto
3487  operator()(_Range&& __r) const
3488  {
3489  using _Tp = remove_cvref_t<_Range>;
3490  if constexpr (__detail::__is_reverse_view<_Tp>)
3491  return std::forward<_Range>(__r).base();
3492  else if constexpr (__detail::__is_reversible_subrange<_Tp>)
3493  {
3494  using _Iter = decltype(ranges::begin(__r).base());
3495  if constexpr (sized_range<_Tp>)
3496  return subrange<_Iter, _Iter, subrange_kind::sized>
3497  {__r.end().base(), __r.begin().base(), __r.size()};
3498  else
3499  return subrange<_Iter, _Iter, subrange_kind::unsized>
3500  {__r.end().base(), __r.begin().base()};
3501  }
3502  else
3503  return reverse_view{std::forward<_Range>(__r)};
3504  }
3505 
3506  static constexpr bool _S_has_simple_call_op = true;
3507  };
3508 
3509  inline constexpr _Reverse reverse;
3510  } // namespace views
3511 
3512  namespace __detail
3513  {
3514  template<typename _Tp, size_t _Nm>
3515  concept __has_tuple_element = requires(_Tp __t)
3516  {
3517  typename tuple_size<_Tp>::type;
3518  requires _Nm < tuple_size_v<_Tp>;
3519  typename tuple_element_t<_Nm, _Tp>;
3520  { std::get<_Nm>(__t) }
3521  -> convertible_to<const tuple_element_t<_Nm, _Tp>&>;
3522  };
3523 
3524  template<typename _Tp, size_t _Nm>
3525  concept __returnable_element
3526  = is_reference_v<_Tp> || move_constructible<tuple_element_t<_Nm, _Tp>>;
3527  }
3528 
3529  template<input_range _Vp, size_t _Nm>
3530  requires view<_Vp>
3531  && __detail::__has_tuple_element<range_value_t<_Vp>, _Nm>
3532  && __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>,
3533  _Nm>
3534  && __detail::__returnable_element<range_reference_t<_Vp>, _Nm>
3535  class elements_view : public view_interface<elements_view<_Vp, _Nm>>
3536  {
3537  public:
3538  elements_view() = default;
3539 
3540  constexpr explicit
3541  elements_view(_Vp base)
3542  : _M_base(std::move(base))
3543  { }
3544 
3545  constexpr const _Vp&
3546  base() const & noexcept
3547  { return _M_base; }
3548 
3549  constexpr _Vp
3550  base() &&
3551  { return std::move(_M_base); }
3552 
3553  constexpr auto
3554  begin() requires (!__detail::__simple_view<_Vp>)
3555  { return _Iterator<false>(ranges::begin(_M_base)); }
3556 
3557  constexpr auto
3558  begin() const requires range<const _Vp>
3559  { return _Iterator<true>(ranges::begin(_M_base)); }
3560 
3561  constexpr auto
3562  end() requires (!__detail::__simple_view<_Vp> && !common_range<_Vp>)
3563  { return _Sentinel<false>{ranges::end(_M_base)}; }
3564 
3565  constexpr auto
3566  end() requires (!__detail::__simple_view<_Vp> && common_range<_Vp>)
3567  { return _Iterator<false>{ranges::end(_M_base)}; }
3568 
3569  constexpr auto
3570  end() const requires range<const _Vp>
3571  { return _Sentinel<true>{ranges::end(_M_base)}; }
3572 
3573  constexpr auto
3574  end() const requires common_range<const _Vp>
3575  { return _Iterator<true>{ranges::end(_M_base)}; }
3576 
3577  constexpr auto
3578  size() requires sized_range<_Vp>
3579  { return ranges::size(_M_base); }
3580 
3581  constexpr auto
3582  size() const requires sized_range<const _Vp>
3583  { return ranges::size(_M_base); }
3584 
3585  private:
3586  template<bool _Const>
3587  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
3588 
3589  template<bool _Const>
3590  struct __iter_cat
3591  { };
3592 
3593  template<bool _Const>
3594  requires forward_range<_Base<_Const>>
3595  struct __iter_cat<_Const>
3596  {
3597  private:
3598  static auto _S_iter_cat()
3599  {
3600  using _Base = elements_view::_Base<_Const>;
3601  using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
3602  using _Res = decltype((std::get<_Nm>(*std::declval<iterator_t<_Base>>())));
3603  if constexpr (!is_lvalue_reference_v<_Res>)
3604  return input_iterator_tag{};
3605  else if constexpr (derived_from<_Cat, random_access_iterator_tag>)
3606  return random_access_iterator_tag{};
3607  else
3608  return _Cat{};
3609  }
3610  public:
3611  using iterator_category = decltype(_S_iter_cat());
3612  };
3613 
3614  template<bool _Const>
3615  struct _Sentinel;
3616 
3617  template<bool _Const>
3618  struct _Iterator : __iter_cat<_Const>
3619  {
3620  private:
3621  using _Base = elements_view::_Base<_Const>;
3622 
3623  iterator_t<_Base> _M_current = iterator_t<_Base>();
3624 
3625  static constexpr decltype(auto)
3626  _S_get_element(const iterator_t<_Base>& __i)
3627  {
3628  if constexpr (is_reference_v<range_reference_t<_Base>>)
3629  return std::get<_Nm>(*__i);
3630  else
3631  {
3632  using _Et = remove_cv_t<tuple_element_t<_Nm, range_reference_t<_Base>>>;
3633  return static_cast<_Et>(std::get<_Nm>(*__i));
3634  }
3635  }
3636 
3637  static auto
3638  _S_iter_concept()
3639  {
3640  if constexpr (random_access_range<_Vp>)
3641  return random_access_iterator_tag{};
3642  else if constexpr (bidirectional_range<_Vp>)
3643  return bidirectional_iterator_tag{};
3644  else if constexpr (forward_range<_Vp>)
3645  return forward_iterator_tag{};
3646  else
3647  return input_iterator_tag{};
3648  }
3649 
3650  friend _Iterator<!_Const>;
3651 
3652  public:
3653  using iterator_concept = decltype(_S_iter_concept());
3654  // iterator_category defined in elements_view::__iter_cat
3655  using value_type
3656  = remove_cvref_t<tuple_element_t<_Nm, range_value_t<_Base>>>;
3657  using difference_type = range_difference_t<_Base>;
3658 
3659  _Iterator() = default;
3660 
3661  constexpr explicit
3662  _Iterator(iterator_t<_Base> current)
3663  : _M_current(std::move(current))
3664  { }
3665 
3666  constexpr
3667  _Iterator(_Iterator<!_Const> i)
3668  requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
3669  : _M_current(std::move(i._M_current))
3670  { }
3671 
3672  constexpr iterator_t<_Base>
3673  base() const&
3674  requires copyable<iterator_t<_Base>>
3675  { return _M_current; }
3676 
3677  constexpr iterator_t<_Base>
3678  base() &&
3679  { return std::move(_M_current); }
3680 
3681  constexpr decltype(auto)
3682  operator*() const
3683  { return _S_get_element(_M_current); }
3684 
3685  constexpr _Iterator&
3686  operator++()
3687  {
3688  ++_M_current;
3689  return *this;
3690  }
3691 
3692  constexpr void
3693  operator++(int)
3694  { ++_M_current; }
3695 
3696  constexpr _Iterator
3697  operator++(int) requires forward_range<_Base>
3698  {
3699  auto __tmp = *this;
3700  ++_M_current;
3701  return __tmp;
3702  }
3703 
3704  constexpr _Iterator&
3705  operator--() requires bidirectional_range<_Base>
3706  {
3707  --_M_current;
3708  return *this;
3709  }
3710 
3711  constexpr _Iterator
3712  operator--(int) requires bidirectional_range<_Base>
3713  {
3714  auto __tmp = *this;
3715  --_M_current;
3716  return __tmp;
3717  }
3718 
3719  constexpr _Iterator&
3720  operator+=(difference_type __n)
3721  requires random_access_range<_Base>
3722  {
3723  _M_current += __n;
3724  return *this;
3725  }
3726 
3727  constexpr _Iterator&
3728  operator-=(difference_type __n)
3729  requires random_access_range<_Base>
3730  {
3731  _M_current -= __n;
3732  return *this;
3733  }
3734 
3735  constexpr decltype(auto)
3736  operator[](difference_type __n) const
3737  requires random_access_range<_Base>
3738  { return _S_get_element(_M_current + __n); }
3739 
3740  friend constexpr bool
3741  operator==(const _Iterator& __x, const _Iterator& __y)
3742  requires equality_comparable<iterator_t<_Base>>
3743  { return __x._M_current == __y._M_current; }
3744 
3745  friend constexpr bool
3746  operator<(const _Iterator& __x, const _Iterator& __y)
3747  requires random_access_range<_Base>
3748  { return __x._M_current < __y._M_current; }
3749 
3750  friend constexpr bool
3751  operator>(const _Iterator& __x, const _Iterator& __y)
3752  requires random_access_range<_Base>
3753  { return __y._M_current < __x._M_current; }
3754 
3755  friend constexpr bool
3756  operator<=(const _Iterator& __x, const _Iterator& __y)
3757  requires random_access_range<_Base>
3758  { return !(__y._M_current > __x._M_current); }
3759 
3760  friend constexpr bool
3761  operator>=(const _Iterator& __x, const _Iterator& __y)
3762  requires random_access_range<_Base>
3763  { return !(__x._M_current > __y._M_current); }
3764 
3765 #ifdef __cpp_lib_three_way_comparison
3766  friend constexpr auto
3767  operator<=>(const _Iterator& __x, const _Iterator& __y)
3768  requires random_access_range<_Base>
3769  && three_way_comparable<iterator_t<_Base>>
3770  { return __x._M_current <=> __y._M_current; }
3771 #endif
3772 
3773  friend constexpr _Iterator
3774  operator+(const _Iterator& __x, difference_type __y)
3775  requires random_access_range<_Base>
3776  { return _Iterator{__x} += __y; }
3777 
3778  friend constexpr _Iterator
3779  operator+(difference_type __x, const _Iterator& __y)
3780  requires random_access_range<_Base>
3781  { return __y + __x; }
3782 
3783  friend constexpr _Iterator
3784  operator-(const _Iterator& __x, difference_type __y)
3785  requires random_access_range<_Base>
3786  { return _Iterator{__x} -= __y; }
3787 
3788  // _GLIBCXX_RESOLVE_LIB_DEFECTS
3789  // 3483. transform_view::iterator's difference is overconstrained
3790  friend constexpr difference_type
3791  operator-(const _Iterator& __x, const _Iterator& __y)
3792  requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
3793  { return __x._M_current - __y._M_current; }
3794 
3795  template <bool> friend struct _Sentinel;
3796  };
3797 
3798  template<bool _Const>
3799  struct _Sentinel
3800  {
3801  private:
3802  template<bool _Const2>
3803  constexpr bool
3804  _M_equal(const _Iterator<_Const2>& __x) const
3805  { return __x._M_current == _M_end; }
3806 
3807  template<bool _Const2>
3808  constexpr auto
3809  _M_distance_from(const _Iterator<_Const2>& __i) const
3810  { return _M_end - __i._M_current; }
3811 
3812  using _Base = elements_view::_Base<_Const>;
3813  sentinel_t<_Base> _M_end = sentinel_t<_Base>();
3814 
3815  public:
3816  _Sentinel() = default;
3817 
3818  constexpr explicit
3819  _Sentinel(sentinel_t<_Base> __end)
3820  : _M_end(std::move(__end))
3821  { }
3822 
3823  constexpr
3824  _Sentinel(_Sentinel<!_Const> __other)
3825  requires _Const
3826  && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
3827  : _M_end(std::move(__other._M_end))
3828  { }
3829 
3830  constexpr sentinel_t<_Base>
3831  base() const
3832  { return _M_end; }
3833 
3834  template<bool _Const2>
3835  requires sentinel_for<sentinel_t<_Base>,
3836  iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
3837  friend constexpr bool
3838  operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
3839  { return __y._M_equal(__x); }
3840 
3841  template<bool _Const2,
3842  typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
3843  requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
3844  friend constexpr range_difference_t<_Base2>
3845  operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
3846  { return -__y._M_distance_from(__x); }
3847 
3848  template<bool _Const2,
3849  typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
3850  requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
3851  friend constexpr range_difference_t<_Base2>
3852  operator-(const _Sentinel& __x, const _Iterator<_Const2>& __y)
3853  { return __x._M_distance_from(__y); }
3854 
3855  friend _Sentinel<!_Const>;
3856  };
3857 
3858  _Vp _M_base = _Vp();
3859  };
3860 
3861  template<typename _Tp, size_t _Nm>
3862  inline constexpr bool enable_borrowed_range<elements_view<_Tp, _Nm>>
3863  = enable_borrowed_range<_Tp>;
3864 
3865  template<typename _Range>
3866  using keys_view = elements_view<views::all_t<_Range>, 0>;
3867 
3868  template<typename _Range>
3869  using values_view = elements_view<views::all_t<_Range>, 1>;
3870 
3871  namespace views
3872  {
3873  namespace __detail
3874  {
3875  template<size_t _Nm, typename _Range>
3876  concept __can_elements_view
3877  = requires { elements_view<all_t<_Range>, _Nm>{std::declval<_Range>()}; };
3878  } // namespace __detail
3879 
3880  template<size_t _Nm>
3881  struct _Elements : __adaptor::_RangeAdaptorClosure
3882  {
3883  template<viewable_range _Range>
3884  requires __detail::__can_elements_view<_Nm, _Range>
3885  constexpr auto
3886  operator()(_Range&& __r) const
3887  {
3888  return elements_view<all_t<_Range>, _Nm>{std::forward<_Range>(__r)};
3889  }
3890 
3891  static constexpr bool _S_has_simple_call_op = true;
3892  };
3893 
3894  template<size_t _Nm>
3895  inline constexpr _Elements<_Nm> elements;
3896  inline constexpr auto keys = elements<0>;
3897  inline constexpr auto values = elements<1>;
3898  } // namespace views
3899 
3900 } // namespace ranges
3901 
3902  namespace views = ranges::views;
3903 
3904 _GLIBCXX_END_NAMESPACE_VERSION
3905 } // namespace
3906 #endif // library concepts
3907 #endif // C++2a
3908 #endif /* _GLIBCXX_RANGES */