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