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