3// Copyright (C) 2019-2023 Free Software Foundation, Inc.
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)
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.
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.
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/>.
25/** @file include/ranges
26 * This is a Standard C++ Library header.
30#ifndef _GLIBCXX_RANGES
31#define _GLIBCXX_RANGES 1
33#if __cplusplus > 201703L
35#pragma GCC system_header
42#include <initializer_list>
48#if __cplusplus > 202002L
52#include <bits/ranges_util.h>
53#include <bits/refwrap.h>
56 * @defgroup ranges Ranges
58 * Components for dealing with ranges of elements.
61namespace std _GLIBCXX_VISIBILITY(default)
63_GLIBCXX_BEGIN_NAMESPACE_VERSION
66 // [range.access] customization point objects
67 // [range.req] range and view concepts
68 // [range.dangling] dangling iterator handling
69 // Defined in <bits/ranges_base.h>
71 // [view.interface] View interface
72 // [range.subrange] Sub-ranges
73 // Defined in <bits/ranges_util.h>
75 // C++20 24.6 [range.factories] Range factories
77 /// A view that contains no elements.
78 template<typename _Tp> requires is_object_v<_Tp>
80 : public view_interface<empty_view<_Tp>>
83 static constexpr _Tp* begin() noexcept { return nullptr; }
84 static constexpr _Tp* end() noexcept { return nullptr; }
85 static constexpr _Tp* data() noexcept { return nullptr; }
86 static constexpr size_t size() noexcept { return 0; }
87 static constexpr bool empty() noexcept { return true; }
90 template<typename _Tp>
91 inline constexpr bool enable_borrowed_range<empty_view<_Tp>> = true;
95 template<typename _Tp>
96 concept __boxable = copy_constructible<_Tp> && is_object_v<_Tp>;
98 template<__boxable _Tp>
99 struct __box : std::optional<_Tp>
101 using std::optional<_Tp>::optional;
105 noexcept(is_nothrow_default_constructible_v<_Tp>)
106 requires default_initializable<_Tp>
107 : std::optional<_Tp>{std::in_place}
110 __box(const __box&) = default;
111 __box(__box&&) = default;
113 using std::optional<_Tp>::operator=;
115 // _GLIBCXX_RESOLVE_LIB_DEFECTS
116 // 3477. Simplify constraints for semiregular-box
117 // 3572. copyable-box should be fully constexpr
119 operator=(const __box& __that)
120 noexcept(is_nothrow_copy_constructible_v<_Tp>)
121 requires (!copyable<_Tp>)
123 if (this != std::__addressof(__that))
126 this->emplace(*__that);
134 operator=(__box&& __that)
135 noexcept(is_nothrow_move_constructible_v<_Tp>)
136 requires (!movable<_Tp>)
138 if (this != std::__addressof(__that))
141 this->emplace(std::move(*__that));
149 // For types which are already copyable, this specialization of the
150 // copyable wrapper stores the object directly without going through
151 // std::optional. It provides just the subset of the primary template's
152 // API that we currently use.
153 template<__boxable _Tp>
154 requires copyable<_Tp> || (is_nothrow_move_constructible_v<_Tp>
155 && is_nothrow_copy_constructible_v<_Tp>)
159 [[no_unique_address]] _Tp _M_value = _Tp();
162 __box() requires default_initializable<_Tp> = default;
165 __box(const _Tp& __t)
166 noexcept(is_nothrow_copy_constructible_v<_Tp>)
172 noexcept(is_nothrow_move_constructible_v<_Tp>)
173 : _M_value(std::move(__t))
176 template<typename... _Args>
177 requires constructible_from<_Tp, _Args...>
179 __box(in_place_t, _Args&&... __args)
180 noexcept(is_nothrow_constructible_v<_Tp, _Args...>)
181 : _M_value(std::forward<_Args>(__args)...)
184 __box(const __box&) = default;
185 __box(__box&&) = default;
186 __box& operator=(const __box&) requires copyable<_Tp> = default;
187 __box& operator=(__box&&) requires copyable<_Tp> = default;
189 // When _Tp is nothrow_copy_constructible but not copy_assignable,
190 // copy assignment is implemented via destroy-then-copy-construct.
192 operator=(const __box& __that) noexcept
194 static_assert(is_nothrow_copy_constructible_v<_Tp>);
195 if (this != std::__addressof(__that))
198 std::construct_at(std::__addressof(_M_value), *__that);
203 // Likewise for move assignment.
205 operator=(__box&& __that) noexcept
207 static_assert(is_nothrow_move_constructible_v<_Tp>);
208 if (this != std::__addressof(__that))
211 std::construct_at(std::__addressof(_M_value), std::move(*__that));
217 has_value() const noexcept
225 operator*() const noexcept
229 operator->() noexcept
230 { return std::__addressof(_M_value); }
233 operator->() const noexcept
234 { return std::__addressof(_M_value); }
236 } // namespace __detail
238 /// A view that contains exactly one element.
239 template<copy_constructible _Tp> requires is_object_v<_Tp>
240 class single_view : public view_interface<single_view<_Tp>>
243 single_view() requires default_initializable<_Tp> = default;
246 single_view(const _Tp& __t)
247 noexcept(is_nothrow_copy_constructible_v<_Tp>)
252 single_view(_Tp&& __t)
253 noexcept(is_nothrow_move_constructible_v<_Tp>)
254 : _M_value(std::move(__t))
257 // _GLIBCXX_RESOLVE_LIB_DEFECTS
258 // 3428. single_view's in place constructor should be explicit
259 template<typename... _Args>
260 requires constructible_from<_Tp, _Args...>
262 single_view(in_place_t, _Args&&... __args)
263 noexcept(is_nothrow_constructible_v<_Tp, _Args...>)
264 : _M_value{in_place, std::forward<_Args>(__args)...}
272 begin() const noexcept
277 { return data() + 1; }
281 { return data() + 1; }
283 static constexpr size_t
289 { return _M_value.operator->(); }
292 data() const noexcept
293 { return _M_value.operator->(); }
296 [[no_unique_address]] __detail::__box<_Tp> _M_value;
299 template<typename _Tp>
300 single_view(_Tp) -> single_view<_Tp>;
304 template<typename _Wp>
305 constexpr auto __to_signed_like(_Wp __w) noexcept
307 if constexpr (!integral<_Wp>)
308 return iter_difference_t<_Wp>();
309 else if constexpr (sizeof(iter_difference_t<_Wp>) > sizeof(_Wp))
310 return iter_difference_t<_Wp>(__w);
311 else if constexpr (sizeof(ptrdiff_t) > sizeof(_Wp))
312 return ptrdiff_t(__w);
313 else if constexpr (sizeof(long long) > sizeof(_Wp))
314 return (long long)(__w);
315#ifdef __SIZEOF_INT128__
316 else if constexpr (__SIZEOF_INT128__ > sizeof(_Wp))
317 return __int128(__w);
320 return __max_diff_type(__w);
323 template<typename _Wp>
324 using __iota_diff_t = decltype(__to_signed_like(std::declval<_Wp>()));
326 template<typename _It>
327 concept __decrementable = incrementable<_It>
330 { --__i } -> same_as<_It&>;
331 { __i-- } -> same_as<_It>;
334 template<typename _It>
335 concept __advanceable = __decrementable<_It> && totally_ordered<_It>
336 && requires( _It __i, const _It __j, const __iota_diff_t<_It> __n)
338 { __i += __n } -> same_as<_It&>;
339 { __i -= __n } -> same_as<_It&>;
343 { __j - __j } -> convertible_to<__iota_diff_t<_It>>;
346 template<typename _Winc>
347 struct __iota_view_iter_cat
350 template<incrementable _Winc>
351 struct __iota_view_iter_cat<_Winc>
352 { using iterator_category = input_iterator_tag; };
353 } // namespace __detail
355 template<weakly_incrementable _Winc,
356 semiregular _Bound = unreachable_sentinel_t>
357 requires std::__detail::__weakly_eq_cmp_with<_Winc, _Bound>
359 class iota_view : public view_interface<iota_view<_Winc, _Bound>>
364 struct _Iterator : __detail::__iota_view_iter_cat<_Winc>
370 using namespace __detail;
371 if constexpr (__advanceable<_Winc>)
372 return random_access_iterator_tag{};
373 else if constexpr (__decrementable<_Winc>)
374 return bidirectional_iterator_tag{};
375 else if constexpr (incrementable<_Winc>)
376 return forward_iterator_tag{};
378 return input_iterator_tag{};
382 using iterator_concept = decltype(_S_iter_concept());
383 // iterator_category defined in __iota_view_iter_cat
384 using value_type = _Winc;
385 using difference_type = __detail::__iota_diff_t<_Winc>;
387 _Iterator() requires default_initializable<_Winc> = default;
390 _Iterator(_Winc __value)
391 : _M_value(__value) { }
394 operator*() const noexcept(is_nothrow_copy_constructible_v<_Winc>)
409 operator++(int) requires incrementable<_Winc>
417 operator--() requires __detail::__decrementable<_Winc>
424 operator--(int) requires __detail::__decrementable<_Winc>
432 operator+=(difference_type __n) requires __detail::__advanceable<_Winc>
434 using __detail::__is_integer_like;
435 using __detail::__is_signed_integer_like;
436 if constexpr (__is_integer_like<_Winc>
437 && !__is_signed_integer_like<_Winc>)
439 if (__n >= difference_type(0))
440 _M_value += static_cast<_Winc>(__n);
442 _M_value -= static_cast<_Winc>(-__n);
450 operator-=(difference_type __n) requires __detail::__advanceable<_Winc>
452 using __detail::__is_integer_like;
453 using __detail::__is_signed_integer_like;
454 if constexpr (__is_integer_like<_Winc>
455 && !__is_signed_integer_like<_Winc>)
457 if (__n >= difference_type(0))
458 _M_value -= static_cast<_Winc>(__n);
460 _M_value += static_cast<_Winc>(-__n);
468 operator[](difference_type __n) const
469 requires __detail::__advanceable<_Winc>
470 { return _Winc(_M_value + __n); }
472 friend constexpr bool
473 operator==(const _Iterator& __x, const _Iterator& __y)
474 requires equality_comparable<_Winc>
475 { return __x._M_value == __y._M_value; }
477 friend constexpr bool
478 operator<(const _Iterator& __x, const _Iterator& __y)
479 requires totally_ordered<_Winc>
480 { return __x._M_value < __y._M_value; }
482 friend constexpr bool
483 operator>(const _Iterator& __x, const _Iterator& __y)
484 requires totally_ordered<_Winc>
485 { return __y < __x; }
487 friend constexpr bool
488 operator<=(const _Iterator& __x, const _Iterator& __y)
489 requires totally_ordered<_Winc>
490 { return !(__y < __x); }
492 friend constexpr bool
493 operator>=(const _Iterator& __x, const _Iterator& __y)
494 requires totally_ordered<_Winc>
495 { return !(__x < __y); }
497#ifdef __cpp_lib_three_way_comparison
498 friend constexpr auto
499 operator<=>(const _Iterator& __x, const _Iterator& __y)
500 requires totally_ordered<_Winc> && three_way_comparable<_Winc>
501 { return __x._M_value <=> __y._M_value; }
504 friend constexpr _Iterator
505 operator+(_Iterator __i, difference_type __n)
506 requires __detail::__advanceable<_Winc>
512 friend constexpr _Iterator
513 operator+(difference_type __n, _Iterator __i)
514 requires __detail::__advanceable<_Winc>
515 { return __i += __n; }
517 friend constexpr _Iterator
518 operator-(_Iterator __i, difference_type __n)
519 requires __detail::__advanceable<_Winc>
525 friend constexpr difference_type
526 operator-(const _Iterator& __x, const _Iterator& __y)
527 requires __detail::__advanceable<_Winc>
529 using __detail::__is_integer_like;
530 using __detail::__is_signed_integer_like;
531 using _Dt = difference_type;
532 if constexpr (__is_integer_like<_Winc>)
534 if constexpr (__is_signed_integer_like<_Winc>)
535 return _Dt(_Dt(__x._M_value) - _Dt(__y._M_value));
537 return (__y._M_value > __x._M_value)
538 ? _Dt(-_Dt(__y._M_value - __x._M_value))
539 : _Dt(__x._M_value - __y._M_value);
542 return __x._M_value - __y._M_value;
546 _Winc _M_value = _Winc();
556 _M_equal(const _Iterator& __x) const
557 { return __x._M_value == _M_bound; }
560 _M_distance_from(const _Iterator& __x) const
561 { return _M_bound - __x._M_value; }
563 _Bound _M_bound = _Bound();
566 _Sentinel() = default;
569 _Sentinel(_Bound __bound)
570 : _M_bound(__bound) { }
572 friend constexpr bool
573 operator==(const _Iterator& __x, const _Sentinel& __y)
574 { return __y._M_equal(__x); }
576 friend constexpr iter_difference_t<_Winc>
577 operator-(const _Iterator& __x, const _Sentinel& __y)
578 requires sized_sentinel_for<_Bound, _Winc>
579 { return -__y._M_distance_from(__x); }
581 friend constexpr iter_difference_t<_Winc>
582 operator-(const _Sentinel& __x, const _Iterator& __y)
583 requires sized_sentinel_for<_Bound, _Winc>
584 { return __x._M_distance_from(__y); }
589 _Winc _M_value = _Winc();
590 [[no_unique_address]] _Bound _M_bound = _Bound();
593 iota_view() requires default_initializable<_Winc> = default;
596 iota_view(_Winc __value)
601 iota_view(type_identity_t<_Winc> __value,
602 type_identity_t<_Bound> __bound)
603 : _M_value(__value), _M_bound(__bound)
605 if constexpr (totally_ordered_with<_Winc, _Bound>)
606 __glibcxx_assert( bool(__value <= __bound) );
610 iota_view(_Iterator __first, _Iterator __last)
611 requires same_as<_Winc, _Bound>
612 : iota_view(__first._M_value, __last._M_value)
616 iota_view(_Iterator __first, unreachable_sentinel_t __last)
617 requires same_as<_Bound, unreachable_sentinel_t>
618 : iota_view(__first._M_value, __last)
622 iota_view(_Iterator __first, _Sentinel __last)
623 requires (!same_as<_Winc, _Bound>) && (!same_as<_Bound, unreachable_sentinel_t>)
624 : iota_view(__first._M_value, __last._M_bound)
628 begin() const { return _Iterator{_M_value}; }
633 if constexpr (same_as<_Bound, unreachable_sentinel_t>)
634 return unreachable_sentinel;
636 return _Sentinel{_M_bound};
640 end() const requires same_as<_Winc, _Bound>
641 { return _Iterator{_M_bound}; }
645 requires (same_as<_Winc, _Bound> && __detail::__advanceable<_Winc>)
646 || (integral<_Winc> && integral<_Bound>)
647 || sized_sentinel_for<_Bound, _Winc>
649 using __detail::__is_integer_like;
650 using __detail::__to_unsigned_like;
651 if constexpr (integral<_Winc> && integral<_Bound>)
653 using _Up = make_unsigned_t<decltype(_M_bound - _M_value)>;
654 return _Up(_M_bound) - _Up(_M_value);
656 else if constexpr (__is_integer_like<_Winc>)
657 return __to_unsigned_like(_M_bound) - __to_unsigned_like(_M_value);
659 return __to_unsigned_like(_M_bound - _M_value);
663 template<typename _Winc, typename _Bound>
664 requires (!__detail::__is_integer_like<_Winc>
665 || !__detail::__is_integer_like<_Bound>
666 || (__detail::__is_signed_integer_like<_Winc>
667 == __detail::__is_signed_integer_like<_Bound>))
668 iota_view(_Winc, _Bound) -> iota_view<_Winc, _Bound>;
670 template<typename _Winc, typename _Bound>
671 inline constexpr bool
672 enable_borrowed_range<iota_view<_Winc, _Bound>> = true;
676 template<typename _Tp>
677 inline constexpr empty_view<_Tp> empty{};
681 template<typename _Tp>
682 concept __can_single_view
683 = requires { single_view<decay_t<_Tp>>(std::declval<_Tp>()); };
684 } // namespace __detail
688 template<__detail::__can_single_view _Tp>
690 operator() [[nodiscard]] (_Tp&& __e) const
691 noexcept(noexcept(single_view<decay_t<_Tp>>(std::forward<_Tp>(__e))))
692 { return single_view<decay_t<_Tp>>(std::forward<_Tp>(__e)); }
695 inline constexpr _Single single{};
699 template<typename... _Args>
700 concept __can_iota_view = requires { iota_view(std::declval<_Args>()...); };
701 } // namespace __detail
705 template<__detail::__can_iota_view _Tp>
707 operator() [[nodiscard]] (_Tp&& __e) const
708 { return iota_view(std::forward<_Tp>(__e)); }
710 template<typename _Tp, typename _Up>
711 requires __detail::__can_iota_view<_Tp, _Up>
713 operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
714 { return iota_view(std::forward<_Tp>(__e), std::forward<_Up>(__f)); }
717 inline constexpr _Iota iota{};
723 template<typename _Val, typename _CharT, typename _Traits>
724 concept __stream_extractable
725 = requires(basic_istream<_CharT, _Traits>& is, _Val& t) { is >> t; };
726 } // namespace __detail
728 template<movable _Val, typename _CharT,
729 typename _Traits = char_traits<_CharT>>
730 requires default_initializable<_Val>
731 && __detail::__stream_extractable<_Val, _CharT, _Traits>
732 class basic_istream_view
733 : public view_interface<basic_istream_view<_Val, _CharT, _Traits>>
737 basic_istream_view(basic_istream<_CharT, _Traits>& __stream)
738 : _M_stream(std::__addressof(__stream))
744 *_M_stream >> _M_object;
745 return _Iterator{this};
748 constexpr default_sentinel_t
750 { return default_sentinel; }
753 basic_istream<_CharT, _Traits>* _M_stream;
754 _Val _M_object = _Val();
759 using iterator_concept = input_iterator_tag;
760 using difference_type = ptrdiff_t;
761 using value_type = _Val;
764 _Iterator(basic_istream_view* __parent) noexcept
765 : _M_parent(__parent)
768 _Iterator(const _Iterator&) = delete;
769 _Iterator(_Iterator&&) = default;
770 _Iterator& operator=(const _Iterator&) = delete;
771 _Iterator& operator=(_Iterator&&) = default;
776 *_M_parent->_M_stream >> _M_parent->_M_object;
786 { return _M_parent->_M_object; }
789 operator==(const _Iterator& __x, default_sentinel_t)
790 { return __x._M_at_end(); }
793 basic_istream_view* _M_parent;
797 { return !*_M_parent->_M_stream; }
803 template<typename _Val>
804 using istream_view = basic_istream_view<_Val, char>;
806 template<typename _Val>
807 using wistream_view = basic_istream_view<_Val, wchar_t>;
813 template<typename _Tp, typename _Up>
814 concept __can_istream_view = requires (_Up __e) {
815 basic_istream_view<_Tp, typename _Up::char_type, typename _Up::traits_type>(__e);
817 } // namespace __detail
819 template<typename _Tp>
822 template<typename _CharT, typename _Traits>
824 operator() [[nodiscard]] (basic_istream<_CharT, _Traits>& __e) const
825 requires __detail::__can_istream_view<_Tp, remove_reference_t<decltype(__e)>>
826 { return basic_istream_view<_Tp, _CharT, _Traits>(__e); }
829 template<typename _Tp>
830 inline constexpr _Istream<_Tp> istream;
834 // C++20 24.7 [range.adaptors] Range adaptors
840 // Alias for a type that is conditionally present
841 // (and is an empty type otherwise).
842 // Data members using this alias should use [[no_unique_address]] so that
843 // they take no space when not needed.
844 template<bool _Present, typename _Tp>
845 using __maybe_present_t = __conditional_t<_Present, _Tp, _Empty>;
847 // Alias for a type that is conditionally const.
848 template<bool _Const, typename _Tp>
849 using __maybe_const_t = __conditional_t<_Const, const _Tp, _Tp>;
851} // namespace __detail
853// Shorthand for __detail::__maybe_const_t.
854using __detail::__maybe_const_t;
856namespace views::__adaptor
858 // True if the range adaptor _Adaptor can be applied with _Args.
859 template<typename _Adaptor, typename... _Args>
860 concept __adaptor_invocable
861 = requires { std::declval<_Adaptor>()(declval<_Args>()...); };
863 // True if the range adaptor non-closure _Adaptor can be partially applied
865 template<typename _Adaptor, typename... _Args>
866 concept __adaptor_partial_app_viable = (_Adaptor::_S_arity > 1)
867 && (sizeof...(_Args) == _Adaptor::_S_arity - 1)
868 && (constructible_from<decay_t<_Args>, _Args> && ...);
870 template<typename _Adaptor, typename... _Args>
873 template<typename _Lhs, typename _Rhs>
876 // The base class of every range adaptor closure.
878 // The derived class should define the optional static data member
879 // _S_has_simple_call_op to true if the behavior of this adaptor is
880 // independent of the constness/value category of the adaptor object.
881 struct _RangeAdaptorClosure
883 // range | adaptor is equivalent to adaptor(range).
884 template<typename _Self, typename _Range>
885 requires derived_from<remove_cvref_t<_Self>, _RangeAdaptorClosure>
886 && __adaptor_invocable<_Self, _Range>
887 friend constexpr auto
888 operator|(_Range&& __r, _Self&& __self)
889 { return std::forward<_Self>(__self)(std::forward<_Range>(__r)); }
891 // Compose the adaptors __lhs and __rhs into a pipeline, returning
892 // another range adaptor closure object.
893 template<typename _Lhs, typename _Rhs>
894 requires derived_from<_Lhs, _RangeAdaptorClosure>
895 && derived_from<_Rhs, _RangeAdaptorClosure>
896 friend constexpr auto
897 operator|(_Lhs __lhs, _Rhs __rhs)
898 { return _Pipe<_Lhs, _Rhs>{std::move(__lhs), std::move(__rhs)}; }
901 // The base class of every range adaptor non-closure.
903 // The static data member _Derived::_S_arity must contain the total number of
904 // arguments that the adaptor takes, and the class _Derived must introduce
905 // _RangeAdaptor::operator() into the class scope via a using-declaration.
907 // The optional static data member _Derived::_S_has_simple_extra_args should
908 // be defined to true if the behavior of this adaptor is independent of the
909 // constness/value category of the extra arguments. This data member could
910 // also be defined as a variable template parameterized by the types of the
912 template<typename _Derived>
915 // Partially apply the arguments __args to the range adaptor _Derived,
916 // returning a range adaptor closure object.
917 template<typename... _Args>
918 requires __adaptor_partial_app_viable<_Derived, _Args...>
920 operator()(_Args&&... __args) const
922 return _Partial<_Derived, decay_t<_Args>...>{std::forward<_Args>(__args)...};
926 // True if the range adaptor closure _Adaptor has a simple operator(), i.e.
927 // one that's not overloaded according to constness or value category of the
929 template<typename _Adaptor>
930 concept __closure_has_simple_call_op = _Adaptor::_S_has_simple_call_op;
932 // True if the behavior of the range adaptor non-closure _Adaptor is
933 // independent of the value category of its extra arguments _Args.
934 template<typename _Adaptor, typename... _Args>
935 concept __adaptor_has_simple_extra_args = _Adaptor::_S_has_simple_extra_args
936 || _Adaptor::template _S_has_simple_extra_args<_Args...>;
938 // A range adaptor closure that represents partial application of
939 // the range adaptor _Adaptor with arguments _Args.
940 template<typename _Adaptor, typename... _Args>
941 struct _Partial : _RangeAdaptorClosure
943 tuple<_Args...> _M_args;
946 _Partial(_Args... __args)
947 : _M_args(std::move(__args)...)
950 // Invoke _Adaptor with arguments __r, _M_args... according to the
951 // value category of this _Partial object.
952 template<typename _Range>
953 requires __adaptor_invocable<_Adaptor, _Range, const _Args&...>
955 operator()(_Range&& __r) const &
957 auto __forwarder = [&__r] (const auto&... __args) {
958 return _Adaptor{}(std::forward<_Range>(__r), __args...);
960 return std::apply(__forwarder, _M_args);
963 template<typename _Range>
964 requires __adaptor_invocable<_Adaptor, _Range, _Args...>
966 operator()(_Range&& __r) &&
968 auto __forwarder = [&__r] (auto&... __args) {
969 return _Adaptor{}(std::forward<_Range>(__r), std::move(__args)...);
971 return std::apply(__forwarder, _M_args);
974 template<typename _Range>
976 operator()(_Range&& __r) const && = delete;
979 // A lightweight specialization of the above primary template for
980 // the common case where _Adaptor accepts a single extra argument.
981 template<typename _Adaptor, typename _Arg>
982 struct _Partial<_Adaptor, _Arg> : _RangeAdaptorClosure
988 : _M_arg(std::move(__arg))
991 template<typename _Range>
992 requires __adaptor_invocable<_Adaptor, _Range, const _Arg&>
994 operator()(_Range&& __r) const &
995 { return _Adaptor{}(std::forward<_Range>(__r), _M_arg); }
997 template<typename _Range>
998 requires __adaptor_invocable<_Adaptor, _Range, _Arg>
1000 operator()(_Range&& __r) &&
1001 { return _Adaptor{}(std::forward<_Range>(__r), std::move(_M_arg)); }
1003 template<typename _Range>
1005 operator()(_Range&& __r) const && = delete;
1008 // Partial specialization of the primary template for the case where the extra
1009 // arguments of the adaptor can always be safely and efficiently forwarded by
1010 // const reference. This lets us get away with a single operator() overload,
1011 // which makes overload resolution failure diagnostics more concise.
1012 template<typename _Adaptor, typename... _Args>
1013 requires __adaptor_has_simple_extra_args<_Adaptor, _Args...>
1014 && (is_trivially_copyable_v<_Args> && ...)
1015 struct _Partial<_Adaptor, _Args...> : _RangeAdaptorClosure
1017 tuple<_Args...> _M_args;
1020 _Partial(_Args... __args)
1021 : _M_args(std::move(__args)...)
1024 // Invoke _Adaptor with arguments __r, const _M_args&... regardless
1025 // of the value category of this _Partial object.
1026 template<typename _Range>
1027 requires __adaptor_invocable<_Adaptor, _Range, const _Args&...>
1029 operator()(_Range&& __r) const
1031 auto __forwarder = [&__r] (const auto&... __args) {
1032 return _Adaptor{}(std::forward<_Range>(__r), __args...);
1034 return std::apply(__forwarder, _M_args);
1037 static constexpr bool _S_has_simple_call_op = true;
1040 // A lightweight specialization of the above template for the common case
1041 // where _Adaptor accepts a single extra argument.
1042 template<typename _Adaptor, typename _Arg>
1043 requires __adaptor_has_simple_extra_args<_Adaptor, _Arg>
1044 && is_trivially_copyable_v<_Arg>
1045 struct _Partial<_Adaptor, _Arg> : _RangeAdaptorClosure
1050 _Partial(_Arg __arg)
1051 : _M_arg(std::move(__arg))
1054 template<typename _Range>
1055 requires __adaptor_invocable<_Adaptor, _Range, const _Arg&>
1057 operator()(_Range&& __r) const
1058 { return _Adaptor{}(std::forward<_Range>(__r), _M_arg); }
1060 static constexpr bool _S_has_simple_call_op = true;
1063 template<typename _Lhs, typename _Rhs, typename _Range>
1064 concept __pipe_invocable
1065 = requires { std::declval<_Rhs>()(std::declval<_Lhs>()(std::declval<_Range>())); };
1067 // A range adaptor closure that represents composition of the range
1068 // adaptor closures _Lhs and _Rhs.
1069 template<typename _Lhs, typename _Rhs>
1070 struct _Pipe : _RangeAdaptorClosure
1072 [[no_unique_address]] _Lhs _M_lhs;
1073 [[no_unique_address]] _Rhs _M_rhs;
1076 _Pipe(_Lhs __lhs, _Rhs __rhs)
1077 : _M_lhs(std::move(__lhs)), _M_rhs(std::move(__rhs))
1080 // Invoke _M_rhs(_M_lhs(__r)) according to the value category of this
1081 // range adaptor closure object.
1082 template<typename _Range>
1083 requires __pipe_invocable<const _Lhs&, const _Rhs&, _Range>
1085 operator()(_Range&& __r) const &
1086 { return _M_rhs(_M_lhs(std::forward<_Range>(__r))); }
1088 template<typename _Range>
1089 requires __pipe_invocable<_Lhs, _Rhs, _Range>
1091 operator()(_Range&& __r) &&
1092 { return std::move(_M_rhs)(std::move(_M_lhs)(std::forward<_Range>(__r))); }
1094 template<typename _Range>
1096 operator()(_Range&& __r) const && = delete;
1099 // A partial specialization of the above primary template for the case where
1100 // both adaptor operands have a simple operator(). This in turn lets us
1101 // implement composition using a single simple operator(), which makes
1102 // overload resolution failure diagnostics more concise.
1103 template<typename _Lhs, typename _Rhs>
1104 requires __closure_has_simple_call_op<_Lhs>
1105 && __closure_has_simple_call_op<_Rhs>
1106 struct _Pipe<_Lhs, _Rhs> : _RangeAdaptorClosure
1108 [[no_unique_address]] _Lhs _M_lhs;
1109 [[no_unique_address]] _Rhs _M_rhs;
1112 _Pipe(_Lhs __lhs, _Rhs __rhs)
1113 : _M_lhs(std::move(__lhs)), _M_rhs(std::move(__rhs))
1116 template<typename _Range>
1117 requires __pipe_invocable<const _Lhs&, const _Rhs&, _Range>
1119 operator()(_Range&& __r) const
1120 { return _M_rhs(_M_lhs(std::forward<_Range>(__r))); }
1122 static constexpr bool _S_has_simple_call_op = true;
1124} // namespace views::__adaptor
1126#if __cplusplus > 202002L
1127 template<typename _Derived>
1128 requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
1129 class range_adaptor_closure
1130 : public views::__adaptor::_RangeAdaptorClosure
1134 template<range _Range> requires is_object_v<_Range>
1135 class ref_view : public view_interface<ref_view<_Range>>
1140 static void _S_fun(_Range&); // not defined
1141 static void _S_fun(_Range&&) = delete;
1144 template<__detail::__different_from<ref_view> _Tp>
1145 requires convertible_to<_Tp, _Range&>
1146 && requires { _S_fun(declval<_Tp>()); }
1149 noexcept(noexcept(static_cast<_Range&>(std::declval<_Tp>())))
1150 : _M_r(std::__addressof(static_cast<_Range&>(std::forward<_Tp>(__t))))
1157 constexpr iterator_t<_Range>
1159 { return ranges::begin(*_M_r); }
1161 constexpr sentinel_t<_Range>
1163 { return ranges::end(*_M_r); }
1166 empty() const requires requires { ranges::empty(*_M_r); }
1167 { return ranges::empty(*_M_r); }
1170 size() const requires sized_range<_Range>
1171 { return ranges::size(*_M_r); }
1174 data() const requires contiguous_range<_Range>
1175 { return ranges::data(*_M_r); }
1178 template<typename _Range>
1179 ref_view(_Range&) -> ref_view<_Range>;
1181 template<typename _Tp>
1182 inline constexpr bool enable_borrowed_range<ref_view<_Tp>> = true;
1184 template<range _Range>
1185 requires movable<_Range>
1186 && (!__detail::__is_initializer_list<remove_cv_t<_Range>>)
1187 class owning_view : public view_interface<owning_view<_Range>>
1190 _Range _M_r = _Range();
1193 owning_view() requires default_initializable<_Range> = default;
1196 owning_view(_Range&& __t)
1197 noexcept(is_nothrow_move_constructible_v<_Range>)
1198 : _M_r(std::move(__t))
1201 owning_view(owning_view&&) = default;
1202 owning_view& operator=(owning_view&&) = default;
1208 constexpr const _Range&
1209 base() const& noexcept
1214 { return std::move(_M_r); }
1216 constexpr const _Range&&
1217 base() const&& noexcept
1218 { return std::move(_M_r); }
1220 constexpr iterator_t<_Range>
1222 { return ranges::begin(_M_r); }
1224 constexpr sentinel_t<_Range>
1226 { return ranges::end(_M_r); }
1229 begin() const requires range<const _Range>
1230 { return ranges::begin(_M_r); }
1233 end() const requires range<const _Range>
1234 { return ranges::end(_M_r); }
1237 empty() requires requires { ranges::empty(_M_r); }
1238 { return ranges::empty(_M_r); }
1241 empty() const requires requires { ranges::empty(_M_r); }
1242 { return ranges::empty(_M_r); }
1245 size() requires sized_range<_Range>
1246 { return ranges::size(_M_r); }
1249 size() const requires sized_range<const _Range>
1250 { return ranges::size(_M_r); }
1253 data() requires contiguous_range<_Range>
1254 { return ranges::data(_M_r); }
1257 data() const requires contiguous_range<const _Range>
1258 { return ranges::data(_M_r); }
1261 template<typename _Tp>
1262 inline constexpr bool enable_borrowed_range<owning_view<_Tp>>
1263 = enable_borrowed_range<_Tp>;
1269 template<typename _Range>
1270 concept __can_ref_view = requires { ref_view{std::declval<_Range>()}; };
1272 template<typename _Range>
1273 concept __can_owning_view = requires { owning_view{std::declval<_Range>()}; };
1274 } // namespace __detail
1276 struct _All : __adaptor::_RangeAdaptorClosure
1278 template<typename _Range>
1279 static constexpr bool
1282 if constexpr (view<decay_t<_Range>>)
1283 return is_nothrow_constructible_v<decay_t<_Range>, _Range>;
1284 else if constexpr (__detail::__can_ref_view<_Range>)
1287 return noexcept(owning_view{std::declval<_Range>()});
1290 template<viewable_range _Range>
1291 requires view<decay_t<_Range>>
1292 || __detail::__can_ref_view<_Range>
1293 || __detail::__can_owning_view<_Range>
1295 operator() [[nodiscard]] (_Range&& __r) const
1296 noexcept(_S_noexcept<_Range>())
1298 if constexpr (view<decay_t<_Range>>)
1299 return std::forward<_Range>(__r);
1300 else if constexpr (__detail::__can_ref_view<_Range>)
1301 return ref_view{std::forward<_Range>(__r)};
1303 return owning_view{std::forward<_Range>(__r)};
1306 static constexpr bool _S_has_simple_call_op = true;
1309 inline constexpr _All all;
1311 template<viewable_range _Range>
1312 using all_t = decltype(all(std::declval<_Range>()));
1313 } // namespace views
1317 template<typename _Tp>
1318 struct __non_propagating_cache
1320 // When _Tp is not an object type (e.g. is a reference type), we make
1321 // __non_propagating_cache<_Tp> empty rather than ill-formed so that
1322 // users can easily conditionally declare data members with this type
1323 // (such as join_view::_M_inner).
1326 template<typename _Tp>
1327 requires is_object_v<_Tp>
1328 struct __non_propagating_cache<_Tp>
1329 : protected _Optional_base<_Tp>
1331 __non_propagating_cache() = default;
1334 __non_propagating_cache(const __non_propagating_cache&) noexcept
1338 __non_propagating_cache(__non_propagating_cache&& __other) noexcept
1339 { __other._M_reset(); }
1341 constexpr __non_propagating_cache&
1342 operator=(const __non_propagating_cache& __other) noexcept
1344 if (std::__addressof(__other) != this)
1349 constexpr __non_propagating_cache&
1350 operator=(__non_propagating_cache&& __other) noexcept
1357 constexpr __non_propagating_cache&
1358 operator=(_Tp __val)
1361 this->_M_payload._M_construct(std::move(__val));
1366 operator bool() const noexcept
1367 { return this->_M_is_engaged(); }
1370 operator*() noexcept
1371 { return this->_M_get(); }
1373 constexpr const _Tp&
1374 operator*() const noexcept
1375 { return this->_M_get(); }
1377 template<typename _Iter>
1379 _M_emplace_deref(const _Iter& __i)
1382 auto __f = [] (auto& __x) { return *__x; };
1383 this->_M_payload._M_apply(_Optional_func{__f}, __i);
1384 return this->_M_get();
1388 template<range _Range>
1389 struct _CachedPosition
1392 _M_has_value() const
1395 constexpr iterator_t<_Range>
1396 _M_get(const _Range&) const
1398 __glibcxx_assert(false);
1399 __builtin_unreachable();
1403 _M_set(const _Range&, const iterator_t<_Range>&) const
1407 template<forward_range _Range>
1408 struct _CachedPosition<_Range>
1409 : protected __non_propagating_cache<iterator_t<_Range>>
1412 _M_has_value() const
1413 { return this->_M_is_engaged(); }
1415 constexpr iterator_t<_Range>
1416 _M_get(const _Range&) const
1418 __glibcxx_assert(_M_has_value());
1423 _M_set(const _Range&, const iterator_t<_Range>& __it)
1425 __glibcxx_assert(!_M_has_value());
1426 std::construct_at(std::__addressof(this->_M_payload._M_payload),
1428 this->_M_payload._M_engaged = true;
1432 template<random_access_range _Range>
1433 requires (sizeof(range_difference_t<_Range>)
1434 <= sizeof(iterator_t<_Range>))
1435 struct _CachedPosition<_Range>
1438 range_difference_t<_Range> _M_offset = -1;
1441 _CachedPosition() = default;
1444 _CachedPosition(const _CachedPosition&) = default;
1447 _CachedPosition(_CachedPosition&& __other) noexcept
1448 { *this = std::move(__other); }
1450 constexpr _CachedPosition&
1451 operator=(const _CachedPosition&) = default;
1453 constexpr _CachedPosition&
1454 operator=(_CachedPosition&& __other) noexcept
1456 // Propagate the cached offset, but invalidate the source.
1457 _M_offset = __other._M_offset;
1458 __other._M_offset = -1;
1463 _M_has_value() const
1464 { return _M_offset >= 0; }
1466 constexpr iterator_t<_Range>
1467 _M_get(_Range& __r) const
1469 __glibcxx_assert(_M_has_value());
1470 return ranges::begin(__r) + _M_offset;
1474 _M_set(_Range& __r, const iterator_t<_Range>& __it)
1476 __glibcxx_assert(!_M_has_value());
1477 _M_offset = __it - ranges::begin(__r);
1480 } // namespace __detail
1484 template<typename _Base>
1485 struct __filter_view_iter_cat
1488 template<forward_range _Base>
1489 struct __filter_view_iter_cat<_Base>
1495 using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
1496 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
1497 return bidirectional_iterator_tag{};
1498 else if constexpr (derived_from<_Cat, forward_iterator_tag>)
1499 return forward_iterator_tag{};
1504 using iterator_category = decltype(_S_iter_cat());
1506 } // namespace __detail
1508 template<input_range _Vp,
1509 indirect_unary_predicate<iterator_t<_Vp>> _Pred>
1510 requires view<_Vp> && is_object_v<_Pred>
1511 class filter_view : public view_interface<filter_view<_Vp, _Pred>>
1516 struct _Iterator : __detail::__filter_view_iter_cat<_Vp>
1519 static constexpr auto
1522 if constexpr (bidirectional_range<_Vp>)
1523 return bidirectional_iterator_tag{};
1524 else if constexpr (forward_range<_Vp>)
1525 return forward_iterator_tag{};
1527 return input_iterator_tag{};
1532 using _Vp_iter = iterator_t<_Vp>;
1534 _Vp_iter _M_current = _Vp_iter();
1535 filter_view* _M_parent = nullptr;
1538 using iterator_concept = decltype(_S_iter_concept());
1539 // iterator_category defined in __filter_view_iter_cat
1540 using value_type = range_value_t<_Vp>;
1541 using difference_type = range_difference_t<_Vp>;
1543 _Iterator() requires default_initializable<_Vp_iter> = default;
1546 _Iterator(filter_view* __parent, _Vp_iter __current)
1547 : _M_current(std::move(__current)),
1551 constexpr const _Vp_iter&
1552 base() const & noexcept
1553 { return _M_current; }
1557 { return std::move(_M_current); }
1559 constexpr range_reference_t<_Vp>
1561 { return *_M_current; }
1565 requires __detail::__has_arrow<_Vp_iter>
1566 && copyable<_Vp_iter>
1567 { return _M_current; }
1569 constexpr _Iterator&
1572 _M_current = ranges::find_if(std::move(++_M_current),
1573 ranges::end(_M_parent->_M_base),
1574 std::ref(*_M_parent->_M_pred));
1583 operator++(int) requires forward_range<_Vp>
1590 constexpr _Iterator&
1591 operator--() requires bidirectional_range<_Vp>
1595 while (!std::__invoke(*_M_parent->_M_pred, *_M_current));
1600 operator--(int) requires bidirectional_range<_Vp>
1607 friend constexpr bool
1608 operator==(const _Iterator& __x, const _Iterator& __y)
1609 requires equality_comparable<_Vp_iter>
1610 { return __x._M_current == __y._M_current; }
1612 friend constexpr range_rvalue_reference_t<_Vp>
1613 iter_move(const _Iterator& __i)
1614 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1615 { return ranges::iter_move(__i._M_current); }
1617 friend constexpr void
1618 iter_swap(const _Iterator& __x, const _Iterator& __y)
1619 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1620 requires indirectly_swappable<_Vp_iter>
1621 { ranges::iter_swap(__x._M_current, __y._M_current); }
1627 sentinel_t<_Vp> _M_end = sentinel_t<_Vp>();
1630 __equal(const _Iterator& __i) const
1631 { return __i._M_current == _M_end; }
1634 _Sentinel() = default;
1637 _Sentinel(filter_view* __parent)
1638 : _M_end(ranges::end(__parent->_M_base))
1641 constexpr sentinel_t<_Vp>
1645 friend constexpr bool
1646 operator==(const _Iterator& __x, const _Sentinel& __y)
1647 { return __y.__equal(__x); }
1650 _Vp _M_base = _Vp();
1651 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
1652 [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
1655 filter_view() requires (default_initializable<_Vp>
1656 && default_initializable<_Pred>)
1660 filter_view(_Vp __base, _Pred __pred)
1661 : _M_base(std::move(__base)), _M_pred(std::move(__pred))
1665 base() const& requires copy_constructible<_Vp>
1670 { return std::move(_M_base); }
1672 constexpr const _Pred&
1674 { return *_M_pred; }
1679 if (_M_cached_begin._M_has_value())
1680 return {this, _M_cached_begin._M_get(_M_base)};
1682 __glibcxx_assert(_M_pred.has_value());
1683 auto __it = ranges::find_if(ranges::begin(_M_base),
1684 ranges::end(_M_base),
1685 std::ref(*_M_pred));
1686 _M_cached_begin._M_set(_M_base, __it);
1687 return {this, std::move(__it)};
1693 if constexpr (common_range<_Vp>)
1694 return _Iterator{this, ranges::end(_M_base)};
1696 return _Sentinel{this};
1700 template<typename _Range, typename _Pred>
1701 filter_view(_Range&&, _Pred) -> filter_view<views::all_t<_Range>, _Pred>;
1707 template<typename _Range, typename _Pred>
1708 concept __can_filter_view
1709 = requires { filter_view(std::declval<_Range>(), std::declval<_Pred>()); };
1710 } // namespace __detail
1712 struct _Filter : __adaptor::_RangeAdaptor<_Filter>
1714 template<viewable_range _Range, typename _Pred>
1715 requires __detail::__can_filter_view<_Range, _Pred>
1717 operator() [[nodiscard]] (_Range&& __r, _Pred&& __p) const
1719 return filter_view(std::forward<_Range>(__r), std::forward<_Pred>(__p));
1722 using _RangeAdaptor<_Filter>::operator();
1723 static constexpr int _S_arity = 2;
1724 static constexpr bool _S_has_simple_extra_args = true;
1727 inline constexpr _Filter filter;
1728 } // namespace views
1730 template<input_range _Vp, copy_constructible _Fp>
1731 requires view<_Vp> && is_object_v<_Fp>
1732 && regular_invocable<_Fp&, range_reference_t<_Vp>>
1733 && std::__detail::__can_reference<invoke_result_t<_Fp&,
1734 range_reference_t<_Vp>>>
1735 class transform_view : public view_interface<transform_view<_Vp, _Fp>>
1738 template<bool _Const>
1739 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1741 template<bool _Const>
1745 template<bool _Const>
1746 requires forward_range<_Base<_Const>>
1747 struct __iter_cat<_Const>
1753 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1754 // 3564. transform_view::iterator<true>::value_type and
1755 // iterator_category should use const F&
1756 using _Base = transform_view::_Base<_Const>;
1757 using _Res = invoke_result_t<__maybe_const_t<_Const, _Fp>&,
1758 range_reference_t<_Base>>;
1759 if constexpr (is_lvalue_reference_v<_Res>)
1762 = typename iterator_traits<iterator_t<_Base>>::iterator_category;
1763 if constexpr (derived_from<_Cat, contiguous_iterator_tag>)
1764 return random_access_iterator_tag{};
1769 return input_iterator_tag{};
1772 using iterator_category = decltype(_S_iter_cat());
1775 template<bool _Const>
1778 template<bool _Const>
1779 struct _Iterator : __iter_cat<_Const>
1782 using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1783 using _Base = transform_view::_Base<_Const>;
1788 if constexpr (random_access_range<_Base>)
1789 return random_access_iterator_tag{};
1790 else if constexpr (bidirectional_range<_Base>)
1791 return bidirectional_iterator_tag{};
1792 else if constexpr (forward_range<_Base>)
1793 return forward_iterator_tag{};
1795 return input_iterator_tag{};
1798 using _Base_iter = iterator_t<_Base>;
1800 _Base_iter _M_current = _Base_iter();
1801 _Parent* _M_parent = nullptr;
1804 using iterator_concept = decltype(_S_iter_concept());
1805 // iterator_category defined in __transform_view_iter_cat
1807 = remove_cvref_t<invoke_result_t<__maybe_const_t<_Const, _Fp>&,
1808 range_reference_t<_Base>>>;
1809 using difference_type = range_difference_t<_Base>;
1811 _Iterator() requires default_initializable<_Base_iter> = default;
1814 _Iterator(_Parent* __parent, _Base_iter __current)
1815 : _M_current(std::move(__current)),
1820 _Iterator(_Iterator<!_Const> __i)
1822 && convertible_to<iterator_t<_Vp>, _Base_iter>
1823 : _M_current(std::move(__i._M_current)), _M_parent(__i._M_parent)
1826 constexpr const _Base_iter&
1827 base() const & noexcept
1828 { return _M_current; }
1830 constexpr _Base_iter
1832 { return std::move(_M_current); }
1834 constexpr decltype(auto)
1836 noexcept(noexcept(std::__invoke(*_M_parent->_M_fun, *_M_current)))
1837 { return std::__invoke(*_M_parent->_M_fun, *_M_current); }
1839 constexpr _Iterator&
1851 operator++(int) requires forward_range<_Base>
1858 constexpr _Iterator&
1859 operator--() requires bidirectional_range<_Base>
1866 operator--(int) requires bidirectional_range<_Base>
1873 constexpr _Iterator&
1874 operator+=(difference_type __n) requires random_access_range<_Base>
1880 constexpr _Iterator&
1881 operator-=(difference_type __n) requires random_access_range<_Base>
1887 constexpr decltype(auto)
1888 operator[](difference_type __n) const
1889 requires random_access_range<_Base>
1890 { return std::__invoke(*_M_parent->_M_fun, _M_current[__n]); }
1892 friend constexpr bool
1893 operator==(const _Iterator& __x, const _Iterator& __y)
1894 requires equality_comparable<_Base_iter>
1895 { return __x._M_current == __y._M_current; }
1897 friend constexpr bool
1898 operator<(const _Iterator& __x, const _Iterator& __y)
1899 requires random_access_range<_Base>
1900 { return __x._M_current < __y._M_current; }
1902 friend constexpr bool
1903 operator>(const _Iterator& __x, const _Iterator& __y)
1904 requires random_access_range<_Base>
1905 { return __y < __x; }
1907 friend constexpr bool
1908 operator<=(const _Iterator& __x, const _Iterator& __y)
1909 requires random_access_range<_Base>
1910 { return !(__y < __x); }
1912 friend constexpr bool
1913 operator>=(const _Iterator& __x, const _Iterator& __y)
1914 requires random_access_range<_Base>
1915 { return !(__x < __y); }
1917#ifdef __cpp_lib_three_way_comparison
1918 friend constexpr auto
1919 operator<=>(const _Iterator& __x, const _Iterator& __y)
1920 requires random_access_range<_Base>
1921 && three_way_comparable<_Base_iter>
1922 { return __x._M_current <=> __y._M_current; }
1925 friend constexpr _Iterator
1926 operator+(_Iterator __i, difference_type __n)
1927 requires random_access_range<_Base>
1928 { return {__i._M_parent, __i._M_current + __n}; }
1930 friend constexpr _Iterator
1931 operator+(difference_type __n, _Iterator __i)
1932 requires random_access_range<_Base>
1933 { return {__i._M_parent, __i._M_current + __n}; }
1935 friend constexpr _Iterator
1936 operator-(_Iterator __i, difference_type __n)
1937 requires random_access_range<_Base>
1938 { return {__i._M_parent, __i._M_current - __n}; }
1940 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1941 // 3483. transform_view::iterator's difference is overconstrained
1942 friend constexpr difference_type
1943 operator-(const _Iterator& __x, const _Iterator& __y)
1944 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
1945 { return __x._M_current - __y._M_current; }
1947 friend constexpr decltype(auto)
1948 iter_move(const _Iterator& __i) noexcept(noexcept(*__i))
1950 if constexpr (is_lvalue_reference_v<decltype(*__i)>)
1951 return std::move(*__i);
1956 friend _Iterator<!_Const>;
1957 template<bool> friend struct _Sentinel;
1960 template<bool _Const>
1964 using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1965 using _Base = transform_view::_Base<_Const>;
1967 template<bool _Const2>
1969 __distance_from(const _Iterator<_Const2>& __i) const
1970 { return _M_end - __i._M_current; }
1972 template<bool _Const2>
1974 __equal(const _Iterator<_Const2>& __i) const
1975 { return __i._M_current == _M_end; }
1977 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1980 _Sentinel() = default;
1983 _Sentinel(sentinel_t<_Base> __end)
1988 _Sentinel(_Sentinel<!_Const> __i)
1990 && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1991 : _M_end(std::move(__i._M_end))
1994 constexpr sentinel_t<_Base>
1998 template<bool _Const2>
1999 requires sentinel_for<sentinel_t<_Base>,
2000 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
2001 friend constexpr bool
2002 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
2003 { return __y.__equal(__x); }
2005 template<bool _Const2,
2006 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
2007 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
2008 friend constexpr range_difference_t<_Base2>
2009 operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
2010 { return -__y.__distance_from(__x); }
2012 template<bool _Const2,
2013 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
2014 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
2015 friend constexpr range_difference_t<_Base2>
2016 operator-(const _Sentinel& __y, const _Iterator<_Const2>& __x)
2017 { return __y.__distance_from(__x); }
2019 friend _Sentinel<!_Const>;
2022 _Vp _M_base = _Vp();
2023 [[no_unique_address]] __detail::__box<_Fp> _M_fun;
2026 transform_view() requires (default_initializable<_Vp>
2027 && default_initializable<_Fp>)
2031 transform_view(_Vp __base, _Fp __fun)
2032 : _M_base(std::move(__base)), _M_fun(std::move(__fun))
2036 base() const& requires copy_constructible<_Vp>
2037 { return _M_base ; }
2041 { return std::move(_M_base); }
2043 constexpr _Iterator<false>
2045 { return _Iterator<false>{this, ranges::begin(_M_base)}; }
2047 constexpr _Iterator<true>
2049 requires range<const _Vp>
2050 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
2051 { return _Iterator<true>{this, ranges::begin(_M_base)}; }
2053 constexpr _Sentinel<false>
2055 { return _Sentinel<false>{ranges::end(_M_base)}; }
2057 constexpr _Iterator<false>
2058 end() requires common_range<_Vp>
2059 { return _Iterator<false>{this, ranges::end(_M_base)}; }
2061 constexpr _Sentinel<true>
2063 requires range<const _Vp>
2064 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
2065 { return _Sentinel<true>{ranges::end(_M_base)}; }
2067 constexpr _Iterator<true>
2069 requires common_range<const _Vp>
2070 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
2071 { return _Iterator<true>{this, ranges::end(_M_base)}; }
2074 size() requires sized_range<_Vp>
2075 { return ranges::size(_M_base); }
2078 size() const requires sized_range<const _Vp>
2079 { return ranges::size(_M_base); }
2082 template<typename _Range, typename _Fp>
2083 transform_view(_Range&&, _Fp) -> transform_view<views::all_t<_Range>, _Fp>;
2089 template<typename _Range, typename _Fp>
2090 concept __can_transform_view
2091 = requires { transform_view(std::declval<_Range>(), std::declval<_Fp>()); };
2092 } // namespace __detail
2094 struct _Transform : __adaptor::_RangeAdaptor<_Transform>
2096 template<viewable_range _Range, typename _Fp>
2097 requires __detail::__can_transform_view<_Range, _Fp>
2099 operator() [[nodiscard]] (_Range&& __r, _Fp&& __f) const
2101 return transform_view(std::forward<_Range>(__r), std::forward<_Fp>(__f));
2104 using _RangeAdaptor<_Transform>::operator();
2105 static constexpr int _S_arity = 2;
2106 static constexpr bool _S_has_simple_extra_args = true;
2109 inline constexpr _Transform transform;
2110 } // namespace views
2113 class take_view : public view_interface<take_view<_Vp>>
2116 template<bool _Const>
2117 using _CI = counted_iterator<
2118 iterator_t<__detail::__maybe_const_t<_Const, _Vp>>>;
2120 template<bool _Const>
2124 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2125 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2128 _Sentinel() = default;
2131 _Sentinel(sentinel_t<_Base> __end)
2136 _Sentinel(_Sentinel<!_Const> __s)
2137 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2138 : _M_end(std::move(__s._M_end))
2141 constexpr sentinel_t<_Base>
2145 friend constexpr bool
2146 operator==(const _CI<_Const>& __y, const _Sentinel& __x)
2147 { return __y.count() == 0 || __y.base() == __x._M_end; }
2149 template<bool _OtherConst = !_Const,
2150 typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
2151 requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
2152 friend constexpr bool
2153 operator==(const _CI<_OtherConst>& __y, const _Sentinel& __x)
2154 { return __y.count() == 0 || __y.base() == __x._M_end; }
2156 friend _Sentinel<!_Const>;
2159 _Vp _M_base = _Vp();
2160 range_difference_t<_Vp> _M_count = 0;
2163 take_view() requires default_initializable<_Vp> = default;
2166 take_view(_Vp __base, range_difference_t<_Vp> __count)
2167 : _M_base(std::move(__base)), _M_count(std::move(__count))
2171 base() const& requires copy_constructible<_Vp>
2176 { return std::move(_M_base); }
2179 begin() requires (!__detail::__simple_view<_Vp>)
2181 if constexpr (sized_range<_Vp>)
2183 if constexpr (random_access_range<_Vp>)
2184 return ranges::begin(_M_base);
2188 return counted_iterator(ranges::begin(_M_base), __sz);
2192 return counted_iterator(ranges::begin(_M_base), _M_count);
2196 begin() const requires range<const _Vp>
2198 if constexpr (sized_range<const _Vp>)
2200 if constexpr (random_access_range<const _Vp>)
2201 return ranges::begin(_M_base);
2205 return counted_iterator(ranges::begin(_M_base), __sz);
2209 return counted_iterator(ranges::begin(_M_base), _M_count);
2213 end() requires (!__detail::__simple_view<_Vp>)
2215 if constexpr (sized_range<_Vp>)
2217 if constexpr (random_access_range<_Vp>)
2218 return ranges::begin(_M_base) + size();
2220 return default_sentinel;
2223 return _Sentinel<false>{ranges::end(_M_base)};
2227 end() const requires range<const _Vp>
2229 if constexpr (sized_range<const _Vp>)
2231 if constexpr (random_access_range<const _Vp>)
2232 return ranges::begin(_M_base) + size();
2234 return default_sentinel;
2237 return _Sentinel<true>{ranges::end(_M_base)};
2241 size() requires sized_range<_Vp>
2243 auto __n = ranges::size(_M_base);
2244 return std::min(__n, static_cast<decltype(__n)>(_M_count));
2248 size() const requires sized_range<const _Vp>
2250 auto __n = ranges::size(_M_base);
2251 return std::min(__n, static_cast<decltype(__n)>(_M_count));
2255 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2256 // 3447. Deduction guides for take_view and drop_view have different
2258 template<typename _Range>
2259 take_view(_Range&&, range_difference_t<_Range>)
2260 -> take_view<views::all_t<_Range>>;
2262 template<typename _Tp>
2263 inline constexpr bool enable_borrowed_range<take_view<_Tp>>
2264 = enable_borrowed_range<_Tp>;
2270 template<typename _Range>
2271 inline constexpr bool __is_empty_view = false;
2273 template<typename _Tp>
2274 inline constexpr bool __is_empty_view<empty_view<_Tp>> = true;
2276 template<typename _Range>
2277 inline constexpr bool __is_basic_string_view = false;
2279 template<typename _CharT, typename _Traits>
2280 inline constexpr bool __is_basic_string_view<basic_string_view<_CharT, _Traits>>
2283 template<typename _Range>
2284 inline constexpr bool __is_subrange = false;
2286 template<typename _Iter, typename _Sent, subrange_kind _Kind>
2287 inline constexpr bool __is_subrange<subrange<_Iter, _Sent, _Kind>> = true;
2289 template<typename _Range>
2290 inline constexpr bool __is_iota_view = false;
2292 template<typename _Winc, typename _Bound>
2293 inline constexpr bool __is_iota_view<iota_view<_Winc, _Bound>> = true;
2295 template<typename _Range>
2296 inline constexpr bool __is_repeat_view = false;
2298 template<typename _Range>
2300 __take_of_repeat_view(_Range&&, range_difference_t<_Range>); // defined later
2302 template<typename _Range, typename _Dp>
2303 concept __can_take_view
2304 = requires { take_view(std::declval<_Range>(), std::declval<_Dp>()); };
2305 } // namespace __detail
2307 struct _Take : __adaptor::_RangeAdaptor<_Take>
2309 template<viewable_range _Range, typename _Dp = range_difference_t<_Range>>
2310 requires __detail::__can_take_view<_Range, _Dp>
2312 operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const
2314 using _Tp = remove_cvref_t<_Range>;
2315 if constexpr (__detail::__is_empty_view<_Tp>)
2317 else if constexpr (random_access_range<_Tp>
2319 && (std::__detail::__is_span<_Tp>
2320 || __detail::__is_basic_string_view<_Tp>
2321 || __detail::__is_subrange<_Tp>
2322 || __detail::__is_iota_view<_Tp>))
2324 __n = std::min<_Dp>(ranges::distance(__r), __n);
2325 auto __begin = ranges::begin(__r);
2326 auto __end = __begin + __n;
2327 if constexpr (std::__detail::__is_span<_Tp>)
2328 return span<typename _Tp::element_type>(__begin, __end);
2329 else if constexpr (__detail::__is_basic_string_view<_Tp>)
2330 return _Tp(__begin, __end);
2331 else if constexpr (__detail::__is_subrange<_Tp>)
2332 return subrange<iterator_t<_Tp>>(__begin, __end);
2334 return iota_view(*__begin, *__end);
2336 else if constexpr (__detail::__is_repeat_view<_Tp>)
2337 return __detail::__take_of_repeat_view(std::forward<_Range>(__r), __n);
2339 return take_view(std::forward<_Range>(__r), __n);
2342 using _RangeAdaptor<_Take>::operator();
2343 static constexpr int _S_arity = 2;
2344 // The count argument of views::take is not always simple -- it can be
2345 // e.g. a move-only class that's implicitly convertible to the difference
2346 // type. But an integer-like count argument is surely simple.
2347 template<typename _Tp>
2348 static constexpr bool _S_has_simple_extra_args
2349 = ranges::__detail::__is_integer_like<_Tp>;
2352 inline constexpr _Take take;
2353 } // namespace views
2355 template<view _Vp, typename _Pred>
2356 requires input_range<_Vp> && is_object_v<_Pred>
2357 && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2358 class take_while_view : public view_interface<take_while_view<_Vp, _Pred>>
2360 template<bool _Const>
2364 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2366 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2367 const _Pred* _M_pred = nullptr;
2370 _Sentinel() = default;
2373 _Sentinel(sentinel_t<_Base> __end, const _Pred* __pred)
2374 : _M_end(__end), _M_pred(__pred)
2378 _Sentinel(_Sentinel<!_Const> __s)
2379 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2380 : _M_end(__s._M_end), _M_pred(__s._M_pred)
2383 constexpr sentinel_t<_Base>
2384 base() const { return _M_end; }
2386 friend constexpr bool
2387 operator==(const iterator_t<_Base>& __x, const _Sentinel& __y)
2388 { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
2390 template<bool _OtherConst = !_Const,
2391 typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
2392 requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
2393 friend constexpr bool
2394 operator==(const iterator_t<_Base2>& __x, const _Sentinel& __y)
2395 { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
2397 friend _Sentinel<!_Const>;
2400 _Vp _M_base = _Vp();
2401 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
2404 take_while_view() requires (default_initializable<_Vp>
2405 && default_initializable<_Pred>)
2409 take_while_view(_Vp __base, _Pred __pred)
2410 : _M_base(std::move(__base)), _M_pred(std::move(__pred))
2414 base() const& requires copy_constructible<_Vp>
2419 { return std::move(_M_base); }
2421 constexpr const _Pred&
2423 { return *_M_pred; }
2426 begin() requires (!__detail::__simple_view<_Vp>)
2427 { return ranges::begin(_M_base); }
2430 begin() const requires range<const _Vp>
2431 && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
2432 { return ranges::begin(_M_base); }
2435 end() requires (!__detail::__simple_view<_Vp>)
2436 { return _Sentinel<false>(ranges::end(_M_base),
2437 std::__addressof(*_M_pred)); }
2440 end() const requires range<const _Vp>
2441 && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
2442 { return _Sentinel<true>(ranges::end(_M_base),
2443 std::__addressof(*_M_pred)); }
2446 template<typename _Range, typename _Pred>
2447 take_while_view(_Range&&, _Pred)
2448 -> take_while_view<views::all_t<_Range>, _Pred>;
2454 template<typename _Range, typename _Pred>
2455 concept __can_take_while_view
2456 = requires { take_while_view(std::declval<_Range>(), std::declval<_Pred>()); };
2457 } // namespace __detail
2459 struct _TakeWhile : __adaptor::_RangeAdaptor<_TakeWhile>
2461 template<viewable_range _Range, typename _Pred>
2462 requires __detail::__can_take_while_view<_Range, _Pred>
2464 operator() [[nodiscard]] (_Range&& __r, _Pred&& __p) const
2466 return take_while_view(std::forward<_Range>(__r), std::forward<_Pred>(__p));
2469 using _RangeAdaptor<_TakeWhile>::operator();
2470 static constexpr int _S_arity = 2;
2471 static constexpr bool _S_has_simple_extra_args = true;
2474 inline constexpr _TakeWhile take_while;
2475 } // namespace views
2478 class drop_view : public view_interface<drop_view<_Vp>>
2481 _Vp _M_base = _Vp();
2482 range_difference_t<_Vp> _M_count = 0;
2484 // ranges::next(begin(base), count, end(base)) is O(1) if _Vp satisfies
2485 // both random_access_range and sized_range. Otherwise, cache its result.
2486 static constexpr bool _S_needs_cached_begin
2487 = !(random_access_range<const _Vp> && sized_range<const _Vp>);
2488 [[no_unique_address]]
2489 __detail::__maybe_present_t<_S_needs_cached_begin,
2490 __detail::_CachedPosition<_Vp>>
2494 drop_view() requires default_initializable<_Vp> = default;
2497 drop_view(_Vp __base, range_difference_t<_Vp> __count)
2498 : _M_base(std::move(__base)), _M_count(__count)
2499 { __glibcxx_assert(__count >= 0); }
2502 base() const& requires copy_constructible<_Vp>
2507 { return std::move(_M_base); }
2509 // This overload is disabled for simple views with constant-time begin().
2512 requires (!(__detail::__simple_view<_Vp>
2513 && random_access_range<const _Vp>
2514 && sized_range<const _Vp>))
2516 if constexpr (_S_needs_cached_begin)
2517 if (_M_cached_begin._M_has_value())
2518 return _M_cached_begin._M_get(_M_base);
2520 auto __it = ranges::next(ranges::begin(_M_base),
2521 _M_count, ranges::end(_M_base));
2522 if constexpr (_S_needs_cached_begin)
2523 _M_cached_begin._M_set(_M_base, __it);
2527 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2528 // 3482. drop_view's const begin should additionally require sized_range
2531 requires random_access_range<const _Vp> && sized_range<const _Vp>
2533 return ranges::begin(_M_base) + ranges::min(ranges::distance(_M_base),
2538 end() requires (!__detail::__simple_view<_Vp>)
2539 { return ranges::end(_M_base); }
2542 end() const requires range<const _Vp>
2543 { return ranges::end(_M_base); }
2546 size() requires sized_range<_Vp>
2548 const auto __s = ranges::size(_M_base);
2549 const auto __c = static_cast<decltype(__s)>(_M_count);
2550 return __s < __c ? 0 : __s - __c;
2554 size() const requires sized_range<const _Vp>
2556 const auto __s = ranges::size(_M_base);
2557 const auto __c = static_cast<decltype(__s)>(_M_count);
2558 return __s < __c ? 0 : __s - __c;
2562 template<typename _Range>
2563 drop_view(_Range&&, range_difference_t<_Range>)
2564 -> drop_view<views::all_t<_Range>>;
2566 template<typename _Tp>
2567 inline constexpr bool enable_borrowed_range<drop_view<_Tp>>
2568 = enable_borrowed_range<_Tp>;
2574 template<typename _Range>
2576 __drop_of_repeat_view(_Range&&, range_difference_t<_Range>); // defined later
2578 template<typename _Range, typename _Dp>
2579 concept __can_drop_view
2580 = requires { drop_view(std::declval<_Range>(), std::declval<_Dp>()); };
2581 } // namespace __detail
2583 struct _Drop : __adaptor::_RangeAdaptor<_Drop>
2585 template<viewable_range _Range, typename _Dp = range_difference_t<_Range>>
2586 requires __detail::__can_drop_view<_Range, _Dp>
2588 operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const
2590 using _Tp = remove_cvref_t<_Range>;
2591 if constexpr (__detail::__is_empty_view<_Tp>)
2593 else if constexpr (random_access_range<_Tp>
2595 && (std::__detail::__is_span<_Tp>
2596 || __detail::__is_basic_string_view<_Tp>
2597 || __detail::__is_iota_view<_Tp>
2598 || __detail::__is_subrange<_Tp>))
2600 __n = std::min<_Dp>(ranges::distance(__r), __n);
2601 auto __begin = ranges::begin(__r) + __n;
2602 auto __end = ranges::end(__r);
2603 if constexpr (std::__detail::__is_span<_Tp>)
2604 return span<typename _Tp::element_type>(__begin, __end);
2605 else if constexpr (__detail::__is_subrange<_Tp>)
2607 if constexpr (_Tp::_S_store_size)
2609 using ranges::__detail::__to_unsigned_like;
2610 auto __m = ranges::distance(__r) - __n;
2611 return _Tp(__begin, __end, __to_unsigned_like(__m));
2614 return _Tp(__begin, __end);
2617 return _Tp(__begin, __end);
2619 else if constexpr (__detail::__is_repeat_view<_Tp>)
2620 return __detail::__drop_of_repeat_view(std::forward<_Range>(__r), __n);
2622 return drop_view(std::forward<_Range>(__r), __n);
2625 using _RangeAdaptor<_Drop>::operator();
2626 static constexpr int _S_arity = 2;
2627 template<typename _Tp>
2628 static constexpr bool _S_has_simple_extra_args
2629 = _Take::_S_has_simple_extra_args<_Tp>;
2632 inline constexpr _Drop drop;
2633 } // namespace views
2635 template<view _Vp, typename _Pred>
2636 requires input_range<_Vp> && is_object_v<_Pred>
2637 && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2638 class drop_while_view : public view_interface<drop_while_view<_Vp, _Pred>>
2641 _Vp _M_base = _Vp();
2642 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
2643 [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
2646 drop_while_view() requires (default_initializable<_Vp>
2647 && default_initializable<_Pred>)
2651 drop_while_view(_Vp __base, _Pred __pred)
2652 : _M_base(std::move(__base)), _M_pred(std::move(__pred))
2656 base() const& requires copy_constructible<_Vp>
2661 { return std::move(_M_base); }
2663 constexpr const _Pred&
2665 { return *_M_pred; }
2670 if (_M_cached_begin._M_has_value())
2671 return _M_cached_begin._M_get(_M_base);
2673 __glibcxx_assert(_M_pred.has_value());
2674 auto __it = ranges::find_if_not(ranges::begin(_M_base),
2675 ranges::end(_M_base),
2676 std::cref(*_M_pred));
2677 _M_cached_begin._M_set(_M_base, __it);
2683 { return ranges::end(_M_base); }
2686 template<typename _Range, typename _Pred>
2687 drop_while_view(_Range&&, _Pred)
2688 -> drop_while_view<views::all_t<_Range>, _Pred>;
2690 template<typename _Tp, typename _Pred>
2691 inline constexpr bool enable_borrowed_range<drop_while_view<_Tp, _Pred>>
2692 = enable_borrowed_range<_Tp>;
2698 template<typename _Range, typename _Pred>
2699 concept __can_drop_while_view
2700 = requires { drop_while_view(std::declval<_Range>(), std::declval<_Pred>()); };
2701 } // namespace __detail
2703 struct _DropWhile : __adaptor::_RangeAdaptor<_DropWhile>
2705 template<viewable_range _Range, typename _Pred>
2706 requires __detail::__can_drop_while_view<_Range, _Pred>
2708 operator() [[nodiscard]] (_Range&& __r, _Pred&& __p) const
2710 return drop_while_view(std::forward<_Range>(__r),
2711 std::forward<_Pred>(__p));
2714 using _RangeAdaptor<_DropWhile>::operator();
2715 static constexpr int _S_arity = 2;
2716 static constexpr bool _S_has_simple_extra_args = true;
2719 inline constexpr _DropWhile drop_while;
2720 } // namespace views
2722 template<input_range _Vp>
2723 requires view<_Vp> && input_range<range_reference_t<_Vp>>
2724 class join_view : public view_interface<join_view<_Vp>>
2727 using _InnerRange = range_reference_t<_Vp>;
2729 template<bool _Const>
2730 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2732 template<bool _Const>
2733 using _Outer_iter = iterator_t<_Base<_Const>>;
2735 template<bool _Const>
2736 using _Inner_iter = iterator_t<range_reference_t<_Base<_Const>>>;
2738 template<bool _Const>
2739 static constexpr bool _S_ref_is_glvalue
2740 = is_reference_v<range_reference_t<_Base<_Const>>>;
2742 template<bool _Const>
2746 template<bool _Const>
2747 requires _S_ref_is_glvalue<_Const>
2748 && forward_range<_Base<_Const>>
2749 && forward_range<range_reference_t<_Base<_Const>>>
2750 struct __iter_cat<_Const>
2753 static constexpr auto
2756 using _Outer_iter = join_view::_Outer_iter<_Const>;
2757 using _Inner_iter = join_view::_Inner_iter<_Const>;
2758 using _OuterCat = typename iterator_traits<_Outer_iter>::iterator_category;
2759 using _InnerCat = typename iterator_traits<_Inner_iter>::iterator_category;
2760 if constexpr (derived_from<_OuterCat, bidirectional_iterator_tag>
2761 && derived_from<_InnerCat, bidirectional_iterator_tag>
2762 && common_range<range_reference_t<_Base<_Const>>>)
2763 return bidirectional_iterator_tag{};
2764 else if constexpr (derived_from<_OuterCat, forward_iterator_tag>
2765 && derived_from<_InnerCat, forward_iterator_tag>)
2766 return forward_iterator_tag{};
2768 return input_iterator_tag{};
2771 using iterator_category = decltype(_S_iter_cat());
2774 template<bool _Const>
2777 template<bool _Const>
2778 struct _Iterator : __iter_cat<_Const>
2781 using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2782 using _Base = join_view::_Base<_Const>;
2784 static constexpr bool _S_ref_is_glvalue
2785 = join_view::_S_ref_is_glvalue<_Const>;
2790 auto __update_inner = [this] (const iterator_t<_Base>& __x) -> auto&& {
2791 if constexpr (_S_ref_is_glvalue)
2794 return _M_parent->_M_inner._M_emplace_deref(__x);
2797 for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer)
2799 auto&& __inner = __update_inner(_M_outer);
2800 _M_inner = ranges::begin(__inner);
2801 if (_M_inner != ranges::end(__inner))
2805 if constexpr (_S_ref_is_glvalue)
2809 static constexpr auto
2812 if constexpr (_S_ref_is_glvalue
2813 && bidirectional_range<_Base>
2814 && bidirectional_range<range_reference_t<_Base>>
2815 && common_range<range_reference_t<_Base>>)
2816 return bidirectional_iterator_tag{};
2817 else if constexpr (_S_ref_is_glvalue
2818 && forward_range<_Base>
2819 && forward_range<range_reference_t<_Base>>)
2820 return forward_iterator_tag{};
2822 return input_iterator_tag{};
2825 using _Outer_iter = join_view::_Outer_iter<_Const>;
2826 using _Inner_iter = join_view::_Inner_iter<_Const>;
2828 _Outer_iter _M_outer = _Outer_iter();
2829 optional<_Inner_iter> _M_inner;
2830 _Parent* _M_parent = nullptr;
2833 using iterator_concept = decltype(_S_iter_concept());
2834 // iterator_category defined in __join_view_iter_cat
2835 using value_type = range_value_t<range_reference_t<_Base>>;
2836 using difference_type
2837 = common_type_t<range_difference_t<_Base>,
2838 range_difference_t<range_reference_t<_Base>>>;
2840 _Iterator() requires default_initializable<_Outer_iter> = default;
2843 _Iterator(_Parent* __parent, _Outer_iter __outer)
2844 : _M_outer(std::move(__outer)),
2849 _Iterator(_Iterator<!_Const> __i)
2851 && convertible_to<iterator_t<_Vp>, _Outer_iter>
2852 && convertible_to<iterator_t<_InnerRange>, _Inner_iter>
2853 : _M_outer(std::move(__i._M_outer)), _M_inner(std::move(__i._M_inner)),
2854 _M_parent(__i._M_parent)
2857 constexpr decltype(auto)
2859 { return **_M_inner; }
2861 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2862 // 3500. join_view::iterator::operator->() is bogus
2863 constexpr _Inner_iter
2865 requires __detail::__has_arrow<_Inner_iter>
2866 && copyable<_Inner_iter>
2867 { return *_M_inner; }
2869 constexpr _Iterator&
2872 auto&& __inner_range = [this] () -> auto&& {
2873 if constexpr (_S_ref_is_glvalue)
2876 return *_M_parent->_M_inner;
2878 if (++*_M_inner == ranges::end(__inner_range))
2892 requires _S_ref_is_glvalue && forward_range<_Base>
2893 && forward_range<range_reference_t<_Base>>
2900 constexpr _Iterator&
2902 requires _S_ref_is_glvalue && bidirectional_range<_Base>
2903 && bidirectional_range<range_reference_t<_Base>>
2904 && common_range<range_reference_t<_Base>>
2906 if (_M_outer == ranges::end(_M_parent->_M_base))
2907 _M_inner = ranges::end(*--_M_outer);
2908 while (*_M_inner == ranges::begin(*_M_outer))
2909 *_M_inner = ranges::end(*--_M_outer);
2916 requires _S_ref_is_glvalue && bidirectional_range<_Base>
2917 && bidirectional_range<range_reference_t<_Base>>
2918 && common_range<range_reference_t<_Base>>
2925 friend constexpr bool
2926 operator==(const _Iterator& __x, const _Iterator& __y)
2927 requires _S_ref_is_glvalue
2928 && equality_comparable<_Outer_iter>
2929 && equality_comparable<_Inner_iter>
2931 return (__x._M_outer == __y._M_outer
2932 && __x._M_inner == __y._M_inner);
2935 friend constexpr decltype(auto)
2936 iter_move(const _Iterator& __i)
2937 noexcept(noexcept(ranges::iter_move(*__i._M_inner)))
2938 { return ranges::iter_move(*__i._M_inner); }
2940 friend constexpr void
2941 iter_swap(const _Iterator& __x, const _Iterator& __y)
2942 noexcept(noexcept(ranges::iter_swap(*__x._M_inner, *__y._M_inner)))
2943 requires indirectly_swappable<_Inner_iter>
2944 { return ranges::iter_swap(*__x._M_inner, *__y._M_inner); }
2946 friend _Iterator<!_Const>;
2947 template<bool> friend struct _Sentinel;
2950 template<bool _Const>
2954 using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2955 using _Base = join_view::_Base<_Const>;
2957 template<bool _Const2>
2959 __equal(const _Iterator<_Const2>& __i) const
2960 { return __i._M_outer == _M_end; }
2962 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2965 _Sentinel() = default;
2968 _Sentinel(_Parent* __parent)
2969 : _M_end(ranges::end(__parent->_M_base))
2973 _Sentinel(_Sentinel<!_Const> __s)
2974 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2975 : _M_end(std::move(__s._M_end))
2978 template<bool _Const2>
2979 requires sentinel_for<sentinel_t<_Base>,
2980 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
2981 friend constexpr bool
2982 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
2983 { return __y.__equal(__x); }
2985 friend _Sentinel<!_Const>;
2988 _Vp _M_base = _Vp();
2989 [[no_unique_address]]
2990 __detail::__non_propagating_cache<remove_cv_t<_InnerRange>> _M_inner;
2993 join_view() requires default_initializable<_Vp> = default;
2996 join_view(_Vp __base)
2997 : _M_base(std::move(__base))
3001 base() const& requires copy_constructible<_Vp>
3006 { return std::move(_M_base); }
3011 constexpr bool __use_const
3012 = (__detail::__simple_view<_Vp>
3013 && is_reference_v<range_reference_t<_Vp>>);
3014 return _Iterator<__use_const>{this, ranges::begin(_M_base)};
3019 requires input_range<const _Vp>
3020 && is_reference_v<range_reference_t<const _Vp>>
3022 return _Iterator<true>{this, ranges::begin(_M_base)};
3028 if constexpr (forward_range<_Vp> && is_reference_v<_InnerRange>
3029 && forward_range<_InnerRange>
3030 && common_range<_Vp> && common_range<_InnerRange>)
3031 return _Iterator<__detail::__simple_view<_Vp>>{this,
3032 ranges::end(_M_base)};
3034 return _Sentinel<__detail::__simple_view<_Vp>>{this};
3039 requires input_range<const _Vp>
3040 && is_reference_v<range_reference_t<const _Vp>>
3042 if constexpr (forward_range<const _Vp>
3043 && is_reference_v<range_reference_t<const _Vp>>
3044 && forward_range<range_reference_t<const _Vp>>
3045 && common_range<const _Vp>
3046 && common_range<range_reference_t<const _Vp>>)
3047 return _Iterator<true>{this, ranges::end(_M_base)};
3049 return _Sentinel<true>{this};
3053 template<typename _Range>
3054 explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;
3060 template<typename _Range>
3061 concept __can_join_view
3062 = requires { join_view<all_t<_Range>>{std::declval<_Range>()}; };
3063 } // namespace __detail
3065 struct _Join : __adaptor::_RangeAdaptorClosure
3067 template<viewable_range _Range>
3068 requires __detail::__can_join_view<_Range>
3070 operator() [[nodiscard]] (_Range&& __r) const
3072 // _GLIBCXX_RESOLVE_LIB_DEFECTS
3073 // 3474. Nesting join_views is broken because of CTAD
3074 return join_view<all_t<_Range>>{std::forward<_Range>(__r)};
3077 static constexpr bool _S_has_simple_call_op = true;
3080 inline constexpr _Join join;
3081 } // namespace views
3086 struct __require_constant;
3088 template<typename _Range>
3089 concept __tiny_range = sized_range<_Range>
3091 { typename __require_constant<remove_reference_t<_Range>::size()>; }
3092 && (remove_reference_t<_Range>::size() <= 1);
3094 template<typename _Base>
3095 struct __lazy_split_view_outer_iter_cat
3098 template<forward_range _Base>
3099 struct __lazy_split_view_outer_iter_cat<_Base>
3100 { using iterator_category = input_iterator_tag; };
3102 template<typename _Base>
3103 struct __lazy_split_view_inner_iter_cat
3106 template<forward_range _Base>
3107 struct __lazy_split_view_inner_iter_cat<_Base>
3110 static constexpr auto
3113 using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
3114 if constexpr (derived_from<_Cat, forward_iterator_tag>)
3115 return forward_iterator_tag{};
3120 using iterator_category = decltype(_S_iter_cat());
3124 template<input_range _Vp, forward_range _Pattern>
3125 requires view<_Vp> && view<_Pattern>
3126 && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
3128 && (forward_range<_Vp> || __detail::__tiny_range<_Pattern>)
3129 class lazy_split_view : public view_interface<lazy_split_view<_Vp, _Pattern>>
3132 template<bool _Const>
3133 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
3135 template<bool _Const>
3138 template<bool _Const>
3140 : __detail::__lazy_split_view_outer_iter_cat<_Base<_Const>>
3143 using _Parent = __detail::__maybe_const_t<_Const, lazy_split_view>;
3144 using _Base = lazy_split_view::_Base<_Const>;
3148 { return __current() == ranges::end(_M_parent->_M_base) && !_M_trailing_empty; }
3150 // [range.lazy.split.outer] p1
3151 // Many of the following specifications refer to the notional member
3152 // current of outer-iterator. current is equivalent to current_ if
3153 // V models forward_range, and parent_->current_ otherwise.
3155 __current() noexcept
3157 if constexpr (forward_range<_Vp>)
3160 return *_M_parent->_M_current;
3164 __current() const noexcept
3166 if constexpr (forward_range<_Vp>)
3169 return *_M_parent->_M_current;
3172 _Parent* _M_parent = nullptr;
3174 [[no_unique_address]]
3175 __detail::__maybe_present_t<forward_range<_Vp>,
3176 iterator_t<_Base>> _M_current;
3177 bool _M_trailing_empty = false;
3180 using iterator_concept = __conditional_t<forward_range<_Base>,
3181 forward_iterator_tag,
3182 input_iterator_tag>;
3183 // iterator_category defined in __lazy_split_view_outer_iter_cat
3184 using difference_type = range_difference_t<_Base>;
3186 struct value_type : view_interface<value_type>
3189 _OuterIter _M_i = _OuterIter();
3192 value_type() = default;
3195 value_type(_OuterIter __i)
3196 : _M_i(std::move(__i))
3199 constexpr _InnerIter<_Const>
3201 { return _InnerIter<_Const>{_M_i}; }
3203 constexpr default_sentinel_t
3204 end() const noexcept
3205 { return default_sentinel; }
3208 _OuterIter() = default;
3211 _OuterIter(_Parent* __parent) requires (!forward_range<_Base>)
3212 : _M_parent(__parent)
3216 _OuterIter(_Parent* __parent, iterator_t<_Base> __current)
3217 requires forward_range<_Base>
3218 : _M_parent(__parent),
3219 _M_current(std::move(__current))
3223 _OuterIter(_OuterIter<!_Const> __i)
3225 && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
3226 : _M_parent(__i._M_parent), _M_current(std::move(__i._M_current)),
3227 _M_trailing_empty(__i._M_trailing_empty)
3230 constexpr value_type
3232 { return value_type{*this}; }
3234 constexpr _OuterIter&
3237 // _GLIBCXX_RESOLVE_LIB_DEFECTS
3238 // 3505. lazy_split_view::outer-iterator::operator++ misspecified
3239 const auto __end = ranges::end(_M_parent->_M_base);
3240 if (__current() == __end)
3242 _M_trailing_empty = false;
3245 const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern};
3246 if (__pbegin == __pend)
3248 else if constexpr (__detail::__tiny_range<_Pattern>)
3250 __current() = ranges::find(std::move(__current()), __end,
3252 if (__current() != __end)
3255 if (__current() == __end)
3256 _M_trailing_empty = true;
3263 = ranges::mismatch(__current(), __end, __pbegin, __pend);
3267 if (__current() == __end)
3268 _M_trailing_empty = true;
3271 } while (++__current() != __end);
3275 constexpr decltype(auto)
3278 if constexpr (forward_range<_Base>)
3288 friend constexpr bool
3289 operator==(const _OuterIter& __x, const _OuterIter& __y)
3290 requires forward_range<_Base>
3292 return __x._M_current == __y._M_current
3293 && __x._M_trailing_empty == __y._M_trailing_empty;
3296 friend constexpr bool
3297 operator==(const _OuterIter& __x, default_sentinel_t)
3298 { return __x.__at_end(); };
3300 friend _OuterIter<!_Const>;
3301 friend _InnerIter<_Const>;
3304 template<bool _Const>
3306 : __detail::__lazy_split_view_inner_iter_cat<_Base<_Const>>
3309 using _Base = lazy_split_view::_Base<_Const>;
3314 auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern};
3315 auto __end = ranges::end(_M_i._M_parent->_M_base);
3316 if constexpr (__detail::__tiny_range<_Pattern>)
3318 const auto& __cur = _M_i_current();
3321 if (__pcur == __pend)
3322 return _M_incremented;
3323 return *__cur == *__pcur;
3327 auto __cur = _M_i_current();
3330 if (__pcur == __pend)
3331 return _M_incremented;
3334 if (*__cur != *__pcur)
3336 if (++__pcur == __pend)
3338 } while (++__cur != __end);
3344 _M_i_current() noexcept
3345 { return _M_i.__current(); }
3348 _M_i_current() const noexcept
3349 { return _M_i.__current(); }
3351 _OuterIter<_Const> _M_i = _OuterIter<_Const>();
3352 bool _M_incremented = false;
3355 using iterator_concept
3356 = typename _OuterIter<_Const>::iterator_concept;
3357 // iterator_category defined in __lazy_split_view_inner_iter_cat
3358 using value_type = range_value_t<_Base>;
3359 using difference_type = range_difference_t<_Base>;
3361 _InnerIter() = default;
3364 _InnerIter(_OuterIter<_Const> __i)
3365 : _M_i(std::move(__i))
3368 constexpr const iterator_t<_Base>&
3369 base() const& noexcept
3370 { return _M_i_current(); }
3372 constexpr iterator_t<_Base>
3373 base() && requires forward_range<_Vp>
3374 { return std::move(_M_i_current()); }
3376 constexpr decltype(auto)
3378 { return *_M_i_current(); }
3380 constexpr _InnerIter&
3383 _M_incremented = true;
3384 if constexpr (!forward_range<_Base>)
3385 if constexpr (_Pattern::size() == 0)
3391 constexpr decltype(auto)
3394 if constexpr (forward_range<_Base>)
3404 friend constexpr bool
3405 operator==(const _InnerIter& __x, const _InnerIter& __y)
3406 requires forward_range<_Base>
3407 { return __x._M_i == __y._M_i; }
3409 friend constexpr bool
3410 operator==(const _InnerIter& __x, default_sentinel_t)
3411 { return __x.__at_end(); }
3413 friend constexpr decltype(auto)
3414 iter_move(const _InnerIter& __i)
3415 noexcept(noexcept(ranges::iter_move(__i._M_i_current())))
3416 { return ranges::iter_move(__i._M_i_current()); }
3418 friend constexpr void
3419 iter_swap(const _InnerIter& __x, const _InnerIter& __y)
3420 noexcept(noexcept(ranges::iter_swap(__x._M_i_current(),
3421 __y._M_i_current())))
3422 requires indirectly_swappable<iterator_t<_Base>>
3423 { ranges::iter_swap(__x._M_i_current(), __y._M_i_current()); }
3426 _Vp _M_base = _Vp();
3427 _Pattern _M_pattern = _Pattern();
3428 [[no_unique_address]]
3429 __detail::__maybe_present_t<!forward_range<_Vp>,
3430 __detail::__non_propagating_cache<iterator_t<_Vp>>> _M_current;
3434 lazy_split_view() requires (default_initializable<_Vp>
3435 && default_initializable<_Pattern>)
3439 lazy_split_view(_Vp __base, _Pattern __pattern)
3440 : _M_base(std::move(__base)), _M_pattern(std::move(__pattern))
3443 template<input_range _Range>
3444 requires constructible_from<_Vp, views::all_t<_Range>>
3445 && constructible_from<_Pattern, single_view<range_value_t<_Range>>>
3447 lazy_split_view(_Range&& __r, range_value_t<_Range> __e)
3448 : _M_base(views::all(std::forward<_Range>(__r))),
3449 _M_pattern(views::single(std::move(__e)))
3453 base() const& requires copy_constructible<_Vp>
3458 { return std::move(_M_base); }
3463 if constexpr (forward_range<_Vp>)
3465 constexpr bool __simple
3466 = __detail::__simple_view<_Vp> && __detail::__simple_view<_Pattern>;
3467 return _OuterIter<__simple>{this, ranges::begin(_M_base)};
3471 _M_current = ranges::begin(_M_base);
3472 return _OuterIter<false>{this};
3477 begin() const requires forward_range<_Vp> && forward_range<const _Vp>
3479 return _OuterIter<true>{this, ranges::begin(_M_base)};
3483 end() requires forward_range<_Vp> && common_range<_Vp>
3485 constexpr bool __simple
3486 = __detail::__simple_view<_Vp> && __detail::__simple_view<_Pattern>;
3487 return _OuterIter<__simple>{this, ranges::end(_M_base)};
3493 if constexpr (forward_range<_Vp>
3494 && forward_range<const _Vp>
3495 && common_range<const _Vp>)
3496 return _OuterIter<true>{this, ranges::end(_M_base)};
3498 return default_sentinel;
3502 template<typename _Range, typename _Pattern>
3503 lazy_split_view(_Range&&, _Pattern&&)
3504 -> lazy_split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
3506 template<input_range _Range>
3507 lazy_split_view(_Range&&, range_value_t<_Range>)
3508 -> lazy_split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
3514 template<typename _Range, typename _Pattern>
3515 concept __can_lazy_split_view
3516 = requires { lazy_split_view(std::declval<_Range>(), std::declval<_Pattern>()); };
3517 } // namespace __detail
3519 struct _LazySplit : __adaptor::_RangeAdaptor<_LazySplit>
3521 template<viewable_range _Range, typename _Pattern>
3522 requires __detail::__can_lazy_split_view<_Range, _Pattern>
3524 operator() [[nodiscard]] (_Range&& __r, _Pattern&& __f) const
3526 return lazy_split_view(std::forward<_Range>(__r), std::forward<_Pattern>(__f));
3529 using _RangeAdaptor<_LazySplit>::operator();
3530 static constexpr int _S_arity = 2;
3531 // The pattern argument of views::lazy_split is not always simple -- it can be
3532 // a non-view range, the value category of which affects whether the call
3533 // is well-formed. But a scalar or a view pattern argument is surely
3535 template<typename _Pattern>
3536 static constexpr bool _S_has_simple_extra_args
3537 = is_scalar_v<_Pattern> || (view<_Pattern>
3538 && copy_constructible<_Pattern>);
3541 inline constexpr _LazySplit lazy_split;
3542 } // namespace views
3544 template<forward_range _Vp, forward_range _Pattern>
3545 requires view<_Vp> && view<_Pattern>
3546 && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
3548 class split_view : public view_interface<split_view<_Vp, _Pattern>>
3551 _Vp _M_base = _Vp();
3552 _Pattern _M_pattern = _Pattern();
3553 __detail::__non_propagating_cache<subrange<iterator_t<_Vp>>> _M_cached_begin;
3559 split_view() requires (default_initializable<_Vp>
3560 && default_initializable<_Pattern>)
3564 split_view(_Vp __base, _Pattern __pattern)
3565 : _M_base(std::move(__base)), _M_pattern(std::move(__pattern))
3568 template<forward_range _Range>
3569 requires constructible_from<_Vp, views::all_t<_Range>>
3570 && constructible_from<_Pattern, single_view<range_value_t<_Range>>>
3572 split_view(_Range&& __r, range_value_t<_Range> __e)
3573 : _M_base(views::all(std::forward<_Range>(__r))),
3574 _M_pattern(views::single(std::move(__e)))
3578 base() const& requires copy_constructible<_Vp>
3583 { return std::move(_M_base); }
3588 if (!_M_cached_begin)
3589 _M_cached_begin = _M_find_next(ranges::begin(_M_base));
3590 return {this, ranges::begin(_M_base), *_M_cached_begin};
3596 if constexpr (common_range<_Vp>)
3597 return _Iterator{this, ranges::end(_M_base), {}};
3599 return _Sentinel{this};
3602 constexpr subrange<iterator_t<_Vp>>
3603 _M_find_next(iterator_t<_Vp> __it)
3605 auto [__b, __e] = ranges::search(subrange(__it, ranges::end(_M_base)), _M_pattern);
3606 if (__b != ranges::end(_M_base) && ranges::empty(_M_pattern))
3618 split_view* _M_parent = nullptr;
3619 iterator_t<_Vp> _M_cur = iterator_t<_Vp>();
3620 subrange<iterator_t<_Vp>> _M_next = subrange<iterator_t<_Vp>>();
3621 bool _M_trailing_empty = false;
3623 friend struct _Sentinel;
3626 using iterator_concept = forward_iterator_tag;
3627 using iterator_category = input_iterator_tag;
3628 using value_type = subrange<iterator_t<_Vp>>;
3629 using difference_type = range_difference_t<_Vp>;
3631 _Iterator() = default;
3634 _Iterator(split_view* __parent,
3635 iterator_t<_Vp> __current,
3636 subrange<iterator_t<_Vp>> __next)
3637 : _M_parent(__parent),
3638 _M_cur(std::move(__current)),
3639 _M_next(std::move(__next))
3642 constexpr iterator_t<_Vp>
3646 constexpr value_type
3648 { return {_M_cur, _M_next.begin()}; }
3650 constexpr _Iterator&
3653 _M_cur = _M_next.begin();
3654 if (_M_cur != ranges::end(_M_parent->_M_base))
3656 _M_cur = _M_next.end();
3657 if (_M_cur == ranges::end(_M_parent->_M_base))
3659 _M_trailing_empty = true;
3660 _M_next = {_M_cur, _M_cur};
3663 _M_next = _M_parent->_M_find_next(_M_cur);
3666 _M_trailing_empty = false;
3678 friend constexpr bool
3679 operator==(const _Iterator& __x, const _Iterator& __y)
3681 return __x._M_cur == __y._M_cur
3682 && __x._M_trailing_empty == __y._M_trailing_empty;
3689 sentinel_t<_Vp> _M_end = sentinel_t<_Vp>();
3692 _M_equal(const _Iterator& __x) const
3693 { return __x._M_cur == _M_end && !__x._M_trailing_empty; }
3696 _Sentinel() = default;
3699 _Sentinel(split_view* __parent)
3700 : _M_end(ranges::end(__parent->_M_base))
3703 friend constexpr bool
3704 operator==(const _Iterator& __x, const _Sentinel& __y)
3705 { return __y._M_equal(__x); }
3709 template<typename _Range, typename _Pattern>
3710 split_view(_Range&&, _Pattern&&)
3711 -> split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
3713 template<forward_range _Range>
3714 split_view(_Range&&, range_value_t<_Range>)
3715 -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
3721 template<typename _Range, typename _Pattern>
3722 concept __can_split_view
3723 = requires { split_view(std::declval<_Range>(), std::declval<_Pattern>()); };
3724 } // namespace __detail
3726 struct _Split : __adaptor::_RangeAdaptor<_Split>
3728 template<viewable_range _Range, typename _Pattern>
3729 requires __detail::__can_split_view<_Range, _Pattern>
3731 operator() [[nodiscard]] (_Range&& __r, _Pattern&& __f) const
3733 return split_view(std::forward<_Range>(__r), std::forward<_Pattern>(__f));
3736 using _RangeAdaptor<_Split>::operator();
3737 static constexpr int _S_arity = 2;
3738 template<typename _Pattern>
3739 static constexpr bool _S_has_simple_extra_args
3740 = _LazySplit::_S_has_simple_extra_args<_Pattern>;
3743 inline constexpr _Split split;
3744 } // namespace views
3750 template<input_or_output_iterator _Iter>
3752 operator() [[nodiscard]] (_Iter __i, iter_difference_t<_Iter> __n) const
3754 if constexpr (contiguous_iterator<_Iter>)
3755 return span(std::__to_address(__i), __n);
3756 else if constexpr (random_access_iterator<_Iter>)
3757 return subrange(__i, __i + __n);
3759 return subrange(counted_iterator(std::move(__i), __n),
3764 inline constexpr _Counted counted{};
3765 } // namespace views
3768 requires (!common_range<_Vp>) && copyable<iterator_t<_Vp>>
3769 class common_view : public view_interface<common_view<_Vp>>
3772 _Vp _M_base = _Vp();
3775 common_view() requires default_initializable<_Vp> = default;
3778 common_view(_Vp __r)
3779 : _M_base(std::move(__r))
3783 base() const& requires copy_constructible<_Vp>
3788 { return std::move(_M_base); }
3793 if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3794 return ranges::begin(_M_base);
3796 return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3797 (ranges::begin(_M_base));
3801 begin() const requires range<const _Vp>
3803 if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3804 return ranges::begin(_M_base);
3806 return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3807 (ranges::begin(_M_base));
3813 if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3814 return ranges::begin(_M_base) + ranges::size(_M_base);
3816 return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3817 (ranges::end(_M_base));
3821 end() const requires range<const _Vp>
3823 if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3824 return ranges::begin(_M_base) + ranges::size(_M_base);
3826 return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3827 (ranges::end(_M_base));
3831 size() requires sized_range<_Vp>
3832 { return ranges::size(_M_base); }
3835 size() const requires sized_range<const _Vp>
3836 { return ranges::size(_M_base); }
3839 template<typename _Range>
3840 common_view(_Range&&) -> common_view<views::all_t<_Range>>;
3842 template<typename _Tp>
3843 inline constexpr bool enable_borrowed_range<common_view<_Tp>>
3844 = enable_borrowed_range<_Tp>;
3850 template<typename _Range>
3851 concept __already_common = common_range<_Range>
3852 && requires { views::all(std::declval<_Range>()); };
3854 template<typename _Range>
3855 concept __can_common_view
3856 = requires { common_view{std::declval<_Range>()}; };
3857 } // namespace __detail
3859 struct _Common : __adaptor::_RangeAdaptorClosure
3861 template<viewable_range _Range>
3862 requires __detail::__already_common<_Range>
3863 || __detail::__can_common_view<_Range>
3865 operator() [[nodiscard]] (_Range&& __r) const
3867 if constexpr (__detail::__already_common<_Range>)
3868 return views::all(std::forward<_Range>(__r));
3870 return common_view{std::forward<_Range>(__r)};
3873 static constexpr bool _S_has_simple_call_op = true;
3876 inline constexpr _Common common;
3877 } // namespace views
3880 requires bidirectional_range<_Vp>
3881 class reverse_view : public view_interface<reverse_view<_Vp>>
3884 static constexpr bool _S_needs_cached_begin
3885 = !common_range<_Vp> && !(random_access_range<_Vp>
3886 && sized_sentinel_for<sentinel_t<_Vp>,
3889 _Vp _M_base = _Vp();
3890 [[no_unique_address]]
3891 __detail::__maybe_present_t<_S_needs_cached_begin,
3892 __detail::_CachedPosition<_Vp>>
3896 reverse_view() requires default_initializable<_Vp> = default;
3899 reverse_view(_Vp __r)
3900 : _M_base(std::move(__r))
3904 base() const& requires copy_constructible<_Vp>
3909 { return std::move(_M_base); }
3911 constexpr reverse_iterator<iterator_t<_Vp>>
3914 if constexpr (_S_needs_cached_begin)
3915 if (_M_cached_begin._M_has_value())
3916 return std::make_reverse_iterator(_M_cached_begin._M_get(_M_base));
3918 auto __it = ranges::next(ranges::begin(_M_base), ranges::end(_M_base));
3919 if constexpr (_S_needs_cached_begin)
3920 _M_cached_begin._M_set(_M_base, __it);
3921 return std::make_reverse_iterator(std::move(__it));
3925 begin() requires common_range<_Vp>
3926 { return std::make_reverse_iterator(ranges::end(_M_base)); }
3929 begin() const requires common_range<const _Vp>
3930 { return std::make_reverse_iterator(ranges::end(_M_base)); }
3932 constexpr reverse_iterator<iterator_t<_Vp>>
3934 { return std::make_reverse_iterator(ranges::begin(_M_base)); }
3937 end() const requires common_range<const _Vp>
3938 { return std::make_reverse_iterator(ranges::begin(_M_base)); }
3941 size() requires sized_range<_Vp>
3942 { return ranges::size(_M_base); }
3945 size() const requires sized_range<const _Vp>
3946 { return ranges::size(_M_base); }
3949 template<typename _Range>
3950 reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>;
3952 template<typename _Tp>
3953 inline constexpr bool enable_borrowed_range<reverse_view<_Tp>>
3954 = enable_borrowed_range<_Tp>;
3961 inline constexpr bool __is_reversible_subrange = false;
3963 template<typename _Iter, subrange_kind _Kind>
3964 inline constexpr bool
3965 __is_reversible_subrange<subrange<reverse_iterator<_Iter>,
3966 reverse_iterator<_Iter>,
3970 inline constexpr bool __is_reverse_view = false;
3972 template<typename _Vp>
3973 inline constexpr bool __is_reverse_view<reverse_view<_Vp>> = true;
3975 template<typename _Range>
3976 concept __can_reverse_view
3977 = requires { reverse_view{std::declval<_Range>()}; };
3978 } // namespace __detail
3980 struct _Reverse : __adaptor::_RangeAdaptorClosure
3982 template<viewable_range _Range>
3983 requires __detail::__is_reverse_view<remove_cvref_t<_Range>>
3984 || __detail::__is_reversible_subrange<remove_cvref_t<_Range>>
3985 || __detail::__can_reverse_view<_Range>
3987 operator() [[nodiscard]] (_Range&& __r) const
3989 using _Tp = remove_cvref_t<_Range>;
3990 if constexpr (__detail::__is_reverse_view<_Tp>)
3991 return std::forward<_Range>(__r).base();
3992 else if constexpr (__detail::__is_reversible_subrange<_Tp>)
3994 using _Iter = decltype(ranges::begin(__r).base());
3995 if constexpr (sized_range<_Tp>)
3996 return subrange<_Iter, _Iter, subrange_kind::sized>
3997 {__r.end().base(), __r.begin().base(), __r.size()};
3999 return subrange<_Iter, _Iter, subrange_kind::unsized>
4000 {__r.end().base(), __r.begin().base()};
4003 return reverse_view{std::forward<_Range>(__r)};
4006 static constexpr bool _S_has_simple_call_op = true;
4009 inline constexpr _Reverse reverse;
4010 } // namespace views
4014 template<typename _Tp, size_t _Nm>
4015 concept __has_tuple_element = requires(_Tp __t)
4017 typename tuple_size<_Tp>::type;
4018 requires _Nm < tuple_size_v<_Tp>;
4019 typename tuple_element_t<_Nm, _Tp>;
4020 { std::get<_Nm>(__t) }
4021 -> convertible_to<const tuple_element_t<_Nm, _Tp>&>;
4024 template<typename _Tp, size_t _Nm>
4025 concept __returnable_element
4026 = is_reference_v<_Tp> || move_constructible<tuple_element_t<_Nm, _Tp>>;
4029 template<input_range _Vp, size_t _Nm>
4031 && __detail::__has_tuple_element<range_value_t<_Vp>, _Nm>
4032 && __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>,
4034 && __detail::__returnable_element<range_reference_t<_Vp>, _Nm>
4035 class elements_view : public view_interface<elements_view<_Vp, _Nm>>
4038 elements_view() requires default_initializable<_Vp> = default;
4041 elements_view(_Vp __base)
4042 : _M_base(std::move(__base))
4046 base() const& requires copy_constructible<_Vp>
4051 { return std::move(_M_base); }
4054 begin() requires (!__detail::__simple_view<_Vp>)
4055 { return _Iterator<false>(ranges::begin(_M_base)); }
4058 begin() const requires range<const _Vp>
4059 { return _Iterator<true>(ranges::begin(_M_base)); }
4062 end() requires (!__detail::__simple_view<_Vp> && !common_range<_Vp>)
4063 { return _Sentinel<false>{ranges::end(_M_base)}; }
4066 end() requires (!__detail::__simple_view<_Vp> && common_range<_Vp>)
4067 { return _Iterator<false>{ranges::end(_M_base)}; }
4070 end() const requires range<const _Vp>
4071 { return _Sentinel<true>{ranges::end(_M_base)}; }
4074 end() const requires common_range<const _Vp>
4075 { return _Iterator<true>{ranges::end(_M_base)}; }
4078 size() requires sized_range<_Vp>
4079 { return ranges::size(_M_base); }
4082 size() const requires sized_range<const _Vp>
4083 { return ranges::size(_M_base); }
4086 template<bool _Const>
4087 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
4089 template<bool _Const>
4093 template<bool _Const>
4094 requires forward_range<_Base<_Const>>
4095 struct __iter_cat<_Const>
4098 static auto _S_iter_cat()
4100 using _Base = elements_view::_Base<_Const>;
4101 using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
4102 using _Res = decltype((std::get<_Nm>(*std::declval<iterator_t<_Base>>())));
4103 if constexpr (!is_lvalue_reference_v<_Res>)
4104 return input_iterator_tag{};
4105 else if constexpr (derived_from<_Cat, random_access_iterator_tag>)
4106 return random_access_iterator_tag{};
4111 using iterator_category = decltype(_S_iter_cat());
4114 template<bool _Const>
4117 template<bool _Const>
4118 struct _Iterator : __iter_cat<_Const>
4121 using _Base = elements_view::_Base<_Const>;
4123 iterator_t<_Base> _M_current = iterator_t<_Base>();
4125 static constexpr decltype(auto)
4126 _S_get_element(const iterator_t<_Base>& __i)
4128 if constexpr (is_reference_v<range_reference_t<_Base>>)
4129 return std::get<_Nm>(*__i);
4132 using _Et = remove_cv_t<tuple_element_t<_Nm, range_reference_t<_Base>>>;
4133 return static_cast<_Et>(std::get<_Nm>(*__i));
4140 if constexpr (random_access_range<_Base>)
4141 return random_access_iterator_tag{};
4142 else if constexpr (bidirectional_range<_Base>)
4143 return bidirectional_iterator_tag{};
4144 else if constexpr (forward_range<_Base>)
4145 return forward_iterator_tag{};
4147 return input_iterator_tag{};
4150 friend _Iterator<!_Const>;
4153 using iterator_concept = decltype(_S_iter_concept());
4154 // iterator_category defined in elements_view::__iter_cat
4156 = remove_cvref_t<tuple_element_t<_Nm, range_value_t<_Base>>>;
4157 using difference_type = range_difference_t<_Base>;
4159 _Iterator() requires default_initializable<iterator_t<_Base>> = default;
4162 _Iterator(iterator_t<_Base> __current)
4163 : _M_current(std::move(__current))
4167 _Iterator(_Iterator<!_Const> __i)
4168 requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
4169 : _M_current(std::move(__i._M_current))
4172 constexpr const iterator_t<_Base>&
4173 base() const& noexcept
4174 { return _M_current; }
4176 constexpr iterator_t<_Base>
4178 { return std::move(_M_current); }
4180 constexpr decltype(auto)
4182 { return _S_get_element(_M_current); }
4184 constexpr _Iterator&
4196 operator++(int) requires forward_range<_Base>
4203 constexpr _Iterator&
4204 operator--() requires bidirectional_range<_Base>
4211 operator--(int) requires bidirectional_range<_Base>
4218 constexpr _Iterator&
4219 operator+=(difference_type __n)
4220 requires random_access_range<_Base>
4226 constexpr _Iterator&
4227 operator-=(difference_type __n)
4228 requires random_access_range<_Base>
4234 constexpr decltype(auto)
4235 operator[](difference_type __n) const
4236 requires random_access_range<_Base>
4237 { return _S_get_element(_M_current + __n); }
4239 friend constexpr bool
4240 operator==(const _Iterator& __x, const _Iterator& __y)
4241 requires equality_comparable<iterator_t<_Base>>
4242 { return __x._M_current == __y._M_current; }
4244 friend constexpr bool
4245 operator<(const _Iterator& __x, const _Iterator& __y)
4246 requires random_access_range<_Base>
4247 { return __x._M_current < __y._M_current; }
4249 friend constexpr bool
4250 operator>(const _Iterator& __x, const _Iterator& __y)
4251 requires random_access_range<_Base>
4252 { return __y._M_current < __x._M_current; }
4254 friend constexpr bool
4255 operator<=(const _Iterator& __x, const _Iterator& __y)
4256 requires random_access_range<_Base>
4257 { return !(__y._M_current > __x._M_current); }
4259 friend constexpr bool
4260 operator>=(const _Iterator& __x, const _Iterator& __y)
4261 requires random_access_range<_Base>
4262 { return !(__x._M_current > __y._M_current); }
4264#ifdef __cpp_lib_three_way_comparison
4265 friend constexpr auto
4266 operator<=>(const _Iterator& __x, const _Iterator& __y)
4267 requires random_access_range<_Base>
4268 && three_way_comparable<iterator_t<_Base>>
4269 { return __x._M_current <=> __y._M_current; }
4272 friend constexpr _Iterator
4273 operator+(const _Iterator& __x, difference_type __y)
4274 requires random_access_range<_Base>
4275 { return _Iterator{__x} += __y; }
4277 friend constexpr _Iterator
4278 operator+(difference_type __x, const _Iterator& __y)
4279 requires random_access_range<_Base>
4280 { return __y + __x; }
4282 friend constexpr _Iterator
4283 operator-(const _Iterator& __x, difference_type __y)
4284 requires random_access_range<_Base>
4285 { return _Iterator{__x} -= __y; }
4287 // _GLIBCXX_RESOLVE_LIB_DEFECTS
4288 // 3483. transform_view::iterator's difference is overconstrained
4289 friend constexpr difference_type
4290 operator-(const _Iterator& __x, const _Iterator& __y)
4291 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
4292 { return __x._M_current - __y._M_current; }
4294 template <bool> friend struct _Sentinel;
4297 template<bool _Const>
4301 template<bool _Const2>
4303 _M_equal(const _Iterator<_Const2>& __x) const
4304 { return __x._M_current == _M_end; }
4306 template<bool _Const2>
4308 _M_distance_from(const _Iterator<_Const2>& __i) const
4309 { return _M_end - __i._M_current; }
4311 using _Base = elements_view::_Base<_Const>;
4312 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
4315 _Sentinel() = default;
4318 _Sentinel(sentinel_t<_Base> __end)
4319 : _M_end(std::move(__end))
4323 _Sentinel(_Sentinel<!_Const> __other)
4325 && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
4326 : _M_end(std::move(__other._M_end))
4329 constexpr sentinel_t<_Base>
4333 template<bool _Const2>
4334 requires sentinel_for<sentinel_t<_Base>,
4335 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
4336 friend constexpr bool
4337 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
4338 { return __y._M_equal(__x); }
4340 template<bool _Const2,
4341 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
4342 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
4343 friend constexpr range_difference_t<_Base2>
4344 operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
4345 { return -__y._M_distance_from(__x); }
4347 template<bool _Const2,
4348 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
4349 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
4350 friend constexpr range_difference_t<_Base2>
4351 operator-(const _Sentinel& __x, const _Iterator<_Const2>& __y)
4352 { return __x._M_distance_from(__y); }
4354 friend _Sentinel<!_Const>;
4357 _Vp _M_base = _Vp();
4360 template<typename _Tp, size_t _Nm>
4361 inline constexpr bool enable_borrowed_range<elements_view<_Tp, _Nm>>
4362 = enable_borrowed_range<_Tp>;
4364 template<typename _Range>
4365 using keys_view = elements_view<views::all_t<_Range>, 0>;
4367 template<typename _Range>
4368 using values_view = elements_view<views::all_t<_Range>, 1>;
4374 template<size_t _Nm, typename _Range>
4375 concept __can_elements_view
4376 = requires { elements_view<all_t<_Range>, _Nm>{std::declval<_Range>()}; };
4377 } // namespace __detail
4379 template<size_t _Nm>
4380 struct _Elements : __adaptor::_RangeAdaptorClosure
4382 template<viewable_range _Range>
4383 requires __detail::__can_elements_view<_Nm, _Range>
4385 operator() [[nodiscard]] (_Range&& __r) const
4387 return elements_view<all_t<_Range>, _Nm>{std::forward<_Range>(__r)};
4390 static constexpr bool _S_has_simple_call_op = true;
4393 template<size_t _Nm>
4394 inline constexpr _Elements<_Nm> elements;
4395 inline constexpr auto keys = elements<0>;
4396 inline constexpr auto values = elements<1>;
4397 } // namespace views
4399#if __cplusplus > 202002L
4401#define __cpp_lib_ranges_zip 202110L
4405 template<typename... _Rs>
4406 concept __zip_is_common = (sizeof...(_Rs) == 1 && (common_range<_Rs> && ...))
4407 || (!(bidirectional_range<_Rs> && ...) && (common_range<_Rs> && ...))
4408 || ((random_access_range<_Rs> && ...) && (sized_range<_Rs> && ...));
4410 template<typename... _Ts>
4411 struct __tuple_or_pair
4412 { using type = std::tuple<_Ts...>; };
4414 template<typename _Tp, typename _Up>
4415 struct __tuple_or_pair<_Tp, _Up>
4416 { using type = pair<_Tp, _Up>; };
4418 template<typename... _Ts>
4419 using __tuple_or_pair_t = typename __tuple_or_pair<_Ts...>::type;
4421 template<typename _Fp, typename _Tuple>
4423 __tuple_transform(_Fp&& __f, _Tuple&& __tuple)
4425 return std::apply([&]<typename... _Ts>(_Ts&&... __elts) {
4426 return __tuple_or_pair_t<invoke_result_t<_Fp&, _Ts>...>
4427 (std::__invoke(__f, std::forward<_Ts>(__elts))...);
4428 }, std::forward<_Tuple>(__tuple));
4431 template<typename _Fp, typename _Tuple>
4433 __tuple_for_each(_Fp&& __f, _Tuple&& __tuple)
4435 std::apply([&]<typename... _Ts>(_Ts&&... __elts) {
4436 (std::__invoke(__f, std::forward<_Ts>(__elts)), ...);
4437 }, std::forward<_Tuple>(__tuple));
4439 } // namespace __detail
4441 template<input_range... _Vs>
4442 requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0)
4443 class zip_view : public view_interface<zip_view<_Vs...>>
4445 tuple<_Vs...> _M_views;
4447 template<bool> class _Iterator;
4448 template<bool> class _Sentinel;
4451 zip_view() = default;
4454 zip_view(_Vs... __views)
4455 : _M_views(std::move(__views)...)
4459 begin() requires (!(__detail::__simple_view<_Vs> && ...))
4460 { return _Iterator<false>(__detail::__tuple_transform(ranges::begin, _M_views)); }
4463 begin() const requires (range<const _Vs> && ...)
4464 { return _Iterator<true>(__detail::__tuple_transform(ranges::begin, _M_views)); }
4467 end() requires (!(__detail::__simple_view<_Vs> && ...))
4469 if constexpr (!__detail::__zip_is_common<_Vs...>)
4470 return _Sentinel<false>(__detail::__tuple_transform(ranges::end, _M_views));
4471 else if constexpr ((random_access_range<_Vs> && ...))
4472 return begin() + iter_difference_t<_Iterator<false>>(size());
4474 return _Iterator<false>(__detail::__tuple_transform(ranges::end, _M_views));
4478 end() const requires (range<const _Vs> && ...)
4480 if constexpr (!__detail::__zip_is_common<const _Vs...>)
4481 return _Sentinel<true>(__detail::__tuple_transform(ranges::end, _M_views));
4482 else if constexpr ((random_access_range<const _Vs> && ...))
4483 return begin() + iter_difference_t<_Iterator<true>>(size());
4485 return _Iterator<true>(__detail::__tuple_transform(ranges::end, _M_views));
4489 size() requires (sized_range<_Vs> && ...)
4491 return std::apply([](auto... sizes) {
4492 using _CT = __detail::__make_unsigned_like_t<common_type_t<decltype(sizes)...>>;
4493 return ranges::min({_CT(sizes)...});
4494 }, __detail::__tuple_transform(ranges::size, _M_views));
4498 size() const requires (sized_range<const _Vs> && ...)
4500 return std::apply([](auto... sizes) {
4501 using _CT = __detail::__make_unsigned_like_t<common_type_t<decltype(sizes)...>>;
4502 return ranges::min({_CT(sizes)...});
4503 }, __detail::__tuple_transform(ranges::size, _M_views));
4507 template<typename... _Rs>
4508 zip_view(_Rs&&...) -> zip_view<views::all_t<_Rs>...>;
4510 template<typename... _Views>
4511 inline constexpr bool enable_borrowed_range<zip_view<_Views...>>
4512 = (enable_borrowed_range<_Views> && ...);
4516 template<bool _Const, typename... _Vs>
4517 concept __all_random_access
4518 = (random_access_range<__maybe_const_t<_Const, _Vs>> && ...);
4520 template<bool _Const, typename... _Vs>
4521 concept __all_bidirectional
4522 = (bidirectional_range<__maybe_const_t<_Const, _Vs>> && ...);
4524 template<bool _Const, typename... _Vs>
4525 concept __all_forward
4526 = (forward_range<__maybe_const_t<_Const, _Vs>> && ...);
4528 template<bool _Const, typename... _Views>
4529 struct __zip_view_iter_cat
4532 template<bool _Const, typename... _Views>
4533 requires __all_forward<_Const, _Views...>
4534 struct __zip_view_iter_cat<_Const, _Views...>
4535 { using iterator_category = input_iterator_tag; };
4536 } // namespace __detail
4538 template<input_range... _Vs>
4539 requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0)
4540 template<bool _Const>
4541 class zip_view<_Vs...>::_Iterator
4542 : public __detail::__zip_view_iter_cat<_Const, _Vs...>
4544#ifdef __clang__ // LLVM-61763 workaround
4547 __detail::__tuple_or_pair_t<iterator_t<__detail::__maybe_const_t<_Const, _Vs>>...> _M_current;
4550 _Iterator(decltype(_M_current) __current)
4551 : _M_current(std::move(__current))
4557 if constexpr (__detail::__all_random_access<_Const, _Vs...>)
4558 return random_access_iterator_tag{};
4559 else if constexpr (__detail::__all_bidirectional<_Const, _Vs...>)
4560 return bidirectional_iterator_tag{};
4561 else if constexpr (__detail::__all_forward<_Const, _Vs...>)
4562 return forward_iterator_tag{};
4564 return input_iterator_tag{};
4567#ifndef __clang__ // LLVM-61763 workaround
4568 template<copy_constructible _Fp, input_range... _Ws>
4569 requires (view<_Ws> && ...) && (sizeof...(_Ws) > 0) && is_object_v<_Fp>
4570 && regular_invocable<_Fp&, range_reference_t<_Ws>...>
4571 && std::__detail::__can_reference<invoke_result_t<_Fp&, range_reference_t<_Ws>...>>
4572 friend class zip_transform_view;
4576 // iterator_category defined in __zip_view_iter_cat
4577 using iterator_concept = decltype(_S_iter_concept());
4579 = __detail::__tuple_or_pair_t<range_value_t<__detail::__maybe_const_t<_Const, _Vs>>...>;
4580 using difference_type
4581 = common_type_t<range_difference_t<__detail::__maybe_const_t<_Const, _Vs>>...>;
4583 _Iterator() = default;
4586 _Iterator(_Iterator<!_Const> __i)
4588 && (convertible_to<iterator_t<_Vs>,
4589 iterator_t<__detail::__maybe_const_t<_Const, _Vs>>> && ...)
4590 : _M_current(std::move(__i._M_current))
4596 auto __f = [](auto& __i) -> decltype(auto) {
4599 return __detail::__tuple_transform(__f, _M_current);
4602 constexpr _Iterator&
4605 __detail::__tuple_for_each([](auto& __i) { ++__i; }, _M_current);
4615 requires __detail::__all_forward<_Const, _Vs...>
4622 constexpr _Iterator&
4624 requires __detail::__all_bidirectional<_Const, _Vs...>
4626 __detail::__tuple_for_each([](auto& __i) { --__i; }, _M_current);
4632 requires __detail::__all_bidirectional<_Const, _Vs...>
4639 constexpr _Iterator&
4640 operator+=(difference_type __x)
4641 requires __detail::__all_random_access<_Const, _Vs...>
4643 auto __f = [&]<typename _It>(_It& __i) {
4644 __i += iter_difference_t<_It>(__x);
4646 __detail::__tuple_for_each(__f, _M_current);
4650 constexpr _Iterator&
4651 operator-=(difference_type __x)
4652 requires __detail::__all_random_access<_Const, _Vs...>
4654 auto __f = [&]<typename _It>(_It& __i) {
4655 __i -= iter_difference_t<_It>(__x);
4657 __detail::__tuple_for_each(__f, _M_current);
4662 operator[](difference_type __n) const
4663 requires __detail::__all_random_access<_Const, _Vs...>
4665 auto __f = [&]<typename _It>(_It& __i) -> decltype(auto) {
4666 return __i[iter_difference_t<_It>(__n)];
4668 return __detail::__tuple_transform(__f, _M_current);
4671 friend constexpr bool
4672 operator==(const _Iterator& __x, const _Iterator& __y)
4673 requires (equality_comparable<iterator_t<__detail::__maybe_const_t<_Const, _Vs>>> && ...)
4675 if constexpr (__detail::__all_bidirectional<_Const, _Vs...>)
4676 return __x._M_current == __y._M_current;
4678 return [&]<size_t... _Is>(index_sequence<_Is...>) {
4679 return ((std::get<_Is>(__x._M_current) == std::get<_Is>(__y._M_current)) || ...);
4680 }(make_index_sequence<sizeof...(_Vs)>{});
4683 friend constexpr auto
4684 operator<=>(const _Iterator& __x, const _Iterator& __y)
4685 requires __detail::__all_random_access<_Const, _Vs...>
4686 { return __x._M_current <=> __y._M_current; }
4688 friend constexpr _Iterator
4689 operator+(const _Iterator& __i, difference_type __n)
4690 requires __detail::__all_random_access<_Const, _Vs...>
4697 friend constexpr _Iterator
4698 operator+(difference_type __n, const _Iterator& __i)
4699 requires __detail::__all_random_access<_Const, _Vs...>
4706 friend constexpr _Iterator
4707 operator-(const _Iterator& __i, difference_type __n)
4708 requires __detail::__all_random_access<_Const, _Vs...>
4715 friend constexpr difference_type
4716 operator-(const _Iterator& __x, const _Iterator& __y)
4717 requires (sized_sentinel_for<iterator_t<__detail::__maybe_const_t<_Const, _Vs>>,
4718 iterator_t<__detail::__maybe_const_t<_Const, _Vs>>> && ...)
4720 return [&]<size_t... _Is>(index_sequence<_Is...>) {
4721 return ranges::min({difference_type(std::get<_Is>(__x._M_current)
4722 - std::get<_Is>(__y._M_current))...},
4724 [](difference_type __i) {
4725 return __detail::__to_unsigned_like(__i < 0 ? -__i : __i);
4727 }(make_index_sequence<sizeof...(_Vs)>{});
4730 friend constexpr auto
4731 iter_move(const _Iterator& __i)
4732 { return __detail::__tuple_transform(ranges::iter_move, __i._M_current); }
4734 friend constexpr void
4735 iter_swap(const _Iterator& __l, const _Iterator& __r)
4736 requires (indirectly_swappable<iterator_t<__detail::__maybe_const_t<_Const, _Vs>>> && ...)
4738 [&]<size_t... _Is>(index_sequence<_Is...>) {
4739 (ranges::iter_swap(std::get<_Is>(__l._M_current), std::get<_Is>(__r._M_current)), ...);
4740 }(make_index_sequence<sizeof...(_Vs)>{});
4743 friend class zip_view;
4746 template<input_range... _Vs>
4747 requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0)
4748 template<bool _Const>
4749 class zip_view<_Vs...>::_Sentinel
4751 __detail::__tuple_or_pair_t<sentinel_t<__detail::__maybe_const_t<_Const, _Vs>>...> _M_end;
4754 _Sentinel(decltype(_M_end) __end)
4758 friend class zip_view;
4761 _Sentinel() = default;
4764 _Sentinel(_Sentinel<!_Const> __i)
4766 && (convertible_to<sentinel_t<_Vs>,
4767 sentinel_t<__detail::__maybe_const_t<_Const, _Vs>>> && ...)
4768 : _M_end(std::move(__i._M_end))
4771 template<bool _OtherConst>
4772 requires (sentinel_for<sentinel_t<__detail::__maybe_const_t<_Const, _Vs>>,
4773 iterator_t<__detail::__maybe_const_t<_OtherConst, _Vs>>> && ...)
4774 friend constexpr bool
4775 operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y)
4777 return [&]<size_t... _Is>(index_sequence<_Is...>) {
4778 return ((std::get<_Is>(__x._M_current) == std::get<_Is>(__y._M_end)) || ...);
4779 }(make_index_sequence<sizeof...(_Vs)>{});
4782 template<bool _OtherConst>
4783 requires (sized_sentinel_for<sentinel_t<__detail::__maybe_const_t<_Const, _Vs>>,
4784 iterator_t<__detail::__maybe_const_t<_OtherConst, _Vs>>> && ...)
4785 friend constexpr auto
4786 operator-(const _Iterator<_OtherConst>& __x, const _Sentinel& __y)
4789 = common_type_t<range_difference_t<__detail::__maybe_const_t<_OtherConst, _Vs>>...>;
4790 return [&]<size_t... _Is>(index_sequence<_Is...>) {
4791 return ranges::min({_Ret(std::get<_Is>(__x._M_current) - std::get<_Is>(__y._M_end))...},
4794 return __detail::__to_unsigned_like(__i < 0 ? -__i : __i);
4796 }(make_index_sequence<sizeof...(_Vs)>{});
4799 template<bool _OtherConst>
4800 requires (sized_sentinel_for<sentinel_t<__detail::__maybe_const_t<_Const, _Vs>>,
4801 iterator_t<__detail::__maybe_const_t<_OtherConst, _Vs>>> && ...)
4802 friend constexpr auto
4803 operator-(const _Sentinel& __y, const _Iterator<_OtherConst>& __x)
4804 { return -(__x - __y); }
4811 template<typename... _Ts>
4812 concept __can_zip_view
4813 = requires { zip_view<all_t<_Ts>...>(std::declval<_Ts>()...); };
4818 template<typename... _Ts>
4819 requires (sizeof...(_Ts) == 0 || __detail::__can_zip_view<_Ts...>)
4821 operator() [[nodiscard]] (_Ts&&... __ts) const
4823 if constexpr (sizeof...(_Ts) == 0)
4824 return views::empty<tuple<>>;
4826 return zip_view<all_t<_Ts>...>(std::forward<_Ts>(__ts)...);
4830 inline constexpr _Zip zip;
4835 template<typename _Range, bool _Const>
4836 using __range_iter_cat
4837 = typename iterator_traits<iterator_t<__maybe_const_t<_Const, _Range>>>::iterator_category;
4840 template<copy_constructible _Fp, input_range... _Vs>
4841 requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) && is_object_v<_Fp>
4842 && regular_invocable<_Fp&, range_reference_t<_Vs>...>
4843 && std::__detail::__can_reference<invoke_result_t<_Fp&, range_reference_t<_Vs>...>>
4844 class zip_transform_view : public view_interface<zip_transform_view<_Fp, _Vs...>>
4846 [[no_unique_address]] __detail::__box<_Fp> _M_fun;
4847 zip_view<_Vs...> _M_zip;
4849 using _InnerView = zip_view<_Vs...>;
4851 template<bool _Const>
4852 using __ziperator = iterator_t<__detail::__maybe_const_t<_Const, _InnerView>>;
4854 template<bool _Const>
4855 using __zentinel = sentinel_t<__detail::__maybe_const_t<_Const, _InnerView>>;
4857 template<bool _Const>
4858 using _Base = __detail::__maybe_const_t<_Const, _InnerView>;
4860 template<bool _Const>
4864 template<bool _Const>
4865 requires forward_range<_Base<_Const>>
4866 struct __iter_cat<_Const>
4872 using __detail::__maybe_const_t;
4873 using __detail::__range_iter_cat;
4874 using _Res = invoke_result_t<__maybe_const_t<_Const, _Fp>&,
4875 range_reference_t<__maybe_const_t<_Const, _Vs>>...>;
4876 if constexpr (!is_lvalue_reference_v<_Res>)
4877 return input_iterator_tag{};
4878 else if constexpr ((derived_from<__range_iter_cat<_Vs, _Const>,
4879 random_access_iterator_tag> && ...))
4880 return random_access_iterator_tag{};
4881 else if constexpr ((derived_from<__range_iter_cat<_Vs, _Const>,
4882 bidirectional_iterator_tag> && ...))
4883 return bidirectional_iterator_tag{};
4884 else if constexpr ((derived_from<__range_iter_cat<_Vs, _Const>,
4885 forward_iterator_tag> && ...))
4886 return forward_iterator_tag{};
4888 return input_iterator_tag{};
4891 using iterator_category = decltype(_S_iter_cat());
4894 template<bool> class _Iterator;
4895 template<bool> class _Sentinel;
4898 zip_transform_view() = default;
4901 zip_transform_view(_Fp __fun, _Vs... __views)
4902 : _M_fun(std::move(__fun)), _M_zip(std::move(__views)...)
4907 { return _Iterator<false>(*this, _M_zip.begin()); }
4911 requires range<const _InnerView>
4912 && regular_invocable<const _Fp&, range_reference_t<const _Vs>...>
4913 { return _Iterator<true>(*this, _M_zip.begin()); }
4918 if constexpr (common_range<_InnerView>)
4919 return _Iterator<false>(*this, _M_zip.end());
4921 return _Sentinel<false>(_M_zip.end());
4926 requires range<const _InnerView>
4927 && regular_invocable<const _Fp&, range_reference_t<const _Vs>...>
4929 if constexpr (common_range<const _InnerView>)
4930 return _Iterator<true>(*this, _M_zip.end());
4932 return _Sentinel<true>(_M_zip.end());
4936 size() requires sized_range<_InnerView>
4937 { return _M_zip.size(); }
4940 size() const requires sized_range<const _InnerView>
4941 { return _M_zip.size(); }
4944 template<class _Fp, class... Rs>
4945 zip_transform_view(_Fp, Rs&&...) -> zip_transform_view<_Fp, views::all_t<Rs>...>;
4947 template<copy_constructible _Fp, input_range... _Vs>
4948 requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) && is_object_v<_Fp>
4949 && regular_invocable<_Fp&, range_reference_t<_Vs>...>
4950 && std::__detail::__can_reference<invoke_result_t<_Fp&, range_reference_t<_Vs>...>>
4951 template<bool _Const>
4952 class zip_transform_view<_Fp, _Vs...>::_Iterator : public __iter_cat<_Const>
4954 using _Parent = __detail::__maybe_const_t<_Const, zip_transform_view>;
4956 _Parent* _M_parent = nullptr;
4957 __ziperator<_Const> _M_inner;
4960 _Iterator(_Parent& __parent, __ziperator<_Const> __inner)
4961 : _M_parent(std::__addressof(__parent)), _M_inner(std::move(__inner))
4964 friend class zip_transform_view;
4967 // iterator_category defined in zip_transform_view::__iter_cat
4968 using iterator_concept = typename __ziperator<_Const>::iterator_concept;
4970 = remove_cvref_t<invoke_result_t<__detail::__maybe_const_t<_Const, _Fp>&,
4971 range_reference_t<__detail::__maybe_const_t<_Const, _Vs>>...>>;
4972 using difference_type = range_difference_t<_Base<_Const>>;
4974 _Iterator() = default;
4977 _Iterator(_Iterator<!_Const> __i)
4978 requires _Const && convertible_to<__ziperator<false>, __ziperator<_Const>>
4979 : _M_parent(__i._M_parent), _M_inner(std::move(__i._M_inner))
4982 constexpr decltype(auto)
4985 return std::apply([&](const auto&... __iters) -> decltype(auto) {
4986 return std::__invoke(*_M_parent->_M_fun, *__iters...);
4987 }, _M_inner._M_current);
4990 constexpr _Iterator&
5002 operator++(int) requires forward_range<_Base<_Const>>
5009 constexpr _Iterator&
5010 operator--() requires bidirectional_range<_Base<_Const>>
5017 operator--(int) requires bidirectional_range<_Base<_Const>>
5024 constexpr _Iterator&
5025 operator+=(difference_type __x) requires random_access_range<_Base<_Const>>
5031 constexpr _Iterator&
5032 operator-=(difference_type __x) requires random_access_range<_Base<_Const>>
5038 constexpr decltype(auto)
5039 operator[](difference_type __n) const requires random_access_range<_Base<_Const>>
5041 return std::apply([&]<typename... _Is>(const _Is&... __iters) -> decltype(auto) {
5042 return std::__invoke(*_M_parent->_M_fun, __iters[iter_difference_t<_Is>(__n)]...);
5043 }, _M_inner._M_current);
5046 friend constexpr bool
5047 operator==(const _Iterator& __x, const _Iterator& __y)
5048 requires equality_comparable<__ziperator<_Const>>
5049 { return __x._M_inner == __y._M_inner; }
5051 friend constexpr auto
5052 operator<=>(const _Iterator& __x, const _Iterator& __y)
5053 requires random_access_range<_Base<_Const>>
5054 { return __x._M_inner <=> __y._M_inner; }
5056 friend constexpr _Iterator
5057 operator+(const _Iterator& __i, difference_type __n)
5058 requires random_access_range<_Base<_Const>>
5059 { return _Iterator(*__i._M_parent, __i._M_inner + __n); }
5061 friend constexpr _Iterator
5062 operator+(difference_type __n, const _Iterator& __i)
5063 requires random_access_range<_Base<_Const>>
5064 { return _Iterator(*__i._M_parent, __i._M_inner + __n); }
5066 friend constexpr _Iterator
5067 operator-(const _Iterator& __i, difference_type __n)
5068 requires random_access_range<_Base<_Const>>
5069 { return _Iterator(*__i._M_parent, __i._M_inner - __n); }
5071 friend constexpr difference_type
5072 operator-(const _Iterator& __x, const _Iterator& __y)
5073 requires sized_sentinel_for<__ziperator<_Const>, __ziperator<_Const>>
5074 { return __x._M_inner - __y._M_inner; }
5077 template<copy_constructible _Fp, input_range... _Vs>
5078 requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) && is_object_v<_Fp>
5079 && regular_invocable<_Fp&, range_reference_t<_Vs>...>
5080 && std::__detail::__can_reference<invoke_result_t<_Fp&, range_reference_t<_Vs>...>>
5081 template<bool _Const>
5082 class zip_transform_view<_Fp, _Vs...>::_Sentinel
5084 __zentinel<_Const> _M_inner;
5087 _Sentinel(__zentinel<_Const> __inner)
5091 friend class zip_transform_view;
5094 _Sentinel() = default;
5097 _Sentinel(_Sentinel<!_Const> __i)
5098 requires _Const && convertible_to<__zentinel<false>, __zentinel<_Const>>
5099 : _M_inner(std::move(__i._M_inner))
5102 template<bool _OtherConst>
5103 requires sentinel_for<__zentinel<_Const>, __ziperator<_OtherConst>>
5104 friend constexpr bool
5105 operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y)
5106 { return __x._M_inner == __y._M_inner; }
5108 template<bool _OtherConst>
5109 requires sized_sentinel_for<__zentinel<_Const>, __ziperator<_OtherConst>>
5110 friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _InnerView>>
5111 operator-(const _Iterator<_OtherConst>& __x, const _Sentinel& __y)
5112 { return __x._M_inner - __y._M_inner; }
5114 template<bool _OtherConst>
5115 requires sized_sentinel_for<__zentinel<_Const>, __ziperator<_OtherConst>>
5116 friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _InnerView>>
5117 operator-(const _Sentinel& __x, const _Iterator<_OtherConst>& __y)
5118 { return __x._M_inner - __y._M_inner; }
5125 template<typename _Fp, typename... _Ts>
5126 concept __can_zip_transform_view
5127 = requires { zip_transform_view(std::declval<_Fp>(), std::declval<_Ts>()...); };
5130 struct _ZipTransform
5132 template<typename _Fp, typename... _Ts>
5133 requires (sizeof...(_Ts) == 0) || __detail::__can_zip_transform_view<_Fp, _Ts...>
5135 operator() [[nodiscard]] (_Fp&& __f, _Ts&&... __ts) const
5137 if constexpr (sizeof...(_Ts) == 0)
5138 return views::empty<decay_t<invoke_result_t<decay_t<_Fp>&>>>;
5140 return zip_transform_view(std::forward<_Fp>(__f), std::forward<_Ts>(__ts)...);
5144 inline constexpr _ZipTransform zip_transform;
5147 template<forward_range _Vp, size_t _Nm>
5148 requires view<_Vp> && (_Nm > 0)
5149 class adjacent_view : public view_interface<adjacent_view<_Vp, _Nm>>
5151 _Vp _M_base = _Vp();
5153 template<bool> class _Iterator;
5154 template<bool> class _Sentinel;
5156 struct __as_sentinel
5160 adjacent_view() requires default_initializable<_Vp> = default;
5163 adjacent_view(_Vp __base)
5164 : _M_base(std::move(__base))
5168 begin() requires (!__detail::__simple_view<_Vp>)
5169 { return _Iterator<false>(ranges::begin(_M_base), ranges::end(_M_base)); }
5172 begin() const requires range<const _Vp>
5173 { return _Iterator<true>(ranges::begin(_M_base), ranges::end(_M_base)); }
5176 end() requires (!__detail::__simple_view<_Vp>)
5178 if constexpr (common_range<_Vp>)
5179 return _Iterator<false>(__as_sentinel{}, ranges::begin(_M_base), ranges::end(_M_base));
5181 return _Sentinel<false>(ranges::end(_M_base));
5185 end() const requires range<const _Vp>
5187 if constexpr (common_range<const _Vp>)
5188 return _Iterator<true>(__as_sentinel{}, ranges::begin(_M_base), ranges::end(_M_base));
5190 return _Sentinel<true>(ranges::end(_M_base));
5194 size() requires sized_range<_Vp>
5196 using _ST = decltype(ranges::size(_M_base));
5197 using _CT = common_type_t<_ST, size_t>;
5198 auto __sz = static_cast<_CT>(ranges::size(_M_base));
5199 __sz -= std::min<_CT>(__sz, _Nm - 1);
5200 return static_cast<_ST>(__sz);
5204 size() const requires sized_range<const _Vp>
5206 using _ST = decltype(ranges::size(_M_base));
5207 using _CT = common_type_t<_ST, size_t>;
5208 auto __sz = static_cast<_CT>(ranges::size(_M_base));
5209 __sz -= std::min<_CT>(__sz, _Nm - 1);
5210 return static_cast<_ST>(__sz);
5214 template<typename _Vp, size_t _Nm>
5215 inline constexpr bool enable_borrowed_range<adjacent_view<_Vp, _Nm>>
5216 = enable_borrowed_range<_Vp>;
5220 // Yields tuple<_Tp, ..., _Tp> with _Nm elements.
5221 template<typename _Tp, size_t _Nm>
5222 using __repeated_tuple = decltype(std::tuple_cat(std::declval<array<_Tp, _Nm>>()));
5224 // For a functor F that is callable with N arguments, the expression
5225 // declval<__unarize<F, N>>(x) is equivalent to declval<F>(x, ..., x).
5226 template<typename _Fp, size_t _Nm>
5229 template<typename... _Ts>
5230 static invoke_result_t<_Fp, _Ts...>
5231 __tuple_apply(const tuple<_Ts...>&); // not defined
5233 template<typename _Tp>
5234 decltype(__tuple_apply(std::declval<__repeated_tuple<_Tp, _Nm>>()))
5235 operator()(_Tp&&); // not defined
5239 template<forward_range _Vp, size_t _Nm>
5240 requires view<_Vp> && (_Nm > 0)
5241 template<bool _Const>
5242 class adjacent_view<_Vp, _Nm>::_Iterator
5244#ifdef __clang__ // LLVM-61763 workaround
5247 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
5248 array<iterator_t<_Base>, _Nm> _M_current = array<iterator_t<_Base>, _Nm>();
5251 _Iterator(iterator_t<_Base> __first, sentinel_t<_Base> __last)
5253 for (auto& __i : _M_current)
5256 ranges::advance(__first, 1, __last);
5261 _Iterator(__as_sentinel, iterator_t<_Base> __first, iterator_t<_Base> __last)
5263 if constexpr (!bidirectional_range<_Base>)
5264 for (auto& __it : _M_current)
5267 for (size_t __i = 0; __i < _Nm; ++__i)
5269 _M_current[_Nm - 1 - __i] = __last;
5270 ranges::advance(__last, -1, __first);
5277 if constexpr (random_access_range<_Base>)
5278 return random_access_iterator_tag{};
5279 else if constexpr (bidirectional_range<_Base>)
5280 return bidirectional_iterator_tag{};
5282 return forward_iterator_tag{};
5285 friend class adjacent_view;
5287#ifndef __clang__ // LLVM-61763 workaround
5288 template<forward_range _Wp, copy_constructible _Fp, size_t _Mm>
5289 requires view<_Wp> && (_Mm > 0) && is_object_v<_Fp>
5290 && regular_invocable<__detail::__unarize<_Fp&, _Mm>, range_reference_t<_Wp>>
5291 && std::__detail::__can_reference<invoke_result_t<__detail::__unarize<_Fp&, _Mm>,
5292 range_reference_t<_Wp>>>
5293 friend class adjacent_transform_view;
5297 using iterator_category = input_iterator_tag;
5298 using iterator_concept = decltype(_S_iter_concept());
5299 using value_type = conditional_t<_Nm == 2,
5300 pair<range_value_t<_Base>, range_value_t<_Base>>,
5301 __detail::__repeated_tuple<range_value_t<_Base>, _Nm>>;
5302 using difference_type = range_difference_t<_Base>;
5304 _Iterator() = default;
5307 _Iterator(_Iterator<!_Const> __i)
5308 requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
5310 for (size_t __j = 0; __j < _Nm; ++__j)
5311 _M_current[__j] = std::move(__i._M_current[__j]);
5317 auto __f = [](auto& __i) -> decltype(auto) { return *__i; };
5318 return __detail::__tuple_transform(__f, _M_current);
5321 constexpr _Iterator&
5324 for (auto& __i : _M_current)
5337 constexpr _Iterator&
5338 operator--() requires bidirectional_range<_Base>
5340 for (auto& __i : _M_current)
5346 operator--(int) requires bidirectional_range<_Base>
5353 constexpr _Iterator&
5354 operator+=(difference_type __x)
5355 requires random_access_range<_Base>
5357 for (auto& __i : _M_current)
5362 constexpr _Iterator&
5363 operator-=(difference_type __x)
5364 requires random_access_range<_Base>
5366 for (auto& __i : _M_current)
5372 operator[](difference_type __n) const
5373 requires random_access_range<_Base>
5375 auto __f = [&](auto& __i) -> decltype(auto) { return __i[__n]; };
5376 return __detail::__tuple_transform(__f, _M_current);
5379 friend constexpr bool
5380 operator==(const _Iterator& __x, const _Iterator& __y)
5381 { return __x._M_current.back() == __y._M_current.back(); }
5383 friend constexpr bool
5384 operator<(const _Iterator& __x, const _Iterator& __y)
5385 requires random_access_range<_Base>
5386 { return __x._M_current.back() < __y._M_current.back(); }
5388 friend constexpr bool
5389 operator>(const _Iterator& __x, const _Iterator& __y)
5390 requires random_access_range<_Base>
5391 { return __y < __x; }
5393 friend constexpr bool
5394 operator<=(const _Iterator& __x, const _Iterator& __y)
5395 requires random_access_range<_Base>
5396 { return !(__y < __x); }
5398 friend constexpr bool
5399 operator>=(const _Iterator& __x, const _Iterator& __y)
5400 requires random_access_range<_Base>
5401 { return !(__x < __y); }
5403 friend constexpr auto
5404 operator<=>(const _Iterator& __x, const _Iterator& __y)
5405 requires random_access_range<_Base>
5406 && three_way_comparable<iterator_t<_Base>>
5407 { return __x._M_current.back() <=> __y._M_current.back(); }
5409 friend constexpr _Iterator
5410 operator+(const _Iterator& __i, difference_type __n)
5411 requires random_access_range<_Base>
5418 friend constexpr _Iterator
5419 operator+(difference_type __n, const _Iterator& __i)
5420 requires random_access_range<_Base>
5427 friend constexpr _Iterator
5428 operator-(const _Iterator& __i, difference_type __n)
5429 requires random_access_range<_Base>
5436 friend constexpr difference_type
5437 operator-(const _Iterator& __x, const _Iterator& __y)
5438 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
5439 { return __x._M_current.back() - __y._M_current.back(); }
5441 friend constexpr auto
5442 iter_move(const _Iterator& __i)
5443 { return __detail::__tuple_transform(ranges::iter_move, __i._M_current); }
5445 friend constexpr void
5446 iter_swap(const _Iterator& __l, const _Iterator& __r)
5447 requires indirectly_swappable<iterator_t<_Base>>
5449 for (size_t __i = 0; __i < _Nm; __i++)
5450 ranges::iter_swap(__l._M_current[__i], __r._M_current[__i]);
5454 template<forward_range _Vp, size_t _Nm>
5455 requires view<_Vp> && (_Nm > 0)
5456 template<bool _Const>
5457 class adjacent_view<_Vp, _Nm>::_Sentinel
5459 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
5461 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
5464 _Sentinel(sentinel_t<_Base> __end)
5468 friend class adjacent_view;
5471 _Sentinel() = default;
5474 _Sentinel(_Sentinel<!_Const> __i)
5475 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
5476 : _M_end(std::move(__i._M_end))
5479 template<bool _OtherConst>
5480 requires sentinel_for<sentinel_t<_Base>,
5481 iterator_t<__detail::__maybe_const_t<_OtherConst, _Vp>>>
5482 friend constexpr bool
5483 operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y)
5484 { return __x._M_current.back() == __y._M_end; }
5486 template<bool _OtherConst>
5487 requires sized_sentinel_for<sentinel_t<_Base>,
5488 iterator_t<__detail::__maybe_const_t<_OtherConst, _Vp>>>
5489 friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _Vp>>
5490 operator-(const _Iterator<_OtherConst>& __x, const _Sentinel& __y)
5491 { return __x._M_current.back() - __y._M_end; }
5493 template<bool _OtherConst>
5494 requires sized_sentinel_for<sentinel_t<_Base>,
5495 iterator_t<__detail::__maybe_const_t<_OtherConst, _Vp>>>
5496 friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _Vp>>
5497 operator-(const _Sentinel& __y, const _Iterator<_OtherConst>& __x)
5498 { return __y._M_end - __x._M_current.back(); }
5505 template<size_t _Nm, typename _Range>
5506 concept __can_adjacent_view
5507 = requires { adjacent_view<all_t<_Range>, _Nm>(std::declval<_Range>()); };
5510 template<size_t _Nm>
5511 struct _Adjacent : __adaptor::_RangeAdaptorClosure
5513 template<viewable_range _Range>
5514 requires (_Nm == 0) || __detail::__can_adjacent_view<_Nm, _Range>
5516 operator() [[nodiscard]] (_Range&& __r) const
5518 if constexpr (_Nm == 0)
5519 return views::empty<tuple<>>;
5521 return adjacent_view<all_t<_Range>, _Nm>(std::forward<_Range>(__r));
5525 template<size_t _Nm>
5526 inline constexpr _Adjacent<_Nm> adjacent;
5528 inline constexpr auto pairwise = adjacent<2>;
5531 template<forward_range _Vp, copy_constructible _Fp, size_t _Nm>
5532 requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp>
5533 && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>>
5534 && std::__detail::__can_reference<invoke_result_t<__detail::__unarize<_Fp&, _Nm>,
5535 range_reference_t<_Vp>>>
5536 class adjacent_transform_view : public view_interface<adjacent_transform_view<_Vp, _Fp, _Nm>>
5538 [[no_unique_address]] __detail::__box<_Fp> _M_fun;
5539 adjacent_view<_Vp, _Nm> _M_inner;
5541 using _InnerView = adjacent_view<_Vp, _Nm>;
5543 template<bool _Const>
5544 using _InnerIter = iterator_t<__detail::__maybe_const_t<_Const, _InnerView>>;
5546 template<bool _Const>
5547 using _InnerSent = sentinel_t<__detail::__maybe_const_t<_Const, _InnerView>>;
5549 template<bool> class _Iterator;
5550 template<bool> class _Sentinel;
5553 adjacent_transform_view() = default;
5556 adjacent_transform_view(_Vp __base, _Fp __fun)
5557 : _M_fun(std::move(__fun)), _M_inner(std::move(__base))
5562 { return _Iterator<false>(*this, _M_inner.begin()); }
5566 requires range<const _InnerView>
5567 && regular_invocable<__detail::__unarize<const _Fp&, _Nm>,
5568 range_reference_t<const _Vp>>
5569 { return _Iterator<true>(*this, _M_inner.begin()); }
5574 if constexpr (common_range<_InnerView>)
5575 return _Iterator<false>(*this, _M_inner.end());
5577 return _Sentinel<false>(_M_inner.end());
5582 requires range<const _InnerView>
5583 && regular_invocable<__detail::__unarize<const _Fp&, _Nm>,
5584 range_reference_t<const _Vp>>
5586 if constexpr (common_range<const _InnerView>)
5587 return _Iterator<true>(*this, _M_inner.end());
5589 return _Sentinel<true>(_M_inner.end());
5593 size() requires sized_range<_InnerView>
5594 { return _M_inner.size(); }
5597 size() const requires sized_range<const _InnerView>
5598 { return _M_inner.size(); }
5601 template<forward_range _Vp, copy_constructible _Fp, size_t _Nm>
5602 requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp>
5603 && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>>
5604 && std::__detail::__can_reference<invoke_result_t<__detail::__unarize<_Fp&, _Nm>,
5605 range_reference_t<_Vp>>>
5606 template<bool _Const>
5607 class adjacent_transform_view<_Vp, _Fp, _Nm>::_Iterator
5609 using _Parent = __detail::__maybe_const_t<_Const, adjacent_transform_view>;
5610 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
5612 _Parent* _M_parent = nullptr;
5613 _InnerIter<_Const> _M_inner;
5616 _Iterator(_Parent& __parent, _InnerIter<_Const> __inner)
5617 : _M_parent(std::__addressof(__parent)), _M_inner(std::move(__inner))
5623 using __detail::__maybe_const_t;
5624 using __detail::__unarize;
5625 using _Res = invoke_result_t<__unarize<__maybe_const_t<_Const, _Fp>&, _Nm>,
5626 range_reference_t<_Base>>;
5627 using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
5628 if constexpr (!is_lvalue_reference_v<_Res>)
5629 return input_iterator_tag{};
5630 else if constexpr (derived_from<_Cat, random_access_iterator_tag>)
5631 return random_access_iterator_tag{};
5632 else if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
5633 return bidirectional_iterator_tag{};
5634 else if constexpr (derived_from<_Cat, forward_iterator_tag>)
5635 return forward_iterator_tag{};
5637 return input_iterator_tag{};
5640 friend class adjacent_transform_view;
5643 using iterator_category = decltype(_S_iter_cat());
5644 using iterator_concept = typename _InnerIter<_Const>::iterator_concept;
5646 = remove_cvref_t<invoke_result_t
5647 <__detail::__unarize<__detail::__maybe_const_t<_Const, _Fp>&, _Nm>,
5648 range_reference_t<_Base>>>;
5649 using difference_type = range_difference_t<_Base>;
5651 _Iterator() = default;
5654 _Iterator(_Iterator<!_Const> __i)
5655 requires _Const && convertible_to<_InnerIter<false>, _InnerIter<_Const>>
5656 : _M_parent(__i._M_parent), _M_inner(std::move(__i._M_inner))
5659 constexpr decltype(auto)
5662 return std::apply([&](const auto&... __iters) -> decltype(auto) {
5663 return std::__invoke(*_M_parent->_M_fun, *__iters...);
5664 }, _M_inner._M_current);
5667 constexpr _Iterator&
5682 constexpr _Iterator&
5683 operator--() requires bidirectional_range<_Base>
5690 operator--(int) requires bidirectional_range<_Base>
5697 constexpr _Iterator&
5698 operator+=(difference_type __x) requires random_access_range<_Base>
5704 constexpr _Iterator&
5705 operator-=(difference_type __x) requires random_access_range<_Base>
5711 constexpr decltype(auto)
5712 operator[](difference_type __n) const requires random_access_range<_Base>
5714 return std::apply([&](const auto&... __iters) -> decltype(auto) {
5715 return std::__invoke(*_M_parent->_M_fun, __iters[__n]...);
5716 }, _M_inner._M_current);
5719 friend constexpr bool
5720 operator==(const _Iterator& __x, const _Iterator& __y)
5721 { return __x._M_inner == __y._M_inner; }
5723 friend constexpr bool
5724 operator<(const _Iterator& __x, const _Iterator& __y)
5725 requires random_access_range<_Base>
5726 { return __x._M_inner < __y._M_inner; }
5728 friend constexpr bool
5729 operator>(const _Iterator& __x, const _Iterator& __y)
5730 requires random_access_range<_Base>
5731 { return __x._M_inner > __y._M_inner; }
5733 friend constexpr bool
5734 operator<=(const _Iterator& __x, const _Iterator& __y)
5735 requires random_access_range<_Base>
5736 { return __x._M_inner <= __y._M_inner; }
5738 friend constexpr bool
5739 operator>=(const _Iterator& __x, const _Iterator& __y)
5740 requires random_access_range<_Base>
5741 { return __x._M_inner >= __y._M_inner; }
5743 friend constexpr auto
5744 operator<=>(const _Iterator& __x, const _Iterator& __y)
5745 requires random_access_range<_Base> &&
5746 three_way_comparable<_InnerIter<_Const>>
5747 { return __x._M_inner <=> __y._M_inner; }
5749 friend constexpr _Iterator
5750 operator+(const _Iterator& __i, difference_type __n)
5751 requires random_access_range<_Base>
5752 { return _Iterator(*__i._M_parent, __i._M_inner + __n); }
5754 friend constexpr _Iterator
5755 operator+(difference_type __n, const _Iterator& __i)
5756 requires random_access_range<_Base>
5757 { return _Iterator(*__i._M_parent, __i._M_inner + __n); }
5759 friend constexpr _Iterator
5760 operator-(const _Iterator& __i, difference_type __n)
5761 requires random_access_range<_Base>
5762 { return _Iterator(*__i._M_parent, __i._M_inner - __n); }
5764 friend constexpr difference_type
5765 operator-(const _Iterator& __x, const _Iterator& __y)
5766 requires sized_sentinel_for<_InnerIter<_Const>, _InnerIter<_Const>>
5767 { return __x._M_inner - __y._M_inner; }
5770 template<forward_range _Vp, copy_constructible _Fp, size_t _Nm>
5771 requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp>
5772 && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>>
5773 && std::__detail::__can_reference<invoke_result_t<__detail::__unarize<_Fp&, _Nm>,
5774 range_reference_t<_Vp>>>
5775 template<bool _Const>
5776 class adjacent_transform_view<_Vp, _Fp, _Nm>::_Sentinel
5778 _InnerSent<_Const> _M_inner;
5781 _Sentinel(_InnerSent<_Const> __inner)
5785 friend class adjacent_transform_view;
5788 _Sentinel() = default;
5791 _Sentinel(_Sentinel<!_Const> __i)
5792 requires _Const && convertible_to<_InnerSent<false>, _InnerSent<_Const>>
5793 : _M_inner(std::move(__i._M_inner))
5796 template<bool _OtherConst>
5797 requires sentinel_for<_InnerSent<_Const>, _InnerIter<_OtherConst>>
5798 friend constexpr bool
5799 operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y)
5800 { return __x._M_inner == __y._M_inner; }
5802 template<bool _OtherConst>
5803 requires sized_sentinel_for<_InnerSent<_Const>, _InnerIter<_OtherConst>>
5804 friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _InnerView>>
5805 operator-(const _Iterator<_OtherConst>& __x, const _Sentinel& __y)
5806 { return __x._M_inner - __y._M_inner; }
5808 template<bool _OtherConst>
5809 requires sized_sentinel_for<_InnerSent<_Const>, _InnerIter<_OtherConst>>
5810 friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _InnerView>>
5811 operator-(const _Sentinel& __x, const _Iterator<_OtherConst>& __y)
5812 { return __x._M_inner - __y._M_inner; }
5819 template<size_t _Nm, typename _Range, typename _Fp>
5820 concept __can_adjacent_transform_view
5821 = requires { adjacent_transform_view<all_t<_Range>, decay_t<_Fp>, _Nm>
5822 (std::declval<_Range>(), std::declval<_Fp>()); };
5825 template<size_t _Nm>
5826 struct _AdjacentTransform : __adaptor::_RangeAdaptor<_AdjacentTransform<_Nm>>
5828 template<viewable_range _Range, typename _Fp>
5829 requires (_Nm == 0) || __detail::__can_adjacent_transform_view<_Nm, _Range, _Fp>
5831 operator() [[nodiscard]] (_Range&& __r, _Fp&& __f) const
5833 if constexpr (_Nm == 0)
5834 return zip_transform(std::forward<_Fp>(__f));
5836 return adjacent_transform_view<all_t<_Range>, decay_t<_Fp>, _Nm>
5837 (std::forward<_Range>(__r), std::forward<_Fp>(__f));
5840 using __adaptor::_RangeAdaptor<_AdjacentTransform>::operator();
5841 static constexpr int _S_arity = 2;
5842 static constexpr bool _S_has_simple_extra_args = true;
5845 template<size_t _Nm>
5846 inline constexpr _AdjacentTransform<_Nm> adjacent_transform;
5848 inline constexpr auto pairwise_transform = adjacent_transform<2>;
5851#define __cpp_lib_ranges_chunk 202202L
5855 template<typename _Tp>
5856 constexpr _Tp __div_ceil(_Tp __num, _Tp __denom)
5858 _Tp __r = __num / __denom;
5859 if (__num % __denom)
5866 requires input_range<_Vp>
5867 class chunk_view : public view_interface<chunk_view<_Vp>>
5870 range_difference_t<_Vp> _M_n;
5871 range_difference_t<_Vp> _M_remainder = 0;
5872 __detail::__non_propagating_cache<iterator_t<_Vp>> _M_current;
5879 chunk_view(_Vp __base, range_difference_t<_Vp> __n)
5880 : _M_base(std::move(__base)), _M_n(__n)
5881 { __glibcxx_assert(__n >= 0); }
5884 base() const & requires copy_constructible<_Vp>
5889 { return std::move(_M_base); }
5891 constexpr _OuterIter
5894 _M_current = ranges::begin(_M_base);
5895 _M_remainder = _M_n;
5896 return _OuterIter(*this);
5899 constexpr default_sentinel_t
5900 end() const noexcept
5901 { return default_sentinel; }
5904 size() requires sized_range<_Vp>
5906 return __detail::__to_unsigned_like(__detail::__div_ceil
5907 (ranges::distance(_M_base), _M_n));
5911 size() const requires sized_range<const _Vp>
5913 return __detail::__to_unsigned_like(__detail::__div_ceil
5914 (ranges::distance(_M_base), _M_n));
5918 template<typename _Range>
5919 chunk_view(_Range&&, range_difference_t<_Range>) -> chunk_view<views::all_t<_Range>>;
5922 requires input_range<_Vp>
5923 class chunk_view<_Vp>::_OuterIter
5925 chunk_view* _M_parent;
5928 _OuterIter(chunk_view& __parent) noexcept
5929 : _M_parent(std::__addressof(__parent))
5935 using iterator_concept = input_iterator_tag;
5936 using difference_type = range_difference_t<_Vp>;
5940 _OuterIter(_OuterIter&&) = default;
5941 _OuterIter& operator=(_OuterIter&&) = default;
5943 constexpr value_type
5946 __glibcxx_assert(*this != default_sentinel);
5947 return value_type(*_M_parent);
5950 constexpr _OuterIter&
5953 __glibcxx_assert(*this != default_sentinel);
5954 ranges::advance(*_M_parent->_M_current, _M_parent->_M_remainder,
5955 ranges::end(_M_parent->_M_base));
5956 _M_parent->_M_remainder = _M_parent->_M_n;
5964 friend constexpr bool
5965 operator==(const _OuterIter& __x, default_sentinel_t)
5967 return *__x._M_parent->_M_current == ranges::end(__x._M_parent->_M_base)
5968 && __x._M_parent->_M_remainder != 0;
5971 friend constexpr difference_type
5972 operator-(default_sentinel_t, const _OuterIter& __x)
5973 requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
5975 const auto __dist = ranges::end(__x._M_parent->_M_base) - *__x._M_parent->_M_current;
5977 if (__dist < __x._M_parent->_M_remainder)
5978 return __dist == 0 ? 0 : 1;
5980 return 1 + __detail::__div_ceil(__dist - __x._M_parent->_M_remainder,
5981 __x._M_parent->_M_n);
5984 friend constexpr difference_type
5985 operator-(const _OuterIter& __x, default_sentinel_t __y)
5986 requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
5987 { return -(__y - __x); }
5991 requires input_range<_Vp>
5992 struct chunk_view<_Vp>::_OuterIter::value_type : view_interface<value_type>
5995 chunk_view* _M_parent;
5998 value_type(chunk_view& __parent) noexcept
5999 : _M_parent(std::__addressof(__parent))
6005 constexpr _InnerIter
6006 begin() const noexcept
6007 { return _InnerIter(*_M_parent); }
6009 constexpr default_sentinel_t
6010 end() const noexcept
6011 { return default_sentinel; }
6015 requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
6017 return __detail::__to_unsigned_like
6018 (ranges::min(_M_parent->_M_remainder,
6019 ranges::end(_M_parent->_M_base) - *_M_parent->_M_current));
6024 requires input_range<_Vp>
6025 class chunk_view<_Vp>::_InnerIter
6027 chunk_view* _M_parent;
6030 _InnerIter(chunk_view& __parent) noexcept
6031 : _M_parent(std::__addressof(__parent))
6034 friend _OuterIter::value_type;
6037 using iterator_concept = input_iterator_tag;
6038 using difference_type = range_difference_t<_Vp>;
6039 using value_type = range_value_t<_Vp>;
6041 _InnerIter(_InnerIter&&) = default;
6042 _InnerIter& operator=(_InnerIter&&) = default;
6044 constexpr const iterator_t<_Vp>&
6046 { return *_M_parent->_M_current; }
6048 constexpr range_reference_t<_Vp>
6051 __glibcxx_assert(*this != default_sentinel);
6052 return **_M_parent->_M_current;
6055 constexpr _InnerIter&
6058 __glibcxx_assert(*this != default_sentinel);
6059 ++*_M_parent->_M_current;
6060 if (*_M_parent->_M_current == ranges::end(_M_parent->_M_base))
6061 _M_parent->_M_remainder = 0;
6063 --_M_parent->_M_remainder;
6071 friend constexpr bool
6072 operator==(const _InnerIter& __x, default_sentinel_t) noexcept
6073 { return __x._M_parent->_M_remainder == 0; }
6075 friend constexpr difference_type
6076 operator-(default_sentinel_t, const _InnerIter& __x)
6077 requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
6079 return ranges::min(__x._M_parent->_M_remainder,
6080 ranges::end(__x._M_parent->_M_base) - *__x._M_parent->_M_current);
6083 friend constexpr difference_type
6084 operator-(const _InnerIter& __x, default_sentinel_t __y)
6085 requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
6086 { return -(__y - __x); }
6090 requires forward_range<_Vp>
6091 class chunk_view<_Vp> : public view_interface<chunk_view<_Vp>>
6094 range_difference_t<_Vp> _M_n;
6095 template<bool> class _Iterator;
6099 chunk_view(_Vp __base, range_difference_t<_Vp> __n)
6100 : _M_base(std::move(__base)), _M_n(__n)
6101 { __glibcxx_assert(__n > 0); }
6104 base() const & requires copy_constructible<_Vp>
6109 { return std::move(_M_base); }
6112 begin() requires (!__detail::__simple_view<_Vp>)
6113 { return _Iterator<false>(this, ranges::begin(_M_base)); }
6116 begin() const requires forward_range<const _Vp>
6117 { return _Iterator<true>(this, ranges::begin(_M_base)); }
6120 end() requires (!__detail::__simple_view<_Vp>)
6122 if constexpr (common_range<_Vp> && sized_range<_Vp>)
6124 auto __missing = (_M_n - ranges::distance(_M_base) % _M_n) % _M_n;
6125 return _Iterator<false>(this, ranges::end(_M_base), __missing);
6127 else if constexpr (common_range<_Vp> && !bidirectional_range<_Vp>)
6128 return _Iterator<false>(this, ranges::end(_M_base));
6130 return default_sentinel;
6134 end() const requires forward_range<const _Vp>
6136 if constexpr (common_range<const _Vp> && sized_range<const _Vp>)
6138 auto __missing = (_M_n - ranges::distance(_M_base) % _M_n) % _M_n;
6139 return _Iterator<true>(this, ranges::end(_M_base), __missing);
6141 else if constexpr (common_range<const _Vp> && !bidirectional_range<const _Vp>)
6142 return _Iterator<true>(this, ranges::end(_M_base));
6144 return default_sentinel;
6148 size() requires sized_range<_Vp>
6150 return __detail::__to_unsigned_like(__detail::__div_ceil
6151 (ranges::distance(_M_base), _M_n));
6155 size() const requires sized_range<const _Vp>
6157 return __detail::__to_unsigned_like(__detail::__div_ceil
6158 (ranges::distance(_M_base), _M_n));
6162 template<typename _Vp>
6163 inline constexpr bool enable_borrowed_range<chunk_view<_Vp>>
6164 = forward_range<_Vp> && enable_borrowed_range<_Vp>;
6167 requires forward_range<_Vp>
6168 template<bool _Const>
6169 class chunk_view<_Vp>::_Iterator
6171 using _Parent = __detail::__maybe_const_t<_Const, chunk_view>;
6172 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
6174 iterator_t<_Base> _M_current = iterator_t<_Base>();
6175 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
6176 range_difference_t<_Base> _M_n = 0;
6177 range_difference_t<_Base> _M_missing = 0;
6180 _Iterator(_Parent* __parent, iterator_t<_Base> __current,
6181 range_difference_t<_Base> __missing = 0)
6182 : _M_current(__current), _M_end(ranges::end(__parent->_M_base)),
6183 _M_n(__parent->_M_n), _M_missing(__missing)
6189 if constexpr (random_access_range<_Base>)
6190 return random_access_iterator_tag{};
6191 else if constexpr (bidirectional_range<_Base>)
6192 return bidirectional_iterator_tag{};
6194 return forward_iterator_tag{};
6200 using iterator_category = input_iterator_tag;
6201 using iterator_concept = decltype(_S_iter_cat());
6202 using value_type = decltype(views::take(subrange(_M_current, _M_end), _M_n));
6203 using difference_type = range_difference_t<_Base>;
6205 _Iterator() = default;
6207 constexpr _Iterator(_Iterator<!_Const> __i)
6209 && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
6210 && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
6211 : _M_current(std::move(__i._M_current)), _M_end(std::move(__i._M_end)),
6212 _M_n(__i._M_n), _M_missing(__i._M_missing)
6215 constexpr iterator_t<_Base>
6217 { return _M_current; }
6219 constexpr value_type
6222 __glibcxx_assert(_M_current != _M_end);
6223 return views::take(subrange(_M_current, _M_end), _M_n);
6226 constexpr _Iterator&
6229 __glibcxx_assert(_M_current != _M_end);
6230 _M_missing = ranges::advance(_M_current, _M_n, _M_end);
6242 constexpr _Iterator&
6243 operator--() requires bidirectional_range<_Base>
6245 ranges::advance(_M_current, _M_missing - _M_n);
6251 operator--(int) requires bidirectional_range<_Base>
6258 constexpr _Iterator&
6259 operator+=(difference_type __x)
6260 requires random_access_range<_Base>
6264 __glibcxx_assert(ranges::distance(_M_current, _M_end) > _M_n * (__x - 1));
6265 _M_missing = ranges::advance(_M_current, _M_n * __x, _M_end);
6269 ranges::advance(_M_current, _M_n * __x + _M_missing);
6275 constexpr _Iterator&
6276 operator-=(difference_type __x)
6277 requires random_access_range<_Base>
6278 { return *this += -__x; }
6280 constexpr value_type
6281 operator[](difference_type __n) const
6282 requires random_access_range<_Base>
6283 { return *(*this + __n); }
6285 friend constexpr bool
6286 operator==(const _Iterator& __x, const _Iterator& __y)
6287 { return __x._M_current == __y._M_current; }
6289 friend constexpr bool
6290 operator==(const _Iterator& __x, default_sentinel_t)
6291 { return __x._M_current == __x._M_end; }
6293 friend constexpr bool
6294 operator<(const _Iterator& __x, const _Iterator& __y)
6295 requires random_access_range<_Base>
6296 { return __x._M_current > __y._M_current; }
6298 friend constexpr bool
6299 operator>(const _Iterator& __x, const _Iterator& __y)
6300 requires random_access_range<_Base>
6301 { return __y < __x; }
6303 friend constexpr bool
6304 operator<=(const _Iterator& __x, const _Iterator& __y)
6305 requires random_access_range<_Base>
6306 { return !(__y < __x); }
6308 friend constexpr bool
6309 operator>=(const _Iterator& __x, const _Iterator& __y)
6310 requires random_access_range<_Base>
6311 { return !(__x < __y); }
6313 friend constexpr auto
6314 operator<=>(const _Iterator& __x, const _Iterator& __y)
6315 requires random_access_range<_Base>
6316 && three_way_comparable<iterator_t<_Base>>
6317 { return __x._M_current <=> __y._M_current; }
6319 friend constexpr _Iterator
6320 operator+(const _Iterator& __i, difference_type __n)
6321 requires random_access_range<_Base>
6328 friend constexpr _Iterator
6329 operator+(difference_type __n, const _Iterator& __i)
6330 requires random_access_range<_Base>
6337 friend constexpr _Iterator
6338 operator-(const _Iterator& __i, difference_type __n)
6339 requires random_access_range<_Base>
6346 friend constexpr difference_type
6347 operator-(const _Iterator& __x, const _Iterator& __y)
6348 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
6350 return (__x._M_current - __y._M_current
6351 + __x._M_missing - __y._M_missing) / __x._M_n;
6354 friend constexpr difference_type
6355 operator-(default_sentinel_t __y, const _Iterator& __x)
6356 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
6357 { return __detail::__div_ceil(__x._M_end - __x._M_current, __x._M_n); }
6359 friend constexpr difference_type
6360 operator-(const _Iterator& __x, default_sentinel_t __y)
6361 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
6362 { return -(__y - __x); }
6369 template<typename _Range, typename _Dp>
6370 concept __can_chunk_view
6371 = requires { chunk_view(std::declval<_Range>(), std::declval<_Dp>()); };
6374 struct _Chunk : __adaptor::_RangeAdaptor<_Chunk>
6376 template<viewable_range _Range, typename _Dp = range_difference_t<_Range>>
6377 requires __detail::__can_chunk_view<_Range, _Dp>
6379 operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const
6380 { return chunk_view(std::forward<_Range>(__r), __n); }
6382 using __adaptor::_RangeAdaptor<_Chunk>::operator();
6383 static constexpr int _S_arity = 2;
6384 static constexpr bool _S_has_simple_extra_args = true;
6387 inline constexpr _Chunk chunk;
6390#define __cpp_lib_ranges_slide 202202L
6394 template<typename _Vp>
6395 concept __slide_caches_nothing = random_access_range<_Vp> && sized_range<_Vp>;
6397 template<typename _Vp>
6398 concept __slide_caches_last
6399 = !__slide_caches_nothing<_Vp> && bidirectional_range<_Vp> && common_range<_Vp>;
6401 template<typename _Vp>
6402 concept __slide_caches_first
6403 = !__slide_caches_nothing<_Vp> && !__slide_caches_last<_Vp>;
6406 template<forward_range _Vp>
6408 class slide_view : public view_interface<slide_view<_Vp>>
6411 range_difference_t<_Vp> _M_n;
6412 [[no_unique_address]]
6413 __detail::__maybe_present_t<__detail::__slide_caches_first<_Vp>,
6414 __detail::_CachedPosition<_Vp>> _M_cached_begin;
6415 [[no_unique_address]]
6416 __detail::__maybe_present_t<__detail::__slide_caches_last<_Vp>,
6417 __detail::_CachedPosition<_Vp>> _M_cached_end;
6419 template<bool> class _Iterator;
6424 slide_view(_Vp __base, range_difference_t<_Vp> __n)
6425 : _M_base(std::move(__base)), _M_n(__n)
6426 { __glibcxx_assert(__n > 0); }
6429 begin() requires (!(__detail::__simple_view<_Vp>
6430 && __detail::__slide_caches_nothing<const _Vp>))
6432 if constexpr (__detail::__slide_caches_first<_Vp>)
6434 iterator_t<_Vp> __it;
6435 if (_M_cached_begin._M_has_value())
6436 __it = _M_cached_begin._M_get(_M_base);
6439 __it = ranges::next(ranges::begin(_M_base), _M_n - 1, ranges::end(_M_base));
6440 _M_cached_begin._M_set(_M_base, __it);
6442 return _Iterator<false>(ranges::begin(_M_base), std::move(__it), _M_n);
6445 return _Iterator<false>(ranges::begin(_M_base), _M_n);
6449 begin() const requires __detail::__slide_caches_nothing<const _Vp>
6450 { return _Iterator<true>(ranges::begin(_M_base), _M_n); }
6453 end() requires (!(__detail::__simple_view<_Vp>
6454 && __detail::__slide_caches_nothing<const _Vp>))
6456 if constexpr (__detail::__slide_caches_nothing<_Vp>)
6457 return _Iterator<false>(ranges::begin(_M_base) + range_difference_t<_Vp>(size()),
6459 else if constexpr (__detail::__slide_caches_last<_Vp>)
6461 iterator_t<_Vp> __it;
6462 if (_M_cached_end._M_has_value())
6463 __it = _M_cached_end._M_get(_M_base);
6466 __it = ranges::prev(ranges::end(_M_base), _M_n - 1, ranges::begin(_M_base));
6467 _M_cached_end._M_set(_M_base, __it);
6469 return _Iterator<false>(std::move(__it), _M_n);
6471 else if constexpr (common_range<_Vp>)
6472 return _Iterator<false>(ranges::end(_M_base), ranges::end(_M_base), _M_n);
6474 return _Sentinel(ranges::end(_M_base));
6478 end() const requires __detail::__slide_caches_nothing<const _Vp>
6479 { return begin() + range_difference_t<const _Vp>(size()); }
6482 size() requires sized_range<_Vp>
6484 auto __sz = ranges::distance(_M_base) - _M_n + 1;
6487 return __detail::__to_unsigned_like(__sz);
6491 size() const requires sized_range<const _Vp>
6493 auto __sz = ranges::distance(_M_base) - _M_n + 1;
6496 return __detail::__to_unsigned_like(__sz);
6500 template<typename _Range>
6501 slide_view(_Range&&, range_difference_t<_Range>) -> slide_view<views::all_t<_Range>>;
6503 template<typename _Vp>
6504 inline constexpr bool enable_borrowed_range<slide_view<_Vp>>
6505 = enable_borrowed_range<_Vp>;
6507 template<forward_range _Vp>
6509 template<bool _Const>
6510 class slide_view<_Vp>::_Iterator
6512 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
6513 static constexpr bool _S_last_elt_present
6514 = __detail::__slide_caches_first<_Base>;
6516 iterator_t<_Base> _M_current = iterator_t<_Base>();
6517 [[no_unique_address]]
6518 __detail::__maybe_present_t<_S_last_elt_present, iterator_t<_Base>>
6519 _M_last_elt = decltype(_M_last_elt)();
6520 range_difference_t<_Base> _M_n = 0;
6523 _Iterator(iterator_t<_Base> __current, range_difference_t<_Base> __n)
6524 requires (!_S_last_elt_present)
6525 : _M_current(__current), _M_n(__n)
6529 _Iterator(iterator_t<_Base> __current, iterator_t<_Base> __last_elt,
6530 range_difference_t<_Base> __n)
6531 requires _S_last_elt_present
6532 : _M_current(__current), _M_last_elt(__last_elt), _M_n(__n)
6538 if constexpr (random_access_range<_Base>)
6539 return random_access_iterator_tag{};
6540 else if constexpr (bidirectional_range<_Base>)
6541 return bidirectional_iterator_tag{};
6543 return forward_iterator_tag{};
6547 friend slide_view::_Sentinel;
6550 using iterator_category = input_iterator_tag;
6551 using iterator_concept = decltype(_S_iter_concept());
6552 using value_type = decltype(views::counted(_M_current, _M_n));
6553 using difference_type = range_difference_t<_Base>;
6555 _Iterator() = default;
6558 _Iterator(_Iterator<!_Const> __i)
6559 requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
6560 : _M_current(std::move(__i._M_current)), _M_n(__i._M_n)
6565 { return views::counted(_M_current, _M_n); }
6567 constexpr _Iterator&
6571 if constexpr (_S_last_elt_present)
6584 constexpr _Iterator&
6585 operator--() requires bidirectional_range<_Base>
6588 if constexpr (_S_last_elt_present)
6594 operator--(int) requires bidirectional_range<_Base>
6601 constexpr _Iterator&
6602 operator+=(difference_type __x)
6603 requires random_access_range<_Base>
6606 if constexpr (_S_last_elt_present)
6611 constexpr _Iterator&
6612 operator-=(difference_type __x)
6613 requires random_access_range<_Base>
6616 if constexpr (_S_last_elt_present)
6622 operator[](difference_type __n) const
6623 requires random_access_range<_Base>
6624 { return views::counted(_M_current + __n, _M_n); }
6626 friend constexpr bool
6627 operator==(const _Iterator& __x, const _Iterator& __y)
6629 if constexpr (_S_last_elt_present)
6630 return __x._M_last_elt == __y._M_last_elt;
6632 return __x._M_current == __y._M_current;
6635 friend constexpr bool
6636 operator<(const _Iterator& __x, const _Iterator& __y)
6637 requires random_access_range<_Base>
6638 { return __x._M_current < __y._M_current; }
6640 friend constexpr bool
6641 operator>(const _Iterator& __x, const _Iterator& __y)
6642 requires random_access_range<_Base>
6643 { return __y < __x; }
6645 friend constexpr bool
6646 operator<=(const _Iterator& __x, const _Iterator& __y)
6647 requires random_access_range<_Base>
6648 { return !(__y < __x); }
6650 friend constexpr bool
6651 operator>=(const _Iterator& __x, const _Iterator& __y)
6652 requires random_access_range<_Base>
6653 { return !(__x < __y); }
6655 friend constexpr auto
6656 operator<=>(const _Iterator& __x, const _Iterator& __y)
6657 requires random_access_range<_Base>
6658 && three_way_comparable<iterator_t<_Base>>
6659 { return __x._M_current <=> __y._M_current; }
6661 friend constexpr _Iterator
6662 operator+(const _Iterator& __i, difference_type __n)
6663 requires random_access_range<_Base>
6670 friend constexpr _Iterator
6671 operator+(difference_type __n, const _Iterator& __i)
6672 requires random_access_range<_Base>
6679 friend constexpr _Iterator
6680 operator-(const _Iterator& __i, difference_type __n)
6681 requires random_access_range<_Base>
6688 friend constexpr difference_type
6689 operator-(const _Iterator& __x, const _Iterator& __y)
6690 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
6692 if constexpr (_S_last_elt_present)
6693 return __x._M_last_elt - __y._M_last_elt;
6695 return __x._M_current - __y._M_current;
6699 template<forward_range _Vp>
6701 class slide_view<_Vp>::_Sentinel
6703 sentinel_t<_Vp> _M_end = sentinel_t<_Vp>();
6706 _Sentinel(sentinel_t<_Vp> __end)
6713 _Sentinel() = default;
6715 friend constexpr bool
6716 operator==(const _Iterator<false>& __x, const _Sentinel& __y)
6717 { return __x._M_last_elt == __y._M_end; }
6719 friend constexpr range_difference_t<_Vp>
6720 operator-(const _Iterator<false>& __x, const _Sentinel& __y)
6721 requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
6722 { return __x._M_last_elt - __y._M_end; }
6724 friend constexpr range_difference_t<_Vp>
6725 operator-(const _Sentinel& __y, const _Iterator<false>& __x)
6726 requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
6727 { return __y._M_end -__x._M_last_elt; }
6734 template<typename _Range, typename _Dp>
6735 concept __can_slide_view
6736 = requires { slide_view(std::declval<_Range>(), std::declval<_Dp>()); };
6739 struct _Slide : __adaptor::_RangeAdaptor<_Slide>
6741 template<viewable_range _Range, typename _Dp = range_difference_t<_Range>>
6742 requires __detail::__can_slide_view<_Range, _Dp>
6744 operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const
6745 { return slide_view(std::forward<_Range>(__r), __n); }
6747 using __adaptor::_RangeAdaptor<_Slide>::operator();
6748 static constexpr int _S_arity = 2;
6749 static constexpr bool _S_has_simple_extra_args = true;
6752 inline constexpr _Slide slide;
6755#define __cpp_lib_ranges_chunk_by 202202L
6757 template<forward_range _Vp,
6758 indirect_binary_predicate<iterator_t<_Vp>, iterator_t<_Vp>> _Pred>
6759 requires view<_Vp> && is_object_v<_Pred>
6760 class chunk_by_view : public view_interface<chunk_by_view<_Vp, _Pred>>
6762 _Vp _M_base = _Vp();
6763 __detail::__box<_Pred> _M_pred;
6764 __detail::_CachedPosition<_Vp> _M_cached_begin;
6766 constexpr iterator_t<_Vp>
6767 _M_find_next(iterator_t<_Vp> __current)
6769 __glibcxx_assert(_M_pred.has_value());
6770 auto __pred = [this]<typename _Tp, typename _Up>(_Tp&& __x, _Up&& __y) {
6771 return !bool((*_M_pred)(std::forward<_Tp>(__x), std::forward<_Up>(__y)));
6773 auto __it = ranges::adjacent_find(__current, ranges::end(_M_base), __pred);
6774 return ranges::next(__it, 1, ranges::end(_M_base));
6777 constexpr iterator_t<_Vp>
6778 _M_find_prev(iterator_t<_Vp> __current) requires bidirectional_range<_Vp>
6780 __glibcxx_assert(_M_pred.has_value());
6781 auto __pred = [this]<typename _Tp, typename _Up>(_Tp&& __x, _Up&& __y) {
6782 return !bool((*_M_pred)(std::forward<_Up>(__y), std::forward<_Tp>(__x)));
6784 auto __rbegin = std::make_reverse_iterator(__current);
6785 auto __rend = std::make_reverse_iterator(ranges::begin(_M_base));
6786 __glibcxx_assert(__rbegin != __rend);
6787 auto __it = ranges::adjacent_find(__rbegin, __rend, __pred).base();
6788 return ranges::prev(__it, 1, ranges::begin(_M_base));
6794 chunk_by_view() requires (default_initializable<_Vp>
6795 && default_initializable<_Pred>)
6799 chunk_by_view(_Vp __base, _Pred __pred)
6800 : _M_base(std::move(__base)), _M_pred(std::move(__pred))
6804 base() const & requires copy_constructible<_Vp>
6809 { return std::move(_M_base); }
6811 constexpr const _Pred&
6813 { return *_M_pred; }
6818 __glibcxx_assert(_M_pred.has_value());
6819 iterator_t<_Vp> __it;
6820 if (_M_cached_begin._M_has_value())
6821 __it = _M_cached_begin._M_get(_M_base);
6824 __it = _M_find_next(ranges::begin(_M_base));
6825 _M_cached_begin._M_set(_M_base, __it);
6827 return _Iterator(*this, ranges::begin(_M_base), __it);
6833 if constexpr (common_range<_Vp>)
6834 return _Iterator(*this, ranges::end(_M_base), ranges::end(_M_base));
6836 return default_sentinel;
6840 template<typename _Range, typename _Pred>
6841 chunk_by_view(_Range&&, _Pred) -> chunk_by_view<views::all_t<_Range>, _Pred>;
6843 template<forward_range _Vp,
6844 indirect_binary_predicate<iterator_t<_Vp>, iterator_t<_Vp>> _Pred>
6845 requires view<_Vp> && is_object_v<_Pred>
6846 class chunk_by_view<_Vp, _Pred>::_Iterator
6848 chunk_by_view* _M_parent = nullptr;
6849 iterator_t<_Vp> _M_current = iterator_t<_Vp>();
6850 iterator_t<_Vp> _M_next = iterator_t<_Vp>();
6853 _Iterator(chunk_by_view& __parent, iterator_t<_Vp> __current, iterator_t<_Vp> __next)
6854 : _M_parent(std::__addressof(__parent)), _M_current(__current), _M_next(__next)
6860 if constexpr (bidirectional_range<_Vp>)
6861 return bidirectional_iterator_tag{};
6863 return forward_iterator_tag{};
6866 friend chunk_by_view;
6869 using value_type = subrange<iterator_t<_Vp>>;
6870 using difference_type = range_difference_t<_Vp>;
6871 using iterator_category = input_iterator_tag;
6872 using iterator_concept = decltype(_S_iter_concept());
6874 _Iterator() = default;
6876 constexpr value_type
6879 __glibcxx_assert(_M_current != _M_next);
6880 return ranges::subrange(_M_current, _M_next);
6883 constexpr _Iterator&
6886 __glibcxx_assert(_M_current != _M_next);
6887 _M_current = _M_next;
6888 _M_next = _M_parent->_M_find_next(_M_current);
6900 constexpr _Iterator&
6901 operator--() requires bidirectional_range<_Vp>
6903 _M_next = _M_current;
6904 _M_current = _M_parent->_M_find_prev(_M_next);
6909 operator--(int) requires bidirectional_range<_Vp>
6916 friend constexpr bool
6917 operator==(const _Iterator& __x, const _Iterator& __y)
6918 { return __x._M_current == __y._M_current; }
6920 friend constexpr bool
6921 operator==(const _Iterator& __x, default_sentinel_t)
6922 { return __x._M_current == __x._M_next; }
6929 template<typename _Range, typename _Pred>
6930 concept __can_chunk_by_view
6931 = requires { chunk_by_view(std::declval<_Range>(), std::declval<_Pred>()); };
6934 struct _ChunkBy : __adaptor::_RangeAdaptor<_ChunkBy>
6936 template<viewable_range _Range, typename _Pred>
6937 requires __detail::__can_chunk_by_view<_Range, _Pred>
6939 operator() [[nodiscard]] (_Range&& __r, _Pred&& __pred) const
6940 { return chunk_by_view(std::forward<_Range>(__r), std::forward<_Pred>(__pred)); }
6942 using __adaptor::_RangeAdaptor<_ChunkBy>::operator();
6943 static constexpr int _S_arity = 2;
6944 static constexpr bool _S_has_simple_extra_args = true;
6947 inline constexpr _ChunkBy chunk_by;
6950#define __cpp_lib_ranges_join_with 202202L
6954 template<typename _Range, typename _Pattern>
6955 concept __compatible_joinable_ranges
6956 = common_with<range_value_t<_Range>, range_value_t<_Pattern>>
6957 && common_reference_with<range_reference_t<_Range>,
6958 range_reference_t<_Pattern>>
6959 && common_reference_with<range_rvalue_reference_t<_Range>,
6960 range_rvalue_reference_t<_Pattern>>;
6962 template<typename _Range>
6963 concept __bidirectional_common = bidirectional_range<_Range> && common_range<_Range>;
6966 template<input_range _Vp, forward_range _Pattern>
6967 requires view<_Vp> && view<_Pattern>
6968 && input_range<range_reference_t<_Vp>>
6969 && __detail::__compatible_joinable_ranges<range_reference_t<_Vp>, _Pattern>
6970 class join_with_view : public view_interface<join_with_view<_Vp, _Pattern>>
6972 using _InnerRange = range_reference_t<_Vp>;
6974 _Vp _M_base = _Vp();
6975 __detail::__non_propagating_cache<remove_cv_t<_InnerRange>> _M_inner;
6976 _Pattern _M_pattern = _Pattern();
6978 template<bool _Const> using _Base = __detail::__maybe_const_t<_Const, _Vp>;
6979 template<bool _Const> using _InnerBase = range_reference_t<_Base<_Const>>;
6980 template<bool _Const> using _PatternBase = __detail::__maybe_const_t<_Const, _Pattern>;
6982 template<bool _Const> using _OuterIter = iterator_t<_Base<_Const>>;
6983 template<bool _Const> using _InnerIter = iterator_t<_InnerBase<_Const>>;
6984 template<bool _Const> using _PatternIter = iterator_t<_PatternBase<_Const>>;
6986 template<bool _Const>
6987 static constexpr bool _S_ref_is_glvalue = is_reference_v<_InnerBase<_Const>>;
6989 template<bool _Const>
6993 template<bool _Const>
6994 requires _S_ref_is_glvalue<_Const>
6995 && forward_range<_Base<_Const>>
6996 && forward_range<_InnerBase<_Const>>
6997 struct __iter_cat<_Const>
7003 using _OuterIter = join_with_view::_OuterIter<_Const>;
7004 using _InnerIter = join_with_view::_InnerIter<_Const>;
7005 using _PatternIter = join_with_view::_PatternIter<_Const>;
7006 using _OuterCat = typename iterator_traits<_OuterIter>::iterator_category;
7007 using _InnerCat = typename iterator_traits<_InnerIter>::iterator_category;
7008 using _PatternCat = typename iterator_traits<_PatternIter>::iterator_category;
7009 if constexpr (!is_lvalue_reference_v<common_reference_t<iter_reference_t<_InnerIter>,
7010 iter_reference_t<_PatternIter>>>)
7011 return input_iterator_tag{};
7012 else if constexpr (derived_from<_OuterCat, bidirectional_iterator_tag>
7013 && derived_from<_InnerCat, bidirectional_iterator_tag>
7014 && derived_from<_PatternCat, bidirectional_iterator_tag>
7015 && common_range<_InnerBase<_Const>>
7016 && common_range<_PatternBase<_Const>>)
7017 return bidirectional_iterator_tag{};
7018 else if constexpr (derived_from<_OuterCat, forward_iterator_tag>
7019 && derived_from<_InnerCat, forward_iterator_tag>
7020 && derived_from<_PatternCat, forward_iterator_tag>)
7021 return forward_iterator_tag{};
7023 return input_iterator_tag{};
7026 using iterator_category = decltype(_S_iter_cat());
7029 template<bool> struct _Iterator;
7030 template<bool> struct _Sentinel;
7033 join_with_view() requires (default_initializable<_Vp>
7034 && default_initializable<_Pattern>)
7038 join_with_view(_Vp __base, _Pattern __pattern)
7039 : _M_base(std::move(__base)), _M_pattern(std::move(__pattern))
7042 template<input_range _Range>
7043 requires constructible_from<_Vp, views::all_t<_Range>>
7044 && constructible_from<_Pattern, single_view<range_value_t<_InnerRange>>>
7046 join_with_view(_Range&& __r, range_value_t<_InnerRange> __e)
7047 : _M_base(views::all(std::forward<_Range>(__r))),
7048 _M_pattern(views::single(std::move(__e)))
7052 base() const& requires copy_constructible<_Vp>
7057 { return std::move(_M_base); }
7062 constexpr bool __use_const = is_reference_v<_InnerRange>
7063 && __detail::__simple_view<_Vp> && __detail::__simple_view<_Pattern>;
7064 return _Iterator<__use_const>{*this, ranges::begin(_M_base)};
7069 requires input_range<const _Vp>
7070 && forward_range<const _Pattern>
7071 && is_reference_v<range_reference_t<const _Vp>>
7072 { return _Iterator<true>{*this, ranges::begin(_M_base)}; }
7077 constexpr bool __use_const
7078 = __detail::__simple_view<_Vp> && __detail::__simple_view<_Pattern>;
7079 if constexpr (is_reference_v<_InnerRange>
7080 && forward_range<_Vp> && common_range<_Vp>
7081 && forward_range<_InnerRange> && common_range<_InnerRange>)
7082 return _Iterator<__use_const>{*this, ranges::end(_M_base)};
7084 return _Sentinel<__use_const>{*this};
7089 requires input_range<const _Vp>
7090 && forward_range<const _Pattern>
7091 && is_reference_v<range_reference_t<const _Vp>>
7093 using _InnerConstRange = range_reference_t<const _Vp>;
7094 if constexpr (forward_range<const _Vp>
7095 && forward_range<_InnerConstRange>
7096 && common_range<const _Vp>
7097 && common_range<_InnerConstRange>)
7098 return _Iterator<true>{*this, ranges::end(_M_base)};
7100 return _Sentinel<true>{*this};
7104 template<typename _Range, typename _Pattern>
7105 join_with_view(_Range&&, _Pattern&&)
7106 -> join_with_view<views::all_t<_Range>, views::all_t<_Pattern>>;
7108 template<input_range _Range>
7109 join_with_view(_Range&&, range_value_t<range_reference_t<_Range>>)
7110 -> join_with_view<views::all_t<_Range>,
7111 single_view<range_value_t<range_reference_t<_Range>>>>;
7113 template<input_range _Vp, forward_range _Pattern>
7114 requires view<_Vp> && view<_Pattern>
7115 && input_range<range_reference_t<_Vp>>
7116 && __detail::__compatible_joinable_ranges<range_reference_t<_Vp>, _Pattern>
7117 template<bool _Const>
7118 class join_with_view<_Vp, _Pattern>::_Iterator : public __iter_cat<_Const>
7120 using _Parent = __detail::__maybe_const_t<_Const, join_with_view>;
7121 using _Base = join_with_view::_Base<_Const>;
7122 using _InnerBase = join_with_view::_InnerBase<_Const>;
7123 using _PatternBase = join_with_view::_PatternBase<_Const>;
7125 using _OuterIter = join_with_view::_OuterIter<_Const>;
7126 using _InnerIter = join_with_view::_InnerIter<_Const>;
7127 using _PatternIter = join_with_view::_PatternIter<_Const>;
7129 static constexpr bool _S_ref_is_glvalue = join_with_view::_S_ref_is_glvalue<_Const>;
7131 _Parent* _M_parent = nullptr;
7132 _OuterIter _M_outer_it = _OuterIter();
7133 variant<_PatternIter, _InnerIter> _M_inner_it;
7136 _Iterator(_Parent& __parent, iterator_t<_Base> __outer)
7137 : _M_parent(std::__addressof(__parent)), _M_outer_it(std::move(__outer))
7139 if (_M_outer_it != ranges::end(_M_parent->_M_base))
7141 auto&& __inner = _M_update_inner(_M_outer_it);
7142 _M_inner_it.template emplace<1>(ranges::begin(__inner));
7148 _M_update_inner(const _OuterIter& __x)
7150 if constexpr (_S_ref_is_glvalue)
7153 return _M_parent->_M_inner._M_emplace_deref(__x);
7157 _M_get_inner(const _OuterIter& __x)
7159 if constexpr (_S_ref_is_glvalue)
7162 return *_M_parent->_M_inner;
7170 if (_M_inner_it.index() == 0)
7172 if (std::get<0>(_M_inner_it) != ranges::end(_M_parent->_M_pattern))
7175 auto&& __inner = _M_update_inner(_M_outer_it);
7176 _M_inner_it.template emplace<1>(ranges::begin(__inner));
7180 auto&& __inner = _M_get_inner(_M_outer_it);
7181 if (std::get<1>(_M_inner_it) != ranges::end(__inner))
7184 if (++_M_outer_it == ranges::end(_M_parent->_M_base))
7186 if constexpr (_S_ref_is_glvalue)
7187 _M_inner_it.template emplace<0>();
7191 _M_inner_it.template emplace<0>(ranges::begin(_M_parent->_M_pattern));
7199 if constexpr (_S_ref_is_glvalue
7200 && bidirectional_range<_Base>
7201 && __detail::__bidirectional_common<_InnerBase>
7202 && __detail::__bidirectional_common<_PatternBase>)
7203 return bidirectional_iterator_tag{};
7204 else if constexpr (_S_ref_is_glvalue
7205 && forward_range<_Base>
7206 && forward_range<_InnerBase>)
7207 return forward_iterator_tag{};
7209 return input_iterator_tag{};
7212 friend join_with_view;
7215 using iterator_concept = decltype(_S_iter_concept());
7216 // iterator_category defined in join_with_view::__iter_cat
7217 using value_type = common_type_t<iter_value_t<_InnerIter>,
7218 iter_value_t<_PatternIter>>;
7219 using difference_type = common_type_t<iter_difference_t<_OuterIter>,
7220 iter_difference_t<_InnerIter>,
7221 iter_difference_t<_PatternIter>>;
7223 _Iterator() requires default_initializable<_OuterIter> = default;
7226 _Iterator(_Iterator<!_Const> __i)
7228 && convertible_to<iterator_t<_Vp>, _OuterIter>
7229 && convertible_to<iterator_t<_InnerRange>, _InnerIter>
7230 && convertible_to<iterator_t<_Pattern>, _PatternIter>
7231 : _M_parent(__i._M_parent),
7232 _M_outer_it(std::move(__i._M_outer_it))
7234 if (__i._M_inner_it.index() == 0)
7235 _M_inner_it.template emplace<0>(std::get<0>(std::move(__i._M_inner_it)));
7237 _M_inner_it.template emplace<1>(std::get<1>(std::move(__i._M_inner_it)));
7240 constexpr common_reference_t<iter_reference_t<_InnerIter>,
7241 iter_reference_t<_PatternIter>>
7244 if (_M_inner_it.index() == 0)
7245 return *std::get<0>(_M_inner_it);
7247 return *std::get<1>(_M_inner_it);
7250 constexpr _Iterator&
7253 if (_M_inner_it.index() == 0)
7254 ++std::get<0>(_M_inner_it);
7256 ++std::get<1>(_M_inner_it);
7267 requires _S_ref_is_glvalue
7268 && forward_iterator<_OuterIter> && forward_iterator<_InnerIter>
7270 _Iterator __tmp = *this;
7275 constexpr _Iterator&
7277 requires _S_ref_is_glvalue
7278 && bidirectional_range<_Base>
7279 && __detail::__bidirectional_common<_InnerBase>
7280 && __detail::__bidirectional_common<_PatternBase>
7282 if (_M_outer_it == ranges::end(_M_parent->_M_base))
7284 auto&& __inner = *--_M_outer_it;
7285 _M_inner_it.template emplace<1>(ranges::end(__inner));
7290 if (_M_inner_it.index() == 0)
7292 auto& __it = std::get<0>(_M_inner_it);
7293 if (__it == ranges::begin(_M_parent->_M_pattern))
7295 auto&& __inner = *--_M_outer_it;
7296 _M_inner_it.template emplace<1>(ranges::end(__inner));
7303 auto& __it = std::get<1>(_M_inner_it);
7304 auto&& __inner = *_M_outer_it;
7305 if (__it == ranges::begin(__inner))
7306 _M_inner_it.template emplace<0>(ranges::end(_M_parent->_M_pattern));
7312 if (_M_inner_it.index() == 0)
7313 --std::get<0>(_M_inner_it);
7315 --std::get<1>(_M_inner_it);
7321 requires _S_ref_is_glvalue && bidirectional_range<_Base>
7322 && __detail::__bidirectional_common<_InnerBase>
7323 && __detail::__bidirectional_common<_PatternBase>
7325 _Iterator __tmp = *this;
7330 friend constexpr bool
7331 operator==(const _Iterator& __x, const _Iterator& __y)
7332 requires _S_ref_is_glvalue
7333 && equality_comparable<_OuterIter> && equality_comparable<_InnerIter>
7334 { return __x._M_outer_it == __y._M_outer_it && __x._M_inner_it ==__y._M_inner_it; }
7336 friend constexpr common_reference_t<iter_rvalue_reference_t<_InnerIter>,
7337 iter_rvalue_reference_t<_PatternIter>>
7338 iter_move(const _Iterator& __x)
7340 if (__x._M_inner_it.index() == 0)
7341 return ranges::iter_move(std::get<0>(__x._M_inner_it));
7343 return ranges::iter_move(std::get<1>(__x._M_inner_it));
7346 friend constexpr void
7347 iter_swap(const _Iterator& __x, const _Iterator& __y)
7348 requires indirectly_swappable<_InnerIter, _PatternIter>
7350 if (__x._M_inner_it.index() == 0)
7352 if (__y._M_inner_it.index() == 0)
7353 ranges::iter_swap(std::get<0>(__x._M_inner_it), std::get<0>(__y._M_inner_it));
7355 ranges::iter_swap(std::get<0>(__x._M_inner_it), std::get<1>(__y._M_inner_it));
7359 if (__y._M_inner_it.index() == 0)
7360 ranges::iter_swap(std::get<1>(__x._M_inner_it), std::get<0>(__y._M_inner_it));
7362 ranges::iter_swap(std::get<1>(__x._M_inner_it), std::get<1>(__y._M_inner_it));
7367 template<input_range _Vp, forward_range _Pattern>
7368 requires view<_Vp> && view<_Pattern>
7369 && input_range<range_reference_t<_Vp>>
7370 && __detail::__compatible_joinable_ranges<range_reference_t<_Vp>, _Pattern>
7371 template<bool _Const>
7372 class join_with_view<_Vp, _Pattern>::_Sentinel
7374 using _Parent = __detail::__maybe_const_t<_Const, join_with_view>;
7375 using _Base = join_with_view::_Base<_Const>;
7377 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
7380 _Sentinel(_Parent& __parent)
7381 : _M_end(ranges::end(__parent._M_base))
7384 friend join_with_view;
7387 _Sentinel() = default;
7390 _Sentinel(_Sentinel<!_Const> __s)
7391 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
7392 : _M_end(std::move(__s._M_end))
7395 template<bool _OtherConst>
7396 requires sentinel_for<sentinel_t<_Base>,
7397 iterator_t<__detail::__maybe_const_t<_OtherConst, _Vp>>>
7398 friend constexpr bool
7399 operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y)
7400 { return __x._M_outer_it == __y._M_end; }
7407 template<typename _Range, typename _Pattern>
7408 concept __can_join_with_view
7409 = requires { join_with_view(std::declval<_Range>(), std::declval<_Pattern>()); };
7410 } // namespace __detail
7412 struct _JoinWith : __adaptor::_RangeAdaptor<_JoinWith>
7414 template<viewable_range _Range, typename _Pattern>
7415 requires __detail::__can_join_with_view<_Range, _Pattern>
7417 operator() [[nodiscard]] (_Range&& __r, _Pattern&& __f) const
7419 return join_with_view(std::forward<_Range>(__r), std::forward<_Pattern>(__f));
7422 using _RangeAdaptor<_JoinWith>::operator();
7423 static constexpr int _S_arity = 2;
7424 template<typename _Pattern>
7425 static constexpr bool _S_has_simple_extra_args
7426 = _LazySplit::_S_has_simple_extra_args<_Pattern>;
7429 inline constexpr _JoinWith join_with;
7430 } // namespace views
7432#define __cpp_lib_ranges_repeat 202207L
7434 template<copy_constructible _Tp, semiregular _Bound = unreachable_sentinel_t>
7435 requires is_object_v<_Tp> && same_as<_Tp, remove_cv_t<_Tp>>
7436 && (__detail::__is_integer_like<_Bound> || same_as<_Bound, unreachable_sentinel_t>)
7437 class repeat_view : public view_interface<repeat_view<_Tp, _Bound>>
7439 __detail::__box<_Tp> _M_value;
7440 [[no_unique_address]] _Bound _M_bound = _Bound();
7444 template<typename _Range>
7445 friend constexpr auto
7446 views::__detail::__take_of_repeat_view(_Range&&, range_difference_t<_Range>);
7448 template<typename _Range>
7449 friend constexpr auto
7450 views::__detail::__drop_of_repeat_view(_Range&&, range_difference_t<_Range>);
7453 repeat_view() requires default_initializable<_Tp> = default;
7456 repeat_view(const _Tp& __value, _Bound __bound = _Bound())
7457 : _M_value(__value), _M_bound(__bound)
7459 if constexpr (!same_as<_Bound, unreachable_sentinel_t>)
7460 __glibcxx_assert(__bound >= 0);
7464 repeat_view(_Tp&& __value, _Bound __bound = _Bound())
7465 : _M_value(std::move(__value)), _M_bound(__bound)
7468 template<typename... _Args, typename... _BoundArgs>
7469 requires constructible_from<_Tp, _Args...>
7470 && constructible_from<_Bound, _BoundArgs...>
7472 repeat_view(piecewise_construct_t,
7473 tuple<_Args...> __args,
7474 tuple<_BoundArgs...> __bound_args = tuple<>{})
7475 : _M_value(std::make_from_tuple<_Tp>(std::move(__args))),
7476 _M_bound(std::make_from_tuple<_Bound>(std::move(__bound_args)))
7481 { return _Iterator(std::__addressof(*_M_value)); }
7484 end() const requires (!same_as<_Bound, unreachable_sentinel_t>)
7485 { return _Iterator(std::__addressof(*_M_value), _M_bound); }
7487 constexpr unreachable_sentinel_t
7488 end() const noexcept
7489 { return unreachable_sentinel; }
7492 size() const requires (!same_as<_Bound, unreachable_sentinel_t>)
7493 { return __detail::__to_unsigned_like(_M_bound); }
7496 template<typename _Tp, typename _Bound>
7497 repeat_view(_Tp, _Bound) -> repeat_view<_Tp, _Bound>;
7499 template<copy_constructible _Tp, semiregular _Bound>
7500 requires is_object_v<_Tp> && same_as<_Tp, remove_cv_t<_Tp>>
7501 && (__detail::__is_integer_like<_Bound> || same_as<_Bound, unreachable_sentinel_t>)
7502 class repeat_view<_Tp, _Bound>::_Iterator
7505 = __conditional_t<same_as<_Bound, unreachable_sentinel_t>, ptrdiff_t, _Bound>;
7507 const _Tp* _M_value = nullptr;
7508 __index_type _M_current = __index_type();
7511 _Iterator(const _Tp* __value, __index_type __bound = __index_type())
7512 : _M_value(__value), _M_current(__bound)
7514 if constexpr (!same_as<_Bound, unreachable_sentinel_t>)
7515 __glibcxx_assert(__bound >= 0);
7521 using iterator_concept = random_access_iterator_tag;
7522 using iterator_category = random_access_iterator_tag;
7523 using value_type = _Tp;
7524 using difference_type = __conditional_t<__detail::__is_signed_integer_like<__index_type>,
7526 __detail::__iota_diff_t<__index_type>>;
7528 _Iterator() = default;
7530 constexpr const _Tp&
7531 operator*() const noexcept
7532 { return *_M_value; }
7534 constexpr _Iterator&
7549 constexpr _Iterator&
7552 if constexpr (!same_as<_Bound, unreachable_sentinel_t>)
7553 __glibcxx_assert(_M_current > 0);
7566 constexpr _Iterator&
7567 operator+=(difference_type __n)
7569 if constexpr (!same_as<_Bound, unreachable_sentinel_t>)
7570 __glibcxx_assert(_M_current + __n >= 0);
7575 constexpr _Iterator&
7576 operator-=(difference_type __n)
7578 if constexpr (!same_as<_Bound, unreachable_sentinel_t>)
7579 __glibcxx_assert(_M_current - __n >= 0);
7584 constexpr const _Tp&
7585 operator[](difference_type __n) const noexcept
7586 { return *(*this + __n); }
7588 friend constexpr bool
7589 operator==(const _Iterator& __x, const _Iterator& __y)
7590 { return __x._M_current == __y._M_current; }
7592 friend constexpr auto
7593 operator<=>(const _Iterator& __x, const _Iterator& __y)
7594 { return __x._M_current <=> __y._M_current; }
7596 friend constexpr _Iterator
7597 operator+(_Iterator __i, difference_type __n)
7603 friend constexpr _Iterator
7604 operator+(difference_type __n, _Iterator __i)
7605 { return __i + __n; }
7607 friend constexpr _Iterator
7608 operator-(_Iterator __i, difference_type __n)
7614 friend constexpr difference_type
7615 operator-(const _Iterator& __x, const _Iterator& __y)
7617 return (static_cast<difference_type>(__x._M_current)
7618 - static_cast<difference_type>(__y._M_current));
7626 template<typename _Tp, typename _Bound>
7627 inline constexpr bool __is_repeat_view<repeat_view<_Tp, _Bound>> = true;
7629 template<typename _Tp>
7630 concept __can_repeat_view
7631 = requires { repeat_view(std::declval<_Tp>()); };
7633 template<typename _Tp, typename _Bound>
7634 concept __can_bounded_repeat_view
7635 = requires { repeat_view(std::declval<_Tp>(), std::declval<_Bound>()); };
7640 template<typename _Tp>
7641 requires __detail::__can_repeat_view<_Tp>
7643 operator() [[nodiscard]] (_Tp&& __value) const
7644 { return repeat_view(std::forward<_Tp>(__value)); }
7646 template<typename _Tp, typename _Bound>
7647 requires __detail::__can_bounded_repeat_view<_Tp, _Bound>
7649 operator() [[nodiscard]] (_Tp&& __value, _Bound __bound) const
7650 { return repeat_view(std::forward<_Tp>(__value), __bound); }
7653 inline constexpr _Repeat repeat;
7657 template<typename _Range>
7659 __take_of_repeat_view(_Range&& __r, range_difference_t<_Range> __n)
7661 using _Tp = remove_cvref_t<_Range>;
7662 static_assert(__is_repeat_view<_Tp>);
7663 if constexpr (sized_range<_Tp>)
7664 return views::repeat(*__r._M_value, std::min(ranges::distance(__r), __n));
7666 return views::repeat(*__r._M_value, __n);
7669 template<typename _Range>
7671 __drop_of_repeat_view(_Range&& __r, range_difference_t<_Range> __n)
7673 using _Tp = remove_cvref_t<_Range>;
7674 static_assert(__is_repeat_view<_Tp>);
7675 if constexpr (sized_range<_Tp>)
7677 auto __sz = ranges::distance(__r);
7678 return views::repeat(*__r._M_value, __sz - std::min(__sz, __n));
7686#define __cpp_lib_ranges_stride 202207L
7688 template<input_range _Vp>
7690 class stride_view : public view_interface<stride_view<_Vp>>
7693 range_difference_t<_Vp> _M_stride;
7695 template<bool _Const> using _Base = __detail::__maybe_const_t<_Const, _Vp>;
7697 template<bool _Const>
7701 template<bool _Const>
7702 requires forward_range<_Base<_Const>>
7703 struct __iter_cat<_Const>
7709 using _Cat = typename iterator_traits<iterator_t<_Base<_Const>>>::iterator_category;
7710 if constexpr (derived_from<_Cat, random_access_iterator_tag>)
7711 return random_access_iterator_tag{};
7716 using iterator_category = decltype(_S_iter_cat());
7719 template<bool> class _Iterator;
7723 stride_view(_Vp __base, range_difference_t<_Vp> __stride)
7724 : _M_base(std::move(__base)), _M_stride(__stride)
7725 { __glibcxx_assert(__stride > 0); }
7728 base() const& requires copy_constructible<_Vp>
7733 { return std::move(_M_base); }
7735 constexpr range_difference_t<_Vp>
7736 stride() const noexcept
7737 { return _M_stride; }
7740 begin() requires (!__detail::__simple_view<_Vp>)
7741 { return _Iterator<false>(this, ranges::begin(_M_base)); }
7744 begin() const requires range<const _Vp>
7745 { return _Iterator<true>(this, ranges::begin(_M_base)); }
7748 end() requires (!__detail::__simple_view<_Vp>)
7750 if constexpr (common_range<_Vp> && sized_range<_Vp> && forward_range<_Vp>)
7752 auto __missing = (_M_stride - ranges::distance(_M_base) % _M_stride) % _M_stride;
7753 return _Iterator<false>(this, ranges::end(_M_base), __missing);
7755 else if constexpr (common_range<_Vp> && !bidirectional_range<_Vp>)
7756 return _Iterator<false>(this, ranges::end(_M_base));
7758 return default_sentinel;
7762 end() const requires range<const _Vp>
7764 if constexpr (common_range<const _Vp> && sized_range<const _Vp>
7765 && forward_range<const _Vp>)
7767 auto __missing = (_M_stride - ranges::distance(_M_base) % _M_stride) % _M_stride;
7768 return _Iterator<true>(this, ranges::end(_M_base), __missing);
7770 else if constexpr (common_range<const _Vp> && !bidirectional_range<const _Vp>)
7771 return _Iterator<true>(this, ranges::end(_M_base));
7773 return default_sentinel;
7777 size() requires sized_range<_Vp>
7779 return __detail::__to_unsigned_like
7780 (__detail::__div_ceil(ranges::distance(_M_base), _M_stride));
7784 size() const requires sized_range<const _Vp>
7786 return __detail::__to_unsigned_like
7787 (__detail::__div_ceil(ranges::distance(_M_base), _M_stride));
7791 template<typename _Range>
7792 stride_view(_Range&&, range_difference_t<_Range>) -> stride_view<views::all_t<_Range>>;
7794 template<typename _Vp>
7795 inline constexpr bool enable_borrowed_range<stride_view<_Vp>>
7796 = enable_borrowed_range<_Vp>;
7798 template<input_range _Vp>
7800 template<bool _Const>
7801 class stride_view<_Vp>::_Iterator : public __iter_cat<_Const>
7803 using _Parent = __detail::__maybe_const_t<_Const, stride_view>;
7804 using _Base = stride_view::_Base<_Const>;
7806 iterator_t<_Base> _M_current = iterator_t<_Base>();
7807 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
7808 range_difference_t<_Base> _M_stride = 0;
7809 range_difference_t<_Base> _M_missing = 0;
7812 _Iterator(_Parent* __parent, iterator_t<_Base> __current,
7813 range_difference_t<_Base> __missing = 0)
7814 : _M_current(std::move(__current)), _M_end(ranges::end(__parent->_M_base)),
7815 _M_stride(__parent->_M_stride), _M_missing(__missing)
7821 if constexpr (random_access_range<_Base>)
7822 return random_access_iterator_tag{};
7823 else if constexpr (bidirectional_range<_Base>)
7824 return bidirectional_iterator_tag{};
7825 else if constexpr (forward_range<_Base>)
7826 return forward_iterator_tag{};
7828 return input_iterator_tag{};
7834 using difference_type = range_difference_t<_Base>;
7835 using value_type = range_value_t<_Base>;
7836 using iterator_concept = decltype(_S_iter_concept());
7837 // iterator_category defined in stride_view::__iter_cat
7839 _Iterator() requires default_initializable<iterator_t<_Base>> = default;
7842 _Iterator(_Iterator<!_Const> __other)
7844 && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
7845 && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
7846 : _M_current(std::move(__other._M_current)), _M_end(std::move(__other._M_end)),
7847 _M_stride(__other._M_stride), _M_missing(__other._M_missing)
7850 constexpr iterator_t<_Base>
7852 { return std::move(_M_current); }
7854 constexpr const iterator_t<_Base>&
7855 base() const & noexcept
7856 { return _M_current; }
7858 constexpr decltype(auto)
7860 { return *_M_current; }
7862 constexpr _Iterator&
7865 __glibcxx_assert(_M_current != _M_end);
7866 _M_missing = ranges::advance(_M_current, _M_stride, _M_end);
7875 operator++(int) requires forward_range<_Base>
7882 constexpr _Iterator&
7883 operator--() requires bidirectional_range<_Base>
7885 ranges::advance(_M_current, _M_missing - _M_stride);
7891 operator--(int) requires bidirectional_range<_Base>
7898 constexpr _Iterator&
7899 operator+=(difference_type __n) requires random_access_range<_Base>
7903 __glibcxx_assert(ranges::distance(_M_current, _M_end) > _M_stride * (__n - 1));
7904 _M_missing = ranges::advance(_M_current, _M_stride * __n, _M_end);
7908 ranges::advance(_M_current, _M_stride * __n + _M_missing);
7914 constexpr _Iterator&
7915 operator-=(difference_type __n) requires random_access_range<_Base>
7916 { return *this += -__n; }
7918 constexpr decltype(auto) operator[](difference_type __n) const
7919 requires random_access_range<_Base>
7920 { return *(*this + __n); }
7922 friend constexpr bool
7923 operator==(const _Iterator& __x, default_sentinel_t)
7924 { return __x._M_current == __x._M_end; }
7926 friend constexpr bool
7927 operator==(const _Iterator& __x, const _Iterator& __y)
7928 requires equality_comparable<iterator_t<_Base>>
7929 { return __x._M_current == __y._M_current; }
7931 friend constexpr bool
7932 operator<(const _Iterator& __x, const _Iterator& __y)
7933 requires random_access_range<_Base>
7934 { return __x._M_current < __y._M_current; }
7936 friend constexpr bool
7937 operator>(const _Iterator& __x, const _Iterator& __y)
7938 requires random_access_range<_Base>
7939 { return __y._M_current < __x._M_current; }
7941 friend constexpr bool
7942 operator<=(const _Iterator& __x, const _Iterator& __y)
7943 requires random_access_range<_Base>
7944 { return !(__y._M_current < __x._M_current); }
7946 friend constexpr bool
7947 operator>=(const _Iterator& __x, const _Iterator& __y)
7948 requires random_access_range<_Base>
7949 { return !(__x._M_current < __y._M_current); }
7951 friend constexpr auto
7952 operator<=>(const _Iterator& __x, const _Iterator& __y)
7953 requires random_access_range<_Base> && three_way_comparable<iterator_t<_Base>>
7954 { return __x._M_current <=> __y._M_current; }
7956 friend constexpr _Iterator
7957 operator+(const _Iterator& __i, difference_type __n)
7958 requires random_access_range<_Base>
7965 friend constexpr _Iterator
7966 operator+(difference_type __n, const _Iterator& __i)
7967 requires random_access_range<_Base>
7968 { return __i + __n; }
7970 friend constexpr _Iterator
7971 operator-(const _Iterator& __i, difference_type __n)
7972 requires random_access_range<_Base>
7979 friend constexpr difference_type
7980 operator-(const _Iterator& __x, const _Iterator& __y)
7981 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
7983 auto __n = __x._M_current - __y._M_current;
7984 if constexpr (forward_range<_Base>)
7985 return (__n + __x._M_missing - __y._M_missing) / __x._M_stride;
7987 return -__detail::__div_ceil(-__n, __x._M_stride);
7989 return __detail::__div_ceil(__n, __x._M_stride);
7992 friend constexpr difference_type
7993 operator-(default_sentinel_t __y, const _Iterator& __x)
7994 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
7995 { return __detail::__div_ceil(__x._M_end - __x._M_current, __x._M_stride); }
7997 friend constexpr difference_type
7998 operator-(const _Iterator& __x, default_sentinel_t __y)
7999 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
8000 { return -(__y - __x); }
8002 friend constexpr range_rvalue_reference_t<_Base>
8003 iter_move(const _Iterator& __i)
8004 noexcept(noexcept(ranges::iter_move(__i._M_current)))
8005 { return ranges::iter_move(__i._M_current); }
8007 friend constexpr void
8008 iter_swap(const _Iterator& __x, const _Iterator& __y)
8009 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
8010 requires indirectly_swappable<iterator_t<_Base>>
8011 { ranges::iter_swap(__x._M_current, __y._M_current); }
8018 template<typename _Range, typename _Dp>
8019 concept __can_stride_view
8020 = requires { stride_view(std::declval<_Range>(), std::declval<_Dp>()); };
8023 struct _Stride : __adaptor::_RangeAdaptor<_Stride>
8025 template<viewable_range _Range, typename _Dp = range_difference_t<_Range>>
8026 requires __detail::__can_stride_view<_Range, _Dp>
8028 operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const
8029 { return stride_view(std::forward<_Range>(__r), __n); }
8031 using __adaptor::_RangeAdaptor<_Stride>::operator();
8032 static constexpr int _S_arity = 2;
8033 static constexpr bool _S_has_simple_extra_args = true;
8036 inline constexpr _Stride stride;
8039#define __cpp_lib_ranges_cartesian_product 202207L
8043 template<bool _Const, typename _First, typename... _Vs>
8044 concept __cartesian_product_is_random_access
8045 = (random_access_range<__maybe_const_t<_Const, _First>>
8047 && (random_access_range<__maybe_const_t<_Const, _Vs>>
8048 && sized_range<__maybe_const_t<_Const, _Vs>>));
8050 template<typename _Range>
8051 concept __cartesian_product_common_arg
8052 = common_range<_Range> || (sized_range<_Range> && random_access_range<_Range>);
8054 template<bool _Const, typename _First, typename... _Vs>
8055 concept __cartesian_product_is_bidirectional
8056 = (bidirectional_range<__maybe_const_t<_Const, _First>>
8058 && (bidirectional_range<__maybe_const_t<_Const, _Vs>>
8059 && __cartesian_product_common_arg<__maybe_const_t<_Const, _Vs>>));
8061 template<typename _First, typename... _Vs>
8062 concept __cartesian_product_is_common = __cartesian_product_common_arg<_First>;
8064 template<typename... _Vs>
8065 concept __cartesian_product_is_sized = (sized_range<_Vs> && ...);
8067 template<bool _Const, template<typename> class FirstSent, typename _First, typename... _Vs>
8068 concept __cartesian_is_sized_sentinel
8069 = (sized_sentinel_for<FirstSent<__maybe_const_t<_Const, _First>>,
8070 iterator_t<__maybe_const_t<_Const, _First>>>
8072 && (sized_range<__maybe_const_t<_Const, _Vs>>
8073 && sized_sentinel_for<iterator_t<__maybe_const_t<_Const, _Vs>>,
8074 iterator_t<__maybe_const_t<_Const, _Vs>>>));
8076 template<__cartesian_product_common_arg _Range>
8078 __cartesian_common_arg_end(_Range& __r)
8080 if constexpr (common_range<_Range>)
8081 return ranges::end(__r);
8083 return ranges::begin(__r) + ranges::distance(__r);
8085 } // namespace __detail
8087 template<input_range _First, forward_range... _Vs>
8088 requires (view<_First> && ... && view<_Vs>)
8089 class cartesian_product_view : public view_interface<cartesian_product_view<_First, _Vs...>>
8091 tuple<_First, _Vs...> _M_bases;
8093 template<bool> class _Iterator;
8096 _S_difference_type()
8098 // TODO: Implement the recommended practice of using the smallest
8099 // sufficiently wide type according to the maximum sizes of the
8100 // underlying ranges?
8101 return common_type_t<ptrdiff_t,
8102 range_difference_t<_First>,
8103 range_difference_t<_Vs>...>{};
8107 cartesian_product_view() = default;
8110 cartesian_product_view(_First __first, _Vs... __rest)
8111 : _M_bases(std::move(__first), std::move(__rest)...)
8114 constexpr _Iterator<false>
8115 begin() requires (!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>)
8116 { return _Iterator<false>(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); }
8118 constexpr _Iterator<true>
8119 begin() const requires (range<const _First> && ... && range<const _Vs>)
8120 { return _Iterator<true>(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); }
8122 constexpr _Iterator<false>
8123 end() requires ((!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>)
8124 && __detail::__cartesian_product_is_common<_First, _Vs...>)
8126 auto __its = [this]<size_t... _Is>(index_sequence<_Is...>) {
8127 using _Ret = __detail::__tuple_or_pair_t<iterator_t<_First>,
8128 iterator_t<_Vs>...>;
8129 bool __empty_tail = (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...);
8130 auto& __first = std::get<0>(_M_bases);
8131 return _Ret{(__empty_tail
8132 ? ranges::begin(__first)
8133 : __detail::__cartesian_common_arg_end(__first)),
8134 ranges::begin(std::get<1 + _Is>(_M_bases))...};
8135 }(make_index_sequence<sizeof...(_Vs)>{});
8137 return _Iterator<false>{*this, std::move(__its)};
8140 constexpr _Iterator<true>
8141 end() const requires __detail::__cartesian_product_is_common<const _First, const _Vs...>
8143 auto __its = [this]<size_t... _Is>(index_sequence<_Is...>) {
8144 using _Ret = __detail::__tuple_or_pair_t<iterator_t<const _First>,
8145 iterator_t<const _Vs>...>;
8146 bool __empty_tail = (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...);
8147 auto& __first = std::get<0>(_M_bases);
8148 return _Ret{(__empty_tail
8149 ? ranges::begin(__first)
8150 : __detail::__cartesian_common_arg_end(__first)),
8151 ranges::begin(std::get<1 + _Is>(_M_bases))...};
8152 }(make_index_sequence<sizeof...(_Vs)>{});
8154 return _Iterator<true>{*this, std::move(__its)};
8157 constexpr default_sentinel_t
8158 end() const noexcept
8159 { return default_sentinel; }
8162 size() requires __detail::__cartesian_product_is_sized<_First, _Vs...>
8164 using _ST = __detail::__make_unsigned_like_t<decltype(_S_difference_type())>;
8165 return [&]<size_t... _Is>(index_sequence<_Is...>) {
8166 auto __size = static_cast<_ST>(1);
8167#ifdef _GLIBCXX_ASSERTIONS
8168 if constexpr (integral<_ST>)
8171 = (__builtin_mul_overflow(__size,
8172 static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))),
8175 __glibcxx_assert(!__overflow);
8179 __size = (static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))) * ...);
8181 }(make_index_sequence<1 + sizeof...(_Vs)>{});
8185 size() const requires __detail::__cartesian_product_is_sized<const _First, const _Vs...>
8187 using _ST = __detail::__make_unsigned_like_t<decltype(_S_difference_type())>;
8188 return [&]<size_t... _Is>(index_sequence<_Is...>) {
8189 auto __size = static_cast<_ST>(1);
8190#ifdef _GLIBCXX_ASSERTIONS
8191 if constexpr (integral<_ST>)
8194 = (__builtin_mul_overflow(__size,
8195 static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))),
8198 __glibcxx_assert(!__overflow);
8202 __size = (static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))) * ...);
8204 }(make_index_sequence<1 + sizeof...(_Vs)>{});
8208 template<typename... _Vs>
8209 cartesian_product_view(_Vs&&...) -> cartesian_product_view<views::all_t<_Vs>...>;
8211 template<input_range _First, forward_range... _Vs>
8212 requires (view<_First> && ... && view<_Vs>)
8213 template<bool _Const>
8214 class cartesian_product_view<_First, _Vs...>::_Iterator
8216 using _Parent = __maybe_const_t<_Const, cartesian_product_view>;
8217 _Parent* _M_parent = nullptr;
8218 __detail::__tuple_or_pair_t<iterator_t<__maybe_const_t<_Const, _First>>,
8219 iterator_t<__maybe_const_t<_Const, _Vs>>...> _M_current;
8222 _Iterator(_Parent& __parent, decltype(_M_current) __current)
8223 : _M_parent(std::__addressof(__parent)),
8224 _M_current(std::move(__current))
8230 if constexpr (__detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>)
8231 return random_access_iterator_tag{};
8232 else if constexpr (__detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...>)
8233 return bidirectional_iterator_tag{};
8234 else if constexpr (forward_range<__maybe_const_t<_Const, _First>>)
8235 return forward_iterator_tag{};
8237 return input_iterator_tag{};
8240 friend cartesian_product_view;
8243 using iterator_category = input_iterator_tag;
8244 using iterator_concept = decltype(_S_iter_concept());
8246 = __detail::__tuple_or_pair_t<range_value_t<__maybe_const_t<_Const, _First>>,
8247 range_value_t<__maybe_const_t<_Const, _Vs>>...>;
8249 = __detail::__tuple_or_pair_t<range_reference_t<__maybe_const_t<_Const, _First>>,
8250 range_reference_t<__maybe_const_t<_Const, _Vs>>...>;
8251 using difference_type = decltype(cartesian_product_view::_S_difference_type());
8253 _Iterator() = default;
8256 _Iterator(_Iterator<!_Const> __i)
8258 && (convertible_to<iterator_t<_First>, iterator_t<const _First>>
8259 && ... && convertible_to<iterator_t<_Vs>, iterator_t<const _Vs>>)
8260 : _M_parent(std::__addressof(__i._M_parent)),
8261 _M_current(std::move(__i._M_current))
8267 auto __f = [](auto& __i) -> decltype(auto) {
8270 return __detail::__tuple_transform(__f, _M_current);
8273 constexpr _Iterator&
8285 operator++(int) requires forward_range<__maybe_const_t<_Const, _First>>
8292 constexpr _Iterator&
8294 requires __detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...>
8302 requires __detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...>
8309 constexpr _Iterator&
8310 operator+=(difference_type __x)
8311 requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
8317 constexpr _Iterator&
8318 operator-=(difference_type __x)
8319 requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
8320 { return *this += -__x; }
8323 operator[](difference_type __n) const
8324 requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
8325 { return *((*this) + __n); }
8327 friend constexpr bool
8328 operator==(const _Iterator& __x, const _Iterator& __y)
8329 requires equality_comparable<iterator_t<__maybe_const_t<_Const, _First>>>
8330 { return __x._M_current == __y._M_current; }
8332 friend constexpr bool
8333 operator==(const _Iterator& __x, default_sentinel_t)
8335 return [&]<size_t... _Is>(index_sequence<_Is...>) {
8336 return ((std::get<_Is>(__x._M_current)
8337 == ranges::end(std::get<_Is>(__x._M_parent->_M_bases)))
8339 }(make_index_sequence<1 + sizeof...(_Vs)>{});
8342 friend constexpr auto
8343 operator<=>(const _Iterator& __x, const _Iterator& __y)
8344 requires __detail::__all_random_access<_Const, _First, _Vs...>
8345 { return __x._M_current <=> __y._M_current; }
8347 friend constexpr _Iterator
8348 operator+(_Iterator __x, difference_type __y)
8349 requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
8350 { return __x += __y; }
8352 friend constexpr _Iterator
8353 operator+(difference_type __x, _Iterator __y)
8354 requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
8355 { return __y += __x; }
8357 friend constexpr _Iterator
8358 operator-(_Iterator __x, difference_type __y)
8359 requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
8360 { return __x -= __y; }
8362 friend constexpr difference_type
8363 operator-(const _Iterator& __x, const _Iterator& __y)
8364 requires __detail::__cartesian_is_sized_sentinel<_Const, iterator_t, _First, _Vs...>
8365 { return __x._M_distance_from(__y._M_current); }
8367 friend constexpr difference_type
8368 operator-(const _Iterator& __i, default_sentinel_t)
8369 requires __detail::__cartesian_is_sized_sentinel<_Const, sentinel_t, _First, _Vs...>
8371 tuple __end_tuple = [&]<size_t... _Is>(index_sequence<_Is...>) {
8372 return tuple{ranges::end(std::get<0>(__i._M_parent->_M_bases)),
8373 ranges::begin(std::get<1 + _Is>(__i._M_parent->_M_bases))...};
8374 }(make_index_sequence<sizeof...(_Vs)>{});
8375 return __i._M_distance_from(__end_tuple);
8378 friend constexpr difference_type
8379 operator-(default_sentinel_t, const _Iterator& __i)
8380 requires __detail::__cartesian_is_sized_sentinel<_Const, sentinel_t, _First, _Vs...>
8381 { return -(__i - default_sentinel); }
8383 friend constexpr auto
8384 iter_move(const _Iterator& __i)
8385 { return __detail::__tuple_transform(ranges::iter_move, __i._M_current); }
8387 friend constexpr void
8388 iter_swap(const _Iterator& __l, const _Iterator& __r)
8389 requires (indirectly_swappable<iterator_t<__maybe_const_t<_Const, _First>>>
8391 && indirectly_swappable<iterator_t<__maybe_const_t<_Const, _Vs>>>)
8393 [&]<size_t... _Is>(index_sequence<_Is...>) {
8394 (ranges::iter_swap(std::get<_Is>(__l._M_current), std::get<_Is>(__r._M_current)), ...);
8395 }(make_index_sequence<1 + sizeof...(_Vs)>{});
8399 template<size_t _Nm = sizeof...(_Vs)>
8403 auto& __it = std::get<_Nm>(_M_current);
8405 if constexpr (_Nm > 0)
8406 if (__it == ranges::end(std::get<_Nm>(_M_parent->_M_bases)))
8408 __it = ranges::begin(std::get<_Nm>(_M_parent->_M_bases));
8413 template<size_t _Nm = sizeof...(_Vs)>
8417 auto& __it = std::get<_Nm>(_M_current);
8418 if constexpr (_Nm > 0)
8419 if (__it == ranges::begin(std::get<_Nm>(_M_parent->_M_bases)))
8421 __it = __detail::__cartesian_common_arg_end(std::get<_Nm>(_M_parent->_M_bases));
8427 template<size_t _Nm = sizeof...(_Vs)>
8429 _M_advance(difference_type __x)
8430 requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
8438 // Constant time iterator advancement.
8439 auto& __r = std::get<_Nm>(_M_parent->_M_bases);
8440 auto& __it = std::get<_Nm>(_M_current);
8441 if constexpr (_Nm == 0)
8443#ifdef _GLIBCXX_ASSERTIONS
8444 if constexpr (sized_range<__maybe_const_t<_Const, _First>>)
8446 auto __size = ranges::ssize(__r);
8447 auto __begin = ranges::begin(__r);
8448 auto __offset = __it - __begin;
8449 __glibcxx_assert(__offset + __x >= 0 && __offset + __x <= __size);
8456 auto __size = ranges::ssize(__r);
8457 auto __begin = ranges::begin(__r);
8458 auto __offset = __it - __begin;
8460 __x = __offset / __size;
8464 __offset = __size + __offset;
8467 __it = __begin + __offset;
8468 _M_advance<_Nm - 1>(__x);
8473 template<typename _Tuple>
8474 constexpr difference_type
8475 _M_distance_from(const _Tuple& __t) const
8477 return [&]<size_t... _Is>(index_sequence<_Is...>) {
8478 auto __sum = static_cast<difference_type>(0);
8479#ifdef _GLIBCXX_ASSERTIONS
8480 if constexpr (integral<difference_type>)
8483 = (__builtin_add_overflow(__sum, _M_scaled_distance<_Is>(__t), &__sum)
8485 __glibcxx_assert(!__overflow);
8489 __sum = (_M_scaled_distance<_Is>(__t) + ...);
8491 }(make_index_sequence<1 + sizeof...(_Vs)>{});
8494 template<size_t _Nm, typename _Tuple>
8495 constexpr difference_type
8496 _M_scaled_distance(const _Tuple& __t) const
8498 auto __dist = static_cast<difference_type>(std::get<_Nm>(_M_current)
8499 - std::get<_Nm>(__t));
8500#ifdef _GLIBCXX_ASSERTIONS
8501 if constexpr (integral<difference_type>)
8503 bool __overflow = __builtin_mul_overflow(__dist, _M_scaled_size<_Nm+1>(), &__dist);
8504 __glibcxx_assert(!__overflow);
8508 __dist *= _M_scaled_size<_Nm+1>();
8512 template<size_t _Nm>
8513 constexpr difference_type
8514 _M_scaled_size() const
8516 if constexpr (_Nm <= sizeof...(_Vs))
8518 auto __size = static_cast<difference_type>(ranges::size
8519 (std::get<_Nm>(_M_parent->_M_bases)));
8520#ifdef _GLIBCXX_ASSERTIONS
8521 if constexpr (integral<difference_type>)
8523 bool __overflow = __builtin_mul_overflow(__size, _M_scaled_size<_Nm+1>(), &__size);
8524 __glibcxx_assert(!__overflow);
8528 __size *= _M_scaled_size<_Nm+1>();
8532 return static_cast<difference_type>(1);
8540 template<typename... _Ts>
8541 concept __can_cartesian_product_view
8542 = requires { cartesian_product_view<all_t<_Ts>...>(std::declval<_Ts>()...); };
8545 struct _CartesianProduct
8547 template<typename... _Ts>
8548 requires (sizeof...(_Ts) == 0 || __detail::__can_cartesian_product_view<_Ts...>)
8550 operator() [[nodiscard]] (_Ts&&... __ts) const
8552 if constexpr (sizeof...(_Ts) == 0)
8553 return views::single(tuple{});
8555 return cartesian_product_view<all_t<_Ts>...>(std::forward<_Ts>(__ts)...);
8559 inline constexpr _CartesianProduct cartesian_product;
8562#define __cpp_lib_ranges_as_rvalue 202207L
8564 template<input_range _Vp>
8566 class as_rvalue_view : public view_interface<as_rvalue_view<_Vp>>
8568 _Vp _M_base = _Vp();
8571 as_rvalue_view() requires default_initializable<_Vp> = default;
8574 as_rvalue_view(_Vp __base)
8575 : _M_base(std::move(__base))
8579 base() const& requires copy_constructible<_Vp>
8584 { return std::move(_M_base); }
8587 begin() requires (!__detail::__simple_view<_Vp>)
8588 { return move_iterator(ranges::begin(_M_base)); }
8591 begin() const requires range<const _Vp>
8592 { return move_iterator(ranges::begin(_M_base)); }
8595 end() requires (!__detail::__simple_view<_Vp>)
8597 if constexpr (common_range<_Vp>)
8598 return move_iterator(ranges::end(_M_base));
8600 return move_sentinel(ranges::end(_M_base));
8604 end() const requires range<const _Vp>
8606 if constexpr (common_range<const _Vp>)
8607 return move_iterator(ranges::end(_M_base));
8609 return move_sentinel(ranges::end(_M_base));
8613 size() requires sized_range<_Vp>
8614 { return ranges::size(_M_base); }
8617 size() const requires sized_range<const _Vp>
8618 { return ranges::size(_M_base); }
8621 template<typename _Range>
8622 as_rvalue_view(_Range&&) -> as_rvalue_view<views::all_t<_Range>>;
8624 template<typename _Tp>
8625 inline constexpr bool enable_borrowed_range<as_rvalue_view<_Tp>>
8626 = enable_borrowed_range<_Tp>;
8632 template<typename _Tp>
8633 concept __can_as_rvalue_view = requires { as_rvalue_view(std::declval<_Tp>()); };
8636 struct _AsRvalue : __adaptor::_RangeAdaptorClosure
8638 template<viewable_range _Range>
8639 requires __detail::__can_as_rvalue_view<_Range>
8641 operator() [[nodiscard]] (_Range&& __r) const
8643 if constexpr (same_as<range_rvalue_reference_t<_Range>,
8644 range_reference_t<_Range>>)
8645 return views::all(std::forward<_Range>(__r));
8647 return as_rvalue_view(std::forward<_Range>(__r));
8651 inline constexpr _AsRvalue as_rvalue;
8654#define __cpp_lib_ranges_enumerate 202302L
8658 template<typename _Range>
8659 concept __range_with_movable_reference = input_range<_Range>
8660 && move_constructible<range_reference_t<_Range>>
8661 && move_constructible<range_rvalue_reference_t<_Range>>;
8665 requires __detail::__range_with_movable_reference<_Vp>
8666 class enumerate_view : public view_interface<enumerate_view<_Vp>>
8668 _Vp _M_base = _Vp();
8670 template<bool _Const> class _Iterator;
8671 template<bool _Const> class _Sentinel;
8674 enumerate_view() requires default_initializable<_Vp> = default;
8677 enumerate_view(_Vp __base)
8678 : _M_base(std::move(__base))
8682 begin() requires (!__detail::__simple_view<_Vp>)
8683 { return _Iterator<false>(ranges::begin(_M_base), 0); }
8686 begin() const requires __detail::__range_with_movable_reference<const _Vp>
8687 { return _Iterator<true>(ranges::begin(_M_base), 0); }
8690 end() requires (!__detail::__simple_view<_Vp>)
8692 if constexpr (common_range<_Vp> && sized_range<_Vp>)
8693 return _Iterator<false>(ranges::end(_M_base), ranges::distance(_M_base));
8695 return _Sentinel<false>(ranges::end(_M_base));
8699 end() const requires __detail::__range_with_movable_reference<const _Vp>
8701 if constexpr (common_range<const _Vp> && sized_range<const _Vp>)
8702 return _Iterator<true>(ranges::end(_M_base), ranges::distance(_M_base));
8704 return _Sentinel<true>(ranges::end(_M_base));
8708 size() requires sized_range<_Vp>
8709 { return ranges::size(_M_base); }
8712 size() const requires sized_range<const _Vp>
8713 { return ranges::size(_M_base); }
8716 base() const & requires copy_constructible<_Vp>
8721 { return std::move(_M_base); }
8724 template<typename _Range>
8725 enumerate_view(_Range&&) -> enumerate_view<views::all_t<_Range>>;
8727 template<typename _Tp>
8728 inline constexpr bool enable_borrowed_range<enumerate_view<_Tp>>
8729 = enable_borrowed_range<_Tp>;
8732 requires __detail::__range_with_movable_reference<_Vp>
8733 template<bool _Const>
8734 class enumerate_view<_Vp>::_Iterator
8736 using _Base = __maybe_const_t<_Const, _Vp>;
8741 if constexpr (random_access_range<_Base>)
8742 return random_access_iterator_tag{};
8743 else if constexpr (bidirectional_range<_Base>)
8744 return bidirectional_iterator_tag{};
8745 else if constexpr (forward_range<_Base>)
8746 return forward_iterator_tag{};
8748 return input_iterator_tag{};
8751 friend enumerate_view;
8754 using iterator_category = input_iterator_tag;
8755 using iterator_concept = decltype(_S_iter_concept());
8756 using difference_type = range_difference_t<_Base>;
8757 using value_type = tuple<difference_type, range_value_t<_Base>>;
8760 using __reference_type = tuple<difference_type, range_reference_t<_Base>>;
8762 iterator_t<_Base> _M_current = iterator_t<_Base>();
8763 difference_type _M_pos = 0;
8766 _Iterator(iterator_t<_Base> __current, difference_type __pos)
8767 : _M_current(std::move(__current)), _M_pos(__pos)
8771 _Iterator() requires default_initializable<iterator_t<_Base>> = default;
8774 _Iterator(_Iterator<!_Const> __i)
8775 requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
8776 : _M_current(std::move(__i._M_current)), _M_pos(__i._M_pos)
8779 constexpr const iterator_t<_Base> &
8780 base() const & noexcept
8781 { return _M_current; }
8783 constexpr iterator_t<_Base>
8785 { return std::move(_M_current); }
8787 constexpr difference_type
8788 index() const noexcept
8793 { return __reference_type(_M_pos, *_M_current); }
8795 constexpr _Iterator&
8808 operator++(int) requires forward_range<_Base>
8815 constexpr _Iterator&
8816 operator--() requires bidirectional_range<_Base>
8824 operator--(int) requires bidirectional_range<_Base>
8831 constexpr _Iterator&
8832 operator+=(difference_type __n) requires random_access_range<_Base>
8839 constexpr _Iterator&
8840 operator-=(difference_type __n) requires random_access_range<_Base>
8848 operator[](difference_type __n) const requires random_access_range<_Base>
8849 { return __reference_type(_M_pos + __n, _M_current[__n]); }
8851 friend constexpr bool
8852 operator==(const _Iterator& __x, const _Iterator& __y) noexcept
8853 { return __x._M_pos == __y._M_pos; }
8855 friend constexpr strong_ordering
8856 operator<=>(const _Iterator& __x, const _Iterator& __y) noexcept
8857 { return __x._M_pos <=> __y._M_pos; }
8859 friend constexpr _Iterator
8860 operator+(const _Iterator& __x, difference_type __y)
8861 requires random_access_range<_Base>
8862 { return (auto(__x) += __y); }
8864 friend constexpr _Iterator
8865 operator+(difference_type __x, const _Iterator& __y)
8866 requires random_access_range<_Base>
8867 { return auto(__y) += __x; }
8869 friend constexpr _Iterator
8870 operator-(const _Iterator& __x, difference_type __y)
8871 requires random_access_range<_Base>
8872 { return auto(__x) -= __y; }
8874 friend constexpr difference_type
8875 operator-(const _Iterator& __x, const _Iterator& __y)
8876 { return __x._M_pos - __y._M_pos; }
8878 friend constexpr auto
8879 iter_move(const _Iterator& __i)
8880 noexcept(noexcept(ranges::iter_move(__i._M_current))
8881 && is_nothrow_move_constructible_v<range_rvalue_reference_t<_Base>>)
8883 return tuple<difference_type, range_rvalue_reference_t<_Base>>
8884 (__i._M_pos, ranges::iter_move(__i._M_current));
8889 requires __detail::__range_with_movable_reference<_Vp>
8890 template<bool _Const>
8891 class enumerate_view<_Vp>::_Sentinel
8893 using _Base = __maybe_const_t<_Const, _Vp>;
8895 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
8898 _Sentinel(sentinel_t<_Base> __end)
8899 : _M_end(std::move(__end))
8902 friend enumerate_view;
8905 _Sentinel() = default;
8908 _Sentinel(_Sentinel<!_Const> __other)
8909 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
8910 : _M_end(std::move(__other._M_end))
8913 constexpr sentinel_t<_Base>
8917 template<bool _OtherConst>
8918 requires sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const_t<_OtherConst, _Vp>>>
8919 friend constexpr bool
8920 operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y)
8921 { return __x._M_current == __y._M_end; }
8923 template<bool _OtherConst>
8924 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const_t<_OtherConst, _Vp>>>
8925 friend constexpr range_difference_t<__maybe_const_t<_OtherConst, _Vp>>
8926 operator-(const _Iterator<_OtherConst>& __x, const _Sentinel& __y)
8927 { return __x._M_current - __y._M_end; }
8929 template<bool _OtherConst>
8930 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const_t<_OtherConst, _Vp>>>
8931 friend constexpr range_difference_t<__maybe_const_t<_OtherConst, _Vp>>
8932 operator-(const _Sentinel& __x, const _Iterator<_OtherConst>& __y)
8933 { return __x._M_end - __y._M_current; }
8940 template<typename _Tp>
8941 concept __can_enumerate_view
8942 = requires { enumerate_view<all_t<_Tp>>(std::declval<_Tp>()); };
8945 struct _Enumerate : __adaptor::_RangeAdaptorClosure
8947 template<viewable_range _Range>
8948 requires __detail::__can_enumerate_view<_Range>
8950 operator() [[nodiscard]] (_Range&& __r) const
8951 { return enumerate_view<all_t<_Range>>(std::forward<_Range>(__r)); }
8954 inline constexpr _Enumerate enumerate;
8957#define __cpp_lib_ranges_as_const 202311L
8960 requires input_range<_Vp>
8961 class as_const_view : public view_interface<as_const_view<_Vp>>
8963 _Vp _M_base = _Vp();
8966 as_const_view() requires default_initializable<_Vp> = default;
8969 as_const_view(_Vp __base)
8970 noexcept(is_nothrow_move_constructible_v<_Vp>)
8971 : _M_base(std::move(__base))
8976 noexcept(is_nothrow_copy_constructible_v<_Vp>)
8977 requires copy_constructible<_Vp>
8982 noexcept(is_nothrow_move_constructible_v<_Vp>)
8983 { return std::move(_M_base); }
8986 begin() requires (!__detail::__simple_view<_Vp>)
8987 { return ranges::cbegin(_M_base); }
8990 begin() const requires range<const _Vp>
8991 { return ranges::cbegin(_M_base); }
8994 end() requires (!__detail::__simple_view<_Vp>)
8995 { return ranges::cend(_M_base); }
8998 end() const requires range<const _Vp>
8999 { return ranges::cend(_M_base); }
9002 size() requires sized_range<_Vp>
9003 { return ranges::size(_M_base); }
9006 size() const requires sized_range<const _Vp>
9007 { return ranges::size(_M_base); }
9010 template<typename _Range>
9011 as_const_view(_Range&&) -> as_const_view<views::all_t<_Range>>;
9013 template<typename _Tp>
9014 inline constexpr bool enable_borrowed_range<as_const_view<_Tp>>
9015 = enable_borrowed_range<_Tp>;
9021 template<typename _Tp>
9022 inline constexpr bool __is_constable_ref_view = false;
9024 template<typename _Range>
9025 inline constexpr bool __is_constable_ref_view<ref_view<_Range>>
9026 = constant_range<const _Range>;
9028 template<typename _Range>
9029 concept __can_as_const_view = requires { as_const_view(std::declval<_Range>()); };
9032 struct _AsConst : __adaptor::_RangeAdaptorClosure
9034 template<viewable_range _Range>
9036 operator()(_Range&& __r) const
9037 noexcept(noexcept(as_const_view(std::declval<_Range>())))
9038 requires __detail::__can_as_const_view<_Range>
9040 using _Tp = remove_cvref_t<_Range>;
9041 using element_type = remove_reference_t<range_reference_t<_Range>>;
9042 if constexpr (constant_range<views::all_t<_Range>>)
9043 return views::all(std::forward<_Range>(__r));
9044 else if constexpr (__detail::__is_empty_view<_Tp>)
9045 return views::empty<const element_type>;
9046 else if constexpr (std::__detail::__is_span<_Tp>)
9047 return span<const element_type, _Tp::extent>(std::forward<_Range>(__r));
9048 else if constexpr (__detail::__is_constable_ref_view<_Tp>)
9049 return ref_view(std::as_const(std::forward<_Range>(__r).base()));
9050 else if constexpr (is_lvalue_reference_v<_Range>
9051 && constant_range<const _Tp>
9053 return ref_view(static_cast<const _Tp&>(__r));
9055 return as_const_view(std::forward<_Range>(__r));
9059 inline constexpr _AsConst as_const;
9062} // namespace ranges
9064 namespace views = ranges::views;
9066_GLIBCXX_END_NAMESPACE_VERSION
9068#endif // library concepts
9070#endif /* _GLIBCXX_RANGES */