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