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