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