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