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