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