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