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