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