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