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