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
728 {
729  namespace __adaptor
730  {
731  template<typename _Tp>
732  inline constexpr auto
733  __maybe_refwrap(_Tp& __arg)
734  { return reference_wrapper<_Tp>{__arg}; }
735 
736  template<typename _Tp>
737  inline constexpr auto
738  __maybe_refwrap(const _Tp& __arg)
739  { return reference_wrapper<const _Tp>{__arg}; }
740 
741  template<typename _Tp>
742  inline constexpr decltype(auto)
743  __maybe_refwrap(_Tp&& __arg)
744  { return std::forward<_Tp>(__arg); }
745 
746  template<typename _Callable>
747  struct _RangeAdaptorClosure;
748 
749  template<typename _Callable>
750  struct _RangeAdaptor
751  {
752  protected:
753  [[no_unique_address]]
754  __detail::__maybe_present_t<!is_default_constructible_v<_Callable>,
755  _Callable> _M_callable;
756 
757  public:
758  constexpr
759  _RangeAdaptor(const _Callable& = {})
760  requires is_default_constructible_v<_Callable>
761  { }
762 
763  constexpr
764  _RangeAdaptor(_Callable __callable)
765  requires (!is_default_constructible_v<_Callable>)
766  : _M_callable(std::move(__callable))
767  { }
768 
769  template<typename... _Args>
770  requires (sizeof...(_Args) >= 1)
771  constexpr auto
772  operator()(_Args&&... __args) const
773  {
774  // [range.adaptor.object]: If a range adaptor object accepts more
775  // than one argument, then the following expressions are equivalent:
776  //
777  // (1) adaptor(range, args...)
778  // (2) adaptor(args...)(range)
779  // (3) range | adaptor(args...)
780  //
781  // In this case, adaptor(args...) is a range adaptor closure object.
782  //
783  // We handle (1) and (2) here, and (3) is just a special case of a
784  // more general case already handled by _RangeAdaptorClosure.
785  if constexpr (is_invocable_v<_Callable, _Args...>)
786  {
787  static_assert(sizeof...(_Args) != 1,
788  "a _RangeAdaptor that accepts only one argument "
789  "should be defined as a _RangeAdaptorClosure");
790  // Here we handle adaptor(range, args...) -- just forward all
791  // arguments to the underlying adaptor routine.
792  return _Callable{}(std::forward<_Args>(__args)...);
793  }
794  else
795  {
796  // Here we handle adaptor(args...)(range).
797  // Given args..., we return a _RangeAdaptorClosure that takes a
798  // range argument, such that (2) is equivalent to (1).
799  //
800  // We need to be careful about how we capture args... in this
801  // closure. By using __maybe_refwrap, we capture lvalue
802  // references by reference (through a reference_wrapper) and
803  // otherwise capture by value.
804  auto __closure
805  = [...__args(__maybe_refwrap(std::forward<_Args>(__args)))]
806  <typename _Range> (_Range&& __r) {
807  // This static_cast has two purposes: it forwards a
808  // reference_wrapper<T> capture as a T&, and otherwise
809  // forwards the captured argument as an rvalue.
810  return _Callable{}(std::forward<_Range>(__r),
811  (static_cast<unwrap_reference_t
812  <remove_const_t<decltype(__args)>>>
813  (__args))...);
814  };
815  using _ClosureType = decltype(__closure);
816  return _RangeAdaptorClosure<_ClosureType>(std::move(__closure));
817  }
818  }
819  };
820 
821  template<typename _Callable>
822  _RangeAdaptor(_Callable) -> _RangeAdaptor<_Callable>;
823 
824  template<typename _Callable>
825  struct _RangeAdaptorClosure : public _RangeAdaptor<_Callable>
826  {
827  using _RangeAdaptor<_Callable>::_RangeAdaptor;
828 
829  template<viewable_range _Range>
830  requires requires { declval<_Callable>()(declval<_Range>()); }
831  constexpr auto
832  operator()(_Range&& __r) const
833  {
834  if constexpr (is_default_constructible_v<_Callable>)
835  return _Callable{}(std::forward<_Range>(__r));
836  else
837  return this->_M_callable(std::forward<_Range>(__r));
838  }
839 
840  template<viewable_range _Range>
841  requires requires { declval<_Callable>()(declval<_Range>()); }
842  friend constexpr auto
843  operator|(_Range&& __r, const _RangeAdaptorClosure& __o)
844  { return __o(std::forward<_Range>(__r)); }
845 
846  template<typename _Tp>
847  friend constexpr auto
848  operator|(const _RangeAdaptorClosure<_Tp>& __x,
849  const _RangeAdaptorClosure& __y)
850  {
851  if constexpr (is_default_constructible_v<_Tp>
852  && is_default_constructible_v<_Callable>)
853  {
854  auto __closure = [] <typename _Up> (_Up&& __e) {
855  return std::forward<_Up>(__e) | decltype(__x){} | decltype(__y){};
856  };
857  return _RangeAdaptorClosure<decltype(__closure)>(__closure);
858  }
859  else if constexpr (is_default_constructible_v<_Tp>
860  && !is_default_constructible_v<_Callable>)
861  {
862  auto __closure = [__y] <typename _Up> (_Up&& __e) {
863  return std::forward<_Up>(__e) | decltype(__x){} | __y;
864  };
865  return _RangeAdaptorClosure<decltype(__closure)>(__closure);
866  }
867  else if constexpr (!is_default_constructible_v<_Tp>
868  && is_default_constructible_v<_Callable>)
869  {
870  auto __closure = [__x] <typename _Up> (_Up&& __e) {
871  return std::forward<_Up>(__e) | __x | decltype(__y){};
872  };
873  return _RangeAdaptorClosure<decltype(__closure)>(__closure);
874  }
875  else
876  {
877  auto __closure = [__x, __y] <typename _Up> (_Up&& __e) {
878  return std::forward<_Up>(__e) | __x | __y;
879  };
880  return _RangeAdaptorClosure<decltype(__closure)>(__closure);
881  }
882  }
883  };
884 
885  template<typename _Callable>
886  _RangeAdaptorClosure(_Callable) -> _RangeAdaptorClosure<_Callable>;
887  } // namespace __adaptor
888 } // namespace views
889 
890  template<range _Range> requires is_object_v<_Range>
891  class ref_view : public view_interface<ref_view<_Range>>
892  {
893  private:
894  _Range* _M_r = nullptr;
895 
896  static void _S_fun(_Range&); // not defined
897  static void _S_fun(_Range&&) = delete;
898 
899  public:
900  constexpr
901  ref_view() noexcept = default;
902 
903  template<__detail::__not_same_as<ref_view> _Tp>
904  requires convertible_to<_Tp, _Range&>
905  && requires { _S_fun(declval<_Tp>()); }
906  constexpr
907  ref_view(_Tp&& __t)
908  : _M_r(std::__addressof(static_cast<_Range&>(std::forward<_Tp>(__t))))
909  { }
910 
911  constexpr _Range&
912  base() const
913  { return *_M_r; }
914 
915  constexpr iterator_t<_Range>
916  begin() const
917  { return ranges::begin(*_M_r); }
918 
919  constexpr sentinel_t<_Range>
920  end() const
921  { return ranges::end(*_M_r); }
922 
923  constexpr bool
924  empty() const requires requires { ranges::empty(*_M_r); }
925  { return ranges::empty(*_M_r); }
926 
927  constexpr auto
928  size() const requires sized_range<_Range>
929  { return ranges::size(*_M_r); }
930 
931  constexpr auto
932  data() const requires contiguous_range<_Range>
933  { return ranges::data(*_M_r); }
934  };
935 
936  template<typename _Range>
937  ref_view(_Range&) -> ref_view<_Range>;
938 
939  template<typename _Tp>
940  inline constexpr bool enable_borrowed_range<ref_view<_Tp>> = true;
941 
942  namespace views
943  {
944  inline constexpr __adaptor::_RangeAdaptorClosure all
945  = [] <viewable_range _Range> (_Range&& __r)
946  {
947  if constexpr (view<decay_t<_Range>>)
948  return std::forward<_Range>(__r);
949  else if constexpr (requires { ref_view{std::forward<_Range>(__r)}; })
950  return ref_view{std::forward<_Range>(__r)};
951  else
952  return subrange{std::forward<_Range>(__r)};
953  };
954 
955  template<viewable_range _Range>
956  using all_t = decltype(all(std::declval<_Range>()));
957 
958  } // namespace views
959 
960  // XXX: the following algos are copied from ranges_algo.h to avoid a circular
961  // dependency with that header.
962  namespace __detail
963  {
964  template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
965  typename _Proj = identity,
966  indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
967  constexpr _Iter
968  find_if(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
969  {
970  while (__first != __last
971  && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
972  ++__first;
973  return __first;
974  }
975 
976  template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
977  typename _Proj = identity,
978  indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
979  constexpr _Iter
980  find_if_not(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
981  {
982  while (__first != __last
983  && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
984  ++__first;
985  return __first;
986  }
987 
988  template<typename _Tp, typename _Proj = identity,
989  indirect_strict_weak_order<projected<const _Tp*, _Proj>>
990  _Comp = ranges::less>
991  constexpr const _Tp&
992  min(const _Tp& __a, const _Tp& __b, _Comp __comp = {}, _Proj __proj = {})
993  {
994  if (std::__invoke(std::move(__comp),
995  std::__invoke(__proj, __b),
996  std::__invoke(__proj, __a)))
997  return __b;
998  else
999  return __a;
1000  }
1001 
1002  template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
1003  input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
1004  typename _Pred = ranges::equal_to,
1005  typename _Proj1 = identity, typename _Proj2 = identity>
1006  requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
1007  constexpr pair<_Iter1, _Iter2>
1008  mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
1009  _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
1010  {
1011  while (__first1 != __last1 && __first2 != __last2
1012  && (bool)std::__invoke(__pred,
1013  std::__invoke(__proj1, *__first1),
1014  std::__invoke(__proj2, *__first2)))
1015  {
1016  ++__first1;
1017  ++__first2;
1018  }
1019  return { std::move(__first1), std::move(__first2) };
1020  }
1021  } // namespace __detail
1022 
1023  namespace __detail
1024  {
1025  template<range _Range>
1026  struct _CachedPosition
1027  {
1028  constexpr bool
1029  _M_has_value() const
1030  { return false; }
1031 
1032  constexpr iterator_t<_Range>
1033  _M_get(const _Range&) const
1034  {
1035  __glibcxx_assert(false);
1036  return {};
1037  }
1038 
1039  constexpr void
1040  _M_set(const _Range&, const iterator_t<_Range>&) const
1041  { }
1042  };
1043 
1044  template<forward_range _Range>
1045  struct _CachedPosition<_Range>
1046  {
1047  private:
1048  iterator_t<_Range> _M_iter{};
1049 
1050  public:
1051  constexpr bool
1052  _M_has_value() const
1053  { return _M_iter != iterator_t<_Range>{}; }
1054 
1055  constexpr iterator_t<_Range>
1056  _M_get(const _Range&) const
1057  {
1058  __glibcxx_assert(_M_has_value());
1059  return _M_iter;
1060  }
1061 
1062  constexpr void
1063  _M_set(const _Range&, const iterator_t<_Range>& __it)
1064  {
1065  __glibcxx_assert(!_M_has_value());
1066  _M_iter = __it;
1067  }
1068  };
1069 
1070  template<random_access_range _Range>
1071  requires (sizeof(range_difference_t<_Range>)
1072  <= sizeof(iterator_t<_Range>))
1073  struct _CachedPosition<_Range>
1074  {
1075  private:
1076  range_difference_t<_Range> _M_offset = -1;
1077 
1078  public:
1079  constexpr bool
1080  _M_has_value() const
1081  { return _M_offset >= 0; }
1082 
1083  constexpr iterator_t<_Range>
1084  _M_get(_Range& __r) const
1085  {
1086  __glibcxx_assert(_M_has_value());
1087  return ranges::begin(__r) + _M_offset;
1088  }
1089 
1090  constexpr void
1091  _M_set(_Range& __r, const iterator_t<_Range>& __it)
1092  {
1093  __glibcxx_assert(!_M_has_value());
1094  _M_offset = __it - ranges::begin(__r);
1095  }
1096  };
1097 
1098  } // namespace __detail
1099 
1100  template<input_range _Vp,
1101  indirect_unary_predicate<iterator_t<_Vp>> _Pred>
1102  requires view<_Vp> && is_object_v<_Pred>
1103  class filter_view : public view_interface<filter_view<_Vp, _Pred>>
1104  {
1105  private:
1106  struct _Sentinel;
1107 
1108  struct _Iterator
1109  {
1110  private:
1111  static constexpr auto
1112  _S_iter_concept()
1113  {
1114  if constexpr (bidirectional_range<_Vp>)
1115  return bidirectional_iterator_tag{};
1116  else if constexpr (forward_range<_Vp>)
1117  return forward_iterator_tag{};
1118  else
1119  return input_iterator_tag{};
1120  }
1121 
1122  static constexpr auto
1123  _S_iter_cat()
1124  {
1125  using _Cat = typename iterator_traits<_Vp_iter>::iterator_category;
1126  if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
1127  return bidirectional_iterator_tag{};
1128  else if constexpr (derived_from<_Cat, forward_iterator_tag>)
1129  return forward_iterator_tag{};
1130  else
1131  return _Cat{};
1132  }
1133 
1134  friend filter_view;
1135 
1136  using _Vp_iter = iterator_t<_Vp>;
1137 
1138  _Vp_iter _M_current = _Vp_iter();
1139  filter_view* _M_parent = nullptr;
1140 
1141  public:
1142  using iterator_concept = decltype(_S_iter_concept());
1143  using iterator_category = decltype(_S_iter_cat());
1144  using value_type = range_value_t<_Vp>;
1145  using difference_type = range_difference_t<_Vp>;
1146 
1147  _Iterator() = default;
1148 
1149  constexpr
1150  _Iterator(filter_view* __parent, _Vp_iter __current)
1151  : _M_current(std::move(__current)),
1152  _M_parent(__parent)
1153  { }
1154 
1155  constexpr _Vp_iter
1156  base() const &
1157  requires copyable<_Vp_iter>
1158  { return _M_current; }
1159 
1160  constexpr _Vp_iter
1161  base() &&
1162  { return std::move(_M_current); }
1163 
1164  constexpr range_reference_t<_Vp>
1165  operator*() const
1166  { return *_M_current; }
1167 
1168  constexpr _Vp_iter
1169  operator->() const
1170  requires __detail::__has_arrow<_Vp_iter>
1171  && copyable<_Vp_iter>
1172  { return _M_current; }
1173 
1174  constexpr _Iterator&
1175  operator++()
1176  {
1177  _M_current = __detail::find_if(std::move(++_M_current),
1178  ranges::end(_M_parent->_M_base),
1179  std::ref(*_M_parent->_M_pred));
1180  return *this;
1181  }
1182 
1183  constexpr void
1184  operator++(int)
1185  { ++*this; }
1186 
1187  constexpr _Iterator
1188  operator++(int) requires forward_range<_Vp>
1189  {
1190  auto __tmp = *this;
1191  ++*this;
1192  return __tmp;
1193  }
1194 
1195  constexpr _Iterator&
1196  operator--() requires bidirectional_range<_Vp>
1197  {
1198  do
1199  --_M_current;
1200  while (!std::__invoke(*_M_parent->_M_pred, *_M_current));
1201  return *this;
1202  }
1203 
1204  constexpr _Iterator
1205  operator--(int) requires bidirectional_range<_Vp>
1206  {
1207  auto __tmp = *this;
1208  --*this;
1209  return __tmp;
1210  }
1211 
1212  friend constexpr bool
1213  operator==(const _Iterator& __x, const _Iterator& __y)
1214  requires equality_comparable<_Vp_iter>
1215  { return __x._M_current == __y._M_current; }
1216 
1217  friend constexpr range_rvalue_reference_t<_Vp>
1218  iter_move(const _Iterator& __i)
1219  noexcept(noexcept(ranges::iter_move(__i._M_current)))
1220  { return ranges::iter_move(__i._M_current); }
1221 
1222  friend constexpr void
1223  iter_swap(const _Iterator& __x, const _Iterator& __y)
1224  noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1225  requires indirectly_swappable<_Vp_iter>
1226  { ranges::iter_swap(__x._M_current, __y._M_current); }
1227  };
1228 
1229  struct _Sentinel
1230  {
1231  private:
1232  sentinel_t<_Vp> _M_end = sentinel_t<_Vp>();
1233 
1234  constexpr bool
1235  __equal(const _Iterator& __i) const
1236  { return __i._M_current == _M_end; }
1237 
1238  public:
1239  _Sentinel() = default;
1240 
1241  constexpr explicit
1242  _Sentinel(filter_view* __parent)
1243  : _M_end(ranges::end(__parent->_M_base))
1244  { }
1245 
1246  constexpr sentinel_t<_Vp>
1247  base() const
1248  { return _M_end; }
1249 
1250  friend constexpr bool
1251  operator==(const _Iterator& __x, const _Sentinel& __y)
1252  { return __y.__equal(__x); }
1253  };
1254 
1255  [[no_unique_address]] __detail::__box<_Pred> _M_pred;
1256  [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
1257  _Vp _M_base = _Vp();
1258 
1259  public:
1260  filter_view() = default;
1261 
1262  constexpr
1263  filter_view(_Vp __base, _Pred __pred)
1264  : _M_pred(std::move(__pred)), _M_base(std::move(__base))
1265  { }
1266 
1267  constexpr _Vp
1268  base() const& requires copy_constructible<_Vp>
1269  { return _M_base; }
1270 
1271  constexpr _Vp
1272  base() &&
1273  { return std::move(_M_base); }
1274 
1275  constexpr const _Pred&
1276  pred() const
1277  { return *_M_pred; }
1278 
1279  constexpr _Iterator
1280  begin()
1281  {
1282  if (_M_cached_begin._M_has_value())
1283  return {this, _M_cached_begin._M_get(_M_base)};
1284 
1285  __glibcxx_assert(_M_pred.has_value());
1286  auto __it = __detail::find_if(ranges::begin(_M_base),
1287  ranges::end(_M_base),
1288  std::ref(*_M_pred));
1289  _M_cached_begin._M_set(_M_base, __it);
1290  return {this, std::move(__it)};
1291  }
1292 
1293  constexpr auto
1294  end()
1295  {
1296  if constexpr (common_range<_Vp>)
1297  return _Iterator{this, ranges::end(_M_base)};
1298  else
1299  return _Sentinel{this};
1300  }
1301  };
1302 
1303  template<typename _Range, typename _Pred>
1304  filter_view(_Range&&, _Pred) -> filter_view<views::all_t<_Range>, _Pred>;
1305 
1306  namespace views
1307  {
1308  inline constexpr __adaptor::_RangeAdaptor filter
1309  = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p)
1310  {
1311  return filter_view{std::forward<_Range>(__r), std::forward<_Pred>(__p)};
1312  };
1313  } // namespace views
1314 
1315  template<input_range _Vp, copy_constructible _Fp>
1316  requires view<_Vp> && is_object_v<_Fp>
1317  && regular_invocable<_Fp&, range_reference_t<_Vp>>
1318  && std::__detail::__can_reference<invoke_result_t<_Fp&,
1319  range_reference_t<_Vp>>>
1320  class transform_view : public view_interface<transform_view<_Vp, _Fp>>
1321  {
1322  private:
1323  template<bool _Const>
1324  struct _Sentinel;
1325 
1326  template<bool _Const>
1327  struct _Iterator
1328  {
1329  private:
1330  using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1331  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1332 
1333  static constexpr auto
1334  _S_iter_concept()
1335  {
1336  if constexpr (random_access_range<_Vp>)
1337  return random_access_iterator_tag{};
1338  else if constexpr (bidirectional_range<_Vp>)
1339  return bidirectional_iterator_tag{};
1340  else if constexpr (forward_range<_Vp>)
1341  return forward_iterator_tag{};
1342  else
1343  return input_iterator_tag{};
1344  }
1345 
1346  static constexpr auto
1347  _S_iter_cat()
1348  {
1349  using _Res = invoke_result_t<_Fp&, range_reference_t<_Base>>;
1350  if constexpr (is_lvalue_reference_v<_Res>)
1351  {
1352  using _Cat
1353  = typename iterator_traits<_Base_iter>::iterator_category;
1354  if constexpr (derived_from<_Cat, contiguous_iterator_tag>)
1355  return random_access_iterator_tag{};
1356  else
1357  return _Cat{};
1358  }
1359  else
1360  return input_iterator_tag{};
1361  }
1362 
1363  using _Base_iter = iterator_t<_Base>;
1364 
1365  _Base_iter _M_current = _Base_iter();
1366  _Parent* _M_parent = nullptr;
1367 
1368  public:
1369  using iterator_concept = decltype(_S_iter_concept());
1370  using iterator_category = decltype(_S_iter_cat());
1371  using value_type
1372  = remove_cvref_t<invoke_result_t<_Fp&, range_reference_t<_Base>>>;
1373  using difference_type = range_difference_t<_Base>;
1374 
1375  _Iterator() = default;
1376 
1377  constexpr
1378  _Iterator(_Parent* __parent, _Base_iter __current)
1379  : _M_current(std::move(__current)),
1380  _M_parent(__parent)
1381  { }
1382 
1383  constexpr
1384  _Iterator(_Iterator<!_Const> __i)
1385  requires _Const
1386  && convertible_to<iterator_t<_Vp>, _Base_iter>
1387  : _M_current(std::move(__i._M_current)), _M_parent(__i._M_parent)
1388  { }
1389 
1390  constexpr _Base_iter
1391  base() const &
1392  requires copyable<_Base_iter>
1393  { return _M_current; }
1394 
1395  constexpr _Base_iter
1396  base() &&
1397  { return std::move(_M_current); }
1398 
1399  constexpr decltype(auto)
1400  operator*() const
1401  noexcept(noexcept(std::__invoke(*_M_parent->_M_fun, *_M_current)))
1402  { return std::__invoke(*_M_parent->_M_fun, *_M_current); }
1403 
1404  constexpr _Iterator&
1405  operator++()
1406  {
1407  ++_M_current;
1408  return *this;
1409  }
1410 
1411  constexpr void
1412  operator++(int)
1413  { ++_M_current; }
1414 
1415  constexpr _Iterator
1416  operator++(int) requires forward_range<_Base>
1417  {
1418  auto __tmp = *this;
1419  ++*this;
1420  return __tmp;
1421  }
1422 
1423  constexpr _Iterator&
1424  operator--() requires bidirectional_range<_Base>
1425  {
1426  --_M_current;
1427  return *this;
1428  }
1429 
1430  constexpr _Iterator
1431  operator--(int) requires bidirectional_range<_Base>
1432  {
1433  auto __tmp = *this;
1434  --*this;
1435  return __tmp;
1436  }
1437 
1438  constexpr _Iterator&
1439  operator+=(difference_type __n) requires random_access_range<_Base>
1440  {
1441  _M_current += __n;
1442  return *this;
1443  }
1444 
1445  constexpr _Iterator&
1446  operator-=(difference_type __n) requires random_access_range<_Base>
1447  {
1448  _M_current -= __n;
1449  return *this;
1450  }
1451 
1452  constexpr decltype(auto)
1453  operator[](difference_type __n) const
1454  requires random_access_range<_Base>
1455  { return std::__invoke(*_M_parent->_M_fun, _M_current[__n]); }
1456 
1457  friend constexpr bool
1458  operator==(const _Iterator& __x, const _Iterator& __y)
1459  requires equality_comparable<_Base_iter>
1460  { return __x._M_current == __y._M_current; }
1461 
1462  friend constexpr bool
1463  operator<(const _Iterator& __x, const _Iterator& __y)
1464  requires random_access_range<_Base>
1465  { return __x._M_current < __y._M_current; }
1466 
1467  friend constexpr bool
1468  operator>(const _Iterator& __x, const _Iterator& __y)
1469  requires random_access_range<_Base>
1470  { return __y < __x; }
1471 
1472  friend constexpr bool
1473  operator<=(const _Iterator& __x, const _Iterator& __y)
1474  requires random_access_range<_Base>
1475  { return !(__y < __x); }
1476 
1477  friend constexpr bool
1478  operator>=(const _Iterator& __x, const _Iterator& __y)
1479  requires random_access_range<_Base>
1480  { return !(__x < __y); }
1481 
1482 #ifdef __cpp_lib_three_way_comparison
1483  friend constexpr auto
1484  operator<=>(const _Iterator& __x, const _Iterator& __y)
1485  requires random_access_range<_Base>
1486  && three_way_comparable<_Base_iter>
1487  { return __x._M_current <=> __y._M_current; }
1488 #endif
1489 
1490  friend constexpr _Iterator
1491  operator+(_Iterator __i, difference_type __n)
1492  requires random_access_range<_Base>
1493  { return {__i._M_parent, __i._M_current + __n}; }
1494 
1495  friend constexpr _Iterator
1496  operator+(difference_type __n, _Iterator __i)
1497  requires random_access_range<_Base>
1498  { return {__i._M_parent, __i._M_current + __n}; }
1499 
1500  friend constexpr _Iterator
1501  operator-(_Iterator __i, difference_type __n)
1502  requires random_access_range<_Base>
1503  { return {__i._M_parent, __i._M_current - __n}; }
1504 
1505  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1506  // 3483. transform_view::iterator's difference is overconstrained
1507  friend constexpr difference_type
1508  operator-(const _Iterator& __x, const _Iterator& __y)
1509  requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
1510  { return __x._M_current - __y._M_current; }
1511 
1512  friend constexpr decltype(auto)
1513  iter_move(const _Iterator& __i) noexcept(noexcept(*__i))
1514  {
1515  if constexpr (is_lvalue_reference_v<decltype(*__i)>)
1516  return std::move(*__i);
1517  else
1518  return *__i;
1519  }
1520 
1521  friend constexpr void
1522  iter_swap(const _Iterator& __x, const _Iterator& __y)
1523  noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1524  requires indirectly_swappable<_Base_iter>
1525  { return ranges::iter_swap(__x._M_current, __y._M_current); }
1526 
1527  friend _Iterator<!_Const>;
1528  template<bool> friend struct _Sentinel;
1529  };
1530 
1531  template<bool _Const>
1532  struct _Sentinel
1533  {
1534  private:
1535  using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1536  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1537 
1538  template<bool _Const2>
1539  constexpr auto
1540  __distance_from(const _Iterator<_Const2>& __i) const
1541  { return _M_end - __i._M_current; }
1542 
1543  template<bool _Const2>
1544  constexpr bool
1545  __equal(const _Iterator<_Const2>& __i) const
1546  { return __i._M_current == _M_end; }
1547 
1548  sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1549 
1550  public:
1551  _Sentinel() = default;
1552 
1553  constexpr explicit
1554  _Sentinel(sentinel_t<_Base> __end)
1555  : _M_end(__end)
1556  { }
1557 
1558  constexpr
1559  _Sentinel(_Sentinel<!_Const> __i)
1560  requires _Const
1561  && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1562  : _M_end(std::move(__i._M_end))
1563  { }
1564 
1565  constexpr sentinel_t<_Base>
1566  base() const
1567  { return _M_end; }
1568 
1569  template<bool _Const2>
1570  requires sentinel_for<sentinel_t<_Base>,
1571  iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
1572  friend constexpr bool
1573  operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
1574  { return __y.__equal(__x); }
1575 
1576  template<bool _Const2,
1577  typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
1578  requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1579  friend constexpr range_difference_t<_Base2>
1580  operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
1581  { return -__y.__distance_from(__x); }
1582 
1583  template<bool _Const2,
1584  typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
1585  requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1586  friend constexpr range_difference_t<_Base2>
1587  operator-(const _Sentinel& __y, const _Iterator<_Const2>& __x)
1588  { return __y.__distance_from(__x); }
1589 
1590  friend _Sentinel<!_Const>;
1591  };
1592 
1593  [[no_unique_address]] __detail::__box<_Fp> _M_fun;
1594  _Vp _M_base = _Vp();
1595 
1596  public:
1597  transform_view() = default;
1598 
1599  constexpr
1600  transform_view(_Vp __base, _Fp __fun)
1601  : _M_fun(std::move(__fun)), _M_base(std::move(__base))
1602  { }
1603 
1604  constexpr _Vp
1605  base() const& requires copy_constructible<_Vp>
1606  { return _M_base ; }
1607 
1608  constexpr _Vp
1609  base() &&
1610  { return std::move(_M_base); }
1611 
1612  constexpr _Iterator<false>
1613  begin()
1614  { return _Iterator<false>{this, ranges::begin(_M_base)}; }
1615 
1616  constexpr _Iterator<true>
1617  begin() const
1618  requires range<const _Vp>
1619  && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1620  { return _Iterator<true>{this, ranges::begin(_M_base)}; }
1621 
1622  constexpr _Sentinel<false>
1623  end()
1624  { return _Sentinel<false>{ranges::end(_M_base)}; }
1625 
1626  constexpr _Iterator<false>
1627  end() requires common_range<_Vp>
1628  { return _Iterator<false>{this, ranges::end(_M_base)}; }
1629 
1630  constexpr _Sentinel<true>
1631  end() const
1632  requires range<const _Vp>
1633  && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1634  { return _Sentinel<true>{ranges::end(_M_base)}; }
1635 
1636  constexpr _Iterator<true>
1637  end() const
1638  requires common_range<const _Vp>
1639  && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1640  { return _Iterator<true>{this, ranges::end(_M_base)}; }
1641 
1642  constexpr auto
1643  size() requires sized_range<_Vp>
1644  { return ranges::size(_M_base); }
1645 
1646  constexpr auto
1647  size() const requires sized_range<const _Vp>
1648  { return ranges::size(_M_base); }
1649  };
1650 
1651  template<typename _Range, typename _Fp>
1652  transform_view(_Range&&, _Fp) -> transform_view<views::all_t<_Range>, _Fp>;
1653 
1654  namespace views
1655  {
1656  inline constexpr __adaptor::_RangeAdaptor transform
1657  = [] <viewable_range _Range, typename _Fp> (_Range&& __r, _Fp&& __f)
1658  {
1659  return transform_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)};
1660  };
1661  } // namespace views
1662 
1663  template<view _Vp>
1664  class take_view : public view_interface<take_view<_Vp>>
1665  {
1666  private:
1667  template<bool _Const>
1668  using _CI = counted_iterator<
1669  iterator_t<__detail::__maybe_const_t<_Const, _Vp>>>;
1670 
1671  template<bool _Const>
1672  struct _Sentinel
1673  {
1674  private:
1675  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1676  sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1677 
1678  public:
1679  _Sentinel() = default;
1680 
1681  constexpr explicit
1682  _Sentinel(sentinel_t<_Base> __end)
1683  : _M_end(__end)
1684  { }
1685 
1686  constexpr
1687  _Sentinel(_Sentinel<!_Const> __s)
1688  requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1689  : _M_end(std::move(__s._M_end))
1690  { }
1691 
1692  constexpr sentinel_t<_Base>
1693  base() const
1694  { return _M_end; }
1695 
1696  friend constexpr bool
1697  operator==(const _CI<_Const>& __y, const _Sentinel& __x)
1698  { return __y.count() == 0 || __y.base() == __x._M_end; }
1699 
1700  template<bool _OtherConst = !_Const,
1701  typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
1702  requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1703  friend constexpr bool
1704  operator==(const _CI<_OtherConst>& __y, const _Sentinel& __x)
1705  { return __y.count() == 0 || __y.base() == __x._M_end; }
1706 
1707  friend _Sentinel<!_Const>;
1708  };
1709 
1710  range_difference_t<_Vp> _M_count = 0;
1711  _Vp _M_base = _Vp();
1712 
1713  public:
1714  take_view() = default;
1715 
1716  constexpr
1717  take_view(_Vp base, range_difference_t<_Vp> __count)
1718  : _M_count(std::move(__count)), _M_base(std::move(base))
1719  { }
1720 
1721  constexpr _Vp
1722  base() const& requires copy_constructible<_Vp>
1723  { return _M_base; }
1724 
1725  constexpr _Vp
1726  base() &&
1727  { return std::move(_M_base); }
1728 
1729  constexpr auto
1730  begin() requires (!__detail::__simple_view<_Vp>)
1731  {
1732  if constexpr (sized_range<_Vp>)
1733  {
1734  if constexpr (random_access_range<_Vp>)
1735  return ranges::begin(_M_base);
1736  else
1737  {
1738  auto __sz = size();
1739  return counted_iterator{ranges::begin(_M_base), __sz};
1740  }
1741  }
1742  else
1743  return counted_iterator{ranges::begin(_M_base), _M_count};
1744  }
1745 
1746  constexpr auto
1747  begin() const requires range<const _Vp>
1748  {
1749  if constexpr (sized_range<const _Vp>)
1750  {
1751  if constexpr (random_access_range<const _Vp>)
1752  return ranges::begin(_M_base);
1753  else
1754  {
1755  auto __sz = size();
1756  return counted_iterator{ranges::begin(_M_base), __sz};
1757  }
1758  }
1759  else
1760  return counted_iterator{ranges::begin(_M_base), _M_count};
1761  }
1762 
1763  constexpr auto
1764  end() requires (!__detail::__simple_view<_Vp>)
1765  {
1766  if constexpr (sized_range<_Vp>)
1767  {
1768  if constexpr (random_access_range<_Vp>)
1769  return ranges::begin(_M_base) + size();
1770  else
1771  return default_sentinel;
1772  }
1773  else
1774  return _Sentinel<false>{ranges::end(_M_base)};
1775  }
1776 
1777  constexpr auto
1778  end() const requires range<const _Vp>
1779  {
1780  if constexpr (sized_range<const _Vp>)
1781  {
1782  if constexpr (random_access_range<const _Vp>)
1783  return ranges::begin(_M_base) + size();
1784  else
1785  return default_sentinel;
1786  }
1787  else
1788  return _Sentinel<true>{ranges::end(_M_base)};
1789  }
1790 
1791  constexpr auto
1792  size() requires sized_range<_Vp>
1793  {
1794  auto __n = ranges::size(_M_base);
1795  return __detail::min(__n, static_cast<decltype(__n)>(_M_count));
1796  }
1797 
1798  constexpr auto
1799  size() const requires sized_range<const _Vp>
1800  {
1801  auto __n = ranges::size(_M_base);
1802  return __detail::min(__n, static_cast<decltype(__n)>(_M_count));
1803  }
1804  };
1805 
1806  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1807  // 3447. Deduction guides for take_view and drop_view have different
1808  // constraints
1809  template<typename _Range>
1810  take_view(_Range&&, range_difference_t<_Range>)
1811  -> take_view<views::all_t<_Range>>;
1812 
1813  template<typename _Tp>
1814  inline constexpr bool enable_borrowed_range<take_view<_Tp>>
1815  = enable_borrowed_range<_Tp>;
1816 
1817  namespace views
1818  {
1819  inline constexpr __adaptor::_RangeAdaptor take
1820  = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n)
1821  {
1822  return take_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
1823  };
1824  } // namespace views
1825 
1826  template<view _Vp, typename _Pred>
1827  requires input_range<_Vp> && is_object_v<_Pred>
1828  && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
1829  class take_while_view : public view_interface<take_while_view<_Vp, _Pred>>
1830  {
1831  template<bool _Const>
1832  struct _Sentinel
1833  {
1834  private:
1835  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1836 
1837  sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1838  const _Pred* _M_pred = nullptr;
1839 
1840  public:
1841  _Sentinel() = default;
1842 
1843  constexpr explicit
1844  _Sentinel(sentinel_t<_Base> __end, const _Pred* __pred)
1845  : _M_end(__end), _M_pred(__pred)
1846  { }
1847 
1848  constexpr
1849  _Sentinel(_Sentinel<!_Const> __s)
1850  requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1851  : _M_end(__s._M_end), _M_pred(__s._M_pred)
1852  { }
1853 
1854  constexpr sentinel_t<_Base>
1855  base() const { return _M_end; }
1856 
1857  friend constexpr bool
1858  operator==(const iterator_t<_Base>& __x, const _Sentinel& __y)
1859  { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
1860 
1861  template<bool _OtherConst = !_Const,
1862  typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
1863  requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1864  friend constexpr bool
1865  operator==(const iterator_t<_Base2>& __x, const _Sentinel& __y)
1866  { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
1867 
1868  friend _Sentinel<!_Const>;
1869  };
1870 
1871  [[no_unique_address]] __detail::__box<_Pred> _M_pred;
1872  _Vp _M_base = _Vp();
1873 
1874  public:
1875  take_while_view() = default;
1876 
1877  constexpr
1878  take_while_view(_Vp base, _Pred __pred)
1879  : _M_pred(std::move(__pred)), _M_base(std::move(base))
1880  { }
1881 
1882  constexpr _Vp
1883  base() const& requires copy_constructible<_Vp>
1884  { return _M_base; }
1885 
1886  constexpr _Vp
1887  base() &&
1888  { return std::move(_M_base); }
1889 
1890  constexpr const _Pred&
1891  pred() const
1892  { return *_M_pred; }
1893 
1894  constexpr auto
1895  begin() requires (!__detail::__simple_view<_Vp>)
1896  { return ranges::begin(_M_base); }
1897 
1898  constexpr auto
1899  begin() const requires range<const _Vp>
1900  && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
1901  { return ranges::begin(_M_base); }
1902 
1903  constexpr auto
1904  end() requires (!__detail::__simple_view<_Vp>)
1905  { return _Sentinel<false>(ranges::end(_M_base),
1906  std::__addressof(*_M_pred)); }
1907 
1908  constexpr auto
1909  end() const requires range<const _Vp>
1910  && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
1911  { return _Sentinel<true>(ranges::end(_M_base),
1912  std::__addressof(*_M_pred)); }
1913  };
1914 
1915  template<typename _Range, typename _Pred>
1916  take_while_view(_Range&&, _Pred)
1917  -> take_while_view<views::all_t<_Range>, _Pred>;
1918 
1919  namespace views
1920  {
1921  inline constexpr __adaptor::_RangeAdaptor take_while
1922  = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p)
1923  {
1924  return take_while_view{std::forward<_Range>(__r), std::forward<_Pred>(__p)};
1925  };
1926  } // namespace views
1927 
1928  template<view _Vp>
1929  class drop_view : public view_interface<drop_view<_Vp>>
1930  {
1931  private:
1932  range_difference_t<_Vp> _M_count = 0;
1933  _Vp _M_base = _Vp();
1934 
1935  // ranges::next(begin(base), count, end(base)) is O(1) if _Vp satisfies
1936  // both random_access_range and sized_range. Otherwise, cache its result.
1937  static constexpr bool _S_needs_cached_begin
1938  = !(random_access_range<const _Vp> && sized_range<const _Vp>);
1939  [[no_unique_address]]
1940  __detail::__maybe_present_t<_S_needs_cached_begin,
1941  __detail::_CachedPosition<_Vp>>
1942  _M_cached_begin;
1943 
1944  public:
1945  drop_view() = default;
1946 
1947  constexpr
1948  drop_view(_Vp __base, range_difference_t<_Vp> __count)
1949  : _M_count(__count), _M_base(std::move(__base))
1950  { __glibcxx_assert(__count >= 0); }
1951 
1952  constexpr _Vp
1953  base() const& requires copy_constructible<_Vp>
1954  { return _M_base; }
1955 
1956  constexpr _Vp
1957  base() &&
1958  { return std::move(_M_base); }
1959 
1960  // This overload is disabled for simple views with constant-time begin().
1961  constexpr auto
1962  begin()
1963  requires (!(__detail::__simple_view<_Vp>
1964  && random_access_range<const _Vp>
1965  && sized_range<const _Vp>))
1966  {
1967  if constexpr (_S_needs_cached_begin)
1968  if (_M_cached_begin._M_has_value())
1969  return _M_cached_begin._M_get(_M_base);
1970 
1971  auto __it = ranges::next(ranges::begin(_M_base),
1972  _M_count, ranges::end(_M_base));
1973  if constexpr (_S_needs_cached_begin)
1974  _M_cached_begin._M_set(_M_base, __it);
1975  return __it;
1976  }
1977 
1978  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1979  // 3482. drop_view's const begin should additionally require sized_range
1980  constexpr auto
1981  begin() const
1982  requires random_access_range<const _Vp> && sized_range<const _Vp>
1983  {
1984  return ranges::next(ranges::begin(_M_base), _M_count,
1985  ranges::end(_M_base));
1986  }
1987 
1988  constexpr auto
1989  end() requires (!__detail::__simple_view<_Vp>)
1990  { return ranges::end(_M_base); }
1991 
1992  constexpr auto
1993  end() const requires range<const _Vp>
1994  { return ranges::end(_M_base); }
1995 
1996  constexpr auto
1997  size() requires sized_range<_Vp>
1998  {
1999  const auto __s = ranges::size(_M_base);
2000  const auto __c = static_cast<decltype(__s)>(_M_count);
2001  return __s < __c ? 0 : __s - __c;
2002  }
2003 
2004  constexpr auto
2005  size() const requires sized_range<const _Vp>
2006  {
2007  const auto __s = ranges::size(_M_base);
2008  const auto __c = static_cast<decltype(__s)>(_M_count);
2009  return __s < __c ? 0 : __s - __c;
2010  }
2011  };
2012 
2013  template<typename _Range>
2014  drop_view(_Range&&, range_difference_t<_Range>)
2015  -> drop_view<views::all_t<_Range>>;
2016 
2017  template<typename _Tp>
2018  inline constexpr bool enable_borrowed_range<drop_view<_Tp>>
2019  = enable_borrowed_range<_Tp>;
2020 
2021  namespace views
2022  {
2023  inline constexpr __adaptor::_RangeAdaptor drop
2024  = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n)
2025  {
2026  return drop_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
2027  };
2028  } // namespace views
2029 
2030  template<view _Vp, typename _Pred>
2031  requires input_range<_Vp> && is_object_v<_Pred>
2032  && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2033  class drop_while_view : public view_interface<drop_while_view<_Vp, _Pred>>
2034  {
2035  private:
2036  [[no_unique_address]] __detail::__box<_Pred> _M_pred;
2037  [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
2038  _Vp _M_base = _Vp();
2039 
2040  public:
2041  drop_while_view() = default;
2042 
2043  constexpr
2044  drop_while_view(_Vp __base, _Pred __pred)
2045  : _M_pred(std::move(__pred)), _M_base(std::move(__base))
2046  { }
2047 
2048  constexpr _Vp
2049  base() const& requires copy_constructible<_Vp>
2050  { return _M_base; }
2051 
2052  constexpr _Vp
2053  base() &&
2054  { return std::move(_M_base); }
2055 
2056  constexpr const _Pred&
2057  pred() const
2058  { return *_M_pred; }
2059 
2060  constexpr auto
2061  begin()
2062  {
2063  if (_M_cached_begin._M_has_value())
2064  return _M_cached_begin._M_get(_M_base);
2065 
2066  auto __it = __detail::find_if_not(ranges::begin(_M_base),
2067  ranges::end(_M_base),
2068  std::cref(*_M_pred));
2069  _M_cached_begin._M_set(_M_base, __it);
2070  return __it;
2071  }
2072 
2073  constexpr auto
2074  end()
2075  { return ranges::end(_M_base); }
2076  };
2077 
2078  template<typename _Range, typename _Pred>
2079  drop_while_view(_Range&&, _Pred)
2080  -> drop_while_view<views::all_t<_Range>, _Pred>;
2081 
2082  template<typename _Tp, typename _Pred>
2083  inline constexpr bool enable_borrowed_range<drop_while_view<_Tp, _Pred>>
2084  = enable_borrowed_range<_Tp>;
2085 
2086  namespace views
2087  {
2088  inline constexpr __adaptor::_RangeAdaptor drop_while
2089  = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p)
2090  {
2091  return drop_while_view{std::forward<_Range>(__r),
2092  std::forward<_Pred>(__p)};
2093  };
2094  } // namespace views
2095 
2096  template<input_range _Vp>
2097  requires view<_Vp> && input_range<range_reference_t<_Vp>>
2098  && (is_reference_v<range_reference_t<_Vp>>
2099  || view<range_value_t<_Vp>>)
2100  class join_view : public view_interface<join_view<_Vp>>
2101  {
2102  private:
2103  using _InnerRange = range_reference_t<_Vp>;
2104 
2105  template<bool _Const>
2106  struct _Sentinel;
2107 
2108  template<bool _Const>
2109  struct _Iterator
2110  {
2111  private:
2112  using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2113  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2114 
2115  static constexpr bool _S_ref_is_glvalue
2116  = is_reference_v<range_reference_t<_Base>>;
2117 
2118  constexpr void
2119  _M_satisfy()
2120  {
2121  auto __update_inner = [this] (range_reference_t<_Base> __x) -> auto&
2122  {
2123  if constexpr (_S_ref_is_glvalue)
2124  return __x;
2125  else
2126  return (_M_parent->_M_inner = views::all(std::move(__x)));
2127  };
2128 
2129  for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer)
2130  {
2131  auto& __inner = __update_inner(*_M_outer);
2132  _M_inner = ranges::begin(__inner);
2133  if (_M_inner != ranges::end(__inner))
2134  return;
2135  }
2136 
2137  if constexpr (_S_ref_is_glvalue)
2138  _M_inner = _Inner_iter();
2139  }
2140 
2141  static constexpr auto
2142  _S_iter_concept()
2143  {
2144  if constexpr (_S_ref_is_glvalue
2145  && bidirectional_range<_Base>
2146  && bidirectional_range<range_reference_t<_Base>>)
2147  return bidirectional_iterator_tag{};
2148  else if constexpr (_S_ref_is_glvalue
2149  && forward_range<_Base>
2150  && forward_range<range_reference_t<_Base>>)
2151  return forward_iterator_tag{};
2152  else
2153  return input_iterator_tag{};
2154  }
2155 
2156  static constexpr auto
2157  _S_iter_cat()
2158  {
2159  using _OuterCat
2160  = typename iterator_traits<_Outer_iter>::iterator_category;
2161  using _InnerCat
2162  = typename iterator_traits<_Inner_iter>::iterator_category;
2163  if constexpr (_S_ref_is_glvalue
2164  && derived_from<_OuterCat, bidirectional_iterator_tag>
2165  && derived_from<_InnerCat, bidirectional_iterator_tag>)
2166  return bidirectional_iterator_tag{};
2167  else if constexpr (_S_ref_is_glvalue
2168  && derived_from<_OuterCat, forward_iterator_tag>
2169  && derived_from<_InnerCat, forward_iterator_tag>)
2170  return forward_iterator_tag{};
2171  else if constexpr (derived_from<_OuterCat, input_iterator_tag>
2172  && derived_from<_InnerCat, input_iterator_tag>)
2173  return input_iterator_tag{};
2174  else
2175  return output_iterator_tag{};
2176  }
2177 
2178  using _Outer_iter = iterator_t<_Base>;
2179  using _Inner_iter = iterator_t<range_reference_t<_Base>>;
2180 
2181  _Outer_iter _M_outer = _Outer_iter();
2182  _Inner_iter _M_inner = _Inner_iter();
2183  _Parent* _M_parent = nullptr;
2184 
2185  public:
2186  using iterator_concept = decltype(_S_iter_concept());
2187  using iterator_category = decltype(_S_iter_cat());
2188  using value_type = range_value_t<range_reference_t<_Base>>;
2189  using difference_type
2190  = common_type_t<range_difference_t<_Base>,
2191  range_difference_t<range_reference_t<_Base>>>;
2192 
2193  _Iterator() = default;
2194 
2195  constexpr
2196  _Iterator(_Parent* __parent, _Outer_iter __outer)
2197  : _M_outer(std::move(__outer)),
2198  _M_parent(__parent)
2199  { _M_satisfy(); }
2200 
2201  constexpr
2202  _Iterator(_Iterator<!_Const> __i)
2203  requires _Const
2204  && convertible_to<iterator_t<_Vp>, _Outer_iter>
2205  && convertible_to<iterator_t<_InnerRange>, _Inner_iter>
2206  : _M_outer(std::move(__i._M_outer)), _M_inner(__i._M_inner),
2207  _M_parent(__i._M_parent)
2208  { }
2209 
2210  constexpr decltype(auto)
2211  operator*() const
2212  { return *_M_inner; }
2213 
2214  // _GLIBCXX_RESOLVE_LIB_DEFECTS
2215  // 3500. join_view::iterator::operator->() is bogus
2216  constexpr _Inner_iter
2217  operator->() const
2218  requires __detail::__has_arrow<_Inner_iter>
2219  && copyable<_Inner_iter>
2220  { return _M_inner; }
2221 
2222  constexpr _Iterator&
2223  operator++()
2224  {
2225  auto&& __inner_range = [this] () -> decltype(auto) {
2226  if constexpr (_S_ref_is_glvalue)
2227  return *_M_outer;
2228  else
2229  return _M_parent->_M_inner;
2230  }();
2231  if (++_M_inner == ranges::end(__inner_range))
2232  {
2233  ++_M_outer;
2234  _M_satisfy();
2235  }
2236  return *this;
2237  }
2238 
2239  constexpr void
2240  operator++(int)
2241  { ++*this; }
2242 
2243  constexpr _Iterator
2244  operator++(int)
2245  requires _S_ref_is_glvalue && forward_range<_Base>
2246  && forward_range<range_reference_t<_Base>>
2247  {
2248  auto __tmp = *this;
2249  ++*this;
2250  return __tmp;
2251  }
2252 
2253  constexpr _Iterator&
2254  operator--()
2255  requires _S_ref_is_glvalue && bidirectional_range<_Base>
2256  && bidirectional_range<range_reference_t<_Base>>
2257  && common_range<range_reference_t<_Base>>
2258  {
2259  if (_M_outer == ranges::end(_M_parent->_M_base))
2260  _M_inner = ranges::end(*--_M_outer);
2261  while (_M_inner == ranges::begin(*_M_outer))
2262  _M_inner = ranges::end(*--_M_outer);
2263  --_M_inner;
2264  return *this;
2265  }
2266 
2267  constexpr _Iterator
2268  operator--(int)
2269  requires _S_ref_is_glvalue && bidirectional_range<_Base>
2270  && bidirectional_range<range_reference_t<_Base>>
2271  && common_range<range_reference_t<_Base>>
2272  {
2273  auto __tmp = *this;
2274  --*this;
2275  return __tmp;
2276  }
2277 
2278  friend constexpr bool
2279  operator==(const _Iterator& __x, const _Iterator& __y)
2280  requires _S_ref_is_glvalue
2281  && equality_comparable<_Outer_iter>
2282  && equality_comparable<_Inner_iter>
2283  {
2284  return (__x._M_outer == __y._M_outer
2285  && __x._M_inner == __y._M_inner);
2286  }
2287 
2288  friend constexpr decltype(auto)
2289  iter_move(const _Iterator& __i)
2290  noexcept(noexcept(ranges::iter_move(__i._M_inner)))
2291  { return ranges::iter_move(__i._M_inner); }
2292 
2293  friend constexpr void
2294  iter_swap(const _Iterator& __x, const _Iterator& __y)
2295  noexcept(noexcept(ranges::iter_swap(__x._M_inner, __y._M_inner)))
2296  { return ranges::iter_swap(__x._M_inner, __y._M_inner); }
2297 
2298  friend _Iterator<!_Const>;
2299  template<bool> friend struct _Sentinel;
2300  };
2301 
2302  template<bool _Const>
2303  struct _Sentinel
2304  {
2305  private:
2306  using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2307  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2308 
2309  template<bool _Const2>
2310  constexpr bool
2311  __equal(const _Iterator<_Const2>& __i) const
2312  { return __i._M_outer == _M_end; }
2313 
2314  sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2315 
2316  public:
2317  _Sentinel() = default;
2318 
2319  constexpr explicit
2320  _Sentinel(_Parent* __parent)
2321  : _M_end(ranges::end(__parent->_M_base))
2322  { }
2323 
2324  constexpr
2325  _Sentinel(_Sentinel<!_Const> __s)
2326  requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2327  : _M_end(std::move(__s._M_end))
2328  { }
2329 
2330  template<bool _Const2>
2331  requires sentinel_for<sentinel_t<_Base>,
2332  iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
2333  friend constexpr bool
2334  operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
2335  { return __y.__equal(__x); }
2336 
2337  friend _Sentinel<!_Const>;
2338  };
2339 
2340  // XXX: _M_inner is "present only when !is_reference_v<_InnerRange>"
2341  [[no_unique_address]]
2342  __detail::__maybe_present_t<!is_reference_v<_InnerRange>,
2343  views::all_t<_InnerRange>> _M_inner;
2344  _Vp _M_base = _Vp();
2345 
2346  public:
2347  join_view() = default;
2348 
2349  constexpr explicit
2350  join_view(_Vp __base)
2351  : _M_base(std::move(__base))
2352  { }
2353 
2354  constexpr _Vp
2355  base() const& requires copy_constructible<_Vp>
2356  { return _M_base; }
2357 
2358  constexpr _Vp
2359  base() &&
2360  { return std::move(_M_base); }
2361 
2362  constexpr auto
2363  begin()
2364  {
2365  constexpr bool __use_const
2366  = (__detail::__simple_view<_Vp>
2367  && is_reference_v<range_reference_t<_Vp>>);
2368  return _Iterator<__use_const>{this, ranges::begin(_M_base)};
2369  }
2370 
2371  constexpr auto
2372  begin() const
2373  requires input_range<const _Vp>
2374  && is_reference_v<range_reference_t<const _Vp>>
2375  {
2376  return _Iterator<true>{this, ranges::begin(_M_base)};
2377  }
2378 
2379  constexpr auto
2380  end()
2381  {
2382  if constexpr (forward_range<_Vp> && is_reference_v<_InnerRange>
2383  && forward_range<_InnerRange>
2384  && common_range<_Vp> && common_range<_InnerRange>)
2385  return _Iterator<__detail::__simple_view<_Vp>>{this,
2386  ranges::end(_M_base)};
2387  else
2388  return _Sentinel<__detail::__simple_view<_Vp>>{this};
2389  }
2390 
2391  constexpr auto
2392  end() const
2393  requires input_range<const _Vp>
2394  && is_reference_v<range_reference_t<const _Vp>>
2395  {
2396  if constexpr (forward_range<const _Vp>
2397  && is_reference_v<range_reference_t<const _Vp>>
2398  && forward_range<range_reference_t<const _Vp>>
2399  && common_range<const _Vp>
2400  && common_range<range_reference_t<const _Vp>>)
2401  return _Iterator<true>{this, ranges::end(_M_base)};
2402  else
2403  return _Sentinel<true>{this};
2404  }
2405  };
2406 
2407  template<typename _Range>
2408  explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;
2409 
2410  namespace views
2411  {
2412  inline constexpr __adaptor::_RangeAdaptorClosure join
2413  = [] <viewable_range _Range> (_Range&& __r)
2414  {
2415  // _GLIBCXX_RESOLVE_LIB_DEFECTS
2416  // 3474. Nesting join_views is broken because of CTAD
2417  return join_view<views::all_t<_Range>>{std::forward<_Range>(__r)};
2418  };
2419  } // namespace views
2420 
2421  namespace __detail
2422  {
2423  template<auto>
2424  struct __require_constant;
2425 
2426  template<typename _Range>
2427  concept __tiny_range = sized_range<_Range>
2428  && requires
2429  { typename __require_constant<remove_reference_t<_Range>::size()>; }
2430  && (remove_reference_t<_Range>::size() <= 1);
2431  }
2432 
2433  template<input_range _Vp, forward_range _Pattern>
2434  requires view<_Vp> && view<_Pattern>
2435  && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
2436  ranges::equal_to>
2437  && (forward_range<_Vp> || __detail::__tiny_range<_Pattern>)
2438  class split_view : public view_interface<split_view<_Vp, _Pattern>>
2439  {
2440  private:
2441  template<bool _Const>
2442  struct _InnerIter;
2443 
2444  template<bool _Const>
2445  struct _OuterIter
2446  {
2447  private:
2448  using _Parent = __detail::__maybe_const_t<_Const, split_view>;
2449  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2450 
2451  constexpr bool
2452  __at_end() const
2453  { return __current() == ranges::end(_M_parent->_M_base); }
2454 
2455  // [range.split.outer] p1
2456  // Many of the following specifications refer to the notional member
2457  // current of outer-iterator. current is equivalent to current_ if
2458  // V models forward_range, and parent_->current_ otherwise.
2459  constexpr auto&
2460  __current() noexcept
2461  {
2462  if constexpr (forward_range<_Vp>)
2463  return _M_current;
2464  else
2465  return _M_parent->_M_current;
2466  }
2467 
2468  constexpr auto&
2469  __current() const noexcept
2470  {
2471  if constexpr (forward_range<_Vp>)
2472  return _M_current;
2473  else
2474  return _M_parent->_M_current;
2475  }
2476 
2477  _Parent* _M_parent = nullptr;
2478 
2479  // XXX: _M_current is present only if "V models forward_range"
2480  [[no_unique_address]]
2481  __detail::__maybe_present_t<forward_range<_Vp>,
2482  iterator_t<_Base>> _M_current;
2483 
2484  public:
2485  using iterator_concept = conditional_t<forward_range<_Base>,
2486  forward_iterator_tag,
2487  input_iterator_tag>;
2488  using iterator_category = input_iterator_tag;
2489  using difference_type = range_difference_t<_Base>;
2490 
2491  struct value_type : view_interface<value_type>
2492  {
2493  private:
2494  _OuterIter _M_i = _OuterIter();
2495 
2496  public:
2497  value_type() = default;
2498 
2499  constexpr explicit
2500  value_type(_OuterIter __i)
2501  : _M_i(std::move(__i))
2502  { }
2503 
2504  constexpr _InnerIter<_Const>
2505  begin() const
2506  requires copyable<_OuterIter>
2507  { return _InnerIter<_Const>{_M_i}; }
2508 
2509  constexpr _InnerIter<_Const>
2510  begin()
2511  requires (!copyable<_OuterIter>)
2512  { return _InnerIter<_Const>{std::move(_M_i)}; }
2513 
2514  constexpr default_sentinel_t
2515  end() const
2516  { return default_sentinel; }
2517  };
2518 
2519  _OuterIter() = default;
2520 
2521  constexpr explicit
2522  _OuterIter(_Parent* __parent) requires (!forward_range<_Base>)
2523  : _M_parent(__parent)
2524  { }
2525 
2526  constexpr
2527  _OuterIter(_Parent* __parent, iterator_t<_Base> __current)
2528  requires forward_range<_Base>
2529  : _M_parent(__parent),
2530  _M_current(std::move(__current))
2531  { }
2532 
2533  constexpr
2534  _OuterIter(_OuterIter<!_Const> __i)
2535  requires _Const
2536  && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
2537  : _M_parent(__i._M_parent), _M_current(std::move(__i._M_current))
2538  { }
2539 
2540  constexpr value_type
2541  operator*() const
2542  { return value_type{*this}; }
2543 
2544  constexpr _OuterIter&
2545  operator++()
2546  {
2547  const auto __end = ranges::end(_M_parent->_M_base);
2548  if (__current() == __end)
2549  return *this;
2550  const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern};
2551  if (__pbegin == __pend)
2552  ++__current();
2553  else
2554  do
2555  {
2556  auto [__b, __p]
2557  = __detail::mismatch(std::move(__current()), __end,
2558  __pbegin, __pend);
2559  __current() = std::move(__b);
2560  if (__p == __pend)
2561  break;
2562  } while (++__current() != __end);
2563  return *this;
2564  }
2565 
2566  constexpr decltype(auto)
2567  operator++(int)
2568  {
2569  if constexpr (forward_range<_Base>)
2570  {
2571  auto __tmp = *this;
2572  ++*this;
2573  return __tmp;
2574  }
2575  else
2576  ++*this;
2577  }
2578 
2579  friend constexpr bool
2580  operator==(const _OuterIter& __x, const _OuterIter& __y)
2581  requires forward_range<_Base>
2582  { return __x._M_current == __y._M_current; }
2583 
2584  friend constexpr bool
2585  operator==(const _OuterIter& __x, default_sentinel_t)
2586  { return __x.__at_end(); };
2587 
2588  friend _OuterIter<!_Const>;
2589  friend _InnerIter<_Const>;
2590  };
2591 
2592  template<bool _Const>
2593  struct _InnerIter
2594  {
2595  private:
2596  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2597 
2598  constexpr bool
2599  __at_end() const
2600  {
2601  auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern};
2602  auto __end = ranges::end(_M_i._M_parent->_M_base);
2603  if constexpr (__detail::__tiny_range<_Pattern>)
2604  {
2605  const auto& __cur = _M_i_current();
2606  if (__cur == __end)
2607  return true;
2608  if (__pcur == __pend)
2609  return _M_incremented;
2610  return *__cur == *__pcur;
2611  }
2612  else
2613  {
2614  auto __cur = _M_i_current();
2615  if (__cur == __end)
2616  return true;
2617  if (__pcur == __pend)
2618  return _M_incremented;
2619  do
2620  {
2621  if (*__cur != *__pcur)
2622  return false;
2623  if (++__pcur == __pend)
2624  return true;
2625  } while (++__cur != __end);
2626  return false;
2627  }
2628  }
2629 
2630  static constexpr auto
2631  _S_iter_cat()
2632  {
2633  using _Cat
2634  = typename iterator_traits<iterator_t<_Base>>::iterator_category;
2635  if constexpr (derived_from<_Cat, forward_iterator_tag>)
2636  return forward_iterator_tag{};
2637  else
2638  return _Cat{};
2639  }
2640 
2641  constexpr auto&
2642  _M_i_current() noexcept
2643  { return _M_i.__current(); }
2644 
2645  constexpr auto&
2646  _M_i_current() const noexcept
2647  { return _M_i.__current(); }
2648 
2649  _OuterIter<_Const> _M_i = _OuterIter<_Const>();
2650  bool _M_incremented = false;
2651 
2652  public:
2653  using iterator_concept
2654  = typename _OuterIter<_Const>::iterator_concept;
2655  using iterator_category = decltype(_S_iter_cat());
2656  using value_type = range_value_t<_Base>;
2657  using difference_type = range_difference_t<_Base>;
2658 
2659  _InnerIter() = default;
2660 
2661  constexpr explicit
2662  _InnerIter(_OuterIter<_Const> __i)
2663  : _M_i(std::move(__i))
2664  { }
2665 
2666  constexpr decltype(auto)
2667  operator*() const
2668  { return *_M_i_current(); }
2669 
2670  constexpr _InnerIter&
2671  operator++()
2672  {
2673  _M_incremented = true;
2674  if constexpr (!forward_range<_Base>)
2675  if constexpr (_Pattern::size() == 0)
2676  return *this;
2677  ++_M_i_current();
2678  return *this;
2679  }
2680 
2681  constexpr decltype(auto)
2682  operator++(int)
2683  {
2684  if constexpr (forward_range<_Vp>)
2685  {
2686  auto __tmp = *this;
2687  ++*this;
2688  return __tmp;
2689  }
2690  else
2691  ++*this;
2692  }
2693 
2694  friend constexpr bool
2695  operator==(const _InnerIter& __x, const _InnerIter& __y)
2696  requires forward_range<_Base>
2697  { return __x._M_i == __y._M_i; }
2698 
2699  friend constexpr bool
2700  operator==(const _InnerIter& __x, default_sentinel_t)
2701  { return __x.__at_end(); }
2702 
2703  friend constexpr decltype(auto)
2704  iter_move(const _InnerIter& __i)
2705  noexcept(noexcept(ranges::iter_move(__i._M_i_current())))
2706  { return ranges::iter_move(__i._M_i_current()); }
2707 
2708  friend constexpr void
2709  iter_swap(const _InnerIter& __x, const _InnerIter& __y)
2710  noexcept(noexcept(ranges::iter_swap(__x._M_i_current(),
2711  __y._M_i_current())))
2712  requires indirectly_swappable<iterator_t<_Base>>
2713  { ranges::iter_swap(__x._M_i_current(), __y._M_i_current()); }
2714  };
2715 
2716  _Pattern _M_pattern = _Pattern();
2717  // XXX: _M_current is "present only if !forward_range<V>"
2718  [[no_unique_address]]
2719  __detail::__maybe_present_t<!forward_range<_Vp>,
2720  iterator_t<_Vp>> _M_current;
2721  _Vp _M_base = _Vp();
2722 
2723 
2724  public:
2725  split_view() = default;
2726 
2727  constexpr
2728  split_view(_Vp __base, _Pattern __pattern)
2729  : _M_pattern(std::move(__pattern)), _M_base(std::move(__base))
2730  { }
2731 
2732  template<input_range _Range>
2733  requires constructible_from<_Vp, views::all_t<_Range>>
2734  && constructible_from<_Pattern, single_view<range_value_t<_Range>>>
2735  constexpr
2736  split_view(_Range&& __r, range_value_t<_Range> __e)
2737  : _M_pattern(std::move(__e)),
2738  _M_base(views::all(std::forward<_Range>(__r)))
2739  { }
2740 
2741  constexpr _Vp
2742  base() const& requires copy_constructible<_Vp>
2743  { return _M_base; }
2744 
2745  constexpr _Vp
2746  base() &&
2747  { return std::move(_M_base); }
2748 
2749  constexpr auto
2750  begin()
2751  {
2752  if constexpr (forward_range<_Vp>)
2753  return _OuterIter<__detail::__simple_view<_Vp>>{
2754  this, ranges::begin(_M_base)};
2755  else
2756  {
2757  _M_current = ranges::begin(_M_base);
2758  return _OuterIter<false>{this};
2759  }
2760  }
2761 
2762  constexpr auto
2763  begin() const requires forward_range<_Vp> && forward_range<const _Vp>
2764  {
2765  return _OuterIter<true>{this, ranges::begin(_M_base)};
2766  }
2767 
2768  constexpr auto
2769  end() requires forward_range<_Vp> && common_range<_Vp>
2770  {
2771  return _OuterIter<__detail::__simple_view<_Vp>>{
2772  this, ranges::end(_M_base)};
2773  }
2774 
2775  constexpr auto
2776  end() const
2777  {
2778  if constexpr (forward_range<_Vp>
2779  && forward_range<const _Vp>
2780  && common_range<const _Vp>)
2781  return _OuterIter<true>{this, ranges::end(_M_base)};
2782  else
2783  return default_sentinel;
2784  }
2785  };
2786 
2787  template<typename _Range, typename _Pred>
2788  split_view(_Range&&, _Pred&&)
2789  -> split_view<views::all_t<_Range>, views::all_t<_Pred>>;
2790 
2791  template<input_range _Range>
2792  split_view(_Range&&, range_value_t<_Range>)
2793  -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
2794 
2795  namespace views
2796  {
2797  inline constexpr __adaptor::_RangeAdaptor split
2798  = [] <viewable_range _Range, typename _Fp> (_Range&& __r, _Fp&& __f)
2799  {
2800  return split_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)};
2801  };
2802  } // namespace views
2803 
2804  namespace views
2805  {
2806  struct _Counted
2807  {
2808  template<input_or_output_iterator _Iter>
2809  constexpr auto
2810  operator()(_Iter __i, iter_difference_t<_Iter> __n) const
2811  {
2812  if constexpr (random_access_iterator<_Iter>)
2813  return subrange{__i, __i + __n};
2814  else
2815  return subrange{counted_iterator{std::move(__i), __n},
2816  default_sentinel};
2817  }
2818  };
2819 
2820  inline constexpr _Counted counted{};
2821  } // namespace views
2822 
2823  template<view _Vp>
2824  requires (!common_range<_Vp>) && copyable<iterator_t<_Vp>>
2825  class common_view : public view_interface<common_view<_Vp>>
2826  {
2827  private:
2828  _Vp _M_base = _Vp();
2829 
2830  public:
2831  common_view() = default;
2832 
2833  constexpr explicit
2834  common_view(_Vp __r)
2835  : _M_base(std::move(__r))
2836  { }
2837 
2838  /* XXX: LWG 3280 didn't remove this constructor, but I think it should?
2839  template<viewable_range _Range>
2840  requires (!common_range<_Range>)
2841  && constructible_from<_Vp, views::all_t<_Range>>
2842  constexpr explicit
2843  common_view(_Range&& __r)
2844  : _M_base(views::all(std::forward<_Range>(__r)))
2845  { }
2846  */
2847 
2848  constexpr _Vp
2849  base() const& requires copy_constructible<_Vp>
2850  { return _M_base; }
2851 
2852  constexpr _Vp
2853  base() &&
2854  { return std::move(_M_base); }
2855 
2856  constexpr auto
2857  begin()
2858  {
2859  if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
2860  return ranges::begin(_M_base);
2861  else
2862  return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
2863  (ranges::begin(_M_base));
2864  }
2865 
2866  constexpr auto
2867  begin() const requires range<const _Vp>
2868  {
2869  if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
2870  return ranges::begin(_M_base);
2871  else
2872  return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
2873  (ranges::begin(_M_base));
2874  }
2875 
2876  constexpr auto
2877  end()
2878  {
2879  if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
2880  return ranges::begin(_M_base) + ranges::size(_M_base);
2881  else
2882  return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
2883  (ranges::end(_M_base));
2884  }
2885 
2886  constexpr auto
2887  end() const requires range<const _Vp>
2888  {
2889  if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
2890  return ranges::begin(_M_base) + ranges::size(_M_base);
2891  else
2892  return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
2893  (ranges::end(_M_base));
2894  }
2895 
2896  constexpr auto
2897  size() requires sized_range<_Vp>
2898  { return ranges::size(_M_base); }
2899 
2900  constexpr auto
2901  size() const requires sized_range<const _Vp>
2902  { return ranges::size(_M_base); }
2903  };
2904 
2905  template<typename _Range>
2906  common_view(_Range&&) -> common_view<views::all_t<_Range>>;
2907 
2908  template<typename _Tp>
2909  inline constexpr bool enable_borrowed_range<common_view<_Tp>>
2910  = enable_borrowed_range<_Tp>;
2911 
2912  namespace views
2913  {
2914  inline constexpr __adaptor::_RangeAdaptorClosure common
2915  = [] <viewable_range _Range> (_Range&& __r)
2916  {
2917  if constexpr (common_range<_Range>
2918  && requires { views::all(std::forward<_Range>(__r)); })
2919  return views::all(std::forward<_Range>(__r));
2920  else
2921  return common_view{std::forward<_Range>(__r)};
2922  };
2923 
2924  } // namespace views
2925 
2926  template<view _Vp>
2927  requires bidirectional_range<_Vp>
2928  class reverse_view : public view_interface<reverse_view<_Vp>>
2929  {
2930  private:
2931  static constexpr bool _S_needs_cached_begin
2932  = !common_range<_Vp> && !random_access_range<_Vp>;
2933 
2934  [[no_unique_address]]
2935  __detail::__maybe_present_t<_S_needs_cached_begin,
2936  __detail::_CachedPosition<_Vp>>
2937  _M_cached_begin;
2938  _Vp _M_base = _Vp();
2939 
2940  public:
2941  reverse_view() = default;
2942 
2943  constexpr explicit
2944  reverse_view(_Vp __r)
2945  : _M_base(std::move(__r))
2946  { }
2947 
2948  constexpr _Vp
2949  base() const& requires copy_constructible<_Vp>
2950  { return _M_base; }
2951 
2952  constexpr _Vp
2953  base() &&
2954  { return std::move(_M_base); }
2955 
2956  constexpr reverse_iterator<iterator_t<_Vp>>
2957  begin()
2958  {
2959  if constexpr (_S_needs_cached_begin)
2960  if (_M_cached_begin._M_has_value())
2961  return std::make_reverse_iterator(_M_cached_begin._M_get(_M_base));
2962 
2963  auto __it = ranges::next(ranges::begin(_M_base), ranges::end(_M_base));
2964  if constexpr (_S_needs_cached_begin)
2965  _M_cached_begin._M_set(_M_base, __it);
2966  return std::make_reverse_iterator(std::move(__it));
2967  }
2968 
2969  constexpr auto
2970  begin() requires common_range<_Vp>
2971  { return std::make_reverse_iterator(ranges::end(_M_base)); }
2972 
2973  constexpr auto
2974  begin() const requires common_range<const _Vp>
2975  { return std::make_reverse_iterator(ranges::end(_M_base)); }
2976 
2977  constexpr reverse_iterator<iterator_t<_Vp>>
2978  end()
2979  { return std::make_reverse_iterator(ranges::begin(_M_base)); }
2980 
2981  constexpr auto
2982  end() const requires common_range<const _Vp>
2983  { return std::make_reverse_iterator(ranges::begin(_M_base)); }
2984 
2985  constexpr auto
2986  size() requires sized_range<_Vp>
2987  { return ranges::size(_M_base); }
2988 
2989  constexpr auto
2990  size() const requires sized_range<const _Vp>
2991  { return ranges::size(_M_base); }
2992  };
2993 
2994  template<typename _Range>
2995  reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>;
2996 
2997  template<typename _Tp>
2998  inline constexpr bool enable_borrowed_range<reverse_view<_Tp>>
2999  = enable_borrowed_range<_Tp>;
3000 
3001  namespace views
3002  {
3003  namespace __detail
3004  {
3005  template<typename>
3006  inline constexpr bool __is_reversible_subrange = false;
3007 
3008  template<typename _Iter, subrange_kind _Kind>
3009  inline constexpr bool
3010  __is_reversible_subrange<subrange<reverse_iterator<_Iter>,
3011  reverse_iterator<_Iter>,
3012  _Kind>> = true;
3013 
3014  template<typename>
3015  inline constexpr bool __is_reverse_view = false;
3016 
3017  template<typename _Vp>
3018  inline constexpr bool __is_reverse_view<reverse_view<_Vp>> = true;
3019  }
3020 
3021  inline constexpr __adaptor::_RangeAdaptorClosure reverse
3022  = [] <viewable_range _Range> (_Range&& __r)
3023  {
3024  using _Tp = remove_cvref_t<_Range>;
3025  if constexpr (__detail::__is_reverse_view<_Tp>)
3026  return std::forward<_Range>(__r).base();
3027  else if constexpr (__detail::__is_reversible_subrange<_Tp>)
3028  {
3029  using _Iter = decltype(ranges::begin(__r).base());
3030  if constexpr (sized_range<_Tp>)
3031  return subrange<_Iter, _Iter, subrange_kind::sized>
3032  (__r.end().base(), __r.begin().base(), __r.size());
3033  else
3034  return subrange<_Iter, _Iter, subrange_kind::unsized>
3035  (__r.end().base(), __r.begin().base());
3036  }
3037  else
3038  return reverse_view{std::forward<_Range>(__r)};
3039  };
3040  } // namespace views
3041 
3042  namespace __detail
3043  {
3044  template<typename _Tp, size_t _Nm>
3045  concept __has_tuple_element = requires(_Tp __t)
3046  {
3047  typename tuple_size<_Tp>::type;
3048  requires _Nm < tuple_size_v<_Tp>;
3049  typename tuple_element_t<_Nm, _Tp>;
3050  { std::get<_Nm>(__t) }
3051  -> convertible_to<const tuple_element_t<_Nm, _Tp>&>;
3052  };
3053  }
3054 
3055  template<input_range _Vp, size_t _Nm>
3056  requires view<_Vp>
3057  && __detail::__has_tuple_element<range_value_t<_Vp>, _Nm>
3058  && __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>,
3059  _Nm>
3060  class elements_view : public view_interface<elements_view<_Vp, _Nm>>
3061  {
3062  public:
3063  elements_view() = default;
3064 
3065  constexpr explicit
3066  elements_view(_Vp base)
3067  : _M_base(std::move(base))
3068  { }
3069 
3070  constexpr _Vp
3071  base() const& requires copy_constructible<_Vp>
3072  { return _M_base; }
3073 
3074  constexpr _Vp
3075  base() &&
3076  { return std::move(_M_base); }
3077 
3078  constexpr auto
3079  begin() requires (!__detail::__simple_view<_Vp>)
3080  { return _Iterator<false>(ranges::begin(_M_base)); }
3081 
3082  constexpr auto
3083  begin() const requires range<const _Vp>
3084  { return _Iterator<true>(ranges::begin(_M_base)); }
3085 
3086  constexpr auto
3087  end() requires (!__detail::__simple_view<_Vp> && !common_range<_Vp>)
3088  { return _Sentinel<false>{ranges::end(_M_base)}; }
3089 
3090  constexpr auto
3091  end() requires (!__detail::__simple_view<_Vp> && common_range<_Vp>)
3092  { return _Iterator<false>{ranges::end(_M_base)}; }
3093 
3094  constexpr auto
3095  end() const requires range<const _Vp>
3096  { return _Sentinel<true>{ranges::end(_M_base)}; }
3097 
3098  constexpr auto
3099  end() const requires common_range<const _Vp>
3100  { return _Iterator<true>{ranges::end(_M_base)}; }
3101 
3102  constexpr auto
3103  size() requires sized_range<_Vp>
3104  { return ranges::size(_M_base); }
3105 
3106  constexpr auto
3107  size() const requires sized_range<const _Vp>
3108  { return ranges::size(_M_base); }
3109 
3110  private:
3111  template<bool _Const>
3112  struct _Sentinel;
3113 
3114  template<bool _Const>
3115  struct _Iterator
3116  {
3117  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
3118 
3119  iterator_t<_Base> _M_current = iterator_t<_Base>();
3120 
3121  friend _Iterator<!_Const>;
3122 
3123  public:
3124  using iterator_category
3125  = typename iterator_traits<iterator_t<_Base>>::iterator_category;
3126  using value_type
3127  = remove_cvref_t<tuple_element_t<_Nm, range_value_t<_Base>>>;
3128  using difference_type = range_difference_t<_Base>;
3129 
3130  _Iterator() = default;
3131 
3132  constexpr explicit
3133  _Iterator(iterator_t<_Base> current)
3134  : _M_current(std::move(current))
3135  { }
3136 
3137  constexpr
3138  _Iterator(_Iterator<!_Const> i)
3139  requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
3140  : _M_current(std::move(i._M_current))
3141  { }
3142 
3143  constexpr iterator_t<_Base>
3144  base() const&
3145  requires copyable<iterator_t<_Base>>
3146  { return _M_current; }
3147 
3148  constexpr iterator_t<_Base>
3149  base() &&
3150  { return std::move(_M_current); }
3151 
3152  constexpr decltype(auto)
3153  operator*() const
3154  { return std::get<_Nm>(*_M_current); }
3155 
3156  constexpr _Iterator&
3157  operator++()
3158  {
3159  ++_M_current;
3160  return *this;
3161  }
3162 
3163  constexpr void
3164  operator++(int) requires (!forward_range<_Base>)
3165  { ++_M_current; }
3166 
3167  constexpr _Iterator
3168  operator++(int) requires forward_range<_Base>
3169  {
3170  auto __tmp = *this;
3171  ++_M_current;
3172  return __tmp;
3173  }
3174 
3175  constexpr _Iterator&
3176  operator--() requires bidirectional_range<_Base>
3177  {
3178  --_M_current;
3179  return *this;
3180  }
3181 
3182  constexpr _Iterator
3183  operator--(int) requires bidirectional_range<_Base>
3184  {
3185  auto __tmp = *this;
3186  --_M_current;
3187  return __tmp;
3188  }
3189 
3190  constexpr _Iterator&
3191  operator+=(difference_type __n)
3192  requires random_access_range<_Base>
3193  {
3194  _M_current += __n;
3195  return *this;
3196  }
3197 
3198  constexpr _Iterator&
3199  operator-=(difference_type __n)
3200  requires random_access_range<_Base>
3201  {
3202  _M_current -= __n;
3203  return *this;
3204  }
3205 
3206  constexpr decltype(auto)
3207  operator[](difference_type __n) const
3208  requires random_access_range<_Base>
3209  { return std::get<_Nm>(*(_M_current + __n)); }
3210 
3211  friend constexpr bool
3212  operator==(const _Iterator& __x, const _Iterator& __y)
3213  requires equality_comparable<iterator_t<_Base>>
3214  { return __x._M_current == __y._M_current; }
3215 
3216  friend constexpr bool
3217  operator<(const _Iterator& __x, const _Iterator& __y)
3218  requires random_access_range<_Base>
3219  { return __x._M_current < __y._M_current; }
3220 
3221  friend constexpr bool
3222  operator>(const _Iterator& __x, const _Iterator& __y)
3223  requires random_access_range<_Base>
3224  { return __y._M_current < __x._M_current; }
3225 
3226  friend constexpr bool
3227  operator<=(const _Iterator& __x, const _Iterator& __y)
3228  requires random_access_range<_Base>
3229  { return !(__y._M_current > __x._M_current); }
3230 
3231  friend constexpr bool
3232  operator>=(const _Iterator& __x, const _Iterator& __y)
3233  requires random_access_range<_Base>
3234  { return !(__x._M_current > __y._M_current); }
3235 
3236 #ifdef __cpp_lib_three_way_comparison
3237  friend constexpr auto
3238  operator<=>(const _Iterator& __x, const _Iterator& __y)
3239  requires random_access_range<_Base>
3240  && three_way_comparable<iterator_t<_Base>>
3241  { return __x._M_current <=> __y._M_current; }
3242 #endif
3243 
3244  friend constexpr _Iterator
3245  operator+(const _Iterator& __x, difference_type __y)
3246  requires random_access_range<_Base>
3247  { return _Iterator{__x} += __y; }
3248 
3249  friend constexpr _Iterator
3250  operator+(difference_type __x, const _Iterator& __y)
3251  requires random_access_range<_Base>
3252  { return __y + __x; }
3253 
3254  friend constexpr _Iterator
3255  operator-(const _Iterator& __x, difference_type __y)
3256  requires random_access_range<_Base>
3257  { return _Iterator{__x} -= __y; }
3258 
3259  // _GLIBCXX_RESOLVE_LIB_DEFECTS
3260  // 3483. transform_view::iterator's difference is overconstrained
3261  friend constexpr difference_type
3262  operator-(const _Iterator& __x, const _Iterator& __y)
3263  requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
3264  { return __x._M_current - __y._M_current; }
3265 
3266  friend _Sentinel<_Const>;
3267  };
3268 
3269  template<bool _Const>
3270  struct _Sentinel
3271  {
3272  private:
3273  constexpr bool
3274  _M_equal(const _Iterator<_Const>& __x) const
3275  { return __x._M_current == _M_end; }
3276 
3277  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
3278  sentinel_t<_Base> _M_end = sentinel_t<_Base>();
3279 
3280  public:
3281  _Sentinel() = default;
3282 
3283  constexpr explicit
3284  _Sentinel(sentinel_t<_Base> __end)
3285  : _M_end(std::move(__end))
3286  { }
3287 
3288  constexpr
3289  _Sentinel(_Sentinel<!_Const> __other)
3290  requires _Const
3291  && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
3292  : _M_end(std::move(__other._M_end))
3293  { }
3294 
3295  constexpr sentinel_t<_Base>
3296  base() const
3297  { return _M_end; }
3298 
3299  template<bool _Const2>
3300  requires sentinel_for<sentinel_t<_Base>,
3301  iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
3302  friend constexpr bool
3303  operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
3304  { return __y._M_equal(__x); }
3305 
3306  template<bool _Const2,
3307  typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
3308  requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
3309  friend constexpr range_difference_t<_Base2>
3310  operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
3311  { return __x._M_current - __y._M_end; }
3312 
3313  template<bool _Const2,
3314  typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
3315  requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
3316  friend constexpr range_difference_t<_Base>
3317  operator-(const _Sentinel& __x, const _Iterator<_Const2>& __y)
3318  { return __x._M_end - __y._M_current; }
3319 
3320  friend _Sentinel<!_Const>;
3321  };
3322 
3323  _Vp _M_base = _Vp();
3324  };
3325 
3326  template<typename _Tp, size_t _Nm>
3327  inline constexpr bool enable_borrowed_range<elements_view<_Tp, _Nm>>
3328  = enable_borrowed_range<_Tp>;
3329 
3330  template<typename _Range>
3331  using keys_view = elements_view<views::all_t<_Range>, 0>;
3332 
3333  template<typename _Range>
3334  using values_view = elements_view<views::all_t<_Range>, 1>;
3335 
3336  namespace views
3337  {
3338  template<size_t _Nm>
3339  inline constexpr __adaptor::_RangeAdaptorClosure elements
3340  = [] <viewable_range _Range> (_Range&& __r)
3341  {
3342  using _El = elements_view<views::all_t<_Range>, _Nm>;
3343  return _El{std::forward<_Range>(__r)};
3344  };
3345 
3346  inline constexpr __adaptor::_RangeAdaptorClosure keys = elements<0>;
3347  inline constexpr __adaptor::_RangeAdaptorClosure values = elements<1>;
3348  } // namespace views
3349 
3350 } // namespace ranges
3351 
3352  namespace views = ranges::views;
3353 
3354 _GLIBCXX_END_NAMESPACE_VERSION
3355 } // namespace
3356 #endif // library concepts
3357 #endif // C++2a
3358 #endif /* _GLIBCXX_RANGES */