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