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