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