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