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