// -*- C++ -*- // Copyright (C) 2019-2023 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 3, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // Under Section 7 of GPL version 3, you are granted additional // permissions described in the GCC Runtime Library Exception, version // 3.1, as published by the Free Software Foundation. // You should have received a copy of the GNU General Public License and // a copy of the GCC Runtime Library Exception along with this program; // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see // . /** @file include/ranges * This is a Standard C++ Library header. * @ingroup concepts */ #ifndef _GLIBCXX_RANGES #define _GLIBCXX_RANGES 1 #if __cplusplus > 201703L #pragma GCC system_header #include #if __cpp_lib_concepts #include #include #include #include #include #include #include #if __cplusplus > 202002L #include #endif #include #include #define __glibcxx_want_ranges #define __glibcxx_want_ranges_as_const #define __glibcxx_want_ranges_as_rvalue #define __glibcxx_want_ranges_cartesian_product #define __glibcxx_want_ranges_chunk #define __glibcxx_want_ranges_chunk_by #define __glibcxx_want_ranges_enumerate #define __glibcxx_want_ranges_iota #define __glibcxx_want_ranges_iota #define __glibcxx_want_ranges_join_with #define __glibcxx_want_ranges_repeat #define __glibcxx_want_ranges_slide #define __glibcxx_want_ranges_stride #define __glibcxx_want_ranges_to_container #define __glibcxx_want_ranges_zip #include /** * @defgroup ranges Ranges * * Components for dealing with ranges of elements. */ namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION namespace ranges { // [range.access] customization point objects // [range.req] range and view concepts // [range.dangling] dangling iterator handling // Defined in // [view.interface] View interface // [range.subrange] Sub-ranges // Defined in // C++20 24.6 [range.factories] Range factories /// A view that contains no elements. template requires is_object_v<_Tp> class empty_view : public view_interface> { public: static constexpr _Tp* begin() noexcept { return nullptr; } static constexpr _Tp* end() noexcept { return nullptr; } static constexpr _Tp* data() noexcept { return nullptr; } static constexpr size_t size() noexcept { return 0; } static constexpr bool empty() noexcept { return true; } }; template inline constexpr bool enable_borrowed_range> = true; namespace __detail { #if __cpp_lib_ranges >= 202207L // C++ >= 23 // P2494R2 Relaxing range adaptors to allow for move only types template concept __boxable = move_constructible<_Tp> && is_object_v<_Tp>; #else template concept __boxable = copy_constructible<_Tp> && is_object_v<_Tp>; #endif template<__boxable _Tp> struct __box : std::optional<_Tp> { using std::optional<_Tp>::optional; constexpr __box() noexcept(is_nothrow_default_constructible_v<_Tp>) requires default_initializable<_Tp> : std::optional<_Tp>{std::in_place} { } __box(const __box&) = default; __box(__box&&) = default; using std::optional<_Tp>::operator=; // _GLIBCXX_RESOLVE_LIB_DEFECTS // 3477. Simplify constraints for semiregular-box // 3572. copyable-box should be fully constexpr constexpr __box& operator=(const __box& __that) noexcept(is_nothrow_copy_constructible_v<_Tp>) requires (!copyable<_Tp>) && copy_constructible<_Tp> { if (this != std::__addressof(__that)) { if ((bool)__that) this->emplace(*__that); else this->reset(); } return *this; } constexpr __box& operator=(__box&& __that) noexcept(is_nothrow_move_constructible_v<_Tp>) requires (!movable<_Tp>) { if (this != std::__addressof(__that)) { if ((bool)__that) this->emplace(std::move(*__that)); else this->reset(); } return *this; } }; template concept __boxable_copyable = copy_constructible<_Tp> && (copyable<_Tp> || (is_nothrow_move_constructible_v<_Tp> && is_nothrow_copy_constructible_v<_Tp>)); template concept __boxable_movable = (!copy_constructible<_Tp>) && (movable<_Tp> || is_nothrow_move_constructible_v<_Tp>); // For types which are already copyable (or since C++23, movable) // this specialization of the box wrapper stores the object directly // without going through std::optional. It provides just the subset of // the primary template's API that we currently use. template<__boxable _Tp> requires __boxable_copyable<_Tp> || __boxable_movable<_Tp> struct __box<_Tp> { private: [[no_unique_address]] _Tp _M_value = _Tp(); public: __box() requires default_initializable<_Tp> = default; constexpr explicit __box(const _Tp& __t) noexcept(is_nothrow_copy_constructible_v<_Tp>) requires copy_constructible<_Tp> : _M_value(__t) { } constexpr explicit __box(_Tp&& __t) noexcept(is_nothrow_move_constructible_v<_Tp>) : _M_value(std::move(__t)) { } template requires constructible_from<_Tp, _Args...> constexpr explicit __box(in_place_t, _Args&&... __args) noexcept(is_nothrow_constructible_v<_Tp, _Args...>) : _M_value(std::forward<_Args>(__args)...) { } __box(const __box&) = default; __box(__box&&) = default; __box& operator=(const __box&) requires copyable<_Tp> = default; __box& operator=(__box&&) requires movable<_Tp> = default; // When _Tp is nothrow_copy_constructible but not copy_assignable, // copy assignment is implemented via destroy-then-copy-construct. constexpr __box& operator=(const __box& __that) noexcept requires (!copyable<_Tp>) && copy_constructible<_Tp> { static_assert(is_nothrow_copy_constructible_v<_Tp>); if (this != std::__addressof(__that)) { _M_value.~_Tp(); std::construct_at(std::__addressof(_M_value), *__that); } return *this; } // Likewise for move assignment. constexpr __box& operator=(__box&& __that) noexcept requires (!movable<_Tp>) { static_assert(is_nothrow_move_constructible_v<_Tp>); if (this != std::__addressof(__that)) { _M_value.~_Tp(); std::construct_at(std::__addressof(_M_value), std::move(*__that)); } return *this; } constexpr bool has_value() const noexcept { return true; }; constexpr _Tp& operator*() & noexcept { return _M_value; } constexpr const _Tp& operator*() const & noexcept { return _M_value; } constexpr _Tp&& operator*() && noexcept { return std::move(_M_value); } constexpr const _Tp&& operator*() const && noexcept { return std::move(_M_value); } constexpr _Tp* operator->() noexcept { return std::__addressof(_M_value); } constexpr const _Tp* operator->() const noexcept { return std::__addressof(_M_value); } }; } // namespace __detail /// A view that contains exactly one element. #if __cpp_lib_ranges >= 202207L // C++ >= 23 template #else template #endif requires is_object_v<_Tp> class single_view : public view_interface> { public: single_view() requires default_initializable<_Tp> = default; constexpr explicit single_view(const _Tp& __t) noexcept(is_nothrow_copy_constructible_v<_Tp>) requires copy_constructible<_Tp> : _M_value(__t) { } constexpr explicit single_view(_Tp&& __t) noexcept(is_nothrow_move_constructible_v<_Tp>) : _M_value(std::move(__t)) { } // _GLIBCXX_RESOLVE_LIB_DEFECTS // 3428. single_view's in place constructor should be explicit template requires constructible_from<_Tp, _Args...> constexpr explicit single_view(in_place_t, _Args&&... __args) noexcept(is_nothrow_constructible_v<_Tp, _Args...>) : _M_value{in_place, std::forward<_Args>(__args)...} { } constexpr _Tp* begin() noexcept { return data(); } constexpr const _Tp* begin() const noexcept { return data(); } constexpr _Tp* end() noexcept { return data() + 1; } constexpr const _Tp* end() const noexcept { return data() + 1; } static constexpr size_t size() noexcept { return 1; } constexpr _Tp* data() noexcept { return _M_value.operator->(); } constexpr const _Tp* data() const noexcept { return _M_value.operator->(); } private: [[no_unique_address]] __detail::__box<_Tp> _M_value; }; template single_view(_Tp) -> single_view<_Tp>; namespace __detail { template constexpr auto __to_signed_like(_Wp __w) noexcept { if constexpr (!integral<_Wp>) return iter_difference_t<_Wp>(); else if constexpr (sizeof(iter_difference_t<_Wp>) > sizeof(_Wp)) return iter_difference_t<_Wp>(__w); else if constexpr (sizeof(ptrdiff_t) > sizeof(_Wp)) return ptrdiff_t(__w); else if constexpr (sizeof(long long) > sizeof(_Wp)) return (long long)(__w); #ifdef __SIZEOF_INT128__ else if constexpr (__SIZEOF_INT128__ > sizeof(_Wp)) return __int128(__w); #endif else return __max_diff_type(__w); } template using __iota_diff_t = decltype(__to_signed_like(std::declval<_Wp>())); template concept __decrementable = incrementable<_It> && requires(_It __i) { { --__i } -> same_as<_It&>; { __i-- } -> same_as<_It>; }; template concept __advanceable = __decrementable<_It> && totally_ordered<_It> && requires( _It __i, const _It __j, const __iota_diff_t<_It> __n) { { __i += __n } -> same_as<_It&>; { __i -= __n } -> same_as<_It&>; _It(__j + __n); _It(__n + __j); _It(__j - __n); { __j - __j } -> convertible_to<__iota_diff_t<_It>>; }; template struct __iota_view_iter_cat { }; template struct __iota_view_iter_cat<_Winc> { using iterator_category = input_iterator_tag; }; } // namespace __detail template requires std::__detail::__weakly_eq_cmp_with<_Winc, _Bound> && copyable<_Winc> class iota_view : public view_interface> { private: struct _Sentinel; struct _Iterator : __detail::__iota_view_iter_cat<_Winc> { private: static auto _S_iter_concept() { using namespace __detail; if constexpr (__advanceable<_Winc>) return random_access_iterator_tag{}; else if constexpr (__decrementable<_Winc>) return bidirectional_iterator_tag{}; else if constexpr (incrementable<_Winc>) return forward_iterator_tag{}; else return input_iterator_tag{}; } public: using iterator_concept = decltype(_S_iter_concept()); // iterator_category defined in __iota_view_iter_cat using value_type = _Winc; using difference_type = __detail::__iota_diff_t<_Winc>; _Iterator() requires default_initializable<_Winc> = default; constexpr explicit _Iterator(_Winc __value) : _M_value(__value) { } constexpr _Winc operator*() const noexcept(is_nothrow_copy_constructible_v<_Winc>) { return _M_value; } constexpr _Iterator& operator++() { ++_M_value; return *this; } constexpr void operator++(int) { ++*this; } constexpr _Iterator operator++(int) requires incrementable<_Winc> { auto __tmp = *this; ++*this; return __tmp; } constexpr _Iterator& operator--() requires __detail::__decrementable<_Winc> { --_M_value; return *this; } constexpr _Iterator operator--(int) requires __detail::__decrementable<_Winc> { auto __tmp = *this; --*this; return __tmp; } constexpr _Iterator& operator+=(difference_type __n) requires __detail::__advanceable<_Winc> { using __detail::__is_integer_like; using __detail::__is_signed_integer_like; if constexpr (__is_integer_like<_Winc> && !__is_signed_integer_like<_Winc>) { if (__n >= difference_type(0)) _M_value += static_cast<_Winc>(__n); else _M_value -= static_cast<_Winc>(-__n); } else _M_value += __n; return *this; } constexpr _Iterator& operator-=(difference_type __n) requires __detail::__advanceable<_Winc> { using __detail::__is_integer_like; using __detail::__is_signed_integer_like; if constexpr (__is_integer_like<_Winc> && !__is_signed_integer_like<_Winc>) { if (__n >= difference_type(0)) _M_value -= static_cast<_Winc>(__n); else _M_value += static_cast<_Winc>(-__n); } else _M_value -= __n; return *this; } constexpr _Winc operator[](difference_type __n) const requires __detail::__advanceable<_Winc> { return _Winc(_M_value + __n); } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) requires equality_comparable<_Winc> { return __x._M_value == __y._M_value; } friend constexpr bool operator<(const _Iterator& __x, const _Iterator& __y) requires totally_ordered<_Winc> { return __x._M_value < __y._M_value; } friend constexpr bool operator>(const _Iterator& __x, const _Iterator& __y) requires totally_ordered<_Winc> { return __y < __x; } friend constexpr bool operator<=(const _Iterator& __x, const _Iterator& __y) requires totally_ordered<_Winc> { return !(__y < __x); } friend constexpr bool operator>=(const _Iterator& __x, const _Iterator& __y) requires totally_ordered<_Winc> { return !(__x < __y); } #ifdef __cpp_lib_three_way_comparison friend constexpr auto operator<=>(const _Iterator& __x, const _Iterator& __y) requires totally_ordered<_Winc> && three_way_comparable<_Winc> { return __x._M_value <=> __y._M_value; } #endif friend constexpr _Iterator operator+(_Iterator __i, difference_type __n) requires __detail::__advanceable<_Winc> { __i += __n; return __i; } friend constexpr _Iterator operator+(difference_type __n, _Iterator __i) requires __detail::__advanceable<_Winc> { return __i += __n; } friend constexpr _Iterator operator-(_Iterator __i, difference_type __n) requires __detail::__advanceable<_Winc> { __i -= __n; return __i; } friend constexpr difference_type operator-(const _Iterator& __x, const _Iterator& __y) requires __detail::__advanceable<_Winc> { using __detail::__is_integer_like; using __detail::__is_signed_integer_like; using _Dt = difference_type; if constexpr (__is_integer_like<_Winc>) { if constexpr (__is_signed_integer_like<_Winc>) return _Dt(_Dt(__x._M_value) - _Dt(__y._M_value)); else return (__y._M_value > __x._M_value) ? _Dt(-_Dt(__y._M_value - __x._M_value)) : _Dt(__x._M_value - __y._M_value); } else return __x._M_value - __y._M_value; } private: _Winc _M_value = _Winc(); friend iota_view; friend _Sentinel; }; struct _Sentinel { private: constexpr bool _M_equal(const _Iterator& __x) const { return __x._M_value == _M_bound; } constexpr auto _M_distance_from(const _Iterator& __x) const { return _M_bound - __x._M_value; } _Bound _M_bound = _Bound(); public: _Sentinel() = default; constexpr explicit _Sentinel(_Bound __bound) : _M_bound(__bound) { } friend constexpr bool operator==(const _Iterator& __x, const _Sentinel& __y) { return __y._M_equal(__x); } friend constexpr iter_difference_t<_Winc> operator-(const _Iterator& __x, const _Sentinel& __y) requires sized_sentinel_for<_Bound, _Winc> { return -__y._M_distance_from(__x); } friend constexpr iter_difference_t<_Winc> operator-(const _Sentinel& __x, const _Iterator& __y) requires sized_sentinel_for<_Bound, _Winc> { return __x._M_distance_from(__y); } friend iota_view; }; _Winc _M_value = _Winc(); [[no_unique_address]] _Bound _M_bound = _Bound(); public: iota_view() requires default_initializable<_Winc> = default; constexpr explicit iota_view(_Winc __value) : _M_value(__value) { } constexpr iota_view(type_identity_t<_Winc> __value, type_identity_t<_Bound> __bound) : _M_value(__value), _M_bound(__bound) { if constexpr (totally_ordered_with<_Winc, _Bound>) __glibcxx_assert( bool(__value <= __bound) ); } constexpr iota_view(_Iterator __first, _Iterator __last) requires same_as<_Winc, _Bound> : iota_view(__first._M_value, __last._M_value) { } constexpr iota_view(_Iterator __first, unreachable_sentinel_t __last) requires same_as<_Bound, unreachable_sentinel_t> : iota_view(__first._M_value, __last) { } constexpr iota_view(_Iterator __first, _Sentinel __last) requires (!same_as<_Winc, _Bound>) && (!same_as<_Bound, unreachable_sentinel_t>) : iota_view(__first._M_value, __last._M_bound) { } constexpr _Iterator begin() const { return _Iterator{_M_value}; } constexpr auto end() const { if constexpr (same_as<_Bound, unreachable_sentinel_t>) return unreachable_sentinel; else return _Sentinel{_M_bound}; } constexpr _Iterator end() const requires same_as<_Winc, _Bound> { return _Iterator{_M_bound}; } constexpr auto size() const requires (same_as<_Winc, _Bound> && __detail::__advanceable<_Winc>) || (integral<_Winc> && integral<_Bound>) || sized_sentinel_for<_Bound, _Winc> { using __detail::__is_integer_like; using __detail::__to_unsigned_like; if constexpr (integral<_Winc> && integral<_Bound>) { using _Up = make_unsigned_t; return _Up(_M_bound) - _Up(_M_value); } else if constexpr (__is_integer_like<_Winc>) return __to_unsigned_like(_M_bound) - __to_unsigned_like(_M_value); else return __to_unsigned_like(_M_bound - _M_value); } }; template requires (!__detail::__is_integer_like<_Winc> || !__detail::__is_integer_like<_Bound> || (__detail::__is_signed_integer_like<_Winc> == __detail::__is_signed_integer_like<_Bound>)) iota_view(_Winc, _Bound) -> iota_view<_Winc, _Bound>; template inline constexpr bool enable_borrowed_range> = true; namespace views { template inline constexpr empty_view<_Tp> empty{}; namespace __detail { template concept __can_single_view = requires { single_view>(std::declval<_Tp>()); }; } // namespace __detail struct _Single { template<__detail::__can_single_view _Tp> constexpr auto operator() [[nodiscard]] (_Tp&& __e) const noexcept(noexcept(single_view>(std::forward<_Tp>(__e)))) { return single_view>(std::forward<_Tp>(__e)); } }; inline constexpr _Single single{}; namespace __detail { template concept __can_iota_view = requires { iota_view(std::declval<_Args>()...); }; } // namespace __detail struct _Iota { template<__detail::__can_iota_view _Tp> constexpr auto operator() [[nodiscard]] (_Tp&& __e) const { return iota_view(std::forward<_Tp>(__e)); } template requires __detail::__can_iota_view<_Tp, _Up> constexpr auto operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const { return iota_view(std::forward<_Tp>(__e), std::forward<_Up>(__f)); } }; inline constexpr _Iota iota{}; } // namespace views #if _GLIBCXX_HOSTED namespace __detail { template concept __stream_extractable = requires(basic_istream<_CharT, _Traits>& is, _Val& t) { is >> t; }; } // namespace __detail template> requires default_initializable<_Val> && __detail::__stream_extractable<_Val, _CharT, _Traits> class basic_istream_view : public view_interface> { public: constexpr explicit basic_istream_view(basic_istream<_CharT, _Traits>& __stream) : _M_stream(std::__addressof(__stream)) { } constexpr auto begin() { *_M_stream >> _M_object; return _Iterator{this}; } constexpr default_sentinel_t end() const noexcept { return default_sentinel; } private: basic_istream<_CharT, _Traits>* _M_stream; _Val _M_object = _Val(); struct _Iterator { public: using iterator_concept = input_iterator_tag; using difference_type = ptrdiff_t; using value_type = _Val; constexpr explicit _Iterator(basic_istream_view* __parent) noexcept : _M_parent(__parent) { } _Iterator(const _Iterator&) = delete; _Iterator(_Iterator&&) = default; _Iterator& operator=(const _Iterator&) = delete; _Iterator& operator=(_Iterator&&) = default; _Iterator& operator++() { *_M_parent->_M_stream >> _M_parent->_M_object; return *this; } void operator++(int) { ++*this; } _Val& operator*() const { return _M_parent->_M_object; } friend bool operator==(const _Iterator& __x, default_sentinel_t) { return __x._M_at_end(); } private: basic_istream_view* _M_parent; bool _M_at_end() const { return !*_M_parent->_M_stream; } }; friend _Iterator; }; template using istream_view = basic_istream_view<_Val, char>; template using wistream_view = basic_istream_view<_Val, wchar_t>; namespace views { namespace __detail { template concept __can_istream_view = requires (_Up __e) { basic_istream_view<_Tp, typename _Up::char_type, typename _Up::traits_type>(__e); }; } // namespace __detail template struct _Istream { template constexpr auto operator() [[nodiscard]] (basic_istream<_CharT, _Traits>& __e) const requires __detail::__can_istream_view<_Tp, remove_reference_t> { return basic_istream_view<_Tp, _CharT, _Traits>(__e); } }; template inline constexpr _Istream<_Tp> istream; } #endif // HOSTED // C++20 24.7 [range.adaptors] Range adaptors namespace __detail { struct _Empty { }; // Alias for a type that is conditionally present // (and is an empty type otherwise). // Data members using this alias should use [[no_unique_address]] so that // they take no space when not needed. template using __maybe_present_t = __conditional_t<_Present, _Tp, _Empty>; // Alias for a type that is conditionally const. template using __maybe_const_t = __conditional_t<_Const, const _Tp, _Tp>; } // namespace __detail // Shorthand for __detail::__maybe_const_t. using __detail::__maybe_const_t; namespace views::__adaptor { // True if the range adaptor _Adaptor can be applied with _Args. template concept __adaptor_invocable = requires { std::declval<_Adaptor>()(declval<_Args>()...); }; // True if the range adaptor non-closure _Adaptor can be partially applied // with _Args. template concept __adaptor_partial_app_viable = (_Adaptor::_S_arity > 1) && (sizeof...(_Args) == _Adaptor::_S_arity - 1) && (constructible_from, _Args> && ...); template struct _Partial; template struct _Pipe; // The base class of every range adaptor closure. // // The derived class should define the optional static data member // _S_has_simple_call_op to true if the behavior of this adaptor is // independent of the constness/value category of the adaptor object. template struct _RangeAdaptorClosure { }; template requires (!same_as<_Tp, _RangeAdaptorClosure<_Up>>) void __is_range_adaptor_closure_fn (const _Tp&, const _RangeAdaptorClosure<_Up>&); // not defined template concept __is_range_adaptor_closure = requires (_Tp __t) { __adaptor::__is_range_adaptor_closure_fn(__t, __t); }; // range | adaptor is equivalent to adaptor(range). template requires __is_range_adaptor_closure<_Self> && __adaptor_invocable<_Self, _Range> constexpr auto operator|(_Range&& __r, _Self&& __self) { return std::forward<_Self>(__self)(std::forward<_Range>(__r)); } // Compose the adaptors __lhs and __rhs into a pipeline, returning // another range adaptor closure object. template requires __is_range_adaptor_closure<_Lhs> && __is_range_adaptor_closure<_Rhs> constexpr auto operator|(_Lhs __lhs, _Rhs __rhs) { return _Pipe<_Lhs, _Rhs>{std::move(__lhs), std::move(__rhs)}; } // The base class of every range adaptor non-closure. // // The static data member _Derived::_S_arity must contain the total number of // arguments that the adaptor takes, and the class _Derived must introduce // _RangeAdaptor::operator() into the class scope via a using-declaration. // // The optional static data member _Derived::_S_has_simple_extra_args should // be defined to true if the behavior of this adaptor is independent of the // constness/value category of the extra arguments. This data member could // also be defined as a variable template parameterized by the types of the // extra arguments. template struct _RangeAdaptor { // Partially apply the arguments __args to the range adaptor _Derived, // returning a range adaptor closure object. template requires __adaptor_partial_app_viable<_Derived, _Args...> constexpr auto operator()(_Args&&... __args) const { return _Partial<_Derived, decay_t<_Args>...>{std::forward<_Args>(__args)...}; } }; // True if the range adaptor closure _Adaptor has a simple operator(), i.e. // one that's not overloaded according to constness or value category of the // _Adaptor object. template concept __closure_has_simple_call_op = _Adaptor::_S_has_simple_call_op; // True if the behavior of the range adaptor non-closure _Adaptor is // independent of the value category of its extra arguments _Args. template concept __adaptor_has_simple_extra_args = _Adaptor::_S_has_simple_extra_args || _Adaptor::template _S_has_simple_extra_args<_Args...>; // A range adaptor closure that represents partial application of // the range adaptor _Adaptor with arguments _Args. template struct _Partial : _RangeAdaptorClosure<_Partial<_Adaptor, _Args...>> { tuple<_Args...> _M_args; constexpr _Partial(_Args... __args) : _M_args(std::move(__args)...) { } // Invoke _Adaptor with arguments __r, _M_args... according to the // value category of this _Partial object. // TODO: use explicit object functions ("deducing this"). template requires __adaptor_invocable<_Adaptor, _Range, const _Args&...> constexpr auto operator()(_Range&& __r) const & { auto __forwarder = [&__r] (const auto&... __args) { return _Adaptor{}(std::forward<_Range>(__r), __args...); }; return std::apply(__forwarder, _M_args); } template requires __adaptor_invocable<_Adaptor, _Range, _Args...> constexpr auto operator()(_Range&& __r) && { auto __forwarder = [&__r] (auto&... __args) { return _Adaptor{}(std::forward<_Range>(__r), std::move(__args)...); }; return std::apply(__forwarder, _M_args); } template constexpr auto operator()(_Range&& __r) const && = delete; }; // A lightweight specialization of the above primary template for // the common case where _Adaptor accepts a single extra argument. template struct _Partial<_Adaptor, _Arg> : _RangeAdaptorClosure<_Partial<_Adaptor, _Arg>> { _Arg _M_arg; constexpr _Partial(_Arg __arg) : _M_arg(std::move(__arg)) { } template requires __adaptor_invocable<_Adaptor, _Range, const _Arg&> constexpr auto operator()(_Range&& __r) const & { return _Adaptor{}(std::forward<_Range>(__r), _M_arg); } template requires __adaptor_invocable<_Adaptor, _Range, _Arg> constexpr auto operator()(_Range&& __r) && { return _Adaptor{}(std::forward<_Range>(__r), std::move(_M_arg)); } template constexpr auto operator()(_Range&& __r) const && = delete; }; // Partial specialization of the primary template for the case where the extra // arguments of the adaptor can always be safely and efficiently forwarded by // const reference. This lets us get away with a single operator() overload, // which makes overload resolution failure diagnostics more concise. template requires __adaptor_has_simple_extra_args<_Adaptor, _Args...> && (is_trivially_copyable_v<_Args> && ...) struct _Partial<_Adaptor, _Args...> : _RangeAdaptorClosure<_Partial<_Adaptor, _Args...>> { tuple<_Args...> _M_args; constexpr _Partial(_Args... __args) : _M_args(std::move(__args)...) { } // Invoke _Adaptor with arguments __r, const _M_args&... regardless // of the value category of this _Partial object. template requires __adaptor_invocable<_Adaptor, _Range, const _Args&...> constexpr auto operator()(_Range&& __r) const { auto __forwarder = [&__r] (const auto&... __args) { return _Adaptor{}(std::forward<_Range>(__r), __args...); }; return std::apply(__forwarder, _M_args); } static constexpr bool _S_has_simple_call_op = true; }; // A lightweight specialization of the above template for the common case // where _Adaptor accepts a single extra argument. template requires __adaptor_has_simple_extra_args<_Adaptor, _Arg> && is_trivially_copyable_v<_Arg> struct _Partial<_Adaptor, _Arg> : _RangeAdaptorClosure<_Partial<_Adaptor, _Arg>> { _Arg _M_arg; constexpr _Partial(_Arg __arg) : _M_arg(std::move(__arg)) { } template requires __adaptor_invocable<_Adaptor, _Range, const _Arg&> constexpr auto operator()(_Range&& __r) const { return _Adaptor{}(std::forward<_Range>(__r), _M_arg); } static constexpr bool _S_has_simple_call_op = true; }; template concept __pipe_invocable = requires { std::declval<_Rhs>()(std::declval<_Lhs>()(std::declval<_Range>())); }; // A range adaptor closure that represents composition of the range // adaptor closures _Lhs and _Rhs. template struct _Pipe : _RangeAdaptorClosure<_Pipe<_Lhs, _Rhs>> { [[no_unique_address]] _Lhs _M_lhs; [[no_unique_address]] _Rhs _M_rhs; constexpr _Pipe(_Lhs __lhs, _Rhs __rhs) : _M_lhs(std::move(__lhs)), _M_rhs(std::move(__rhs)) { } // Invoke _M_rhs(_M_lhs(__r)) according to the value category of this // range adaptor closure object. // TODO: use explicit object functions ("deducing this"). template requires __pipe_invocable constexpr auto operator()(_Range&& __r) const & { return _M_rhs(_M_lhs(std::forward<_Range>(__r))); } template requires __pipe_invocable<_Lhs, _Rhs, _Range> constexpr auto operator()(_Range&& __r) && { return std::move(_M_rhs)(std::move(_M_lhs)(std::forward<_Range>(__r))); } template constexpr auto operator()(_Range&& __r) const && = delete; }; // A partial specialization of the above primary template for the case where // both adaptor operands have a simple operator(). This in turn lets us // implement composition using a single simple operator(), which makes // overload resolution failure diagnostics more concise. template requires __closure_has_simple_call_op<_Lhs> && __closure_has_simple_call_op<_Rhs> struct _Pipe<_Lhs, _Rhs> : _RangeAdaptorClosure<_Pipe<_Lhs, _Rhs>> { [[no_unique_address]] _Lhs _M_lhs; [[no_unique_address]] _Rhs _M_rhs; constexpr _Pipe(_Lhs __lhs, _Rhs __rhs) : _M_lhs(std::move(__lhs)), _M_rhs(std::move(__rhs)) { } template requires __pipe_invocable constexpr auto operator()(_Range&& __r) const { return _M_rhs(_M_lhs(std::forward<_Range>(__r))); } static constexpr bool _S_has_simple_call_op = true; }; } // namespace views::__adaptor #if __cpp_lib_ranges >= 202202L // P2387R3 Pipe support for user-defined range adaptors template requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>> class range_adaptor_closure : public views::__adaptor::_RangeAdaptorClosure<_Derived> { }; #endif template requires is_object_v<_Range> class ref_view : public view_interface> { private: _Range* _M_r; static void _S_fun(_Range&); // not defined static void _S_fun(_Range&&) = delete; public: template<__detail::__different_from _Tp> requires convertible_to<_Tp, _Range&> && requires { _S_fun(declval<_Tp>()); } constexpr ref_view(_Tp&& __t) noexcept(noexcept(static_cast<_Range&>(std::declval<_Tp>()))) : _M_r(std::__addressof(static_cast<_Range&>(std::forward<_Tp>(__t)))) { } constexpr _Range& base() const { return *_M_r; } constexpr iterator_t<_Range> begin() const { return ranges::begin(*_M_r); } constexpr sentinel_t<_Range> end() const { return ranges::end(*_M_r); } constexpr bool empty() const requires requires { ranges::empty(*_M_r); } { return ranges::empty(*_M_r); } constexpr auto size() const requires sized_range<_Range> { return ranges::size(*_M_r); } constexpr auto data() const requires contiguous_range<_Range> { return ranges::data(*_M_r); } }; template ref_view(_Range&) -> ref_view<_Range>; template inline constexpr bool enable_borrowed_range> = true; template requires movable<_Range> && (!__detail::__is_initializer_list>) class owning_view : public view_interface> { private: _Range _M_r = _Range(); public: owning_view() requires default_initializable<_Range> = default; constexpr owning_view(_Range&& __t) noexcept(is_nothrow_move_constructible_v<_Range>) : _M_r(std::move(__t)) { } owning_view(owning_view&&) = default; owning_view& operator=(owning_view&&) = default; constexpr _Range& base() & noexcept { return _M_r; } constexpr const _Range& base() const& noexcept { return _M_r; } constexpr _Range&& base() && noexcept { return std::move(_M_r); } constexpr const _Range&& base() const&& noexcept { return std::move(_M_r); } constexpr iterator_t<_Range> begin() { return ranges::begin(_M_r); } constexpr sentinel_t<_Range> end() { return ranges::end(_M_r); } constexpr auto begin() const requires range { return ranges::begin(_M_r); } constexpr auto end() const requires range { return ranges::end(_M_r); } constexpr bool empty() requires requires { ranges::empty(_M_r); } { return ranges::empty(_M_r); } constexpr bool empty() const requires requires { ranges::empty(_M_r); } { return ranges::empty(_M_r); } constexpr auto size() requires sized_range<_Range> { return ranges::size(_M_r); } constexpr auto size() const requires sized_range { return ranges::size(_M_r); } constexpr auto data() requires contiguous_range<_Range> { return ranges::data(_M_r); } constexpr auto data() const requires contiguous_range { return ranges::data(_M_r); } }; template inline constexpr bool enable_borrowed_range> = enable_borrowed_range<_Tp>; namespace views { namespace __detail { template concept __can_ref_view = requires { ref_view{std::declval<_Range>()}; }; template concept __can_owning_view = requires { owning_view{std::declval<_Range>()}; }; } // namespace __detail struct _All : __adaptor::_RangeAdaptorClosure<_All> { template static constexpr bool _S_noexcept() { if constexpr (view>) return is_nothrow_constructible_v, _Range>; else if constexpr (__detail::__can_ref_view<_Range>) return true; else return noexcept(owning_view{std::declval<_Range>()}); } template requires view> || __detail::__can_ref_view<_Range> || __detail::__can_owning_view<_Range> constexpr auto operator() [[nodiscard]] (_Range&& __r) const noexcept(_S_noexcept<_Range>()) { if constexpr (view>) return std::forward<_Range>(__r); else if constexpr (__detail::__can_ref_view<_Range>) return ref_view{std::forward<_Range>(__r)}; else return owning_view{std::forward<_Range>(__r)}; } static constexpr bool _S_has_simple_call_op = true; }; inline constexpr _All all; template using all_t = decltype(all(std::declval<_Range>())); } // namespace views namespace __detail { template struct __non_propagating_cache { // When _Tp is not an object type (e.g. is a reference type), we make // __non_propagating_cache<_Tp> empty rather than ill-formed so that // users can easily conditionally declare data members with this type // (such as join_view::_M_inner). }; template requires is_object_v<_Tp> struct __non_propagating_cache<_Tp> : protected _Optional_base<_Tp> { __non_propagating_cache() = default; constexpr __non_propagating_cache(const __non_propagating_cache&) noexcept { } constexpr __non_propagating_cache(__non_propagating_cache&& __other) noexcept { __other._M_reset(); } constexpr __non_propagating_cache& operator=(const __non_propagating_cache& __other) noexcept { if (std::__addressof(__other) != this) this->_M_reset(); return *this; } constexpr __non_propagating_cache& operator=(__non_propagating_cache&& __other) noexcept { this->_M_reset(); __other._M_reset(); return *this; } constexpr __non_propagating_cache& operator=(_Tp __val) { this->_M_reset(); this->_M_payload._M_construct(std::move(__val)); return *this; } constexpr explicit operator bool() const noexcept { return this->_M_is_engaged(); } constexpr _Tp& operator*() noexcept { return this->_M_get(); } constexpr const _Tp& operator*() const noexcept { return this->_M_get(); } template constexpr _Tp& _M_emplace_deref(const _Iter& __i) { this->_M_reset(); auto __f = [] (auto& __x) { return *__x; }; this->_M_payload._M_apply(_Optional_func{__f}, __i); return this->_M_get(); } }; template struct _CachedPosition { constexpr bool _M_has_value() const { return false; } constexpr iterator_t<_Range> _M_get(const _Range&) const { __glibcxx_assert(false); __builtin_unreachable(); } constexpr void _M_set(const _Range&, const iterator_t<_Range>&) const { } }; template struct _CachedPosition<_Range> : protected __non_propagating_cache> { constexpr bool _M_has_value() const { return this->_M_is_engaged(); } constexpr iterator_t<_Range> _M_get(const _Range&) const { __glibcxx_assert(_M_has_value()); return **this; } constexpr void _M_set(const _Range&, const iterator_t<_Range>& __it) { __glibcxx_assert(!_M_has_value()); std::construct_at(std::__addressof(this->_M_payload._M_payload), in_place, __it); this->_M_payload._M_engaged = true; } }; template requires (sizeof(range_difference_t<_Range>) <= sizeof(iterator_t<_Range>)) struct _CachedPosition<_Range> { private: range_difference_t<_Range> _M_offset = -1; public: _CachedPosition() = default; constexpr _CachedPosition(const _CachedPosition&) = default; constexpr _CachedPosition(_CachedPosition&& __other) noexcept { *this = std::move(__other); } constexpr _CachedPosition& operator=(const _CachedPosition&) = default; constexpr _CachedPosition& operator=(_CachedPosition&& __other) noexcept { // Propagate the cached offset, but invalidate the source. _M_offset = __other._M_offset; __other._M_offset = -1; return *this; } constexpr bool _M_has_value() const { return _M_offset >= 0; } constexpr iterator_t<_Range> _M_get(_Range& __r) const { __glibcxx_assert(_M_has_value()); return ranges::begin(__r) + _M_offset; } constexpr void _M_set(_Range& __r, const iterator_t<_Range>& __it) { __glibcxx_assert(!_M_has_value()); _M_offset = __it - ranges::begin(__r); } }; } // namespace __detail namespace __detail { template struct __filter_view_iter_cat { }; template struct __filter_view_iter_cat<_Base> { private: static auto _S_iter_cat() { using _Cat = typename iterator_traits>::iterator_category; if constexpr (derived_from<_Cat, bidirectional_iterator_tag>) return bidirectional_iterator_tag{}; else if constexpr (derived_from<_Cat, forward_iterator_tag>) return forward_iterator_tag{}; else return _Cat{}; } public: using iterator_category = decltype(_S_iter_cat()); }; } // namespace __detail template> _Pred> requires view<_Vp> && is_object_v<_Pred> class filter_view : public view_interface> { private: struct _Sentinel; struct _Iterator : __detail::__filter_view_iter_cat<_Vp> { private: static constexpr auto _S_iter_concept() { if constexpr (bidirectional_range<_Vp>) return bidirectional_iterator_tag{}; else if constexpr (forward_range<_Vp>) return forward_iterator_tag{}; else return input_iterator_tag{}; } friend filter_view; using _Vp_iter = iterator_t<_Vp>; _Vp_iter _M_current = _Vp_iter(); filter_view* _M_parent = nullptr; public: using iterator_concept = decltype(_S_iter_concept()); // iterator_category defined in __filter_view_iter_cat using value_type = range_value_t<_Vp>; using difference_type = range_difference_t<_Vp>; _Iterator() requires default_initializable<_Vp_iter> = default; constexpr _Iterator(filter_view* __parent, _Vp_iter __current) : _M_current(std::move(__current)), _M_parent(__parent) { } constexpr const _Vp_iter& base() const & noexcept { return _M_current; } constexpr _Vp_iter base() && { return std::move(_M_current); } constexpr range_reference_t<_Vp> operator*() const { return *_M_current; } constexpr _Vp_iter operator->() const requires __detail::__has_arrow<_Vp_iter> && copyable<_Vp_iter> { return _M_current; } constexpr _Iterator& operator++() { _M_current = ranges::find_if(std::move(++_M_current), ranges::end(_M_parent->_M_base), std::ref(*_M_parent->_M_pred)); return *this; } constexpr void operator++(int) { ++*this; } constexpr _Iterator operator++(int) requires forward_range<_Vp> { auto __tmp = *this; ++*this; return __tmp; } constexpr _Iterator& operator--() requires bidirectional_range<_Vp> { do --_M_current; while (!std::__invoke(*_M_parent->_M_pred, *_M_current)); return *this; } constexpr _Iterator operator--(int) requires bidirectional_range<_Vp> { auto __tmp = *this; --*this; return __tmp; } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) requires equality_comparable<_Vp_iter> { return __x._M_current == __y._M_current; } friend constexpr range_rvalue_reference_t<_Vp> iter_move(const _Iterator& __i) noexcept(noexcept(ranges::iter_move(__i._M_current))) { return ranges::iter_move(__i._M_current); } friend constexpr void iter_swap(const _Iterator& __x, const _Iterator& __y) noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current))) requires indirectly_swappable<_Vp_iter> { ranges::iter_swap(__x._M_current, __y._M_current); } }; struct _Sentinel { private: sentinel_t<_Vp> _M_end = sentinel_t<_Vp>(); constexpr bool __equal(const _Iterator& __i) const { return __i._M_current == _M_end; } public: _Sentinel() = default; constexpr explicit _Sentinel(filter_view* __parent) : _M_end(ranges::end(__parent->_M_base)) { } constexpr sentinel_t<_Vp> base() const { return _M_end; } friend constexpr bool operator==(const _Iterator& __x, const _Sentinel& __y) { return __y.__equal(__x); } }; _Vp _M_base = _Vp(); [[no_unique_address]] __detail::__box<_Pred> _M_pred; [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin; public: filter_view() requires (default_initializable<_Vp> && default_initializable<_Pred>) = default; constexpr filter_view(_Vp __base, _Pred __pred) : _M_base(std::move(__base)), _M_pred(std::move(__pred)) { } constexpr _Vp base() const& requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } constexpr const _Pred& pred() const { return *_M_pred; } constexpr _Iterator begin() { if (_M_cached_begin._M_has_value()) return {this, _M_cached_begin._M_get(_M_base)}; __glibcxx_assert(_M_pred.has_value()); auto __it = ranges::find_if(ranges::begin(_M_base), ranges::end(_M_base), std::ref(*_M_pred)); _M_cached_begin._M_set(_M_base, __it); return {this, std::move(__it)}; } constexpr auto end() { if constexpr (common_range<_Vp>) return _Iterator{this, ranges::end(_M_base)}; else return _Sentinel{this}; } }; template filter_view(_Range&&, _Pred) -> filter_view, _Pred>; namespace views { namespace __detail { template concept __can_filter_view = requires { filter_view(std::declval<_Range>(), std::declval<_Pred>()); }; } // namespace __detail struct _Filter : __adaptor::_RangeAdaptor<_Filter> { template requires __detail::__can_filter_view<_Range, _Pred> constexpr auto operator() [[nodiscard]] (_Range&& __r, _Pred&& __p) const { return filter_view(std::forward<_Range>(__r), std::forward<_Pred>(__p)); } using _RangeAdaptor<_Filter>::operator(); static constexpr int _S_arity = 2; static constexpr bool _S_has_simple_extra_args = true; }; inline constexpr _Filter filter; } // namespace views #if __cpp_lib_ranges >= 202207L // C++ >= 23 template #else template #endif requires view<_Vp> && is_object_v<_Fp> && regular_invocable<_Fp&, range_reference_t<_Vp>> && std::__detail::__can_reference>> class transform_view : public view_interface> { private: template using _Base = __detail::__maybe_const_t<_Const, _Vp>; template struct __iter_cat { }; template requires forward_range<_Base<_Const>> struct __iter_cat<_Const> { private: static auto _S_iter_cat() { using _Base = transform_view::_Base<_Const>; using _Res = invoke_result_t<_Fp&, range_reference_t<_Base>>; if constexpr (is_lvalue_reference_v<_Res>) { using _Cat = typename iterator_traits>::iterator_category; if constexpr (derived_from<_Cat, contiguous_iterator_tag>) return random_access_iterator_tag{}; else return _Cat{}; } else return input_iterator_tag{}; } public: using iterator_category = decltype(_S_iter_cat()); }; template struct _Sentinel; template struct _Iterator : __iter_cat<_Const> { private: using _Parent = __detail::__maybe_const_t<_Const, transform_view>; using _Base = transform_view::_Base<_Const>; static auto _S_iter_concept() { if constexpr (random_access_range<_Base>) return random_access_iterator_tag{}; else if constexpr (bidirectional_range<_Base>) return bidirectional_iterator_tag{}; else if constexpr (forward_range<_Base>) return forward_iterator_tag{}; else return input_iterator_tag{}; } using _Base_iter = iterator_t<_Base>; _Base_iter _M_current = _Base_iter(); _Parent* _M_parent = nullptr; public: using iterator_concept = decltype(_S_iter_concept()); // iterator_category defined in __transform_view_iter_cat using value_type = remove_cvref_t>>; using difference_type = range_difference_t<_Base>; _Iterator() requires default_initializable<_Base_iter> = default; constexpr _Iterator(_Parent* __parent, _Base_iter __current) : _M_current(std::move(__current)), _M_parent(__parent) { } constexpr _Iterator(_Iterator __i) requires _Const && convertible_to, _Base_iter> : _M_current(std::move(__i._M_current)), _M_parent(__i._M_parent) { } constexpr const _Base_iter& base() const & noexcept { return _M_current; } constexpr _Base_iter base() && { return std::move(_M_current); } constexpr decltype(auto) operator*() const noexcept(noexcept(std::__invoke(*_M_parent->_M_fun, *_M_current))) { return std::__invoke(*_M_parent->_M_fun, *_M_current); } constexpr _Iterator& operator++() { ++_M_current; return *this; } constexpr void operator++(int) { ++_M_current; } constexpr _Iterator operator++(int) requires forward_range<_Base> { auto __tmp = *this; ++*this; return __tmp; } constexpr _Iterator& operator--() requires bidirectional_range<_Base> { --_M_current; return *this; } constexpr _Iterator operator--(int) requires bidirectional_range<_Base> { auto __tmp = *this; --*this; return __tmp; } constexpr _Iterator& operator+=(difference_type __n) requires random_access_range<_Base> { _M_current += __n; return *this; } constexpr _Iterator& operator-=(difference_type __n) requires random_access_range<_Base> { _M_current -= __n; return *this; } constexpr decltype(auto) operator[](difference_type __n) const requires random_access_range<_Base> { return std::__invoke(*_M_parent->_M_fun, _M_current[__n]); } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) requires equality_comparable<_Base_iter> { return __x._M_current == __y._M_current; } friend constexpr bool operator<(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return __x._M_current < __y._M_current; } friend constexpr bool operator>(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return __y < __x; } friend constexpr bool operator<=(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return !(__y < __x); } friend constexpr bool operator>=(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return !(__x < __y); } #ifdef __cpp_lib_three_way_comparison friend constexpr auto operator<=>(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> && three_way_comparable<_Base_iter> { return __x._M_current <=> __y._M_current; } #endif friend constexpr _Iterator operator+(_Iterator __i, difference_type __n) requires random_access_range<_Base> { return {__i._M_parent, __i._M_current + __n}; } friend constexpr _Iterator operator+(difference_type __n, _Iterator __i) requires random_access_range<_Base> { return {__i._M_parent, __i._M_current + __n}; } friend constexpr _Iterator operator-(_Iterator __i, difference_type __n) requires random_access_range<_Base> { return {__i._M_parent, __i._M_current - __n}; } // _GLIBCXX_RESOLVE_LIB_DEFECTS // 3483. transform_view::iterator's difference is overconstrained friend constexpr difference_type operator-(const _Iterator& __x, const _Iterator& __y) requires sized_sentinel_for, iterator_t<_Base>> { return __x._M_current - __y._M_current; } friend constexpr decltype(auto) iter_move(const _Iterator& __i) noexcept(noexcept(*__i)) { if constexpr (is_lvalue_reference_v) return std::move(*__i); else return *__i; } friend _Iterator; template friend struct _Sentinel; }; template struct _Sentinel { private: using _Parent = __detail::__maybe_const_t<_Const, transform_view>; using _Base = transform_view::_Base<_Const>; template constexpr auto __distance_from(const _Iterator<_Const2>& __i) const { return _M_end - __i._M_current; } template constexpr bool __equal(const _Iterator<_Const2>& __i) const { return __i._M_current == _M_end; } sentinel_t<_Base> _M_end = sentinel_t<_Base>(); public: _Sentinel() = default; constexpr explicit _Sentinel(sentinel_t<_Base> __end) : _M_end(__end) { } constexpr _Sentinel(_Sentinel __i) requires _Const && convertible_to, sentinel_t<_Base>> : _M_end(std::move(__i._M_end)) { } constexpr sentinel_t<_Base> base() const { return _M_end; } template requires sentinel_for, iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>> friend constexpr bool operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y) { return __y.__equal(__x); } template> requires sized_sentinel_for, iterator_t<_Base2>> friend constexpr range_difference_t<_Base2> operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y) { return -__y.__distance_from(__x); } template> requires sized_sentinel_for, iterator_t<_Base2>> friend constexpr range_difference_t<_Base2> operator-(const _Sentinel& __y, const _Iterator<_Const2>& __x) { return __y.__distance_from(__x); } friend _Sentinel; }; _Vp _M_base = _Vp(); [[no_unique_address]] __detail::__box<_Fp> _M_fun; public: transform_view() requires (default_initializable<_Vp> && default_initializable<_Fp>) = default; constexpr transform_view(_Vp __base, _Fp __fun) : _M_base(std::move(__base)), _M_fun(std::move(__fun)) { } constexpr _Vp base() const& requires copy_constructible<_Vp> { return _M_base ; } constexpr _Vp base() && { return std::move(_M_base); } constexpr _Iterator begin() { return _Iterator{this, ranges::begin(_M_base)}; } constexpr _Iterator begin() const requires range && regular_invocable> { return _Iterator{this, ranges::begin(_M_base)}; } constexpr _Sentinel end() { return _Sentinel{ranges::end(_M_base)}; } constexpr _Iterator end() requires common_range<_Vp> { return _Iterator{this, ranges::end(_M_base)}; } constexpr _Sentinel end() const requires range && regular_invocable> { return _Sentinel{ranges::end(_M_base)}; } constexpr _Iterator end() const requires common_range && regular_invocable> { return _Iterator{this, ranges::end(_M_base)}; } constexpr auto size() requires sized_range<_Vp> { return ranges::size(_M_base); } constexpr auto size() const requires sized_range { return ranges::size(_M_base); } }; template transform_view(_Range&&, _Fp) -> transform_view, _Fp>; namespace views { namespace __detail { template concept __can_transform_view = requires { transform_view(std::declval<_Range>(), std::declval<_Fp>()); }; } // namespace __detail struct _Transform : __adaptor::_RangeAdaptor<_Transform> { template requires __detail::__can_transform_view<_Range, _Fp> constexpr auto operator() [[nodiscard]] (_Range&& __r, _Fp&& __f) const { return transform_view(std::forward<_Range>(__r), std::forward<_Fp>(__f)); } using _RangeAdaptor<_Transform>::operator(); static constexpr int _S_arity = 2; static constexpr bool _S_has_simple_extra_args = true; }; inline constexpr _Transform transform; } // namespace views template class take_view : public view_interface> { private: template using _CI = counted_iterator< iterator_t<__detail::__maybe_const_t<_Const, _Vp>>>; template struct _Sentinel { private: using _Base = __detail::__maybe_const_t<_Const, _Vp>; sentinel_t<_Base> _M_end = sentinel_t<_Base>(); public: _Sentinel() = default; constexpr explicit _Sentinel(sentinel_t<_Base> __end) : _M_end(__end) { } constexpr _Sentinel(_Sentinel __s) requires _Const && convertible_to, sentinel_t<_Base>> : _M_end(std::move(__s._M_end)) { } constexpr sentinel_t<_Base> base() const { return _M_end; } friend constexpr bool operator==(const _CI<_Const>& __y, const _Sentinel& __x) { return __y.count() == 0 || __y.base() == __x._M_end; } template> requires sentinel_for, iterator_t<_Base2>> friend constexpr bool operator==(const _CI<_OtherConst>& __y, const _Sentinel& __x) { return __y.count() == 0 || __y.base() == __x._M_end; } friend _Sentinel; }; _Vp _M_base = _Vp(); range_difference_t<_Vp> _M_count = 0; public: take_view() requires default_initializable<_Vp> = default; constexpr take_view(_Vp __base, range_difference_t<_Vp> __count) : _M_base(std::move(__base)), _M_count(std::move(__count)) { } constexpr _Vp base() const& requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } constexpr auto begin() requires (!__detail::__simple_view<_Vp>) { if constexpr (sized_range<_Vp>) { if constexpr (random_access_range<_Vp>) return ranges::begin(_M_base); else { auto __sz = size(); return counted_iterator(ranges::begin(_M_base), __sz); } } else return counted_iterator(ranges::begin(_M_base), _M_count); } constexpr auto begin() const requires range { if constexpr (sized_range) { if constexpr (random_access_range) return ranges::begin(_M_base); else { auto __sz = size(); return counted_iterator(ranges::begin(_M_base), __sz); } } else return counted_iterator(ranges::begin(_M_base), _M_count); } constexpr auto end() requires (!__detail::__simple_view<_Vp>) { if constexpr (sized_range<_Vp>) { if constexpr (random_access_range<_Vp>) return ranges::begin(_M_base) + size(); else return default_sentinel; } else return _Sentinel{ranges::end(_M_base)}; } constexpr auto end() const requires range { if constexpr (sized_range) { if constexpr (random_access_range) return ranges::begin(_M_base) + size(); else return default_sentinel; } else return _Sentinel{ranges::end(_M_base)}; } constexpr auto size() requires sized_range<_Vp> { auto __n = ranges::size(_M_base); return std::min(__n, static_cast(_M_count)); } constexpr auto size() const requires sized_range { auto __n = ranges::size(_M_base); return std::min(__n, static_cast(_M_count)); } }; // _GLIBCXX_RESOLVE_LIB_DEFECTS // 3447. Deduction guides for take_view and drop_view have different // constraints template take_view(_Range&&, range_difference_t<_Range>) -> take_view>; template inline constexpr bool enable_borrowed_range> = enable_borrowed_range<_Tp>; namespace views { namespace __detail { template inline constexpr bool __is_empty_view = false; template inline constexpr bool __is_empty_view> = true; template inline constexpr bool __is_basic_string_view = false; template inline constexpr bool __is_basic_string_view> = true; template inline constexpr bool __is_subrange = false; template inline constexpr bool __is_subrange> = true; template inline constexpr bool __is_iota_view = false; template inline constexpr bool __is_iota_view> = true; template inline constexpr bool __is_repeat_view = false; template constexpr auto __take_of_repeat_view(_Range&&, range_difference_t<_Range>); // defined later template concept __can_take_view = requires { take_view(std::declval<_Range>(), std::declval<_Dp>()); }; } // namespace __detail struct _Take : __adaptor::_RangeAdaptor<_Take> { template> requires __detail::__can_take_view<_Range, _Dp> constexpr auto operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const { using _Tp = remove_cvref_t<_Range>; if constexpr (__detail::__is_empty_view<_Tp>) return _Tp(); else if constexpr (random_access_range<_Tp> && sized_range<_Tp> && (std::__detail::__is_span<_Tp> || __detail::__is_basic_string_view<_Tp> || __detail::__is_subrange<_Tp> || __detail::__is_iota_view<_Tp>)) { __n = std::min<_Dp>(ranges::distance(__r), __n); auto __begin = ranges::begin(__r); auto __end = __begin + __n; if constexpr (std::__detail::__is_span<_Tp>) return span(__begin, __end); else if constexpr (__detail::__is_basic_string_view<_Tp>) return _Tp(__begin, __end); else if constexpr (__detail::__is_subrange<_Tp>) return subrange>(__begin, __end); else return iota_view(*__begin, *__end); } else if constexpr (__detail::__is_repeat_view<_Tp>) return __detail::__take_of_repeat_view(std::forward<_Range>(__r), __n); else return take_view(std::forward<_Range>(__r), __n); } using _RangeAdaptor<_Take>::operator(); static constexpr int _S_arity = 2; // The count argument of views::take is not always simple -- it can be // e.g. a move-only class that's implicitly convertible to the difference // type. But an integer-like count argument is surely simple. template static constexpr bool _S_has_simple_extra_args = ranges::__detail::__is_integer_like<_Tp>; }; inline constexpr _Take take; } // namespace views template requires input_range<_Vp> && is_object_v<_Pred> && indirect_unary_predicate> class take_while_view : public view_interface> { template struct _Sentinel { private: using _Base = __detail::__maybe_const_t<_Const, _Vp>; sentinel_t<_Base> _M_end = sentinel_t<_Base>(); const _Pred* _M_pred = nullptr; public: _Sentinel() = default; constexpr explicit _Sentinel(sentinel_t<_Base> __end, const _Pred* __pred) : _M_end(__end), _M_pred(__pred) { } constexpr _Sentinel(_Sentinel __s) requires _Const && convertible_to, sentinel_t<_Base>> : _M_end(__s._M_end), _M_pred(__s._M_pred) { } constexpr sentinel_t<_Base> base() const { return _M_end; } friend constexpr bool operator==(const iterator_t<_Base>& __x, const _Sentinel& __y) { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); } template> requires sentinel_for, iterator_t<_Base2>> friend constexpr bool operator==(const iterator_t<_Base2>& __x, const _Sentinel& __y) { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); } friend _Sentinel; }; _Vp _M_base = _Vp(); [[no_unique_address]] __detail::__box<_Pred> _M_pred; public: take_while_view() requires (default_initializable<_Vp> && default_initializable<_Pred>) = default; constexpr take_while_view(_Vp __base, _Pred __pred) : _M_base(std::move(__base)), _M_pred(std::move(__pred)) { } constexpr _Vp base() const& requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } constexpr const _Pred& pred() const { return *_M_pred; } constexpr auto begin() requires (!__detail::__simple_view<_Vp>) { return ranges::begin(_M_base); } constexpr auto begin() const requires range && indirect_unary_predicate> { return ranges::begin(_M_base); } constexpr auto end() requires (!__detail::__simple_view<_Vp>) { return _Sentinel(ranges::end(_M_base), std::__addressof(*_M_pred)); } constexpr auto end() const requires range && indirect_unary_predicate> { return _Sentinel(ranges::end(_M_base), std::__addressof(*_M_pred)); } }; template take_while_view(_Range&&, _Pred) -> take_while_view, _Pred>; namespace views { namespace __detail { template concept __can_take_while_view = requires { take_while_view(std::declval<_Range>(), std::declval<_Pred>()); }; } // namespace __detail struct _TakeWhile : __adaptor::_RangeAdaptor<_TakeWhile> { template requires __detail::__can_take_while_view<_Range, _Pred> constexpr auto operator() [[nodiscard]] (_Range&& __r, _Pred&& __p) const { return take_while_view(std::forward<_Range>(__r), std::forward<_Pred>(__p)); } using _RangeAdaptor<_TakeWhile>::operator(); static constexpr int _S_arity = 2; static constexpr bool _S_has_simple_extra_args = true; }; inline constexpr _TakeWhile take_while; } // namespace views template class drop_view : public view_interface> { private: _Vp _M_base = _Vp(); range_difference_t<_Vp> _M_count = 0; // ranges::next(begin(base), count, end(base)) is O(1) if _Vp satisfies // both random_access_range and sized_range. Otherwise, cache its result. static constexpr bool _S_needs_cached_begin = !(random_access_range && sized_range); [[no_unique_address]] __detail::__maybe_present_t<_S_needs_cached_begin, __detail::_CachedPosition<_Vp>> _M_cached_begin; public: drop_view() requires default_initializable<_Vp> = default; constexpr drop_view(_Vp __base, range_difference_t<_Vp> __count) : _M_base(std::move(__base)), _M_count(__count) { __glibcxx_assert(__count >= 0); } constexpr _Vp base() const& requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } // This overload is disabled for simple views with constant-time begin(). constexpr auto begin() requires (!(__detail::__simple_view<_Vp> && random_access_range && sized_range)) { if constexpr (_S_needs_cached_begin) if (_M_cached_begin._M_has_value()) return _M_cached_begin._M_get(_M_base); auto __it = ranges::next(ranges::begin(_M_base), _M_count, ranges::end(_M_base)); if constexpr (_S_needs_cached_begin) _M_cached_begin._M_set(_M_base, __it); return __it; } // _GLIBCXX_RESOLVE_LIB_DEFECTS // 3482. drop_view's const begin should additionally require sized_range constexpr auto begin() const requires random_access_range && sized_range { return ranges::next(ranges::begin(_M_base), _M_count, ranges::end(_M_base)); } constexpr auto end() requires (!__detail::__simple_view<_Vp>) { return ranges::end(_M_base); } constexpr auto end() const requires range { return ranges::end(_M_base); } constexpr auto size() requires sized_range<_Vp> { const auto __s = ranges::size(_M_base); const auto __c = static_cast(_M_count); return __s < __c ? 0 : __s - __c; } constexpr auto size() const requires sized_range { const auto __s = ranges::size(_M_base); const auto __c = static_cast(_M_count); return __s < __c ? 0 : __s - __c; } }; template drop_view(_Range&&, range_difference_t<_Range>) -> drop_view>; template inline constexpr bool enable_borrowed_range> = enable_borrowed_range<_Tp>; namespace views { namespace __detail { template constexpr auto __drop_of_repeat_view(_Range&&, range_difference_t<_Range>); // defined later template concept __can_drop_view = requires { drop_view(std::declval<_Range>(), std::declval<_Dp>()); }; } // namespace __detail struct _Drop : __adaptor::_RangeAdaptor<_Drop> { template> requires __detail::__can_drop_view<_Range, _Dp> constexpr auto operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const { using _Tp = remove_cvref_t<_Range>; if constexpr (__detail::__is_empty_view<_Tp>) return _Tp(); else if constexpr (random_access_range<_Tp> && sized_range<_Tp> && (std::__detail::__is_span<_Tp> || __detail::__is_basic_string_view<_Tp> || __detail::__is_iota_view<_Tp> || __detail::__is_subrange<_Tp>)) { __n = std::min<_Dp>(ranges::distance(__r), __n); auto __begin = ranges::begin(__r) + __n; auto __end = ranges::end(__r); if constexpr (std::__detail::__is_span<_Tp>) return span(__begin, __end); else if constexpr (__detail::__is_subrange<_Tp>) { if constexpr (_Tp::_S_store_size) { using ranges::__detail::__to_unsigned_like; auto __m = ranges::distance(__r) - __n; return _Tp(__begin, __end, __to_unsigned_like(__m)); } else return _Tp(__begin, __end); } else return _Tp(__begin, __end); } else if constexpr (__detail::__is_repeat_view<_Tp>) return __detail::__drop_of_repeat_view(std::forward<_Range>(__r), __n); else return drop_view(std::forward<_Range>(__r), __n); } using _RangeAdaptor<_Drop>::operator(); static constexpr int _S_arity = 2; template static constexpr bool _S_has_simple_extra_args = _Take::_S_has_simple_extra_args<_Tp>; }; inline constexpr _Drop drop; } // namespace views template requires input_range<_Vp> && is_object_v<_Pred> && indirect_unary_predicate> class drop_while_view : public view_interface> { private: _Vp _M_base = _Vp(); [[no_unique_address]] __detail::__box<_Pred> _M_pred; [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin; public: drop_while_view() requires (default_initializable<_Vp> && default_initializable<_Pred>) = default; constexpr drop_while_view(_Vp __base, _Pred __pred) : _M_base(std::move(__base)), _M_pred(std::move(__pred)) { } constexpr _Vp base() const& requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } constexpr const _Pred& pred() const { return *_M_pred; } constexpr auto begin() { if (_M_cached_begin._M_has_value()) return _M_cached_begin._M_get(_M_base); __glibcxx_assert(_M_pred.has_value()); auto __it = ranges::find_if_not(ranges::begin(_M_base), ranges::end(_M_base), std::cref(*_M_pred)); _M_cached_begin._M_set(_M_base, __it); return __it; } constexpr auto end() { return ranges::end(_M_base); } }; template drop_while_view(_Range&&, _Pred) -> drop_while_view, _Pred>; template inline constexpr bool enable_borrowed_range> = enable_borrowed_range<_Tp>; namespace views { namespace __detail { template concept __can_drop_while_view = requires { drop_while_view(std::declval<_Range>(), std::declval<_Pred>()); }; } // namespace __detail struct _DropWhile : __adaptor::_RangeAdaptor<_DropWhile> { template requires __detail::__can_drop_while_view<_Range, _Pred> constexpr auto operator() [[nodiscard]] (_Range&& __r, _Pred&& __p) const { return drop_while_view(std::forward<_Range>(__r), std::forward<_Pred>(__p)); } using _RangeAdaptor<_DropWhile>::operator(); static constexpr int _S_arity = 2; static constexpr bool _S_has_simple_extra_args = true; }; inline constexpr _DropWhile drop_while; } // namespace views namespace __detail { template constexpr _Tp& __as_lvalue(_Tp&& __t) { return static_cast<_Tp&>(__t); } } // namespace __detail template requires view<_Vp> && input_range> class join_view : public view_interface> { private: using _InnerRange = range_reference_t<_Vp>; template using _Base = __detail::__maybe_const_t<_Const, _Vp>; template using _Outer_iter = iterator_t<_Base<_Const>>; template using _Inner_iter = iterator_t>>; template static constexpr bool _S_ref_is_glvalue = is_reference_v>>; template struct __iter_cat { }; template requires _S_ref_is_glvalue<_Const> && forward_range<_Base<_Const>> && forward_range>> struct __iter_cat<_Const> { private: static constexpr auto _S_iter_cat() { using _Outer_iter = join_view::_Outer_iter<_Const>; using _Inner_iter = join_view::_Inner_iter<_Const>; using _OuterCat = typename iterator_traits<_Outer_iter>::iterator_category; using _InnerCat = typename iterator_traits<_Inner_iter>::iterator_category; if constexpr (derived_from<_OuterCat, bidirectional_iterator_tag> && derived_from<_InnerCat, bidirectional_iterator_tag> && common_range>>) return bidirectional_iterator_tag{}; else if constexpr (derived_from<_OuterCat, forward_iterator_tag> && derived_from<_InnerCat, forward_iterator_tag>) return forward_iterator_tag{}; else return input_iterator_tag{}; } public: using iterator_category = decltype(_S_iter_cat()); }; template struct _Sentinel; template struct _Iterator : __iter_cat<_Const> { private: using _Parent = __detail::__maybe_const_t<_Const, join_view>; using _Base = join_view::_Base<_Const>; friend join_view; static constexpr bool _S_ref_is_glvalue = join_view::_S_ref_is_glvalue<_Const>; constexpr void _M_satisfy() { auto __update_inner = [this] (const iterator_t<_Base>& __x) -> auto&& { if constexpr (_S_ref_is_glvalue) return *__x; else return _M_parent->_M_inner._M_emplace_deref(__x); }; _Outer_iter& __outer = _M_get_outer(); for (; __outer != ranges::end(_M_parent->_M_base); ++__outer) { auto&& __inner = __update_inner(__outer); _M_inner = ranges::begin(__inner); if (_M_inner != ranges::end(__inner)) return; } if constexpr (_S_ref_is_glvalue) _M_inner.reset(); } static constexpr auto _S_iter_concept() { if constexpr (_S_ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range> && common_range>) return bidirectional_iterator_tag{}; else if constexpr (_S_ref_is_glvalue && forward_range<_Base> && forward_range>) return forward_iterator_tag{}; else return input_iterator_tag{}; } using _Outer_iter = join_view::_Outer_iter<_Const>; using _Inner_iter = join_view::_Inner_iter<_Const>; constexpr _Outer_iter& _M_get_outer() { if constexpr (forward_range<_Base>) return _M_outer; else return *_M_parent->_M_outer; } constexpr const _Outer_iter& _M_get_outer() const { if constexpr (forward_range<_Base>) return _M_outer; else return *_M_parent->_M_outer; } constexpr _Iterator(_Parent* __parent, _Outer_iter __outer) requires forward_range<_Base> : _M_outer(std::move(__outer)), _M_parent(__parent) { _M_satisfy(); } constexpr explicit _Iterator(_Parent* __parent) requires (!forward_range<_Base>) : _M_parent(__parent) { _M_satisfy(); } [[no_unique_address]] __detail::__maybe_present_t, _Outer_iter> _M_outer; optional<_Inner_iter> _M_inner; _Parent* _M_parent = nullptr; public: using iterator_concept = decltype(_S_iter_concept()); // iterator_category defined in __join_view_iter_cat using value_type = range_value_t>; using difference_type = common_type_t, range_difference_t>>; _Iterator() = default; constexpr _Iterator(_Iterator __i) requires _Const && convertible_to, _Outer_iter> && convertible_to, _Inner_iter> : _M_outer(std::move(__i._M_outer)), _M_inner(std::move(__i._M_inner)), _M_parent(__i._M_parent) { } constexpr decltype(auto) operator*() const { return **_M_inner; } // _GLIBCXX_RESOLVE_LIB_DEFECTS // 3500. join_view::iterator::operator->() is bogus constexpr _Inner_iter operator->() const requires __detail::__has_arrow<_Inner_iter> && copyable<_Inner_iter> { return *_M_inner; } constexpr _Iterator& operator++() { auto&& __inner_range = [this] () -> auto&& { if constexpr (_S_ref_is_glvalue) return *_M_get_outer(); else return *_M_parent->_M_inner; }(); if (++*_M_inner == ranges::end(__inner_range)) { ++_M_get_outer(); _M_satisfy(); } return *this; } constexpr void operator++(int) { ++*this; } constexpr _Iterator operator++(int) requires _S_ref_is_glvalue && forward_range<_Base> && forward_range> { auto __tmp = *this; ++*this; return __tmp; } constexpr _Iterator& operator--() requires _S_ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range> && common_range> { if (_M_outer == ranges::end(_M_parent->_M_base)) _M_inner = ranges::end(__detail::__as_lvalue(*--_M_outer)); while (*_M_inner == ranges::begin(__detail::__as_lvalue(*_M_outer))) *_M_inner = ranges::end(__detail::__as_lvalue(*--_M_outer)); --*_M_inner; return *this; } constexpr _Iterator operator--(int) requires _S_ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range> && common_range> { auto __tmp = *this; --*this; return __tmp; } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) requires _S_ref_is_glvalue && forward_range<_Base> && equality_comparable<_Inner_iter> { return (__x._M_outer == __y._M_outer && __x._M_inner == __y._M_inner); } friend constexpr decltype(auto) iter_move(const _Iterator& __i) noexcept(noexcept(ranges::iter_move(*__i._M_inner))) { return ranges::iter_move(*__i._M_inner); } friend constexpr void iter_swap(const _Iterator& __x, const _Iterator& __y) noexcept(noexcept(ranges::iter_swap(*__x._M_inner, *__y._M_inner))) requires indirectly_swappable<_Inner_iter> { return ranges::iter_swap(*__x._M_inner, *__y._M_inner); } friend _Iterator; template friend struct _Sentinel; }; template struct _Sentinel { private: using _Parent = __detail::__maybe_const_t<_Const, join_view>; using _Base = join_view::_Base<_Const>; template constexpr bool __equal(const _Iterator<_Const2>& __i) const { return __i._M_get_outer() == _M_end; } sentinel_t<_Base> _M_end = sentinel_t<_Base>(); public: _Sentinel() = default; constexpr explicit _Sentinel(_Parent* __parent) : _M_end(ranges::end(__parent->_M_base)) { } constexpr _Sentinel(_Sentinel __s) requires _Const && convertible_to, sentinel_t<_Base>> : _M_end(std::move(__s._M_end)) { } template requires sentinel_for, iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>> friend constexpr bool operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y) { return __y.__equal(__x); } friend _Sentinel; }; _Vp _M_base = _Vp(); [[no_unique_address]] __detail::__maybe_present_t, __detail::__non_propagating_cache>> _M_outer; [[no_unique_address]] __detail::__non_propagating_cache> _M_inner; public: join_view() requires default_initializable<_Vp> = default; constexpr explicit join_view(_Vp __base) : _M_base(std::move(__base)) { } constexpr _Vp base() const& requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } constexpr auto begin() { if constexpr (forward_range<_Vp>) { constexpr bool __use_const = (__detail::__simple_view<_Vp> && is_reference_v>); return _Iterator<__use_const>{this, ranges::begin(_M_base)}; } else { _M_outer = ranges::begin(_M_base); return _Iterator{this}; } } constexpr auto begin() const requires forward_range && is_reference_v> && input_range> { return _Iterator{this, ranges::begin(_M_base)}; } constexpr auto end() { if constexpr (forward_range<_Vp> && is_reference_v<_InnerRange> && forward_range<_InnerRange> && common_range<_Vp> && common_range<_InnerRange>) return _Iterator<__detail::__simple_view<_Vp>>{this, ranges::end(_M_base)}; else return _Sentinel<__detail::__simple_view<_Vp>>{this}; } constexpr auto end() const requires forward_range && is_reference_v> && input_range> { if constexpr (is_reference_v> && forward_range> && common_range && common_range>) return _Iterator{this, ranges::end(_M_base)}; else return _Sentinel{this}; } }; template explicit join_view(_Range&&) -> join_view>; namespace views { namespace __detail { template concept __can_join_view = requires { join_view>{std::declval<_Range>()}; }; } // namespace __detail struct _Join : __adaptor::_RangeAdaptorClosure<_Join> { template requires __detail::__can_join_view<_Range> constexpr auto operator() [[nodiscard]] (_Range&& __r) const { // _GLIBCXX_RESOLVE_LIB_DEFECTS // 3474. Nesting join_views is broken because of CTAD return join_view>{std::forward<_Range>(__r)}; } static constexpr bool _S_has_simple_call_op = true; }; inline constexpr _Join join; } // namespace views namespace __detail { template struct __require_constant; template concept __tiny_range = sized_range<_Range> && requires { typename __require_constant::size()>; } && (remove_reference_t<_Range>::size() <= 1); template struct __lazy_split_view_outer_iter_cat { }; template struct __lazy_split_view_outer_iter_cat<_Base> { using iterator_category = input_iterator_tag; }; template struct __lazy_split_view_inner_iter_cat { }; template struct __lazy_split_view_inner_iter_cat<_Base> { private: static constexpr auto _S_iter_cat() { using _Cat = typename iterator_traits>::iterator_category; if constexpr (derived_from<_Cat, forward_iterator_tag>) return forward_iterator_tag{}; else return _Cat{}; } public: using iterator_category = decltype(_S_iter_cat()); }; } template requires view<_Vp> && view<_Pattern> && indirectly_comparable, iterator_t<_Pattern>, ranges::equal_to> && (forward_range<_Vp> || __detail::__tiny_range<_Pattern>) class lazy_split_view : public view_interface> { private: template using _Base = __detail::__maybe_const_t<_Const, _Vp>; template struct _InnerIter; template struct _OuterIter : __detail::__lazy_split_view_outer_iter_cat<_Base<_Const>> { private: using _Parent = __detail::__maybe_const_t<_Const, lazy_split_view>; using _Base = lazy_split_view::_Base<_Const>; constexpr bool __at_end() const { return __current() == ranges::end(_M_parent->_M_base) && !_M_trailing_empty; } // [range.lazy.split.outer] p1 // Many of the following specifications refer to the notional member // current of outer-iterator. current is equivalent to current_ if // V models forward_range, and parent_->current_ otherwise. constexpr auto& __current() noexcept { if constexpr (forward_range<_Vp>) return _M_current; else return *_M_parent->_M_current; } constexpr auto& __current() const noexcept { if constexpr (forward_range<_Vp>) return _M_current; else return *_M_parent->_M_current; } _Parent* _M_parent = nullptr; [[no_unique_address]] __detail::__maybe_present_t, iterator_t<_Base>> _M_current; bool _M_trailing_empty = false; public: using iterator_concept = __conditional_t, forward_iterator_tag, input_iterator_tag>; // iterator_category defined in __lazy_split_view_outer_iter_cat using difference_type = range_difference_t<_Base>; struct value_type : view_interface { private: _OuterIter _M_i = _OuterIter(); public: value_type() = default; constexpr explicit value_type(_OuterIter __i) : _M_i(std::move(__i)) { } constexpr _InnerIter<_Const> begin() const { return _InnerIter<_Const>{_M_i}; } constexpr default_sentinel_t end() const noexcept { return default_sentinel; } }; _OuterIter() = default; constexpr explicit _OuterIter(_Parent* __parent) requires (!forward_range<_Base>) : _M_parent(__parent) { } constexpr _OuterIter(_Parent* __parent, iterator_t<_Base> __current) requires forward_range<_Base> : _M_parent(__parent), _M_current(std::move(__current)) { } constexpr _OuterIter(_OuterIter __i) requires _Const && convertible_to, iterator_t<_Base>> : _M_parent(__i._M_parent), _M_current(std::move(__i._M_current)), _M_trailing_empty(__i._M_trailing_empty) { } constexpr value_type operator*() const { return value_type{*this}; } constexpr _OuterIter& operator++() { // _GLIBCXX_RESOLVE_LIB_DEFECTS // 3505. lazy_split_view::outer-iterator::operator++ misspecified const auto __end = ranges::end(_M_parent->_M_base); if (__current() == __end) { _M_trailing_empty = false; return *this; } const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern}; if (__pbegin == __pend) ++__current(); else if constexpr (__detail::__tiny_range<_Pattern>) { __current() = ranges::find(std::move(__current()), __end, *__pbegin); if (__current() != __end) { ++__current(); if (__current() == __end) _M_trailing_empty = true; } } else do { auto [__b, __p] = ranges::mismatch(__current(), __end, __pbegin, __pend); if (__p == __pend) { __current() = __b; if (__current() == __end) _M_trailing_empty = true; break; } } while (++__current() != __end); return *this; } constexpr decltype(auto) operator++(int) { if constexpr (forward_range<_Base>) { auto __tmp = *this; ++*this; return __tmp; } else ++*this; } friend constexpr bool operator==(const _OuterIter& __x, const _OuterIter& __y) requires forward_range<_Base> { return __x._M_current == __y._M_current && __x._M_trailing_empty == __y._M_trailing_empty; } friend constexpr bool operator==(const _OuterIter& __x, default_sentinel_t) { return __x.__at_end(); }; friend _OuterIter; friend _InnerIter<_Const>; }; template struct _InnerIter : __detail::__lazy_split_view_inner_iter_cat<_Base<_Const>> { private: using _Base = lazy_split_view::_Base<_Const>; constexpr bool __at_end() const { auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern}; auto __end = ranges::end(_M_i._M_parent->_M_base); if constexpr (__detail::__tiny_range<_Pattern>) { const auto& __cur = _M_i_current(); if (__cur == __end) return true; if (__pcur == __pend) return _M_incremented; return *__cur == *__pcur; } else { auto __cur = _M_i_current(); if (__cur == __end) return true; if (__pcur == __pend) return _M_incremented; do { if (*__cur != *__pcur) return false; if (++__pcur == __pend) return true; } while (++__cur != __end); return false; } } constexpr auto& _M_i_current() noexcept { return _M_i.__current(); } constexpr auto& _M_i_current() const noexcept { return _M_i.__current(); } _OuterIter<_Const> _M_i = _OuterIter<_Const>(); bool _M_incremented = false; public: using iterator_concept = typename _OuterIter<_Const>::iterator_concept; // iterator_category defined in __lazy_split_view_inner_iter_cat using value_type = range_value_t<_Base>; using difference_type = range_difference_t<_Base>; _InnerIter() = default; constexpr explicit _InnerIter(_OuterIter<_Const> __i) : _M_i(std::move(__i)) { } constexpr const iterator_t<_Base>& base() const& noexcept { return _M_i_current(); } constexpr iterator_t<_Base> base() && requires forward_range<_Vp> { return std::move(_M_i_current()); } constexpr decltype(auto) operator*() const { return *_M_i_current(); } constexpr _InnerIter& operator++() { _M_incremented = true; if constexpr (!forward_range<_Base>) if constexpr (_Pattern::size() == 0) return *this; ++_M_i_current(); return *this; } constexpr decltype(auto) operator++(int) { if constexpr (forward_range<_Base>) { auto __tmp = *this; ++*this; return __tmp; } else ++*this; } friend constexpr bool operator==(const _InnerIter& __x, const _InnerIter& __y) requires forward_range<_Base> { return __x._M_i == __y._M_i; } friend constexpr bool operator==(const _InnerIter& __x, default_sentinel_t) { return __x.__at_end(); } friend constexpr decltype(auto) iter_move(const _InnerIter& __i) noexcept(noexcept(ranges::iter_move(__i._M_i_current()))) { return ranges::iter_move(__i._M_i_current()); } friend constexpr void iter_swap(const _InnerIter& __x, const _InnerIter& __y) noexcept(noexcept(ranges::iter_swap(__x._M_i_current(), __y._M_i_current()))) requires indirectly_swappable> { ranges::iter_swap(__x._M_i_current(), __y._M_i_current()); } }; _Vp _M_base = _Vp(); _Pattern _M_pattern = _Pattern(); [[no_unique_address]] __detail::__maybe_present_t, __detail::__non_propagating_cache>> _M_current; public: lazy_split_view() requires (default_initializable<_Vp> && default_initializable<_Pattern>) = default; constexpr lazy_split_view(_Vp __base, _Pattern __pattern) : _M_base(std::move(__base)), _M_pattern(std::move(__pattern)) { } template requires constructible_from<_Vp, views::all_t<_Range>> && constructible_from<_Pattern, single_view>> constexpr lazy_split_view(_Range&& __r, range_value_t<_Range> __e) : _M_base(views::all(std::forward<_Range>(__r))), _M_pattern(views::single(std::move(__e))) { } constexpr _Vp base() const& requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } constexpr auto begin() { if constexpr (forward_range<_Vp>) { constexpr bool __simple = __detail::__simple_view<_Vp> && __detail::__simple_view<_Pattern>; return _OuterIter<__simple>{this, ranges::begin(_M_base)}; } else { _M_current = ranges::begin(_M_base); return _OuterIter{this}; } } constexpr auto begin() const requires forward_range<_Vp> && forward_range { return _OuterIter{this, ranges::begin(_M_base)}; } constexpr auto end() requires forward_range<_Vp> && common_range<_Vp> { constexpr bool __simple = __detail::__simple_view<_Vp> && __detail::__simple_view<_Pattern>; return _OuterIter<__simple>{this, ranges::end(_M_base)}; } constexpr auto end() const { if constexpr (forward_range<_Vp> && forward_range && common_range) return _OuterIter{this, ranges::end(_M_base)}; else return default_sentinel; } }; template lazy_split_view(_Range&&, _Pattern&&) -> lazy_split_view, views::all_t<_Pattern>>; template lazy_split_view(_Range&&, range_value_t<_Range>) -> lazy_split_view, single_view>>; namespace views { namespace __detail { template concept __can_lazy_split_view = requires { lazy_split_view(std::declval<_Range>(), std::declval<_Pattern>()); }; } // namespace __detail struct _LazySplit : __adaptor::_RangeAdaptor<_LazySplit> { template requires __detail::__can_lazy_split_view<_Range, _Pattern> constexpr auto operator() [[nodiscard]] (_Range&& __r, _Pattern&& __f) const { return lazy_split_view(std::forward<_Range>(__r), std::forward<_Pattern>(__f)); } using _RangeAdaptor<_LazySplit>::operator(); static constexpr int _S_arity = 2; // The pattern argument of views::lazy_split is not always simple -- it can be // a non-view range, the value category of which affects whether the call // is well-formed. But a scalar or a view pattern argument is surely // simple. template static constexpr bool _S_has_simple_extra_args = is_scalar_v<_Pattern> || (view<_Pattern> && copy_constructible<_Pattern>); }; inline constexpr _LazySplit lazy_split; } // namespace views template requires view<_Vp> && view<_Pattern> && indirectly_comparable, iterator_t<_Pattern>, ranges::equal_to> class split_view : public view_interface> { private: _Vp _M_base = _Vp(); _Pattern _M_pattern = _Pattern(); __detail::__non_propagating_cache>> _M_cached_begin; struct _Iterator; struct _Sentinel; public: split_view() requires (default_initializable<_Vp> && default_initializable<_Pattern>) = default; constexpr split_view(_Vp __base, _Pattern __pattern) : _M_base(std::move(__base)), _M_pattern(std::move(__pattern)) { } template requires constructible_from<_Vp, views::all_t<_Range>> && constructible_from<_Pattern, single_view>> constexpr split_view(_Range&& __r, range_value_t<_Range> __e) : _M_base(views::all(std::forward<_Range>(__r))), _M_pattern(views::single(std::move(__e))) { } constexpr _Vp base() const& requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } constexpr _Iterator begin() { if (!_M_cached_begin) _M_cached_begin = _M_find_next(ranges::begin(_M_base)); return {this, ranges::begin(_M_base), *_M_cached_begin}; } constexpr auto end() { if constexpr (common_range<_Vp>) return _Iterator{this, ranges::end(_M_base), {}}; else return _Sentinel{this}; } constexpr subrange> _M_find_next(iterator_t<_Vp> __it) { auto [__b, __e] = ranges::search(subrange(__it, ranges::end(_M_base)), _M_pattern); if (__b != ranges::end(_M_base) && ranges::empty(_M_pattern)) { ++__b; ++__e; } return {__b, __e}; } private: struct _Iterator { private: split_view* _M_parent = nullptr; iterator_t<_Vp> _M_cur = iterator_t<_Vp>(); subrange> _M_next = subrange>(); bool _M_trailing_empty = false; friend struct _Sentinel; public: using iterator_concept = forward_iterator_tag; using iterator_category = input_iterator_tag; using value_type = subrange>; using difference_type = range_difference_t<_Vp>; _Iterator() = default; constexpr _Iterator(split_view* __parent, iterator_t<_Vp> __current, subrange> __next) : _M_parent(__parent), _M_cur(std::move(__current)), _M_next(std::move(__next)) { } constexpr iterator_t<_Vp> base() const { return _M_cur; } constexpr value_type operator*() const { return {_M_cur, _M_next.begin()}; } constexpr _Iterator& operator++() { _M_cur = _M_next.begin(); if (_M_cur != ranges::end(_M_parent->_M_base)) { _M_cur = _M_next.end(); if (_M_cur == ranges::end(_M_parent->_M_base)) { _M_trailing_empty = true; _M_next = {_M_cur, _M_cur}; } else _M_next = _M_parent->_M_find_next(_M_cur); } else _M_trailing_empty = false; return *this; } constexpr _Iterator operator++(int) { auto __tmp = *this; ++*this; return __tmp; } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) { return __x._M_cur == __y._M_cur && __x._M_trailing_empty == __y._M_trailing_empty; } }; struct _Sentinel { private: sentinel_t<_Vp> _M_end = sentinel_t<_Vp>(); constexpr bool _M_equal(const _Iterator& __x) const { return __x._M_cur == _M_end && !__x._M_trailing_empty; } public: _Sentinel() = default; constexpr explicit _Sentinel(split_view* __parent) : _M_end(ranges::end(__parent->_M_base)) { } friend constexpr bool operator==(const _Iterator& __x, const _Sentinel& __y) { return __y._M_equal(__x); } }; }; template split_view(_Range&&, _Pattern&&) -> split_view, views::all_t<_Pattern>>; template split_view(_Range&&, range_value_t<_Range>) -> split_view, single_view>>; namespace views { namespace __detail { template concept __can_split_view = requires { split_view(std::declval<_Range>(), std::declval<_Pattern>()); }; } // namespace __detail struct _Split : __adaptor::_RangeAdaptor<_Split> { template requires __detail::__can_split_view<_Range, _Pattern> constexpr auto operator() [[nodiscard]] (_Range&& __r, _Pattern&& __f) const { return split_view(std::forward<_Range>(__r), std::forward<_Pattern>(__f)); } using _RangeAdaptor<_Split>::operator(); static constexpr int _S_arity = 2; template static constexpr bool _S_has_simple_extra_args = _LazySplit::_S_has_simple_extra_args<_Pattern>; }; inline constexpr _Split split; } // namespace views namespace views { struct _Counted { template constexpr auto operator() [[nodiscard]] (_Iter __i, iter_difference_t<_Iter> __n) const { if constexpr (contiguous_iterator<_Iter>) return span(std::__to_address(__i), __n); else if constexpr (random_access_iterator<_Iter>) return subrange(__i, __i + __n); else return subrange(counted_iterator(std::move(__i), __n), default_sentinel); } }; inline constexpr _Counted counted{}; } // namespace views template requires (!common_range<_Vp>) && copyable> class common_view : public view_interface> { private: _Vp _M_base = _Vp(); public: common_view() requires default_initializable<_Vp> = default; constexpr explicit common_view(_Vp __r) : _M_base(std::move(__r)) { } constexpr _Vp base() const& requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } constexpr auto begin() { if constexpr (random_access_range<_Vp> && sized_range<_Vp>) return ranges::begin(_M_base); else return common_iterator, sentinel_t<_Vp>> (ranges::begin(_M_base)); } constexpr auto begin() const requires range { if constexpr (random_access_range && sized_range) return ranges::begin(_M_base); else return common_iterator, sentinel_t> (ranges::begin(_M_base)); } constexpr auto end() { if constexpr (random_access_range<_Vp> && sized_range<_Vp>) return ranges::begin(_M_base) + ranges::size(_M_base); else return common_iterator, sentinel_t<_Vp>> (ranges::end(_M_base)); } constexpr auto end() const requires range { if constexpr (random_access_range && sized_range) return ranges::begin(_M_base) + ranges::size(_M_base); else return common_iterator, sentinel_t> (ranges::end(_M_base)); } constexpr auto size() requires sized_range<_Vp> { return ranges::size(_M_base); } constexpr auto size() const requires sized_range { return ranges::size(_M_base); } }; template common_view(_Range&&) -> common_view>; template inline constexpr bool enable_borrowed_range> = enable_borrowed_range<_Tp>; namespace views { namespace __detail { template concept __already_common = common_range<_Range> && requires { views::all(std::declval<_Range>()); }; template concept __can_common_view = requires { common_view{std::declval<_Range>()}; }; } // namespace __detail struct _Common : __adaptor::_RangeAdaptorClosure<_Common> { template requires __detail::__already_common<_Range> || __detail::__can_common_view<_Range> constexpr auto operator() [[nodiscard]] (_Range&& __r) const { if constexpr (__detail::__already_common<_Range>) return views::all(std::forward<_Range>(__r)); else return common_view{std::forward<_Range>(__r)}; } static constexpr bool _S_has_simple_call_op = true; }; inline constexpr _Common common; } // namespace views template requires bidirectional_range<_Vp> class reverse_view : public view_interface> { private: static constexpr bool _S_needs_cached_begin = !common_range<_Vp> && !(random_access_range<_Vp> && sized_sentinel_for, iterator_t<_Vp>>); _Vp _M_base = _Vp(); [[no_unique_address]] __detail::__maybe_present_t<_S_needs_cached_begin, __detail::_CachedPosition<_Vp>> _M_cached_begin; public: reverse_view() requires default_initializable<_Vp> = default; constexpr explicit reverse_view(_Vp __r) : _M_base(std::move(__r)) { } constexpr _Vp base() const& requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } constexpr reverse_iterator> begin() { if constexpr (_S_needs_cached_begin) if (_M_cached_begin._M_has_value()) return std::make_reverse_iterator(_M_cached_begin._M_get(_M_base)); auto __it = ranges::next(ranges::begin(_M_base), ranges::end(_M_base)); if constexpr (_S_needs_cached_begin) _M_cached_begin._M_set(_M_base, __it); return std::make_reverse_iterator(std::move(__it)); } constexpr auto begin() requires common_range<_Vp> { return std::make_reverse_iterator(ranges::end(_M_base)); } constexpr auto begin() const requires common_range { return std::make_reverse_iterator(ranges::end(_M_base)); } constexpr reverse_iterator> end() { return std::make_reverse_iterator(ranges::begin(_M_base)); } constexpr auto end() const requires common_range { return std::make_reverse_iterator(ranges::begin(_M_base)); } constexpr auto size() requires sized_range<_Vp> { return ranges::size(_M_base); } constexpr auto size() const requires sized_range { return ranges::size(_M_base); } }; template reverse_view(_Range&&) -> reverse_view>; template inline constexpr bool enable_borrowed_range> = enable_borrowed_range<_Tp>; namespace views { namespace __detail { template inline constexpr bool __is_reversible_subrange = false; template inline constexpr bool __is_reversible_subrange, reverse_iterator<_Iter>, _Kind>> = true; template inline constexpr bool __is_reverse_view = false; template inline constexpr bool __is_reverse_view> = true; template concept __can_reverse_view = requires { reverse_view{std::declval<_Range>()}; }; } // namespace __detail struct _Reverse : __adaptor::_RangeAdaptorClosure<_Reverse> { template requires __detail::__is_reverse_view> || __detail::__is_reversible_subrange> || __detail::__can_reverse_view<_Range> constexpr auto operator() [[nodiscard]] (_Range&& __r) const { using _Tp = remove_cvref_t<_Range>; if constexpr (__detail::__is_reverse_view<_Tp>) return std::forward<_Range>(__r).base(); else if constexpr (__detail::__is_reversible_subrange<_Tp>) { using _Iter = decltype(ranges::begin(__r).base()); if constexpr (sized_range<_Tp>) return subrange<_Iter, _Iter, subrange_kind::sized> {__r.end().base(), __r.begin().base(), __r.size()}; else return subrange<_Iter, _Iter, subrange_kind::unsized> {__r.end().base(), __r.begin().base()}; } else return reverse_view{std::forward<_Range>(__r)}; } static constexpr bool _S_has_simple_call_op = true; }; inline constexpr _Reverse reverse; } // namespace views namespace __detail { template concept __has_tuple_element = requires(_Tp __t) { typename tuple_size<_Tp>::type; requires _Nm < tuple_size_v<_Tp>; typename tuple_element_t<_Nm, _Tp>; { std::get<_Nm>(__t) } -> convertible_to&>; }; template concept __returnable_element = is_reference_v<_Tp> || move_constructible>; } template requires view<_Vp> && __detail::__has_tuple_element, _Nm> && __detail::__has_tuple_element>, _Nm> && __detail::__returnable_element, _Nm> class elements_view : public view_interface> { public: elements_view() requires default_initializable<_Vp> = default; constexpr explicit elements_view(_Vp __base) : _M_base(std::move(__base)) { } constexpr _Vp base() const& requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } constexpr auto begin() requires (!__detail::__simple_view<_Vp>) { return _Iterator(ranges::begin(_M_base)); } constexpr auto begin() const requires range { return _Iterator(ranges::begin(_M_base)); } constexpr auto end() requires (!__detail::__simple_view<_Vp> && !common_range<_Vp>) { return _Sentinel{ranges::end(_M_base)}; } constexpr auto end() requires (!__detail::__simple_view<_Vp> && common_range<_Vp>) { return _Iterator{ranges::end(_M_base)}; } constexpr auto end() const requires range { return _Sentinel{ranges::end(_M_base)}; } constexpr auto end() const requires common_range { return _Iterator{ranges::end(_M_base)}; } constexpr auto size() requires sized_range<_Vp> { return ranges::size(_M_base); } constexpr auto size() const requires sized_range { return ranges::size(_M_base); } private: template using _Base = __detail::__maybe_const_t<_Const, _Vp>; template struct __iter_cat { }; template requires forward_range<_Base<_Const>> struct __iter_cat<_Const> { private: static auto _S_iter_cat() { using _Base = elements_view::_Base<_Const>; using _Cat = typename iterator_traits>::iterator_category; using _Res = decltype((std::get<_Nm>(*std::declval>()))); if constexpr (!is_lvalue_reference_v<_Res>) return input_iterator_tag{}; else if constexpr (derived_from<_Cat, random_access_iterator_tag>) return random_access_iterator_tag{}; else return _Cat{}; } public: using iterator_category = decltype(_S_iter_cat()); }; template struct _Sentinel; template struct _Iterator : __iter_cat<_Const> { private: using _Base = elements_view::_Base<_Const>; iterator_t<_Base> _M_current = iterator_t<_Base>(); static constexpr decltype(auto) _S_get_element(const iterator_t<_Base>& __i) { if constexpr (is_reference_v>) return std::get<_Nm>(*__i); else { using _Et = remove_cv_t>>; return static_cast<_Et>(std::get<_Nm>(*__i)); } } static auto _S_iter_concept() { if constexpr (random_access_range<_Base>) return random_access_iterator_tag{}; else if constexpr (bidirectional_range<_Base>) return bidirectional_iterator_tag{}; else if constexpr (forward_range<_Base>) return forward_iterator_tag{}; else return input_iterator_tag{}; } friend _Iterator; public: using iterator_concept = decltype(_S_iter_concept()); // iterator_category defined in elements_view::__iter_cat using value_type = remove_cvref_t>>; using difference_type = range_difference_t<_Base>; _Iterator() requires default_initializable> = default; constexpr explicit _Iterator(iterator_t<_Base> __current) : _M_current(std::move(__current)) { } constexpr _Iterator(_Iterator __i) requires _Const && convertible_to, iterator_t<_Base>> : _M_current(std::move(__i._M_current)) { } constexpr const iterator_t<_Base>& base() const& noexcept { return _M_current; } constexpr iterator_t<_Base> base() && { return std::move(_M_current); } constexpr decltype(auto) operator*() const { return _S_get_element(_M_current); } constexpr _Iterator& operator++() { ++_M_current; return *this; } constexpr void operator++(int) { ++_M_current; } constexpr _Iterator operator++(int) requires forward_range<_Base> { auto __tmp = *this; ++_M_current; return __tmp; } constexpr _Iterator& operator--() requires bidirectional_range<_Base> { --_M_current; return *this; } constexpr _Iterator operator--(int) requires bidirectional_range<_Base> { auto __tmp = *this; --_M_current; return __tmp; } constexpr _Iterator& operator+=(difference_type __n) requires random_access_range<_Base> { _M_current += __n; return *this; } constexpr _Iterator& operator-=(difference_type __n) requires random_access_range<_Base> { _M_current -= __n; return *this; } constexpr decltype(auto) operator[](difference_type __n) const requires random_access_range<_Base> { return _S_get_element(_M_current + __n); } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) requires equality_comparable> { return __x._M_current == __y._M_current; } friend constexpr bool operator<(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return __x._M_current < __y._M_current; } friend constexpr bool operator>(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return __y._M_current < __x._M_current; } friend constexpr bool operator<=(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return !(__y._M_current > __x._M_current); } friend constexpr bool operator>=(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return !(__x._M_current > __y._M_current); } #ifdef __cpp_lib_three_way_comparison friend constexpr auto operator<=>(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> && three_way_comparable> { return __x._M_current <=> __y._M_current; } #endif friend constexpr _Iterator operator+(const _Iterator& __x, difference_type __y) requires random_access_range<_Base> { return _Iterator{__x} += __y; } friend constexpr _Iterator operator+(difference_type __x, const _Iterator& __y) requires random_access_range<_Base> { return __y + __x; } friend constexpr _Iterator operator-(const _Iterator& __x, difference_type __y) requires random_access_range<_Base> { return _Iterator{__x} -= __y; } // _GLIBCXX_RESOLVE_LIB_DEFECTS // 3483. transform_view::iterator's difference is overconstrained friend constexpr difference_type operator-(const _Iterator& __x, const _Iterator& __y) requires sized_sentinel_for, iterator_t<_Base>> { return __x._M_current - __y._M_current; } template friend struct _Sentinel; }; template struct _Sentinel { private: template constexpr bool _M_equal(const _Iterator<_Const2>& __x) const { return __x._M_current == _M_end; } template constexpr auto _M_distance_from(const _Iterator<_Const2>& __i) const { return _M_end - __i._M_current; } using _Base = elements_view::_Base<_Const>; sentinel_t<_Base> _M_end = sentinel_t<_Base>(); public: _Sentinel() = default; constexpr explicit _Sentinel(sentinel_t<_Base> __end) : _M_end(std::move(__end)) { } constexpr _Sentinel(_Sentinel __other) requires _Const && convertible_to, sentinel_t<_Base>> : _M_end(std::move(__other._M_end)) { } constexpr sentinel_t<_Base> base() const { return _M_end; } template requires sentinel_for, iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>> friend constexpr bool operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y) { return __y._M_equal(__x); } template> requires sized_sentinel_for, iterator_t<_Base2>> friend constexpr range_difference_t<_Base2> operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y) { return -__y._M_distance_from(__x); } template> requires sized_sentinel_for, iterator_t<_Base2>> friend constexpr range_difference_t<_Base2> operator-(const _Sentinel& __x, const _Iterator<_Const2>& __y) { return __x._M_distance_from(__y); } friend _Sentinel; }; _Vp _M_base = _Vp(); }; template inline constexpr bool enable_borrowed_range> = enable_borrowed_range<_Tp>; template using keys_view = elements_view, 0>; template using values_view = elements_view, 1>; namespace views { namespace __detail { template concept __can_elements_view = requires { elements_view, _Nm>{std::declval<_Range>()}; }; } // namespace __detail template struct _Elements : __adaptor::_RangeAdaptorClosure<_Elements<_Nm>> { template requires __detail::__can_elements_view<_Nm, _Range> constexpr auto operator() [[nodiscard]] (_Range&& __r) const { return elements_view, _Nm>{std::forward<_Range>(__r)}; } static constexpr bool _S_has_simple_call_op = true; }; template inline constexpr _Elements<_Nm> elements; inline constexpr auto keys = elements<0>; inline constexpr auto values = elements<1>; } // namespace views #ifdef __cpp_lib_ranges_zip // C++ >= 23 namespace __detail { template concept __zip_is_common = (sizeof...(_Rs) == 1 && (common_range<_Rs> && ...)) || (!(bidirectional_range<_Rs> && ...) && (common_range<_Rs> && ...)) || ((random_access_range<_Rs> && ...) && (sized_range<_Rs> && ...)); template struct __tuple_or_pair { using type = std::tuple<_Ts...>; }; template struct __tuple_or_pair<_Tp, _Up> { using type = pair<_Tp, _Up>; }; template using __tuple_or_pair_t = typename __tuple_or_pair<_Ts...>::type; template constexpr auto __tuple_transform(_Fp&& __f, _Tuple&& __tuple) { return std::apply([&](_Ts&&... __elts) { return __tuple_or_pair_t...> (std::__invoke(__f, std::forward<_Ts>(__elts))...); }, std::forward<_Tuple>(__tuple)); } template constexpr void __tuple_for_each(_Fp&& __f, _Tuple&& __tuple) { std::apply([&](_Ts&&... __elts) { (std::__invoke(__f, std::forward<_Ts>(__elts)), ...); }, std::forward<_Tuple>(__tuple)); } } // namespace __detail template requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) class zip_view : public view_interface> { tuple<_Vs...> _M_views; template class _Iterator; template class _Sentinel; public: zip_view() = default; constexpr explicit zip_view(_Vs... __views) : _M_views(std::move(__views)...) { } constexpr auto begin() requires (!(__detail::__simple_view<_Vs> && ...)) { return _Iterator(__detail::__tuple_transform(ranges::begin, _M_views)); } constexpr auto begin() const requires (range && ...) { return _Iterator(__detail::__tuple_transform(ranges::begin, _M_views)); } constexpr auto end() requires (!(__detail::__simple_view<_Vs> && ...)) { if constexpr (!__detail::__zip_is_common<_Vs...>) return _Sentinel(__detail::__tuple_transform(ranges::end, _M_views)); else if constexpr ((random_access_range<_Vs> && ...)) return begin() + iter_difference_t<_Iterator>(size()); else return _Iterator(__detail::__tuple_transform(ranges::end, _M_views)); } constexpr auto end() const requires (range && ...) { if constexpr (!__detail::__zip_is_common) return _Sentinel(__detail::__tuple_transform(ranges::end, _M_views)); else if constexpr ((random_access_range && ...)) return begin() + iter_difference_t<_Iterator>(size()); else return _Iterator(__detail::__tuple_transform(ranges::end, _M_views)); } constexpr auto size() requires (sized_range<_Vs> && ...) { return std::apply([](auto... sizes) { using _CT = __detail::__make_unsigned_like_t>; return ranges::min({_CT(sizes)...}); }, __detail::__tuple_transform(ranges::size, _M_views)); } constexpr auto size() const requires (sized_range && ...) { return std::apply([](auto... sizes) { using _CT = __detail::__make_unsigned_like_t>; return ranges::min({_CT(sizes)...}); }, __detail::__tuple_transform(ranges::size, _M_views)); } }; template zip_view(_Rs&&...) -> zip_view...>; template inline constexpr bool enable_borrowed_range> = (enable_borrowed_range<_Views> && ...); namespace __detail { template concept __all_random_access = (random_access_range<__maybe_const_t<_Const, _Vs>> && ...); template concept __all_bidirectional = (bidirectional_range<__maybe_const_t<_Const, _Vs>> && ...); template concept __all_forward = (forward_range<__maybe_const_t<_Const, _Vs>> && ...); template struct __zip_view_iter_cat { }; template requires __all_forward<_Const, _Views...> struct __zip_view_iter_cat<_Const, _Views...> { using iterator_category = input_iterator_tag; }; } // namespace __detail template requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) template class zip_view<_Vs...>::_Iterator : public __detail::__zip_view_iter_cat<_Const, _Vs...> { #ifdef __clang__ // LLVM-61763 workaround public: #endif __detail::__tuple_or_pair_t>...> _M_current; constexpr explicit _Iterator(decltype(_M_current) __current) : _M_current(std::move(__current)) { } static auto _S_iter_concept() { if constexpr (__detail::__all_random_access<_Const, _Vs...>) return random_access_iterator_tag{}; else if constexpr (__detail::__all_bidirectional<_Const, _Vs...>) return bidirectional_iterator_tag{}; else if constexpr (__detail::__all_forward<_Const, _Vs...>) return forward_iterator_tag{}; else return input_iterator_tag{}; } #ifndef __clang__ // LLVM-61763 workaround template requires (view<_Ws> && ...) && (sizeof...(_Ws) > 0) && is_object_v<_Fp> && regular_invocable<_Fp&, range_reference_t<_Ws>...> && std::__detail::__can_reference...>> friend class zip_transform_view; #endif public: // iterator_category defined in __zip_view_iter_cat using iterator_concept = decltype(_S_iter_concept()); using value_type = __detail::__tuple_or_pair_t>...>; using difference_type = common_type_t>...>; _Iterator() = default; constexpr _Iterator(_Iterator __i) requires _Const && (convertible_to, iterator_t<__detail::__maybe_const_t<_Const, _Vs>>> && ...) : _M_current(std::move(__i._M_current)) { } constexpr auto operator*() const { auto __f = [](auto& __i) -> decltype(auto) { return *__i; }; return __detail::__tuple_transform(__f, _M_current); } constexpr _Iterator& operator++() { __detail::__tuple_for_each([](auto& __i) { ++__i; }, _M_current); return *this; } constexpr void operator++(int) { ++*this; } constexpr _Iterator operator++(int) requires __detail::__all_forward<_Const, _Vs...> { auto __tmp = *this; ++*this; return __tmp; } constexpr _Iterator& operator--() requires __detail::__all_bidirectional<_Const, _Vs...> { __detail::__tuple_for_each([](auto& __i) { --__i; }, _M_current); return *this; } constexpr _Iterator operator--(int) requires __detail::__all_bidirectional<_Const, _Vs...> { auto __tmp = *this; --*this; return __tmp; } constexpr _Iterator& operator+=(difference_type __x) requires __detail::__all_random_access<_Const, _Vs...> { auto __f = [&](_It& __i) { __i += iter_difference_t<_It>(__x); }; __detail::__tuple_for_each(__f, _M_current); return *this; } constexpr _Iterator& operator-=(difference_type __x) requires __detail::__all_random_access<_Const, _Vs...> { auto __f = [&](_It& __i) { __i -= iter_difference_t<_It>(__x); }; __detail::__tuple_for_each(__f, _M_current); return *this; } constexpr auto operator[](difference_type __n) const requires __detail::__all_random_access<_Const, _Vs...> { auto __f = [&](_It& __i) -> decltype(auto) { return __i[iter_difference_t<_It>(__n)]; }; return __detail::__tuple_transform(__f, _M_current); } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) requires (equality_comparable>> && ...) { if constexpr (__detail::__all_bidirectional<_Const, _Vs...>) return __x._M_current == __y._M_current; else return [&](index_sequence<_Is...>) { return ((std::get<_Is>(__x._M_current) == std::get<_Is>(__y._M_current)) || ...); }(make_index_sequence{}); } friend constexpr auto operator<=>(const _Iterator& __x, const _Iterator& __y) requires __detail::__all_random_access<_Const, _Vs...> { return __x._M_current <=> __y._M_current; } friend constexpr _Iterator operator+(const _Iterator& __i, difference_type __n) requires __detail::__all_random_access<_Const, _Vs...> { auto __r = __i; __r += __n; return __r; } friend constexpr _Iterator operator+(difference_type __n, const _Iterator& __i) requires __detail::__all_random_access<_Const, _Vs...> { auto __r = __i; __r += __n; return __r; } friend constexpr _Iterator operator-(const _Iterator& __i, difference_type __n) requires __detail::__all_random_access<_Const, _Vs...> { auto __r = __i; __r -= __n; return __r; } friend constexpr difference_type operator-(const _Iterator& __x, const _Iterator& __y) requires (sized_sentinel_for>, iterator_t<__detail::__maybe_const_t<_Const, _Vs>>> && ...) { return [&](index_sequence<_Is...>) { return ranges::min({difference_type(std::get<_Is>(__x._M_current) - std::get<_Is>(__y._M_current))...}, ranges::less{}, [](difference_type __i) { return __detail::__to_unsigned_like(__i < 0 ? -__i : __i); }); }(make_index_sequence{}); } friend constexpr auto iter_move(const _Iterator& __i) { return __detail::__tuple_transform(ranges::iter_move, __i._M_current); } friend constexpr void iter_swap(const _Iterator& __l, const _Iterator& __r) requires (indirectly_swappable>> && ...) { [&](index_sequence<_Is...>) { (ranges::iter_swap(std::get<_Is>(__l._M_current), std::get<_Is>(__r._M_current)), ...); }(make_index_sequence{}); } friend class zip_view; }; template requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) template class zip_view<_Vs...>::_Sentinel { __detail::__tuple_or_pair_t>...> _M_end; constexpr explicit _Sentinel(decltype(_M_end) __end) : _M_end(__end) { } friend class zip_view; public: _Sentinel() = default; constexpr _Sentinel(_Sentinel __i) requires _Const && (convertible_to, sentinel_t<__detail::__maybe_const_t<_Const, _Vs>>> && ...) : _M_end(std::move(__i._M_end)) { } template requires (sentinel_for>, iterator_t<__detail::__maybe_const_t<_OtherConst, _Vs>>> && ...) friend constexpr bool operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) { return [&](index_sequence<_Is...>) { return ((std::get<_Is>(__x._M_current) == std::get<_Is>(__y._M_end)) || ...); }(make_index_sequence{}); } template requires (sized_sentinel_for>, iterator_t<__detail::__maybe_const_t<_OtherConst, _Vs>>> && ...) friend constexpr auto operator-(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) { using _Ret = common_type_t>...>; return [&](index_sequence<_Is...>) { return ranges::min({_Ret(std::get<_Is>(__x._M_current) - std::get<_Is>(__y._M_end))...}, ranges::less{}, [](_Ret __i) { return __detail::__to_unsigned_like(__i < 0 ? -__i : __i); }); }(make_index_sequence{}); } template requires (sized_sentinel_for>, iterator_t<__detail::__maybe_const_t<_OtherConst, _Vs>>> && ...) friend constexpr auto operator-(const _Sentinel& __y, const _Iterator<_OtherConst>& __x) { return -(__x - __y); } }; namespace views { namespace __detail { template concept __can_zip_view = requires { zip_view...>(std::declval<_Ts>()...); }; } struct _Zip { template requires (sizeof...(_Ts) == 0 || __detail::__can_zip_view<_Ts...>) constexpr auto operator() [[nodiscard]] (_Ts&&... __ts) const { if constexpr (sizeof...(_Ts) == 0) return views::empty>; else return zip_view...>(std::forward<_Ts>(__ts)...); } }; inline constexpr _Zip zip; } namespace __detail { template using __range_iter_cat = typename iterator_traits>>::iterator_category; } template requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) && is_object_v<_Fp> && regular_invocable<_Fp&, range_reference_t<_Vs>...> && std::__detail::__can_reference...>> class zip_transform_view : public view_interface> { [[no_unique_address]] __detail::__box<_Fp> _M_fun; zip_view<_Vs...> _M_zip; using _InnerView = zip_view<_Vs...>; template using __ziperator = iterator_t<__detail::__maybe_const_t<_Const, _InnerView>>; template using __zentinel = sentinel_t<__detail::__maybe_const_t<_Const, _InnerView>>; template using _Base = __detail::__maybe_const_t<_Const, _InnerView>; template struct __iter_cat { }; template requires forward_range<_Base<_Const>> struct __iter_cat<_Const> { private: static auto _S_iter_cat() { using __detail::__maybe_const_t; using __detail::__range_iter_cat; using _Res = invoke_result_t<__maybe_const_t<_Const, _Fp>&, range_reference_t<__maybe_const_t<_Const, _Vs>>...>; if constexpr (!is_lvalue_reference_v<_Res>) return input_iterator_tag{}; else if constexpr ((derived_from<__range_iter_cat<_Vs, _Const>, random_access_iterator_tag> && ...)) return random_access_iterator_tag{}; else if constexpr ((derived_from<__range_iter_cat<_Vs, _Const>, bidirectional_iterator_tag> && ...)) return bidirectional_iterator_tag{}; else if constexpr ((derived_from<__range_iter_cat<_Vs, _Const>, forward_iterator_tag> && ...)) return forward_iterator_tag{}; else return input_iterator_tag{}; } public: using iterator_category = decltype(_S_iter_cat()); }; template class _Iterator; template class _Sentinel; public: zip_transform_view() = default; constexpr explicit zip_transform_view(_Fp __fun, _Vs... __views) : _M_fun(std::move(__fun)), _M_zip(std::move(__views)...) { } constexpr auto begin() { return _Iterator(*this, _M_zip.begin()); } constexpr auto begin() const requires range && regular_invocable...> { return _Iterator(*this, _M_zip.begin()); } constexpr auto end() { if constexpr (common_range<_InnerView>) return _Iterator(*this, _M_zip.end()); else return _Sentinel(_M_zip.end()); } constexpr auto end() const requires range && regular_invocable...> { if constexpr (common_range) return _Iterator(*this, _M_zip.end()); else return _Sentinel(_M_zip.end()); } constexpr auto size() requires sized_range<_InnerView> { return _M_zip.size(); } constexpr auto size() const requires sized_range { return _M_zip.size(); } }; template zip_transform_view(_Fp, Rs&&...) -> zip_transform_view<_Fp, views::all_t...>; template requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) && is_object_v<_Fp> && regular_invocable<_Fp&, range_reference_t<_Vs>...> && std::__detail::__can_reference...>> template class zip_transform_view<_Fp, _Vs...>::_Iterator : public __iter_cat<_Const> { using _Parent = __detail::__maybe_const_t<_Const, zip_transform_view>; _Parent* _M_parent = nullptr; __ziperator<_Const> _M_inner; constexpr _Iterator(_Parent& __parent, __ziperator<_Const> __inner) : _M_parent(std::__addressof(__parent)), _M_inner(std::move(__inner)) { } friend class zip_transform_view; public: // iterator_category defined in zip_transform_view::__iter_cat using iterator_concept = typename __ziperator<_Const>::iterator_concept; using value_type = remove_cvref_t&, range_reference_t<__detail::__maybe_const_t<_Const, _Vs>>...>>; using difference_type = range_difference_t<_Base<_Const>>; _Iterator() = default; constexpr _Iterator(_Iterator __i) requires _Const && convertible_to<__ziperator, __ziperator<_Const>> : _M_parent(__i._M_parent), _M_inner(std::move(__i._M_inner)) { } constexpr decltype(auto) operator*() const { return std::apply([&](const auto&... __iters) -> decltype(auto) { return std::__invoke(*_M_parent->_M_fun, *__iters...); }, _M_inner._M_current); } constexpr _Iterator& operator++() { ++_M_inner; return *this; } constexpr void operator++(int) { ++*this; } constexpr _Iterator operator++(int) requires forward_range<_Base<_Const>> { auto __tmp = *this; ++*this; return __tmp; } constexpr _Iterator& operator--() requires bidirectional_range<_Base<_Const>> { --_M_inner; return *this; } constexpr _Iterator operator--(int) requires bidirectional_range<_Base<_Const>> { auto __tmp = *this; --*this; return __tmp; } constexpr _Iterator& operator+=(difference_type __x) requires random_access_range<_Base<_Const>> { _M_inner += __x; return *this; } constexpr _Iterator& operator-=(difference_type __x) requires random_access_range<_Base<_Const>> { _M_inner -= __x; return *this; } constexpr decltype(auto) operator[](difference_type __n) const requires random_access_range<_Base<_Const>> { return std::apply([&](const _Is&... __iters) -> decltype(auto) { return std::__invoke(*_M_parent->_M_fun, __iters[iter_difference_t<_Is>(__n)]...); }, _M_inner._M_current); } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) requires equality_comparable<__ziperator<_Const>> { return __x._M_inner == __y._M_inner; } friend constexpr auto operator<=>(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base<_Const>> { return __x._M_inner <=> __y._M_inner; } friend constexpr _Iterator operator+(const _Iterator& __i, difference_type __n) requires random_access_range<_Base<_Const>> { return _Iterator(*__i._M_parent, __i._M_inner + __n); } friend constexpr _Iterator operator+(difference_type __n, const _Iterator& __i) requires random_access_range<_Base<_Const>> { return _Iterator(*__i._M_parent, __i._M_inner + __n); } friend constexpr _Iterator operator-(const _Iterator& __i, difference_type __n) requires random_access_range<_Base<_Const>> { return _Iterator(*__i._M_parent, __i._M_inner - __n); } friend constexpr difference_type operator-(const _Iterator& __x, const _Iterator& __y) requires sized_sentinel_for<__ziperator<_Const>, __ziperator<_Const>> { return __x._M_inner - __y._M_inner; } }; template requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) && is_object_v<_Fp> && regular_invocable<_Fp&, range_reference_t<_Vs>...> && std::__detail::__can_reference...>> template class zip_transform_view<_Fp, _Vs...>::_Sentinel { __zentinel<_Const> _M_inner; constexpr explicit _Sentinel(__zentinel<_Const> __inner) : _M_inner(__inner) { } friend class zip_transform_view; public: _Sentinel() = default; constexpr _Sentinel(_Sentinel __i) requires _Const && convertible_to<__zentinel, __zentinel<_Const>> : _M_inner(std::move(__i._M_inner)) { } template requires sentinel_for<__zentinel<_Const>, __ziperator<_OtherConst>> friend constexpr bool operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) { return __x._M_inner == __y._M_inner; } template requires sized_sentinel_for<__zentinel<_Const>, __ziperator<_OtherConst>> friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _InnerView>> operator-(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) { return __x._M_inner - __y._M_inner; } template requires sized_sentinel_for<__zentinel<_Const>, __ziperator<_OtherConst>> friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _InnerView>> operator-(const _Sentinel& __x, const _Iterator<_OtherConst>& __y) { return __x._M_inner - __y._M_inner; } }; namespace views { namespace __detail { template concept __can_zip_transform_view = requires { zip_transform_view(std::declval<_Fp>(), std::declval<_Ts>()...); }; } struct _ZipTransform { template requires (sizeof...(_Ts) == 0) || __detail::__can_zip_transform_view<_Fp, _Ts...> constexpr auto operator() [[nodiscard]] (_Fp&& __f, _Ts&&... __ts) const { if constexpr (sizeof...(_Ts) == 0) return views::empty&>>>; else return zip_transform_view(std::forward<_Fp>(__f), std::forward<_Ts>(__ts)...); } }; inline constexpr _ZipTransform zip_transform; } template requires view<_Vp> && (_Nm > 0) class adjacent_view : public view_interface> { _Vp _M_base = _Vp(); template class _Iterator; template class _Sentinel; struct __as_sentinel { }; public: adjacent_view() requires default_initializable<_Vp> = default; constexpr explicit adjacent_view(_Vp __base) : _M_base(std::move(__base)) { } constexpr auto begin() requires (!__detail::__simple_view<_Vp>) { return _Iterator(ranges::begin(_M_base), ranges::end(_M_base)); } constexpr auto begin() const requires range { return _Iterator(ranges::begin(_M_base), ranges::end(_M_base)); } constexpr auto end() requires (!__detail::__simple_view<_Vp>) { if constexpr (common_range<_Vp>) return _Iterator(__as_sentinel{}, ranges::begin(_M_base), ranges::end(_M_base)); else return _Sentinel(ranges::end(_M_base)); } constexpr auto end() const requires range { if constexpr (common_range) return _Iterator(__as_sentinel{}, ranges::begin(_M_base), ranges::end(_M_base)); else return _Sentinel(ranges::end(_M_base)); } constexpr auto size() requires sized_range<_Vp> { using _ST = decltype(ranges::size(_M_base)); using _CT = common_type_t<_ST, size_t>; auto __sz = static_cast<_CT>(ranges::size(_M_base)); __sz -= std::min<_CT>(__sz, _Nm - 1); return static_cast<_ST>(__sz); } constexpr auto size() const requires sized_range { using _ST = decltype(ranges::size(_M_base)); using _CT = common_type_t<_ST, size_t>; auto __sz = static_cast<_CT>(ranges::size(_M_base)); __sz -= std::min<_CT>(__sz, _Nm - 1); return static_cast<_ST>(__sz); } }; template inline constexpr bool enable_borrowed_range> = enable_borrowed_range<_Vp>; namespace __detail { // Yields tuple<_Tp, ..., _Tp> with _Nm elements. template using __repeated_tuple = decltype(std::tuple_cat(std::declval>())); // For a functor F that is callable with N arguments, the expression // declval<__unarize>(x) is equivalent to declval(x, ..., x). template struct __unarize { template static invoke_result_t<_Fp, _Ts...> __tuple_apply(const tuple<_Ts...>&); // not defined template decltype(__tuple_apply(std::declval<__repeated_tuple<_Tp, _Nm>>())) operator()(_Tp&&); // not defined }; } template requires view<_Vp> && (_Nm > 0) template class adjacent_view<_Vp, _Nm>::_Iterator { #ifdef __clang__ // LLVM-61763 workaround public: #endif using _Base = __detail::__maybe_const_t<_Const, _Vp>; array, _Nm> _M_current = array, _Nm>(); constexpr _Iterator(iterator_t<_Base> __first, sentinel_t<_Base> __last) { for (auto& __i : _M_current) { __i = __first; ranges::advance(__first, 1, __last); } } constexpr _Iterator(__as_sentinel, iterator_t<_Base> __first, iterator_t<_Base> __last) { if constexpr (!bidirectional_range<_Base>) for (auto& __it : _M_current) __it = __last; else for (size_t __i = 0; __i < _Nm; ++__i) { _M_current[_Nm - 1 - __i] = __last; ranges::advance(__last, -1, __first); } } static auto _S_iter_concept() { if constexpr (random_access_range<_Base>) return random_access_iterator_tag{}; else if constexpr (bidirectional_range<_Base>) return bidirectional_iterator_tag{}; else return forward_iterator_tag{}; } friend class adjacent_view; #ifndef __clang__ // LLVM-61763 workaround template requires view<_Wp> && (_Mm > 0) && is_object_v<_Fp> && regular_invocable<__detail::__unarize<_Fp&, _Mm>, range_reference_t<_Wp>> && std::__detail::__can_reference, range_reference_t<_Wp>>> friend class adjacent_transform_view; #endif public: using iterator_category = input_iterator_tag; using iterator_concept = decltype(_S_iter_concept()); using value_type = conditional_t<_Nm == 2, pair, range_value_t<_Base>>, __detail::__repeated_tuple, _Nm>>; using difference_type = range_difference_t<_Base>; _Iterator() = default; constexpr _Iterator(_Iterator __i) requires _Const && convertible_to, iterator_t<_Base>> { for (size_t __j = 0; __j < _Nm; ++__j) _M_current[__j] = std::move(__i._M_current[__j]); } constexpr auto operator*() const { auto __f = [](auto& __i) -> decltype(auto) { return *__i; }; return __detail::__tuple_transform(__f, _M_current); } constexpr _Iterator& operator++() { for (auto& __i : _M_current) ++__i; return *this; } constexpr _Iterator operator++(int) { auto __tmp = *this; ++*this; return __tmp; } constexpr _Iterator& operator--() requires bidirectional_range<_Base> { for (auto& __i : _M_current) --__i; return *this; } constexpr _Iterator operator--(int) requires bidirectional_range<_Base> { auto __tmp = *this; --*this; return __tmp; } constexpr _Iterator& operator+=(difference_type __x) requires random_access_range<_Base> { for (auto& __i : _M_current) __i += __x; return *this; } constexpr _Iterator& operator-=(difference_type __x) requires random_access_range<_Base> { for (auto& __i : _M_current) __i -= __x; return *this; } constexpr auto operator[](difference_type __n) const requires random_access_range<_Base> { auto __f = [&](auto& __i) -> decltype(auto) { return __i[__n]; }; return __detail::__tuple_transform(__f, _M_current); } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) { return __x._M_current.back() == __y._M_current.back(); } friend constexpr bool operator<(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return __x._M_current.back() < __y._M_current.back(); } friend constexpr bool operator>(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return __y < __x; } friend constexpr bool operator<=(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return !(__y < __x); } friend constexpr bool operator>=(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return !(__x < __y); } friend constexpr auto operator<=>(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> && three_way_comparable> { return __x._M_current.back() <=> __y._M_current.back(); } friend constexpr _Iterator operator+(const _Iterator& __i, difference_type __n) requires random_access_range<_Base> { auto __r = __i; __r += __n; return __r; } friend constexpr _Iterator operator+(difference_type __n, const _Iterator& __i) requires random_access_range<_Base> { auto __r = __i; __r += __n; return __r; } friend constexpr _Iterator operator-(const _Iterator& __i, difference_type __n) requires random_access_range<_Base> { auto __r = __i; __r -= __n; return __r; } friend constexpr difference_type operator-(const _Iterator& __x, const _Iterator& __y) requires sized_sentinel_for, iterator_t<_Base>> { return __x._M_current.back() - __y._M_current.back(); } friend constexpr auto iter_move(const _Iterator& __i) { return __detail::__tuple_transform(ranges::iter_move, __i._M_current); } friend constexpr void iter_swap(const _Iterator& __l, const _Iterator& __r) requires indirectly_swappable> { for (size_t __i = 0; __i < _Nm; __i++) ranges::iter_swap(__l._M_current[__i], __r._M_current[__i]); } }; template requires view<_Vp> && (_Nm > 0) template class adjacent_view<_Vp, _Nm>::_Sentinel { using _Base = __detail::__maybe_const_t<_Const, _Vp>; sentinel_t<_Base> _M_end = sentinel_t<_Base>(); constexpr explicit _Sentinel(sentinel_t<_Base> __end) : _M_end(__end) { } friend class adjacent_view; public: _Sentinel() = default; constexpr _Sentinel(_Sentinel __i) requires _Const && convertible_to, sentinel_t<_Base>> : _M_end(std::move(__i._M_end)) { } template requires sentinel_for, iterator_t<__detail::__maybe_const_t<_OtherConst, _Vp>>> friend constexpr bool operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) { return __x._M_current.back() == __y._M_end; } template requires sized_sentinel_for, iterator_t<__detail::__maybe_const_t<_OtherConst, _Vp>>> friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _Vp>> operator-(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) { return __x._M_current.back() - __y._M_end; } template requires sized_sentinel_for, iterator_t<__detail::__maybe_const_t<_OtherConst, _Vp>>> friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _Vp>> operator-(const _Sentinel& __y, const _Iterator<_OtherConst>& __x) { return __y._M_end - __x._M_current.back(); } }; namespace views { namespace __detail { template concept __can_adjacent_view = requires { adjacent_view, _Nm>(std::declval<_Range>()); }; } template struct _Adjacent : __adaptor::_RangeAdaptorClosure<_Adjacent<_Nm>> { template requires (_Nm == 0) || __detail::__can_adjacent_view<_Nm, _Range> constexpr auto operator() [[nodiscard]] (_Range&& __r) const { if constexpr (_Nm == 0) return views::empty>; else return adjacent_view, _Nm>(std::forward<_Range>(__r)); } }; template inline constexpr _Adjacent<_Nm> adjacent; inline constexpr auto pairwise = adjacent<2>; } template requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp> && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>> && std::__detail::__can_reference, range_reference_t<_Vp>>> class adjacent_transform_view : public view_interface> { [[no_unique_address]] __detail::__box<_Fp> _M_fun; adjacent_view<_Vp, _Nm> _M_inner; using _InnerView = adjacent_view<_Vp, _Nm>; template using _InnerIter = iterator_t<__detail::__maybe_const_t<_Const, _InnerView>>; template using _InnerSent = sentinel_t<__detail::__maybe_const_t<_Const, _InnerView>>; template class _Iterator; template class _Sentinel; public: adjacent_transform_view() = default; constexpr explicit adjacent_transform_view(_Vp __base, _Fp __fun) : _M_fun(std::move(__fun)), _M_inner(std::move(__base)) { } constexpr auto begin() { return _Iterator(*this, _M_inner.begin()); } constexpr auto begin() const requires range && regular_invocable<__detail::__unarize, range_reference_t> { return _Iterator(*this, _M_inner.begin()); } constexpr auto end() { if constexpr (common_range<_InnerView>) return _Iterator(*this, _M_inner.end()); else return _Sentinel(_M_inner.end()); } constexpr auto end() const requires range && regular_invocable<__detail::__unarize, range_reference_t> { if constexpr (common_range) return _Iterator(*this, _M_inner.end()); else return _Sentinel(_M_inner.end()); } constexpr auto size() requires sized_range<_InnerView> { return _M_inner.size(); } constexpr auto size() const requires sized_range { return _M_inner.size(); } }; template requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp> && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>> && std::__detail::__can_reference, range_reference_t<_Vp>>> template class adjacent_transform_view<_Vp, _Fp, _Nm>::_Iterator { using _Parent = __detail::__maybe_const_t<_Const, adjacent_transform_view>; using _Base = __detail::__maybe_const_t<_Const, _Vp>; _Parent* _M_parent = nullptr; _InnerIter<_Const> _M_inner; constexpr _Iterator(_Parent& __parent, _InnerIter<_Const> __inner) : _M_parent(std::__addressof(__parent)), _M_inner(std::move(__inner)) { } static auto _S_iter_cat() { using __detail::__maybe_const_t; using __detail::__unarize; using _Res = invoke_result_t<__unarize<__maybe_const_t<_Const, _Fp>&, _Nm>, range_reference_t<_Base>>; using _Cat = typename iterator_traits>::iterator_category; if constexpr (!is_lvalue_reference_v<_Res>) return input_iterator_tag{}; else if constexpr (derived_from<_Cat, random_access_iterator_tag>) return random_access_iterator_tag{}; else if constexpr (derived_from<_Cat, bidirectional_iterator_tag>) return bidirectional_iterator_tag{}; else if constexpr (derived_from<_Cat, forward_iterator_tag>) return forward_iterator_tag{}; else return input_iterator_tag{}; } friend class adjacent_transform_view; public: using iterator_category = decltype(_S_iter_cat()); using iterator_concept = typename _InnerIter<_Const>::iterator_concept; using value_type = remove_cvref_t&, _Nm>, range_reference_t<_Base>>>; using difference_type = range_difference_t<_Base>; _Iterator() = default; constexpr _Iterator(_Iterator __i) requires _Const && convertible_to<_InnerIter, _InnerIter<_Const>> : _M_parent(__i._M_parent), _M_inner(std::move(__i._M_inner)) { } constexpr decltype(auto) operator*() const { return std::apply([&](const auto&... __iters) -> decltype(auto) { return std::__invoke(*_M_parent->_M_fun, *__iters...); }, _M_inner._M_current); } constexpr _Iterator& operator++() { ++_M_inner; return *this; } constexpr _Iterator operator++(int) { auto __tmp = *this; ++*this; return __tmp; } constexpr _Iterator& operator--() requires bidirectional_range<_Base> { --_M_inner; return *this; } constexpr _Iterator operator--(int) requires bidirectional_range<_Base> { auto __tmp = *this; --*this; return __tmp; } constexpr _Iterator& operator+=(difference_type __x) requires random_access_range<_Base> { _M_inner += __x; return *this; } constexpr _Iterator& operator-=(difference_type __x) requires random_access_range<_Base> { _M_inner -= __x; return *this; } constexpr decltype(auto) operator[](difference_type __n) const requires random_access_range<_Base> { return std::apply([&](const auto&... __iters) -> decltype(auto) { return std::__invoke(*_M_parent->_M_fun, __iters[__n]...); }, _M_inner._M_current); } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) { return __x._M_inner == __y._M_inner; } friend constexpr bool operator<(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return __x._M_inner < __y._M_inner; } friend constexpr bool operator>(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return __x._M_inner > __y._M_inner; } friend constexpr bool operator<=(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return __x._M_inner <= __y._M_inner; } friend constexpr bool operator>=(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return __x._M_inner >= __y._M_inner; } friend constexpr auto operator<=>(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> && three_way_comparable<_InnerIter<_Const>> { return __x._M_inner <=> __y._M_inner; } friend constexpr _Iterator operator+(const _Iterator& __i, difference_type __n) requires random_access_range<_Base> { return _Iterator(*__i._M_parent, __i._M_inner + __n); } friend constexpr _Iterator operator+(difference_type __n, const _Iterator& __i) requires random_access_range<_Base> { return _Iterator(*__i._M_parent, __i._M_inner + __n); } friend constexpr _Iterator operator-(const _Iterator& __i, difference_type __n) requires random_access_range<_Base> { return _Iterator(*__i._M_parent, __i._M_inner - __n); } friend constexpr difference_type operator-(const _Iterator& __x, const _Iterator& __y) requires sized_sentinel_for<_InnerIter<_Const>, _InnerIter<_Const>> { return __x._M_inner - __y._M_inner; } }; template requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp> && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>> && std::__detail::__can_reference, range_reference_t<_Vp>>> template class adjacent_transform_view<_Vp, _Fp, _Nm>::_Sentinel { _InnerSent<_Const> _M_inner; constexpr explicit _Sentinel(_InnerSent<_Const> __inner) : _M_inner(__inner) { } friend class adjacent_transform_view; public: _Sentinel() = default; constexpr _Sentinel(_Sentinel __i) requires _Const && convertible_to<_InnerSent, _InnerSent<_Const>> : _M_inner(std::move(__i._M_inner)) { } template requires sentinel_for<_InnerSent<_Const>, _InnerIter<_OtherConst>> friend constexpr bool operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) { return __x._M_inner == __y._M_inner; } template requires sized_sentinel_for<_InnerSent<_Const>, _InnerIter<_OtherConst>> friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _InnerView>> operator-(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) { return __x._M_inner - __y._M_inner; } template requires sized_sentinel_for<_InnerSent<_Const>, _InnerIter<_OtherConst>> friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _InnerView>> operator-(const _Sentinel& __x, const _Iterator<_OtherConst>& __y) { return __x._M_inner - __y._M_inner; } }; namespace views { namespace __detail { template concept __can_adjacent_transform_view = requires { adjacent_transform_view, decay_t<_Fp>, _Nm> (std::declval<_Range>(), std::declval<_Fp>()); }; } template struct _AdjacentTransform : __adaptor::_RangeAdaptor<_AdjacentTransform<_Nm>> { template requires (_Nm == 0) || __detail::__can_adjacent_transform_view<_Nm, _Range, _Fp> constexpr auto operator() [[nodiscard]] (_Range&& __r, _Fp&& __f) const { if constexpr (_Nm == 0) return zip_transform(std::forward<_Fp>(__f)); else return adjacent_transform_view, decay_t<_Fp>, _Nm> (std::forward<_Range>(__r), std::forward<_Fp>(__f)); } using __adaptor::_RangeAdaptor<_AdjacentTransform>::operator(); static constexpr int _S_arity = 2; static constexpr bool _S_has_simple_extra_args = true; }; template inline constexpr _AdjacentTransform<_Nm> adjacent_transform; inline constexpr auto pairwise_transform = adjacent_transform<2>; } #endif // __cpp_lib_ranges_zip #ifdef __cpp_lib_ranges_chunk // C++ >= 23 namespace __detail { template constexpr _Tp __div_ceil(_Tp __num, _Tp __denom) { _Tp __r = __num / __denom; if (__num % __denom) ++__r; return __r; } } template requires input_range<_Vp> class chunk_view : public view_interface> { _Vp _M_base; range_difference_t<_Vp> _M_n; range_difference_t<_Vp> _M_remainder = 0; __detail::__non_propagating_cache> _M_current; class _OuterIter; class _InnerIter; public: constexpr explicit chunk_view(_Vp __base, range_difference_t<_Vp> __n) : _M_base(std::move(__base)), _M_n(__n) { __glibcxx_assert(__n >= 0); } constexpr _Vp base() const & requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } constexpr _OuterIter begin() { _M_current = ranges::begin(_M_base); _M_remainder = _M_n; return _OuterIter(*this); } constexpr default_sentinel_t end() const noexcept { return default_sentinel; } constexpr auto size() requires sized_range<_Vp> { return __detail::__to_unsigned_like(__detail::__div_ceil (ranges::distance(_M_base), _M_n)); } constexpr auto size() const requires sized_range { return __detail::__to_unsigned_like(__detail::__div_ceil (ranges::distance(_M_base), _M_n)); } }; template chunk_view(_Range&&, range_difference_t<_Range>) -> chunk_view>; template requires input_range<_Vp> class chunk_view<_Vp>::_OuterIter { chunk_view* _M_parent; constexpr explicit _OuterIter(chunk_view& __parent) noexcept : _M_parent(std::__addressof(__parent)) { } friend chunk_view; public: using iterator_concept = input_iterator_tag; using difference_type = range_difference_t<_Vp>; struct value_type; _OuterIter(_OuterIter&&) = default; _OuterIter& operator=(_OuterIter&&) = default; constexpr value_type operator*() const { __glibcxx_assert(*this != default_sentinel); return value_type(*_M_parent); } constexpr _OuterIter& operator++() { __glibcxx_assert(*this != default_sentinel); ranges::advance(*_M_parent->_M_current, _M_parent->_M_remainder, ranges::end(_M_parent->_M_base)); _M_parent->_M_remainder = _M_parent->_M_n; return *this; } constexpr void operator++(int) { ++*this; } friend constexpr bool operator==(const _OuterIter& __x, default_sentinel_t) { return *__x._M_parent->_M_current == ranges::end(__x._M_parent->_M_base) && __x._M_parent->_M_remainder != 0; } friend constexpr difference_type operator-(default_sentinel_t, const _OuterIter& __x) requires sized_sentinel_for, iterator_t<_Vp>> { const auto __dist = ranges::end(__x._M_parent->_M_base) - *__x._M_parent->_M_current; if (__dist < __x._M_parent->_M_remainder) return __dist == 0 ? 0 : 1; return 1 + __detail::__div_ceil(__dist - __x._M_parent->_M_remainder, __x._M_parent->_M_n); } friend constexpr difference_type operator-(const _OuterIter& __x, default_sentinel_t __y) requires sized_sentinel_for, iterator_t<_Vp>> { return -(__y - __x); } }; template requires input_range<_Vp> struct chunk_view<_Vp>::_OuterIter::value_type : view_interface { private: chunk_view* _M_parent; constexpr explicit value_type(chunk_view& __parent) noexcept : _M_parent(std::__addressof(__parent)) { } friend _OuterIter; public: constexpr _InnerIter begin() const noexcept { return _InnerIter(*_M_parent); } constexpr default_sentinel_t end() const noexcept { return default_sentinel; } constexpr auto size() const requires sized_sentinel_for, iterator_t<_Vp>> { return __detail::__to_unsigned_like (ranges::min(_M_parent->_M_remainder, ranges::end(_M_parent->_M_base) - *_M_parent->_M_current)); } }; template requires input_range<_Vp> class chunk_view<_Vp>::_InnerIter { chunk_view* _M_parent; constexpr explicit _InnerIter(chunk_view& __parent) noexcept : _M_parent(std::__addressof(__parent)) { } friend _OuterIter::value_type; public: using iterator_concept = input_iterator_tag; using difference_type = range_difference_t<_Vp>; using value_type = range_value_t<_Vp>; _InnerIter(_InnerIter&&) = default; _InnerIter& operator=(_InnerIter&&) = default; constexpr const iterator_t<_Vp>& base() const & { return *_M_parent->_M_current; } constexpr range_reference_t<_Vp> operator*() const { __glibcxx_assert(*this != default_sentinel); return **_M_parent->_M_current; } constexpr _InnerIter& operator++() { __glibcxx_assert(*this != default_sentinel); ++*_M_parent->_M_current; if (*_M_parent->_M_current == ranges::end(_M_parent->_M_base)) _M_parent->_M_remainder = 0; else --_M_parent->_M_remainder; return *this; } constexpr void operator++(int) { ++*this; } friend constexpr bool operator==(const _InnerIter& __x, default_sentinel_t) noexcept { return __x._M_parent->_M_remainder == 0; } friend constexpr difference_type operator-(default_sentinel_t, const _InnerIter& __x) requires sized_sentinel_for, iterator_t<_Vp>> { return ranges::min(__x._M_parent->_M_remainder, ranges::end(__x._M_parent->_M_base) - *__x._M_parent->_M_current); } friend constexpr difference_type operator-(const _InnerIter& __x, default_sentinel_t __y) requires sized_sentinel_for, iterator_t<_Vp>> { return -(__y - __x); } }; template requires forward_range<_Vp> class chunk_view<_Vp> : public view_interface> { _Vp _M_base; range_difference_t<_Vp> _M_n; template class _Iterator; public: constexpr explicit chunk_view(_Vp __base, range_difference_t<_Vp> __n) : _M_base(std::move(__base)), _M_n(__n) { __glibcxx_assert(__n > 0); } constexpr _Vp base() const & requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } constexpr auto begin() requires (!__detail::__simple_view<_Vp>) { return _Iterator(this, ranges::begin(_M_base)); } constexpr auto begin() const requires forward_range { return _Iterator(this, ranges::begin(_M_base)); } constexpr auto end() requires (!__detail::__simple_view<_Vp>) { if constexpr (common_range<_Vp> && sized_range<_Vp>) { auto __missing = (_M_n - ranges::distance(_M_base) % _M_n) % _M_n; return _Iterator(this, ranges::end(_M_base), __missing); } else if constexpr (common_range<_Vp> && !bidirectional_range<_Vp>) return _Iterator(this, ranges::end(_M_base)); else return default_sentinel; } constexpr auto end() const requires forward_range { if constexpr (common_range && sized_range) { auto __missing = (_M_n - ranges::distance(_M_base) % _M_n) % _M_n; return _Iterator(this, ranges::end(_M_base), __missing); } else if constexpr (common_range && !bidirectional_range) return _Iterator(this, ranges::end(_M_base)); else return default_sentinel; } constexpr auto size() requires sized_range<_Vp> { return __detail::__to_unsigned_like(__detail::__div_ceil (ranges::distance(_M_base), _M_n)); } constexpr auto size() const requires sized_range { return __detail::__to_unsigned_like(__detail::__div_ceil (ranges::distance(_M_base), _M_n)); } }; template inline constexpr bool enable_borrowed_range> = forward_range<_Vp> && enable_borrowed_range<_Vp>; template requires forward_range<_Vp> template class chunk_view<_Vp>::_Iterator { using _Parent = __detail::__maybe_const_t<_Const, chunk_view>; using _Base = __detail::__maybe_const_t<_Const, _Vp>; iterator_t<_Base> _M_current = iterator_t<_Base>(); sentinel_t<_Base> _M_end = sentinel_t<_Base>(); range_difference_t<_Base> _M_n = 0; range_difference_t<_Base> _M_missing = 0; constexpr _Iterator(_Parent* __parent, iterator_t<_Base> __current, range_difference_t<_Base> __missing = 0) : _M_current(__current), _M_end(ranges::end(__parent->_M_base)), _M_n(__parent->_M_n), _M_missing(__missing) { } static auto _S_iter_cat() { if constexpr (random_access_range<_Base>) return random_access_iterator_tag{}; else if constexpr (bidirectional_range<_Base>) return bidirectional_iterator_tag{}; else return forward_iterator_tag{}; } friend chunk_view; public: using iterator_category = input_iterator_tag; using iterator_concept = decltype(_S_iter_cat()); using value_type = decltype(views::take(subrange(_M_current, _M_end), _M_n)); using difference_type = range_difference_t<_Base>; _Iterator() = default; constexpr _Iterator(_Iterator __i) requires _Const && convertible_to, iterator_t<_Base>> && convertible_to, sentinel_t<_Base>> : _M_current(std::move(__i._M_current)), _M_end(std::move(__i._M_end)), _M_n(__i._M_n), _M_missing(__i._M_missing) { } constexpr iterator_t<_Base> base() const { return _M_current; } constexpr value_type operator*() const { __glibcxx_assert(_M_current != _M_end); return views::take(subrange(_M_current, _M_end), _M_n); } constexpr _Iterator& operator++() { __glibcxx_assert(_M_current != _M_end); _M_missing = ranges::advance(_M_current, _M_n, _M_end); return *this; } constexpr _Iterator operator++(int) { auto __tmp = *this; ++*this; return __tmp; } constexpr _Iterator& operator--() requires bidirectional_range<_Base> { ranges::advance(_M_current, _M_missing - _M_n); _M_missing = 0; return *this; } constexpr _Iterator operator--(int) requires bidirectional_range<_Base> { auto __tmp = *this; --*this; return __tmp; } constexpr _Iterator& operator+=(difference_type __x) requires random_access_range<_Base> { if (__x > 0) { __glibcxx_assert(ranges::distance(_M_current, _M_end) > _M_n * (__x - 1)); _M_missing = ranges::advance(_M_current, _M_n * __x, _M_end); } else if (__x < 0) { ranges::advance(_M_current, _M_n * __x + _M_missing); _M_missing = 0; } return *this; } constexpr _Iterator& operator-=(difference_type __x) requires random_access_range<_Base> { return *this += -__x; } constexpr value_type operator[](difference_type __n) const requires random_access_range<_Base> { return *(*this + __n); } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) { return __x._M_current == __y._M_current; } friend constexpr bool operator==(const _Iterator& __x, default_sentinel_t) { return __x._M_current == __x._M_end; } friend constexpr bool operator<(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return __x._M_current > __y._M_current; } friend constexpr bool operator>(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return __y < __x; } friend constexpr bool operator<=(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return !(__y < __x); } friend constexpr bool operator>=(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return !(__x < __y); } friend constexpr auto operator<=>(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> && three_way_comparable> { return __x._M_current <=> __y._M_current; } friend constexpr _Iterator operator+(const _Iterator& __i, difference_type __n) requires random_access_range<_Base> { auto __r = __i; __r += __n; return __r; } friend constexpr _Iterator operator+(difference_type __n, const _Iterator& __i) requires random_access_range<_Base> { auto __r = __i; __r += __n; return __r; } friend constexpr _Iterator operator-(const _Iterator& __i, difference_type __n) requires random_access_range<_Base> { auto __r = __i; __r -= __n; return __r; } friend constexpr difference_type operator-(const _Iterator& __x, const _Iterator& __y) requires sized_sentinel_for, iterator_t<_Base>> { return (__x._M_current - __y._M_current + __x._M_missing - __y._M_missing) / __x._M_n; } friend constexpr difference_type operator-(default_sentinel_t __y, const _Iterator& __x) requires sized_sentinel_for, iterator_t<_Base>> { return __detail::__div_ceil(__x._M_end - __x._M_current, __x._M_n); } friend constexpr difference_type operator-(const _Iterator& __x, default_sentinel_t __y) requires sized_sentinel_for, iterator_t<_Base>> { return -(__y - __x); } }; namespace views { namespace __detail { template concept __can_chunk_view = requires { chunk_view(std::declval<_Range>(), std::declval<_Dp>()); }; } struct _Chunk : __adaptor::_RangeAdaptor<_Chunk> { template> requires __detail::__can_chunk_view<_Range, _Dp> constexpr auto operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const { return chunk_view(std::forward<_Range>(__r), __n); } using __adaptor::_RangeAdaptor<_Chunk>::operator(); static constexpr int _S_arity = 2; static constexpr bool _S_has_simple_extra_args = true; }; inline constexpr _Chunk chunk; } #endif // __cpp_lib_ranges_chunk #ifdef __cpp_lib_ranges_slide // C++ >= 23 namespace __detail { template concept __slide_caches_nothing = random_access_range<_Vp> && sized_range<_Vp>; template concept __slide_caches_last = !__slide_caches_nothing<_Vp> && bidirectional_range<_Vp> && common_range<_Vp>; template concept __slide_caches_first = !__slide_caches_nothing<_Vp> && !__slide_caches_last<_Vp>; } template requires view<_Vp> class slide_view : public view_interface> { _Vp _M_base; range_difference_t<_Vp> _M_n; [[no_unique_address]] __detail::__maybe_present_t<__detail::__slide_caches_first<_Vp>, __detail::_CachedPosition<_Vp>> _M_cached_begin; [[no_unique_address]] __detail::__maybe_present_t<__detail::__slide_caches_last<_Vp>, __detail::_CachedPosition<_Vp>> _M_cached_end; template class _Iterator; class _Sentinel; public: constexpr explicit slide_view(_Vp __base, range_difference_t<_Vp> __n) : _M_base(std::move(__base)), _M_n(__n) { __glibcxx_assert(__n > 0); } constexpr auto begin() requires (!(__detail::__simple_view<_Vp> && __detail::__slide_caches_nothing)) { if constexpr (__detail::__slide_caches_first<_Vp>) { iterator_t<_Vp> __it; if (_M_cached_begin._M_has_value()) __it = _M_cached_begin._M_get(_M_base); else { __it = ranges::next(ranges::begin(_M_base), _M_n - 1, ranges::end(_M_base)); _M_cached_begin._M_set(_M_base, __it); } return _Iterator(ranges::begin(_M_base), std::move(__it), _M_n); } else return _Iterator(ranges::begin(_M_base), _M_n); } constexpr auto begin() const requires __detail::__slide_caches_nothing { return _Iterator(ranges::begin(_M_base), _M_n); } constexpr auto end() requires (!(__detail::__simple_view<_Vp> && __detail::__slide_caches_nothing)) { if constexpr (__detail::__slide_caches_nothing<_Vp>) return _Iterator(ranges::begin(_M_base) + range_difference_t<_Vp>(size()), _M_n); else if constexpr (__detail::__slide_caches_last<_Vp>) { iterator_t<_Vp> __it; if (_M_cached_end._M_has_value()) __it = _M_cached_end._M_get(_M_base); else { __it = ranges::prev(ranges::end(_M_base), _M_n - 1, ranges::begin(_M_base)); _M_cached_end._M_set(_M_base, __it); } return _Iterator(std::move(__it), _M_n); } else if constexpr (common_range<_Vp>) return _Iterator(ranges::end(_M_base), ranges::end(_M_base), _M_n); else return _Sentinel(ranges::end(_M_base)); } constexpr auto end() const requires __detail::__slide_caches_nothing { return begin() + range_difference_t(size()); } constexpr auto size() requires sized_range<_Vp> { auto __sz = ranges::distance(_M_base) - _M_n + 1; if (__sz < 0) __sz = 0; return __detail::__to_unsigned_like(__sz); } constexpr auto size() const requires sized_range { auto __sz = ranges::distance(_M_base) - _M_n + 1; if (__sz < 0) __sz = 0; return __detail::__to_unsigned_like(__sz); } }; template slide_view(_Range&&, range_difference_t<_Range>) -> slide_view>; template inline constexpr bool enable_borrowed_range> = enable_borrowed_range<_Vp>; template requires view<_Vp> template class slide_view<_Vp>::_Iterator { using _Base = __detail::__maybe_const_t<_Const, _Vp>; static constexpr bool _S_last_elt_present = __detail::__slide_caches_first<_Base>; iterator_t<_Base> _M_current = iterator_t<_Base>(); [[no_unique_address]] __detail::__maybe_present_t<_S_last_elt_present, iterator_t<_Base>> _M_last_elt = decltype(_M_last_elt)(); range_difference_t<_Base> _M_n = 0; constexpr _Iterator(iterator_t<_Base> __current, range_difference_t<_Base> __n) requires (!_S_last_elt_present) : _M_current(__current), _M_n(__n) { } constexpr _Iterator(iterator_t<_Base> __current, iterator_t<_Base> __last_elt, range_difference_t<_Base> __n) requires _S_last_elt_present : _M_current(__current), _M_last_elt(__last_elt), _M_n(__n) { } static auto _S_iter_concept() { if constexpr (random_access_range<_Base>) return random_access_iterator_tag{}; else if constexpr (bidirectional_range<_Base>) return bidirectional_iterator_tag{}; else return forward_iterator_tag{}; } friend slide_view; friend slide_view::_Sentinel; public: using iterator_category = input_iterator_tag; using iterator_concept = decltype(_S_iter_concept()); using value_type = decltype(views::counted(_M_current, _M_n)); using difference_type = range_difference_t<_Base>; _Iterator() = default; constexpr _Iterator(_Iterator __i) requires _Const && convertible_to, iterator_t<_Base>> : _M_current(std::move(__i._M_current)), _M_n(__i._M_n) { } constexpr auto operator*() const { return views::counted(_M_current, _M_n); } constexpr _Iterator& operator++() { ++_M_current; if constexpr (_S_last_elt_present) ++_M_last_elt; return *this; } constexpr _Iterator operator++(int) { auto __tmp = *this; ++*this; return __tmp; } constexpr _Iterator& operator--() requires bidirectional_range<_Base> { --_M_current; if constexpr (_S_last_elt_present) --_M_last_elt; return *this; } constexpr _Iterator operator--(int) requires bidirectional_range<_Base> { auto __tmp = *this; --*this; return __tmp; } constexpr _Iterator& operator+=(difference_type __x) requires random_access_range<_Base> { _M_current += __x; if constexpr (_S_last_elt_present) _M_last_elt += __x; return *this; } constexpr _Iterator& operator-=(difference_type __x) requires random_access_range<_Base> { _M_current -= __x; if constexpr (_S_last_elt_present) _M_last_elt -= __x; return *this; } constexpr auto operator[](difference_type __n) const requires random_access_range<_Base> { return views::counted(_M_current + __n, _M_n); } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) { if constexpr (_S_last_elt_present) return __x._M_last_elt == __y._M_last_elt; else return __x._M_current == __y._M_current; } friend constexpr bool operator<(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return __x._M_current < __y._M_current; } friend constexpr bool operator>(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return __y < __x; } friend constexpr bool operator<=(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return !(__y < __x); } friend constexpr bool operator>=(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return !(__x < __y); } friend constexpr auto operator<=>(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> && three_way_comparable> { return __x._M_current <=> __y._M_current; } friend constexpr _Iterator operator+(const _Iterator& __i, difference_type __n) requires random_access_range<_Base> { auto __r = __i; __r += __n; return __r; } friend constexpr _Iterator operator+(difference_type __n, const _Iterator& __i) requires random_access_range<_Base> { auto __r = __i; __r += __n; return __r; } friend constexpr _Iterator operator-(const _Iterator& __i, difference_type __n) requires random_access_range<_Base> { auto __r = __i; __r -= __n; return __r; } friend constexpr difference_type operator-(const _Iterator& __x, const _Iterator& __y) requires sized_sentinel_for, iterator_t<_Base>> { if constexpr (_S_last_elt_present) return __x._M_last_elt - __y._M_last_elt; else return __x._M_current - __y._M_current; } }; template requires view<_Vp> class slide_view<_Vp>::_Sentinel { sentinel_t<_Vp> _M_end = sentinel_t<_Vp>(); constexpr explicit _Sentinel(sentinel_t<_Vp> __end) : _M_end(__end) { } friend slide_view; public: _Sentinel() = default; friend constexpr bool operator==(const _Iterator& __x, const _Sentinel& __y) { return __x._M_last_elt == __y._M_end; } friend constexpr range_difference_t<_Vp> operator-(const _Iterator& __x, const _Sentinel& __y) requires sized_sentinel_for, iterator_t<_Vp>> { return __x._M_last_elt - __y._M_end; } friend constexpr range_difference_t<_Vp> operator-(const _Sentinel& __y, const _Iterator& __x) requires sized_sentinel_for, iterator_t<_Vp>> { return __y._M_end -__x._M_last_elt; } }; namespace views { namespace __detail { template concept __can_slide_view = requires { slide_view(std::declval<_Range>(), std::declval<_Dp>()); }; } struct _Slide : __adaptor::_RangeAdaptor<_Slide> { template> requires __detail::__can_slide_view<_Range, _Dp> constexpr auto operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const { return slide_view(std::forward<_Range>(__r), __n); } using __adaptor::_RangeAdaptor<_Slide>::operator(); static constexpr int _S_arity = 2; static constexpr bool _S_has_simple_extra_args = true; }; inline constexpr _Slide slide; } #endif // __cpp_lib_ranges_slide #ifdef __cpp_lib_ranges_chunk_by // C++ >= 23 template, iterator_t<_Vp>> _Pred> requires view<_Vp> && is_object_v<_Pred> class chunk_by_view : public view_interface> { _Vp _M_base = _Vp(); __detail::__box<_Pred> _M_pred; __detail::_CachedPosition<_Vp> _M_cached_begin; constexpr iterator_t<_Vp> _M_find_next(iterator_t<_Vp> __current) { __glibcxx_assert(_M_pred.has_value()); auto __pred = [this](_Tp&& __x, _Up&& __y) { return !bool((*_M_pred)(std::forward<_Tp>(__x), std::forward<_Up>(__y))); }; auto __it = ranges::adjacent_find(__current, ranges::end(_M_base), __pred); return ranges::next(__it, 1, ranges::end(_M_base)); } constexpr iterator_t<_Vp> _M_find_prev(iterator_t<_Vp> __current) requires bidirectional_range<_Vp> { __glibcxx_assert(_M_pred.has_value()); auto __pred = [this](_Tp&& __x, _Up&& __y) { return !bool((*_M_pred)(std::forward<_Up>(__y), std::forward<_Tp>(__x))); }; auto __rbegin = std::make_reverse_iterator(__current); auto __rend = std::make_reverse_iterator(ranges::begin(_M_base)); __glibcxx_assert(__rbegin != __rend); auto __it = ranges::adjacent_find(__rbegin, __rend, __pred).base(); return ranges::prev(__it, 1, ranges::begin(_M_base)); } class _Iterator; public: chunk_by_view() requires (default_initializable<_Vp> && default_initializable<_Pred>) = default; constexpr explicit chunk_by_view(_Vp __base, _Pred __pred) : _M_base(std::move(__base)), _M_pred(std::move(__pred)) { } constexpr _Vp base() const & requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } constexpr const _Pred& pred() const { return *_M_pred; } constexpr _Iterator begin() { __glibcxx_assert(_M_pred.has_value()); iterator_t<_Vp> __it; if (_M_cached_begin._M_has_value()) __it = _M_cached_begin._M_get(_M_base); else { __it = _M_find_next(ranges::begin(_M_base)); _M_cached_begin._M_set(_M_base, __it); } return _Iterator(*this, ranges::begin(_M_base), __it); } constexpr auto end() { if constexpr (common_range<_Vp>) return _Iterator(*this, ranges::end(_M_base), ranges::end(_M_base)); else return default_sentinel; } }; template chunk_by_view(_Range&&, _Pred) -> chunk_by_view, _Pred>; template, iterator_t<_Vp>> _Pred> requires view<_Vp> && is_object_v<_Pred> class chunk_by_view<_Vp, _Pred>::_Iterator { chunk_by_view* _M_parent = nullptr; iterator_t<_Vp> _M_current = iterator_t<_Vp>(); iterator_t<_Vp> _M_next = iterator_t<_Vp>(); constexpr _Iterator(chunk_by_view& __parent, iterator_t<_Vp> __current, iterator_t<_Vp> __next) : _M_parent(std::__addressof(__parent)), _M_current(__current), _M_next(__next) { } static auto _S_iter_concept() { if constexpr (bidirectional_range<_Vp>) return bidirectional_iterator_tag{}; else return forward_iterator_tag{}; } friend chunk_by_view; public: using value_type = subrange>; using difference_type = range_difference_t<_Vp>; using iterator_category = input_iterator_tag; using iterator_concept = decltype(_S_iter_concept()); _Iterator() = default; constexpr value_type operator*() const { __glibcxx_assert(_M_current != _M_next); return ranges::subrange(_M_current, _M_next); } constexpr _Iterator& operator++() { __glibcxx_assert(_M_current != _M_next); _M_current = _M_next; _M_next = _M_parent->_M_find_next(_M_current); return *this; } constexpr _Iterator operator++(int) { auto __tmp = *this; ++*this; return __tmp; } constexpr _Iterator& operator--() requires bidirectional_range<_Vp> { _M_next = _M_current; _M_current = _M_parent->_M_find_prev(_M_next); return *this; } constexpr _Iterator operator--(int) requires bidirectional_range<_Vp> { auto __tmp = *this; --*this; return __tmp; } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) { return __x._M_current == __y._M_current; } friend constexpr bool operator==(const _Iterator& __x, default_sentinel_t) { return __x._M_current == __x._M_next; } }; namespace views { namespace __detail { template concept __can_chunk_by_view = requires { chunk_by_view(std::declval<_Range>(), std::declval<_Pred>()); }; } struct _ChunkBy : __adaptor::_RangeAdaptor<_ChunkBy> { template requires __detail::__can_chunk_by_view<_Range, _Pred> constexpr auto operator() [[nodiscard]] (_Range&& __r, _Pred&& __pred) const { return chunk_by_view(std::forward<_Range>(__r), std::forward<_Pred>(__pred)); } using __adaptor::_RangeAdaptor<_ChunkBy>::operator(); static constexpr int _S_arity = 2; static constexpr bool _S_has_simple_extra_args = true; }; inline constexpr _ChunkBy chunk_by; } #endif // __cpp_lib_ranges_chunk_by #ifdef __cpp_lib_ranges_join_with // C++ >= 23 namespace __detail { template concept __compatible_joinable_ranges = common_with, range_value_t<_Pattern>> && common_reference_with, range_reference_t<_Pattern>> && common_reference_with, range_rvalue_reference_t<_Pattern>>; template concept __bidirectional_common = bidirectional_range<_Range> && common_range<_Range>; } template requires view<_Vp> && view<_Pattern> && input_range> && __detail::__compatible_joinable_ranges, _Pattern> class join_with_view : public view_interface> { using _InnerRange = range_reference_t<_Vp>; _Vp _M_base = _Vp(); [[no_unique_address]] __detail::__maybe_present_t, __detail::__non_propagating_cache>> _M_outer_it; __detail::__non_propagating_cache> _M_inner; _Pattern _M_pattern = _Pattern(); template using _Base = __detail::__maybe_const_t<_Const, _Vp>; template using _InnerBase = range_reference_t<_Base<_Const>>; template using _PatternBase = __detail::__maybe_const_t<_Const, _Pattern>; template using _OuterIter = iterator_t<_Base<_Const>>; template using _InnerIter = iterator_t<_InnerBase<_Const>>; template using _PatternIter = iterator_t<_PatternBase<_Const>>; template static constexpr bool _S_ref_is_glvalue = is_reference_v<_InnerBase<_Const>>; template struct __iter_cat { }; template requires _S_ref_is_glvalue<_Const> && forward_range<_Base<_Const>> && forward_range<_InnerBase<_Const>> struct __iter_cat<_Const> { private: static auto _S_iter_cat() { using _OuterIter = join_with_view::_OuterIter<_Const>; using _InnerIter = join_with_view::_InnerIter<_Const>; using _PatternIter = join_with_view::_PatternIter<_Const>; using _OuterCat = typename iterator_traits<_OuterIter>::iterator_category; using _InnerCat = typename iterator_traits<_InnerIter>::iterator_category; using _PatternCat = typename iterator_traits<_PatternIter>::iterator_category; if constexpr (!is_lvalue_reference_v, iter_reference_t<_PatternIter>>>) return input_iterator_tag{}; else if constexpr (derived_from<_OuterCat, bidirectional_iterator_tag> && derived_from<_InnerCat, bidirectional_iterator_tag> && derived_from<_PatternCat, bidirectional_iterator_tag> && common_range<_InnerBase<_Const>> && common_range<_PatternBase<_Const>>) return bidirectional_iterator_tag{}; else if constexpr (derived_from<_OuterCat, forward_iterator_tag> && derived_from<_InnerCat, forward_iterator_tag> && derived_from<_PatternCat, forward_iterator_tag>) return forward_iterator_tag{}; else return input_iterator_tag{}; } public: using iterator_category = decltype(_S_iter_cat()); }; template struct _Iterator; template struct _Sentinel; public: join_with_view() requires (default_initializable<_Vp> && default_initializable<_Pattern>) = default; constexpr join_with_view(_Vp __base, _Pattern __pattern) : _M_base(std::move(__base)), _M_pattern(std::move(__pattern)) { } template requires constructible_from<_Vp, views::all_t<_Range>> && constructible_from<_Pattern, single_view>> constexpr join_with_view(_Range&& __r, range_value_t<_InnerRange> __e) : _M_base(views::all(std::forward<_Range>(__r))), _M_pattern(views::single(std::move(__e))) { } constexpr _Vp base() const& requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } constexpr auto begin() { if constexpr (forward_range<_Vp>) { constexpr bool __use_const = is_reference_v<_InnerRange> && __detail::__simple_view<_Vp> && __detail::__simple_view<_Pattern>; return _Iterator<__use_const>{*this, ranges::begin(_M_base)}; } else { _M_outer_it = ranges::begin(_M_base); return _Iterator{*this}; } } constexpr auto begin() const requires forward_range && forward_range && is_reference_v> && input_range> { return _Iterator{*this, ranges::begin(_M_base)}; } constexpr auto end() { constexpr bool __use_const = __detail::__simple_view<_Vp> && __detail::__simple_view<_Pattern>; if constexpr (is_reference_v<_InnerRange> && forward_range<_Vp> && common_range<_Vp> && forward_range<_InnerRange> && common_range<_InnerRange>) return _Iterator<__use_const>{*this, ranges::end(_M_base)}; else return _Sentinel<__use_const>{*this}; } constexpr auto end() const requires forward_range && forward_range && is_reference_v> && input_range> { using _InnerConstRange = range_reference_t; if constexpr (forward_range<_InnerConstRange> && common_range && common_range<_InnerConstRange>) return _Iterator{*this, ranges::end(_M_base)}; else return _Sentinel{*this}; } }; template join_with_view(_Range&&, _Pattern&&) -> join_with_view, views::all_t<_Pattern>>; template join_with_view(_Range&&, range_value_t>) -> join_with_view, single_view>>>; template requires view<_Vp> && view<_Pattern> && input_range> && __detail::__compatible_joinable_ranges, _Pattern> template class join_with_view<_Vp, _Pattern>::_Iterator : public __iter_cat<_Const> { using _Parent = __detail::__maybe_const_t<_Const, join_with_view>; using _Base = join_with_view::_Base<_Const>; using _InnerBase = join_with_view::_InnerBase<_Const>; using _PatternBase = join_with_view::_PatternBase<_Const>; using _OuterIter = join_with_view::_OuterIter<_Const>; using _InnerIter = join_with_view::_InnerIter<_Const>; using _PatternIter = join_with_view::_PatternIter<_Const>; static constexpr bool _S_ref_is_glvalue = join_with_view::_S_ref_is_glvalue<_Const>; _Parent* _M_parent = nullptr; [[no_unique_address]] __detail::__maybe_present_t, _OuterIter> _M_outer_it; variant<_PatternIter, _InnerIter> _M_inner_it; constexpr _OuterIter& _M_get_outer() { if constexpr (forward_range<_Base>) return _M_outer_it; else return *_M_parent->_M_outer_it; } constexpr const _OuterIter& _M_get_outer() const { if constexpr (forward_range<_Base>) return _M_outer_it; else return *_M_parent->_M_outer_it; } constexpr _Iterator(_Parent& __parent, _OuterIter __outer) requires forward_range<_Base> : _M_parent(std::__addressof(__parent)), _M_outer_it(std::move(__outer)) { if (_M_get_outer() != ranges::end(_M_parent->_M_base)) { auto&& __inner = _M_update_inner(); _M_inner_it.template emplace<1>(ranges::begin(__inner)); _M_satisfy(); } } constexpr _Iterator(_Parent& __parent) requires (!forward_range<_Base>) : _M_parent(std::__addressof(__parent)) { if (_M_get_outer() != ranges::end(_M_parent->_M_base)) { auto&& __inner = _M_update_inner(); _M_inner_it.template emplace<1>(ranges::begin(__inner)); _M_satisfy(); } } constexpr auto& _M_update_inner() { _OuterIter& __outer = _M_get_outer(); if constexpr (_S_ref_is_glvalue) return __detail::__as_lvalue(*__outer); else return _M_parent->_M_inner._M_emplace_deref(__outer); } constexpr auto& _M_get_inner() { if constexpr (_S_ref_is_glvalue) return __detail::__as_lvalue(*_M_get_outer()); else return *_M_parent->_M_inner; } constexpr void _M_satisfy() { while (true) { if (_M_inner_it.index() == 0) { if (std::get<0>(_M_inner_it) != ranges::end(_M_parent->_M_pattern)) break; auto&& __inner = _M_update_inner(); _M_inner_it.template emplace<1>(ranges::begin(__inner)); } else { auto&& __inner = _M_get_inner(); if (std::get<1>(_M_inner_it) != ranges::end(__inner)) break; if (++_M_get_outer() == ranges::end(_M_parent->_M_base)) { if constexpr (_S_ref_is_glvalue) _M_inner_it.template emplace<0>(); break; } _M_inner_it.template emplace<0>(ranges::begin(_M_parent->_M_pattern)); } } } static auto _S_iter_concept() { if constexpr (_S_ref_is_glvalue && bidirectional_range<_Base> && __detail::__bidirectional_common<_InnerBase> && __detail::__bidirectional_common<_PatternBase>) return bidirectional_iterator_tag{}; else if constexpr (_S_ref_is_glvalue && forward_range<_Base> && forward_range<_InnerBase>) return forward_iterator_tag{}; else return input_iterator_tag{}; } friend join_with_view; public: using iterator_concept = decltype(_S_iter_concept()); // iterator_category defined in join_with_view::__iter_cat using value_type = common_type_t, iter_value_t<_PatternIter>>; using difference_type = common_type_t, iter_difference_t<_InnerIter>, iter_difference_t<_PatternIter>>; _Iterator() = default; constexpr _Iterator(_Iterator __i) requires _Const && convertible_to, _OuterIter> && convertible_to, _InnerIter> && convertible_to, _PatternIter> : _M_parent(__i._M_parent), _M_outer_it(std::move(__i._M_outer_it)) { if (__i._M_inner_it.index() == 0) _M_inner_it.template emplace<0>(std::get<0>(std::move(__i._M_inner_it))); else _M_inner_it.template emplace<1>(std::get<1>(std::move(__i._M_inner_it))); } constexpr common_reference_t, iter_reference_t<_PatternIter>> operator*() const { if (_M_inner_it.index() == 0) return *std::get<0>(_M_inner_it); else return *std::get<1>(_M_inner_it); } constexpr _Iterator& operator++() { if (_M_inner_it.index() == 0) ++std::get<0>(_M_inner_it); else ++std::get<1>(_M_inner_it); _M_satisfy(); return *this; } constexpr void operator++(int) { ++*this; } constexpr _Iterator operator++(int) requires _S_ref_is_glvalue && forward_iterator<_OuterIter> && forward_iterator<_InnerIter> { _Iterator __tmp = *this; ++*this; return __tmp; } constexpr _Iterator& operator--() requires _S_ref_is_glvalue && bidirectional_range<_Base> && __detail::__bidirectional_common<_InnerBase> && __detail::__bidirectional_common<_PatternBase> { if (_M_outer_it == ranges::end(_M_parent->_M_base)) { auto&& __inner = *--_M_outer_it; _M_inner_it.template emplace<1>(ranges::end(__inner)); } while (true) { if (_M_inner_it.index() == 0) { auto& __it = std::get<0>(_M_inner_it); if (__it == ranges::begin(_M_parent->_M_pattern)) { auto&& __inner = *--_M_outer_it; _M_inner_it.template emplace<1>(ranges::end(__inner)); } else break; } else { auto& __it = std::get<1>(_M_inner_it); auto&& __inner = *_M_outer_it; if (__it == ranges::begin(__inner)) _M_inner_it.template emplace<0>(ranges::end(_M_parent->_M_pattern)); else break; } } if (_M_inner_it.index() == 0) --std::get<0>(_M_inner_it); else --std::get<1>(_M_inner_it); return *this; } constexpr _Iterator operator--(int) requires _S_ref_is_glvalue && bidirectional_range<_Base> && __detail::__bidirectional_common<_InnerBase> && __detail::__bidirectional_common<_PatternBase> { _Iterator __tmp = *this; --*this; return __tmp; } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) requires _S_ref_is_glvalue && forward_range<_Base> && equality_comparable<_InnerIter> { return __x._M_outer_it == __y._M_outer_it && __x._M_inner_it ==__y._M_inner_it; } friend constexpr common_reference_t, iter_rvalue_reference_t<_PatternIter>> iter_move(const _Iterator& __x) { if (__x._M_inner_it.index() == 0) return ranges::iter_move(std::get<0>(__x._M_inner_it)); else return ranges::iter_move(std::get<1>(__x._M_inner_it)); } friend constexpr void iter_swap(const _Iterator& __x, const _Iterator& __y) requires indirectly_swappable<_InnerIter, _PatternIter> { if (__x._M_inner_it.index() == 0) { if (__y._M_inner_it.index() == 0) ranges::iter_swap(std::get<0>(__x._M_inner_it), std::get<0>(__y._M_inner_it)); else ranges::iter_swap(std::get<0>(__x._M_inner_it), std::get<1>(__y._M_inner_it)); } else { if (__y._M_inner_it.index() == 0) ranges::iter_swap(std::get<1>(__x._M_inner_it), std::get<0>(__y._M_inner_it)); else ranges::iter_swap(std::get<1>(__x._M_inner_it), std::get<1>(__y._M_inner_it)); } } }; template requires view<_Vp> && view<_Pattern> && input_range> && __detail::__compatible_joinable_ranges, _Pattern> template class join_with_view<_Vp, _Pattern>::_Sentinel { using _Parent = __detail::__maybe_const_t<_Const, join_with_view>; using _Base = join_with_view::_Base<_Const>; sentinel_t<_Base> _M_end = sentinel_t<_Base>(); constexpr explicit _Sentinel(_Parent& __parent) : _M_end(ranges::end(__parent._M_base)) { } friend join_with_view; public: _Sentinel() = default; constexpr _Sentinel(_Sentinel __s) requires _Const && convertible_to, sentinel_t<_Base>> : _M_end(std::move(__s._M_end)) { } template requires sentinel_for, iterator_t<__detail::__maybe_const_t<_OtherConst, _Vp>>> friend constexpr bool operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) { return __x._M_get_outer() == __y._M_end; } }; namespace views { namespace __detail { template concept __can_join_with_view = requires { join_with_view(std::declval<_Range>(), std::declval<_Pattern>()); }; } // namespace __detail struct _JoinWith : __adaptor::_RangeAdaptor<_JoinWith> { template requires __detail::__can_join_with_view<_Range, _Pattern> constexpr auto operator() [[nodiscard]] (_Range&& __r, _Pattern&& __f) const { return join_with_view(std::forward<_Range>(__r), std::forward<_Pattern>(__f)); } using _RangeAdaptor<_JoinWith>::operator(); static constexpr int _S_arity = 2; template static constexpr bool _S_has_simple_extra_args = _LazySplit::_S_has_simple_extra_args<_Pattern>; }; inline constexpr _JoinWith join_with; } // namespace views #endif // __cpp_lib_ranges_join_with #ifdef __cpp_lib_ranges_repeat // C++ >= 23 template requires is_object_v<_Tp> && same_as<_Tp, remove_cv_t<_Tp>> && (__detail::__is_integer_like<_Bound> || same_as<_Bound, unreachable_sentinel_t>) class repeat_view : public view_interface> { __detail::__box<_Tp> _M_value; [[no_unique_address]] _Bound _M_bound = _Bound(); struct _Iterator; template friend constexpr auto views::__detail::__take_of_repeat_view(_Range&&, range_difference_t<_Range>); template friend constexpr auto views::__detail::__drop_of_repeat_view(_Range&&, range_difference_t<_Range>); public: repeat_view() requires default_initializable<_Tp> = default; constexpr explicit repeat_view(const _Tp& __value, _Bound __bound = _Bound()) requires copy_constructible<_Tp> : _M_value(__value), _M_bound(__bound) { if constexpr (!same_as<_Bound, unreachable_sentinel_t>) __glibcxx_assert(__bound >= 0); } constexpr explicit repeat_view(_Tp&& __value, _Bound __bound = _Bound()) : _M_value(std::move(__value)), _M_bound(__bound) { } template requires constructible_from<_Tp, _Args...> && constructible_from<_Bound, _BoundArgs...> constexpr explicit repeat_view(piecewise_construct_t, tuple<_Args...> __args, tuple<_BoundArgs...> __bound_args = tuple<>{}) : _M_value(std::make_from_tuple<_Tp>(std::move(__args))), _M_bound(std::make_from_tuple<_Bound>(std::move(__bound_args))) { } constexpr _Iterator begin() const { return _Iterator(std::__addressof(*_M_value)); } constexpr _Iterator end() const requires (!same_as<_Bound, unreachable_sentinel_t>) { return _Iterator(std::__addressof(*_M_value), _M_bound); } constexpr unreachable_sentinel_t end() const noexcept { return unreachable_sentinel; } constexpr auto size() const requires (!same_as<_Bound, unreachable_sentinel_t>) { return __detail::__to_unsigned_like(_M_bound); } }; template repeat_view(_Tp, _Bound) -> repeat_view<_Tp, _Bound>; template requires is_object_v<_Tp> && same_as<_Tp, remove_cv_t<_Tp>> && (__detail::__is_integer_like<_Bound> || same_as<_Bound, unreachable_sentinel_t>) class repeat_view<_Tp, _Bound>::_Iterator { using __index_type = __conditional_t, ptrdiff_t, _Bound>; const _Tp* _M_value = nullptr; __index_type _M_current = __index_type(); constexpr explicit _Iterator(const _Tp* __value, __index_type __bound = __index_type()) : _M_value(__value), _M_current(__bound) { if constexpr (!same_as<_Bound, unreachable_sentinel_t>) __glibcxx_assert(__bound >= 0); } friend repeat_view; public: using iterator_concept = random_access_iterator_tag; using iterator_category = random_access_iterator_tag; using value_type = _Tp; using difference_type = __conditional_t<__detail::__is_signed_integer_like<__index_type>, __index_type, __detail::__iota_diff_t<__index_type>>; _Iterator() = default; constexpr const _Tp& operator*() const noexcept { return *_M_value; } constexpr _Iterator& operator++() { ++_M_current; return *this; } constexpr _Iterator operator++(int) { auto __tmp = *this; ++*this; return __tmp; } constexpr _Iterator& operator--() { if constexpr (!same_as<_Bound, unreachable_sentinel_t>) __glibcxx_assert(_M_current > 0); --_M_current; return *this; } constexpr _Iterator operator--(int) { auto __tmp = *this; --*this; return __tmp; } constexpr _Iterator& operator+=(difference_type __n) { if constexpr (!same_as<_Bound, unreachable_sentinel_t>) __glibcxx_assert(_M_current + __n >= 0); _M_current += __n; return *this; } constexpr _Iterator& operator-=(difference_type __n) { if constexpr (!same_as<_Bound, unreachable_sentinel_t>) __glibcxx_assert(_M_current - __n >= 0); _M_current -= __n; return *this; } constexpr const _Tp& operator[](difference_type __n) const noexcept { return *(*this + __n); } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) { return __x._M_current == __y._M_current; } friend constexpr auto operator<=>(const _Iterator& __x, const _Iterator& __y) { return __x._M_current <=> __y._M_current; } friend constexpr _Iterator operator+(_Iterator __i, difference_type __n) { __i += __n; return __i; } friend constexpr _Iterator operator+(difference_type __n, _Iterator __i) { return __i + __n; } friend constexpr _Iterator operator-(_Iterator __i, difference_type __n) { __i -= __n; return __i; } friend constexpr difference_type operator-(const _Iterator& __x, const _Iterator& __y) { return (static_cast(__x._M_current) - static_cast(__y._M_current)); } }; namespace views { namespace __detail { template inline constexpr bool __is_repeat_view> = true; template concept __can_repeat_view = requires { repeat_view(std::declval<_Tp>()); }; template concept __can_bounded_repeat_view = requires { repeat_view(std::declval<_Tp>(), std::declval<_Bound>()); }; } struct _Repeat { template requires __detail::__can_repeat_view<_Tp> constexpr auto operator() [[nodiscard]] (_Tp&& __value) const { return repeat_view(std::forward<_Tp>(__value)); } template requires __detail::__can_bounded_repeat_view<_Tp, _Bound> constexpr auto operator() [[nodiscard]] (_Tp&& __value, _Bound __bound) const { return repeat_view(std::forward<_Tp>(__value), __bound); } }; inline constexpr _Repeat repeat; namespace __detail { template constexpr auto __take_of_repeat_view(_Range&& __r, range_difference_t<_Range> __n) { using _Tp = remove_cvref_t<_Range>; static_assert(__is_repeat_view<_Tp>); if constexpr (sized_range<_Tp>) return views::repeat(*std::forward<_Range>(__r)._M_value, std::min(ranges::distance(__r), __n)); else return views::repeat(*std::forward<_Range>(__r)._M_value, __n); } template constexpr auto __drop_of_repeat_view(_Range&& __r, range_difference_t<_Range> __n) { using _Tp = remove_cvref_t<_Range>; static_assert(__is_repeat_view<_Tp>); if constexpr (sized_range<_Tp>) { auto __sz = ranges::distance(__r); return views::repeat(*std::forward<_Range>(__r)._M_value, __sz - std::min(__sz, __n)); } else return __r; } } } #endif // __cpp_lib_ranges_repeat #ifdef __cpp_lib_ranges_stride // C++ >= 23 template requires view<_Vp> class stride_view : public view_interface> { _Vp _M_base; range_difference_t<_Vp> _M_stride; template using _Base = __detail::__maybe_const_t<_Const, _Vp>; template struct __iter_cat { }; template requires forward_range<_Base<_Const>> struct __iter_cat<_Const> { private: static auto _S_iter_cat() { using _Cat = typename iterator_traits>>::iterator_category; if constexpr (derived_from<_Cat, random_access_iterator_tag>) return random_access_iterator_tag{}; else return _Cat{}; } public: using iterator_category = decltype(_S_iter_cat()); }; template class _Iterator; public: constexpr explicit stride_view(_Vp __base, range_difference_t<_Vp> __stride) : _M_base(std::move(__base)), _M_stride(__stride) { __glibcxx_assert(__stride > 0); } constexpr _Vp base() const& requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } constexpr range_difference_t<_Vp> stride() const noexcept { return _M_stride; } constexpr auto begin() requires (!__detail::__simple_view<_Vp>) { return _Iterator(this, ranges::begin(_M_base)); } constexpr auto begin() const requires range { return _Iterator(this, ranges::begin(_M_base)); } constexpr auto end() requires (!__detail::__simple_view<_Vp>) { if constexpr (common_range<_Vp> && sized_range<_Vp> && forward_range<_Vp>) { auto __missing = (_M_stride - ranges::distance(_M_base) % _M_stride) % _M_stride; return _Iterator(this, ranges::end(_M_base), __missing); } else if constexpr (common_range<_Vp> && !bidirectional_range<_Vp>) return _Iterator(this, ranges::end(_M_base)); else return default_sentinel; } constexpr auto end() const requires range { if constexpr (common_range && sized_range && forward_range) { auto __missing = (_M_stride - ranges::distance(_M_base) % _M_stride) % _M_stride; return _Iterator(this, ranges::end(_M_base), __missing); } else if constexpr (common_range && !bidirectional_range) return _Iterator(this, ranges::end(_M_base)); else return default_sentinel; } constexpr auto size() requires sized_range<_Vp> { return __detail::__to_unsigned_like (__detail::__div_ceil(ranges::distance(_M_base), _M_stride)); } constexpr auto size() const requires sized_range { return __detail::__to_unsigned_like (__detail::__div_ceil(ranges::distance(_M_base), _M_stride)); } }; template stride_view(_Range&&, range_difference_t<_Range>) -> stride_view>; template inline constexpr bool enable_borrowed_range> = enable_borrowed_range<_Vp>; template requires view<_Vp> template class stride_view<_Vp>::_Iterator : public __iter_cat<_Const> { using _Parent = __detail::__maybe_const_t<_Const, stride_view>; using _Base = stride_view::_Base<_Const>; iterator_t<_Base> _M_current = iterator_t<_Base>(); sentinel_t<_Base> _M_end = sentinel_t<_Base>(); range_difference_t<_Base> _M_stride = 0; range_difference_t<_Base> _M_missing = 0; constexpr _Iterator(_Parent* __parent, iterator_t<_Base> __current, range_difference_t<_Base> __missing = 0) : _M_current(std::move(__current)), _M_end(ranges::end(__parent->_M_base)), _M_stride(__parent->_M_stride), _M_missing(__missing) { } static auto _S_iter_concept() { if constexpr (random_access_range<_Base>) return random_access_iterator_tag{}; else if constexpr (bidirectional_range<_Base>) return bidirectional_iterator_tag{}; else if constexpr (forward_range<_Base>) return forward_iterator_tag{}; else return input_iterator_tag{}; } friend stride_view; public: using difference_type = range_difference_t<_Base>; using value_type = range_value_t<_Base>; using iterator_concept = decltype(_S_iter_concept()); // iterator_category defined in stride_view::__iter_cat _Iterator() requires default_initializable> = default; constexpr _Iterator(_Iterator __other) requires _Const && convertible_to, iterator_t<_Base>> && convertible_to, sentinel_t<_Base>> : _M_current(std::move(__other._M_current)), _M_end(std::move(__other._M_end)), _M_stride(__other._M_stride), _M_missing(__other._M_missing) { } constexpr iterator_t<_Base> base() && { return std::move(_M_current); } constexpr const iterator_t<_Base>& base() const & noexcept { return _M_current; } constexpr decltype(auto) operator*() const { return *_M_current; } constexpr _Iterator& operator++() { __glibcxx_assert(_M_current != _M_end); _M_missing = ranges::advance(_M_current, _M_stride, _M_end); return *this; } constexpr void operator++(int) { ++*this; } constexpr _Iterator operator++(int) requires forward_range<_Base> { auto __tmp = *this; ++*this; return __tmp; } constexpr _Iterator& operator--() requires bidirectional_range<_Base> { ranges::advance(_M_current, _M_missing - _M_stride); _M_missing = 0; return *this; } constexpr _Iterator operator--(int) requires bidirectional_range<_Base> { auto __tmp = *this; --*this; return __tmp; } constexpr _Iterator& operator+=(difference_type __n) requires random_access_range<_Base> { if (__n > 0) { __glibcxx_assert(ranges::distance(_M_current, _M_end) > _M_stride * (__n - 1)); _M_missing = ranges::advance(_M_current, _M_stride * __n, _M_end); } else if (__n < 0) { ranges::advance(_M_current, _M_stride * __n + _M_missing); _M_missing = 0; } return *this; } constexpr _Iterator& operator-=(difference_type __n) requires random_access_range<_Base> { return *this += -__n; } constexpr decltype(auto) operator[](difference_type __n) const requires random_access_range<_Base> { return *(*this + __n); } friend constexpr bool operator==(const _Iterator& __x, default_sentinel_t) { return __x._M_current == __x._M_end; } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) requires equality_comparable> { return __x._M_current == __y._M_current; } friend constexpr bool operator<(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return __x._M_current < __y._M_current; } friend constexpr bool operator>(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return __y._M_current < __x._M_current; } friend constexpr bool operator<=(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return !(__y._M_current < __x._M_current); } friend constexpr bool operator>=(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> { return !(__x._M_current < __y._M_current); } friend constexpr auto operator<=>(const _Iterator& __x, const _Iterator& __y) requires random_access_range<_Base> && three_way_comparable> { return __x._M_current <=> __y._M_current; } friend constexpr _Iterator operator+(const _Iterator& __i, difference_type __n) requires random_access_range<_Base> { auto __r = __i; __r += __n; return __r; } friend constexpr _Iterator operator+(difference_type __n, const _Iterator& __i) requires random_access_range<_Base> { return __i + __n; } friend constexpr _Iterator operator-(const _Iterator& __i, difference_type __n) requires random_access_range<_Base> { auto __r = __i; __r -= __n; return __r; } friend constexpr difference_type operator-(const _Iterator& __x, const _Iterator& __y) requires sized_sentinel_for, iterator_t<_Base>> { auto __n = __x._M_current - __y._M_current; if constexpr (forward_range<_Base>) return (__n + __x._M_missing - __y._M_missing) / __x._M_stride; else if (__n < 0) return -__detail::__div_ceil(-__n, __x._M_stride); else return __detail::__div_ceil(__n, __x._M_stride); } friend constexpr difference_type operator-(default_sentinel_t __y, const _Iterator& __x) requires sized_sentinel_for, iterator_t<_Base>> { return __detail::__div_ceil(__x._M_end - __x._M_current, __x._M_stride); } friend constexpr difference_type operator-(const _Iterator& __x, default_sentinel_t __y) requires sized_sentinel_for, iterator_t<_Base>> { return -(__y - __x); } friend constexpr range_rvalue_reference_t<_Base> iter_move(const _Iterator& __i) noexcept(noexcept(ranges::iter_move(__i._M_current))) { return ranges::iter_move(__i._M_current); } friend constexpr void iter_swap(const _Iterator& __x, const _Iterator& __y) noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current))) requires indirectly_swappable> { ranges::iter_swap(__x._M_current, __y._M_current); } }; namespace views { namespace __detail { template concept __can_stride_view = requires { stride_view(std::declval<_Range>(), std::declval<_Dp>()); }; } struct _Stride : __adaptor::_RangeAdaptor<_Stride> { template> requires __detail::__can_stride_view<_Range, _Dp> constexpr auto operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const { return stride_view(std::forward<_Range>(__r), __n); } using __adaptor::_RangeAdaptor<_Stride>::operator(); static constexpr int _S_arity = 2; static constexpr bool _S_has_simple_extra_args = true; }; inline constexpr _Stride stride; } #endif // __cpp_lib_ranges_stride #ifdef __cpp_lib_ranges_cartesian_product // C++ >= 23 namespace __detail { template concept __cartesian_product_is_random_access = (random_access_range<__maybe_const_t<_Const, _First>> && ... && (random_access_range<__maybe_const_t<_Const, _Vs>> && sized_range<__maybe_const_t<_Const, _Vs>>)); template concept __cartesian_product_common_arg = common_range<_Range> || (sized_range<_Range> && random_access_range<_Range>); template concept __cartesian_product_is_bidirectional = (bidirectional_range<__maybe_const_t<_Const, _First>> && ... && (bidirectional_range<__maybe_const_t<_Const, _Vs>> && __cartesian_product_common_arg<__maybe_const_t<_Const, _Vs>>)); template concept __cartesian_product_is_common = __cartesian_product_common_arg<_First>; template concept __cartesian_product_is_sized = (sized_range<_Vs> && ...); template class FirstSent, typename _First, typename... _Vs> concept __cartesian_is_sized_sentinel = (sized_sentinel_for>, iterator_t<__maybe_const_t<_Const, _First>>> && ... && (sized_range<__maybe_const_t<_Const, _Vs>> && sized_sentinel_for>, iterator_t<__maybe_const_t<_Const, _Vs>>>)); template<__cartesian_product_common_arg _Range> constexpr auto __cartesian_common_arg_end(_Range& __r) { if constexpr (common_range<_Range>) return ranges::end(__r); else return ranges::begin(__r) + ranges::distance(__r); } } // namespace __detail template requires (view<_First> && ... && view<_Vs>) class cartesian_product_view : public view_interface> { tuple<_First, _Vs...> _M_bases; template class _Iterator; static auto _S_difference_type() { // TODO: Implement the recommended practice of using the smallest // sufficiently wide type according to the maximum sizes of the // underlying ranges? return common_type_t, range_difference_t<_Vs>...>{}; } public: cartesian_product_view() = default; constexpr explicit cartesian_product_view(_First __first, _Vs... __rest) : _M_bases(std::move(__first), std::move(__rest)...) { } constexpr _Iterator begin() requires (!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>) { return _Iterator(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); } constexpr _Iterator begin() const requires (range && ... && range) { return _Iterator(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); } constexpr _Iterator end() requires ((!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>) && __detail::__cartesian_product_is_common<_First, _Vs...>) { auto __its = [this](index_sequence<_Is...>) { using _Ret = __detail::__tuple_or_pair_t, iterator_t<_Vs>...>; bool __empty_tail = (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...); auto& __first = std::get<0>(_M_bases); return _Ret{(__empty_tail ? ranges::begin(__first) : __detail::__cartesian_common_arg_end(__first)), ranges::begin(std::get<1 + _Is>(_M_bases))...}; }(make_index_sequence{}); return _Iterator{*this, std::move(__its)}; } constexpr _Iterator end() const requires __detail::__cartesian_product_is_common { auto __its = [this](index_sequence<_Is...>) { using _Ret = __detail::__tuple_or_pair_t, iterator_t...>; bool __empty_tail = (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...); auto& __first = std::get<0>(_M_bases); return _Ret{(__empty_tail ? ranges::begin(__first) : __detail::__cartesian_common_arg_end(__first)), ranges::begin(std::get<1 + _Is>(_M_bases))...}; }(make_index_sequence{}); return _Iterator{*this, std::move(__its)}; } constexpr default_sentinel_t end() const noexcept { return default_sentinel; } constexpr auto size() requires __detail::__cartesian_product_is_sized<_First, _Vs...> { using _ST = __detail::__make_unsigned_like_t; return [&](index_sequence<_Is...>) { auto __size = static_cast<_ST>(1); #ifdef _GLIBCXX_ASSERTIONS if constexpr (integral<_ST>) { bool __overflow = (__builtin_mul_overflow(__size, static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))), &__size) || ...); __glibcxx_assert(!__overflow); } else #endif __size = (static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))) * ...); return __size; }(make_index_sequence<1 + sizeof...(_Vs)>{}); } constexpr auto size() const requires __detail::__cartesian_product_is_sized { using _ST = __detail::__make_unsigned_like_t; return [&](index_sequence<_Is...>) { auto __size = static_cast<_ST>(1); #ifdef _GLIBCXX_ASSERTIONS if constexpr (integral<_ST>) { bool __overflow = (__builtin_mul_overflow(__size, static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))), &__size) || ...); __glibcxx_assert(!__overflow); } else #endif __size = (static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))) * ...); return __size; }(make_index_sequence<1 + sizeof...(_Vs)>{}); } }; template cartesian_product_view(_Vs&&...) -> cartesian_product_view...>; template requires (view<_First> && ... && view<_Vs>) template class cartesian_product_view<_First, _Vs...>::_Iterator { using _Parent = __maybe_const_t<_Const, cartesian_product_view>; _Parent* _M_parent = nullptr; __detail::__tuple_or_pair_t>, iterator_t<__maybe_const_t<_Const, _Vs>>...> _M_current; constexpr _Iterator(_Parent& __parent, decltype(_M_current) __current) : _M_parent(std::__addressof(__parent)), _M_current(std::move(__current)) { } static auto _S_iter_concept() { if constexpr (__detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>) return random_access_iterator_tag{}; else if constexpr (__detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...>) return bidirectional_iterator_tag{}; else if constexpr (forward_range<__maybe_const_t<_Const, _First>>) return forward_iterator_tag{}; else return input_iterator_tag{}; } friend cartesian_product_view; public: using iterator_category = input_iterator_tag; using iterator_concept = decltype(_S_iter_concept()); using value_type = __detail::__tuple_or_pair_t>, range_value_t<__maybe_const_t<_Const, _Vs>>...>; using reference = __detail::__tuple_or_pair_t>, range_reference_t<__maybe_const_t<_Const, _Vs>>...>; using difference_type = decltype(cartesian_product_view::_S_difference_type()); _Iterator() = default; constexpr _Iterator(_Iterator __i) requires _Const && (convertible_to, iterator_t> && ... && convertible_to, iterator_t>) : _M_parent(std::__addressof(__i._M_parent)), _M_current(std::move(__i._M_current)) { } constexpr auto operator*() const { auto __f = [](auto& __i) -> decltype(auto) { return *__i; }; return __detail::__tuple_transform(__f, _M_current); } constexpr _Iterator& operator++() { _M_next(); return *this; } constexpr void operator++(int) { ++*this; } constexpr _Iterator operator++(int) requires forward_range<__maybe_const_t<_Const, _First>> { auto __tmp = *this; ++*this; return __tmp; } constexpr _Iterator& operator--() requires __detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...> { _M_prev(); return *this; } constexpr _Iterator operator--(int) requires __detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...> { auto __tmp = *this; --*this; return __tmp; } constexpr _Iterator& operator+=(difference_type __x) requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...> { _M_advance(__x); return *this; } constexpr _Iterator& operator-=(difference_type __x) requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...> { return *this += -__x; } constexpr reference operator[](difference_type __n) const requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...> { return *((*this) + __n); } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) requires equality_comparable>> { return __x._M_current == __y._M_current; } friend constexpr bool operator==(const _Iterator& __x, default_sentinel_t) { return [&](index_sequence<_Is...>) { return ((std::get<_Is>(__x._M_current) == ranges::end(std::get<_Is>(__x._M_parent->_M_bases))) || ...); }(make_index_sequence<1 + sizeof...(_Vs)>{}); } friend constexpr auto operator<=>(const _Iterator& __x, const _Iterator& __y) requires __detail::__all_random_access<_Const, _First, _Vs...> { return __x._M_current <=> __y._M_current; } friend constexpr _Iterator operator+(_Iterator __x, difference_type __y) requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...> { return __x += __y; } friend constexpr _Iterator operator+(difference_type __x, _Iterator __y) requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...> { return __y += __x; } friend constexpr _Iterator operator-(_Iterator __x, difference_type __y) requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...> { return __x -= __y; } friend constexpr difference_type operator-(const _Iterator& __x, const _Iterator& __y) requires __detail::__cartesian_is_sized_sentinel<_Const, iterator_t, _First, _Vs...> { return __x._M_distance_from(__y._M_current); } friend constexpr difference_type operator-(const _Iterator& __i, default_sentinel_t) requires __detail::__cartesian_is_sized_sentinel<_Const, sentinel_t, _First, _Vs...> { tuple __end_tuple = [&](index_sequence<_Is...>) { return tuple{ranges::end(std::get<0>(__i._M_parent->_M_bases)), ranges::begin(std::get<1 + _Is>(__i._M_parent->_M_bases))...}; }(make_index_sequence{}); return __i._M_distance_from(__end_tuple); } friend constexpr difference_type operator-(default_sentinel_t, const _Iterator& __i) requires __detail::__cartesian_is_sized_sentinel<_Const, sentinel_t, _First, _Vs...> { return -(__i - default_sentinel); } friend constexpr auto iter_move(const _Iterator& __i) { return __detail::__tuple_transform(ranges::iter_move, __i._M_current); } friend constexpr void iter_swap(const _Iterator& __l, const _Iterator& __r) requires (indirectly_swappable>> && ... && indirectly_swappable>>) { [&](index_sequence<_Is...>) { (ranges::iter_swap(std::get<_Is>(__l._M_current), std::get<_Is>(__r._M_current)), ...); }(make_index_sequence<1 + sizeof...(_Vs)>{}); } private: template constexpr void _M_next() { auto& __it = std::get<_Nm>(_M_current); ++__it; if constexpr (_Nm > 0) if (__it == ranges::end(std::get<_Nm>(_M_parent->_M_bases))) { __it = ranges::begin(std::get<_Nm>(_M_parent->_M_bases)); _M_next<_Nm - 1>(); } } template constexpr void _M_prev() { auto& __it = std::get<_Nm>(_M_current); if constexpr (_Nm > 0) if (__it == ranges::begin(std::get<_Nm>(_M_parent->_M_bases))) { __it = __detail::__cartesian_common_arg_end(std::get<_Nm>(_M_parent->_M_bases)); _M_prev<_Nm - 1>(); } --__it; } template constexpr void _M_advance(difference_type __x) requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...> { if (__x == 1) _M_next<_Nm>(); else if (__x == -1) _M_prev<_Nm>(); else if (__x != 0) { // Constant time iterator advancement. auto& __r = std::get<_Nm>(_M_parent->_M_bases); auto& __it = std::get<_Nm>(_M_current); if constexpr (_Nm == 0) { #ifdef _GLIBCXX_ASSERTIONS if constexpr (sized_range<__maybe_const_t<_Const, _First>>) { auto __size = ranges::ssize(__r); auto __begin = ranges::begin(__r); auto __offset = __it - __begin; __glibcxx_assert(__offset + __x >= 0 && __offset + __x <= __size); } #endif __it += __x; } else { auto __size = ranges::ssize(__r); auto __begin = ranges::begin(__r); auto __offset = __it - __begin; __offset += __x; __x = __offset / __size; __offset %= __size; if (__offset < 0) { __offset = __size + __offset; --__x; } __it = __begin + __offset; _M_advance<_Nm - 1>(__x); } } } template constexpr difference_type _M_distance_from(const _Tuple& __t) const { return [&](index_sequence<_Is...>) { auto __sum = static_cast(0); #ifdef _GLIBCXX_ASSERTIONS if constexpr (integral) { bool __overflow = (__builtin_add_overflow(__sum, _M_scaled_distance<_Is>(__t), &__sum) || ...); __glibcxx_assert(!__overflow); } else #endif __sum = (_M_scaled_distance<_Is>(__t) + ...); return __sum; }(make_index_sequence<1 + sizeof...(_Vs)>{}); } template constexpr difference_type _M_scaled_distance(const _Tuple& __t) const { auto __dist = static_cast(std::get<_Nm>(_M_current) - std::get<_Nm>(__t)); #ifdef _GLIBCXX_ASSERTIONS if constexpr (integral) { bool __overflow = __builtin_mul_overflow(__dist, _M_scaled_size<_Nm+1>(), &__dist); __glibcxx_assert(!__overflow); } else #endif __dist *= _M_scaled_size<_Nm+1>(); return __dist; } template constexpr difference_type _M_scaled_size() const { if constexpr (_Nm <= sizeof...(_Vs)) { auto __size = static_cast(ranges::size (std::get<_Nm>(_M_parent->_M_bases))); #ifdef _GLIBCXX_ASSERTIONS if constexpr (integral) { bool __overflow = __builtin_mul_overflow(__size, _M_scaled_size<_Nm+1>(), &__size); __glibcxx_assert(!__overflow); } else #endif __size *= _M_scaled_size<_Nm+1>(); return __size; } else return static_cast(1); } }; namespace views { namespace __detail { template concept __can_cartesian_product_view = requires { cartesian_product_view...>(std::declval<_Ts>()...); }; } struct _CartesianProduct { template requires (sizeof...(_Ts) == 0 || __detail::__can_cartesian_product_view<_Ts...>) constexpr auto operator() [[nodiscard]] (_Ts&&... __ts) const { if constexpr (sizeof...(_Ts) == 0) return views::empty>; else return cartesian_product_view...>(std::forward<_Ts>(__ts)...); } }; inline constexpr _CartesianProduct cartesian_product; } #endif // __cpp_lib_ranges_cartesian_product #ifdef __cpp_lib_ranges_as_rvalue // C++ >= 23 template requires view<_Vp> class as_rvalue_view : public view_interface> { _Vp _M_base = _Vp(); public: as_rvalue_view() requires default_initializable<_Vp> = default; constexpr explicit as_rvalue_view(_Vp __base) : _M_base(std::move(__base)) { } constexpr _Vp base() const& requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } constexpr auto begin() requires (!__detail::__simple_view<_Vp>) { return move_iterator(ranges::begin(_M_base)); } constexpr auto begin() const requires range { return move_iterator(ranges::begin(_M_base)); } constexpr auto end() requires (!__detail::__simple_view<_Vp>) { if constexpr (common_range<_Vp>) return move_iterator(ranges::end(_M_base)); else return move_sentinel(ranges::end(_M_base)); } constexpr auto end() const requires range { if constexpr (common_range) return move_iterator(ranges::end(_M_base)); else return move_sentinel(ranges::end(_M_base)); } constexpr auto size() requires sized_range<_Vp> { return ranges::size(_M_base); } constexpr auto size() const requires sized_range { return ranges::size(_M_base); } }; template as_rvalue_view(_Range&&) -> as_rvalue_view>; template inline constexpr bool enable_borrowed_range> = enable_borrowed_range<_Tp>; namespace views { namespace __detail { template concept __can_as_rvalue_view = requires { as_rvalue_view(std::declval<_Tp>()); }; } struct _AsRvalue : __adaptor::_RangeAdaptorClosure<_AsRvalue> { template requires __detail::__can_as_rvalue_view<_Range> constexpr auto operator() [[nodiscard]] (_Range&& __r) const { if constexpr (same_as, range_reference_t<_Range>>) return views::all(std::forward<_Range>(__r)); else return as_rvalue_view(std::forward<_Range>(__r)); } }; inline constexpr _AsRvalue as_rvalue; } #endif // __cpp_lib_as_rvalue #ifdef __cpp_lib_ranges_enumerate // C++ >= 23 namespace __detail { template concept __range_with_movable_reference = input_range<_Range> && move_constructible> && move_constructible>; } template requires __detail::__range_with_movable_reference<_Vp> class enumerate_view : public view_interface> { _Vp _M_base = _Vp(); template class _Iterator; template class _Sentinel; public: enumerate_view() requires default_initializable<_Vp> = default; constexpr explicit enumerate_view(_Vp __base) : _M_base(std::move(__base)) { } constexpr auto begin() requires (!__detail::__simple_view<_Vp>) { return _Iterator(ranges::begin(_M_base), 0); } constexpr auto begin() const requires __detail::__range_with_movable_reference { return _Iterator(ranges::begin(_M_base), 0); } constexpr auto end() requires (!__detail::__simple_view<_Vp>) { if constexpr (common_range<_Vp> && sized_range<_Vp>) return _Iterator(ranges::end(_M_base), ranges::distance(_M_base)); else return _Sentinel(ranges::end(_M_base)); } constexpr auto end() const requires __detail::__range_with_movable_reference { if constexpr (common_range && sized_range) return _Iterator(ranges::end(_M_base), ranges::distance(_M_base)); else return _Sentinel(ranges::end(_M_base)); } constexpr auto size() requires sized_range<_Vp> { return ranges::size(_M_base); } constexpr auto size() const requires sized_range { return ranges::size(_M_base); } constexpr _Vp base() const & requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && { return std::move(_M_base); } }; template enumerate_view(_Range&&) -> enumerate_view>; template inline constexpr bool enable_borrowed_range> = enable_borrowed_range<_Tp>; template requires __detail::__range_with_movable_reference<_Vp> template class enumerate_view<_Vp>::_Iterator { using _Base = __maybe_const_t<_Const, _Vp>; static auto _S_iter_concept() { if constexpr (random_access_range<_Base>) return random_access_iterator_tag{}; else if constexpr (bidirectional_range<_Base>) return bidirectional_iterator_tag{}; else if constexpr (forward_range<_Base>) return forward_iterator_tag{}; else return input_iterator_tag{}; } friend enumerate_view; public: using iterator_category = input_iterator_tag; using iterator_concept = decltype(_S_iter_concept()); using difference_type = range_difference_t<_Base>; using value_type = tuple>; private: using __reference_type = tuple>; iterator_t<_Base> _M_current = iterator_t<_Base>(); difference_type _M_pos = 0; constexpr explicit _Iterator(iterator_t<_Base> __current, difference_type __pos) : _M_current(std::move(__current)), _M_pos(__pos) { } public: _Iterator() requires default_initializable> = default; constexpr _Iterator(_Iterator __i) requires _Const && convertible_to, iterator_t<_Base>> : _M_current(std::move(__i._M_current)), _M_pos(__i._M_pos) { } constexpr const iterator_t<_Base> & base() const & noexcept { return _M_current; } constexpr iterator_t<_Base> base() && { return std::move(_M_current); } constexpr difference_type index() const noexcept { return _M_pos; } constexpr auto operator*() const { return __reference_type(_M_pos, *_M_current); } constexpr _Iterator& operator++() { ++_M_current; ++_M_pos; return *this; } constexpr void operator++(int) { ++*this; } constexpr _Iterator operator++(int) requires forward_range<_Base> { auto __tmp = *this; ++*this; return __tmp; } constexpr _Iterator& operator--() requires bidirectional_range<_Base> { --_M_current; --_M_pos; return *this; } constexpr _Iterator operator--(int) requires bidirectional_range<_Base> { auto __tmp = *this; --*this; return __tmp; } constexpr _Iterator& operator+=(difference_type __n) requires random_access_range<_Base> { _M_current += __n; _M_pos += __n; return *this; } constexpr _Iterator& operator-=(difference_type __n) requires random_access_range<_Base> { _M_current -= __n; _M_pos -= __n; return *this; } constexpr auto operator[](difference_type __n) const requires random_access_range<_Base> { return __reference_type(_M_pos + __n, _M_current[__n]); } friend constexpr bool operator==(const _Iterator& __x, const _Iterator& __y) noexcept { return __x._M_pos == __y._M_pos; } friend constexpr strong_ordering operator<=>(const _Iterator& __x, const _Iterator& __y) noexcept { return __x._M_pos <=> __y._M_pos; } friend constexpr _Iterator operator+(const _Iterator& __x, difference_type __y) requires random_access_range<_Base> { return (auto(__x) += __y); } friend constexpr _Iterator operator+(difference_type __x, const _Iterator& __y) requires random_access_range<_Base> { return auto(__y) += __x; } friend constexpr _Iterator operator-(const _Iterator& __x, difference_type __y) requires random_access_range<_Base> { return auto(__x) -= __y; } friend constexpr difference_type operator-(const _Iterator& __x, const _Iterator& __y) { return __x._M_pos - __y._M_pos; } friend constexpr auto iter_move(const _Iterator& __i) noexcept(noexcept(ranges::iter_move(__i._M_current)) && is_nothrow_move_constructible_v>) { return tuple> (__i._M_pos, ranges::iter_move(__i._M_current)); } }; template requires __detail::__range_with_movable_reference<_Vp> template class enumerate_view<_Vp>::_Sentinel { using _Base = __maybe_const_t<_Const, _Vp>; sentinel_t<_Base> _M_end = sentinel_t<_Base>(); constexpr explicit _Sentinel(sentinel_t<_Base> __end) : _M_end(std::move(__end)) { } friend enumerate_view; public: _Sentinel() = default; constexpr _Sentinel(_Sentinel __other) requires _Const && convertible_to, sentinel_t<_Base>> : _M_end(std::move(__other._M_end)) { } constexpr sentinel_t<_Base> base() const { return _M_end; } template requires sentinel_for, iterator_t<__maybe_const_t<_OtherConst, _Vp>>> friend constexpr bool operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) { return __x._M_current == __y._M_end; } template requires sized_sentinel_for, iterator_t<__maybe_const_t<_OtherConst, _Vp>>> friend constexpr range_difference_t<__maybe_const_t<_OtherConst, _Vp>> operator-(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) { return __x._M_current - __y._M_end; } template requires sized_sentinel_for, iterator_t<__maybe_const_t<_OtherConst, _Vp>>> friend constexpr range_difference_t<__maybe_const_t<_OtherConst, _Vp>> operator-(const _Sentinel& __x, const _Iterator<_OtherConst>& __y) { return __x._M_end - __y._M_current; } }; namespace views { namespace __detail { template concept __can_enumerate_view = requires { enumerate_view>(std::declval<_Tp>()); }; } struct _Enumerate : __adaptor::_RangeAdaptorClosure<_Enumerate> { template requires __detail::__can_enumerate_view<_Range> constexpr auto operator() [[nodiscard]] (_Range&& __r) const { return enumerate_view>(std::forward<_Range>(__r)); } }; inline constexpr _Enumerate enumerate; } #endif // __cpp_lib_ranges_enumerate #ifdef __cpp_lib_ranges_as_const // C++ >= 23 template requires input_range<_Vp> class as_const_view : public view_interface> { _Vp _M_base = _Vp(); public: as_const_view() requires default_initializable<_Vp> = default; constexpr explicit as_const_view(_Vp __base) noexcept(is_nothrow_move_constructible_v<_Vp>) : _M_base(std::move(__base)) { } constexpr _Vp base() const & noexcept(is_nothrow_copy_constructible_v<_Vp>) requires copy_constructible<_Vp> { return _M_base; } constexpr _Vp base() && noexcept(is_nothrow_move_constructible_v<_Vp>) { return std::move(_M_base); } constexpr auto begin() requires (!__detail::__simple_view<_Vp>) { return ranges::cbegin(_M_base); } constexpr auto begin() const requires range { return ranges::cbegin(_M_base); } constexpr auto end() requires (!__detail::__simple_view<_Vp>) { return ranges::cend(_M_base); } constexpr auto end() const requires range { return ranges::cend(_M_base); } constexpr auto size() requires sized_range<_Vp> { return ranges::size(_M_base); } constexpr auto size() const requires sized_range { return ranges::size(_M_base); } }; template as_const_view(_Range&&) -> as_const_view>; template inline constexpr bool enable_borrowed_range> = enable_borrowed_range<_Tp>; namespace views { namespace __detail { template inline constexpr bool __is_ref_view = false; template inline constexpr bool __is_ref_view> = true; template concept __can_as_const_view = requires { as_const_view(std::declval<_Range>()); }; } struct _AsConst : __adaptor::_RangeAdaptorClosure<_AsConst> { template constexpr auto operator()(_Range&& __r) const noexcept(noexcept(as_const_view(std::declval<_Range>()))) requires __detail::__can_as_const_view<_Range> { using _Tp = remove_cvref_t<_Range>; using element_type = remove_reference_t>; if constexpr (constant_range>) return views::all(std::forward<_Range>(__r)); else if constexpr (__detail::__is_empty_view<_Tp>) return views::empty; else if constexpr (std::__detail::__is_span<_Tp>) return span(std::forward<_Range>(__r)); else if constexpr (__detail::__is_ref_view<_Tp> && constant_range) return ref_view(static_cast (std::forward<_Range>(__r).base())); else if constexpr (is_lvalue_reference_v<_Range> && constant_range && !view<_Tp>) return ref_view(static_cast(__r)); else return as_const_view(std::forward<_Range>(__r)); } }; inline constexpr _AsConst as_const; } #endif // __cpp_lib_as_const } // namespace ranges namespace views = ranges::views; #if __cpp_lib_ranges_to_container // C++ >= 23 namespace ranges { /// @cond undocumented namespace __detail { template constexpr bool __reservable_container = sized_range<_Container> && requires(_Container& __c, range_size_t<_Container> __n) { __c.reserve(__n); { __c.capacity() } -> same_as; { __c.max_size() } -> same_as; }; template constexpr bool __toable = requires { requires (!input_range<_Cont> || convertible_to, range_value_t<_Cont>>); }; } // namespace __detail /// @endcond /// Convert a range to a container. /** * @tparam _Cont A container type. * @param __r A range that models the `input_range` concept. * @param __args... Arguments to pass to the container constructor. * @since C++23 * * This function converts a range to the `_Cont` type. * * For example, `std::ranges::to>(some_view)` * will convert the view to `std::vector`. * * Additional constructor arguments for the container can be supplied after * the input range argument, e.g. * `std::ranges::to>>(a_range, an_allocator)`. */ template requires (!view<_Cont>) constexpr _Cont to [[nodiscard]] (_Rg&& __r, _Args&&... __args) { static_assert(!is_const_v<_Cont> && !is_volatile_v<_Cont>); static_assert(is_class_v<_Cont>); if constexpr (__detail::__toable<_Cont, _Rg>) { if constexpr (constructible_from<_Cont, _Rg, _Args...>) return _Cont(std::forward<_Rg>(__r), std::forward<_Args>(__args)...); else if constexpr (constructible_from<_Cont, from_range_t, _Rg, _Args...>) return _Cont(from_range, std::forward<_Rg>(__r), std::forward<_Args>(__args)...); else if constexpr (requires { requires common_range<_Rg>; typename __iter_category_t>; requires derived_from<__iter_category_t>, input_iterator_tag>; requires constructible_from<_Cont, iterator_t<_Rg>, sentinel_t<_Rg>, _Args...>; }) return _Cont(ranges::begin(__r), ranges::end(__r), std::forward<_Args>(__args)...); else { using _RefT = range_reference_t<_Rg>; static_assert(constructible_from<_Cont, _Args...>); _Cont __c(std::forward<_Args>(__args)...); if constexpr (sized_range<_Rg> && __detail::__reservable_container<_Cont>) __c.reserve(static_cast>(ranges::size(__r))); // _GLIBCXX_RESOLVE_LIB_DEFECTS // 4016. container-insertable checks do not match what // container-inserter does auto __it = ranges::begin(__r); const auto __sent = ranges::end(__r); while (__it != __sent) { if constexpr (requires { __c.emplace_back(*__it); }) __c.emplace_back(*__it); else if constexpr (requires { __c.push_back(*__it); }) __c.push_back(*__it); else if constexpr (requires { __c.emplace(__c.end(), *__it); }) __c.emplace(__c.end(), *__it); else __c.insert(__c.end(), *__it); ++__it; } return __c; } } else { static_assert(input_range>); // _GLIBCXX_RESOLVE_LIB_DEFECTS // 3984. ranges::to's recursion branch may be ill-formed return ranges::to<_Cont>(ref_view(__r) | views::transform( [](_Elt&& __elem) { using _ValT = range_value_t<_Cont>; return ranges::to<_ValT>(std::forward<_Elt>(__elem)); }), std::forward<_Args>(__args)...); } } /// @cond undocumented namespace __detail { template struct _InputIter { using iterator_category = input_iterator_tag; using value_type = range_value_t<_Rg>; using difference_type = ptrdiff_t; using pointer = add_pointer_t>; using reference = range_reference_t<_Rg>; reference operator*() const; pointer operator->() const; _InputIter& operator++(); _InputIter operator++(int); bool operator==(const _InputIter&) const; }; template typename _Cont, input_range _Rg, typename... _Args> using _DeduceExpr1 = decltype(_Cont(std::declval<_Rg>(), std::declval<_Args>()...)); template typename _Cont, input_range _Rg, typename... _Args> using _DeduceExpr2 = decltype(_Cont(from_range, std::declval<_Rg>(), std::declval<_Args>()...)); template typename _Cont, input_range _Rg, typename... _Args> using _DeduceExpr3 = decltype(_Cont(std::declval<_InputIter<_Rg>>(), std::declval<_InputIter<_Rg>>(), std::declval<_Args>()...)); } // namespace __detail /// @endcond template typename _Cont, input_range _Rg, typename... _Args> constexpr auto to [[nodiscard]] (_Rg&& __r, _Args&&... __args) { using __detail::_DeduceExpr1; using __detail::_DeduceExpr2; using __detail::_DeduceExpr3; if constexpr (requires { typename _DeduceExpr1<_Cont, _Rg, _Args...>; }) return ranges::to<_DeduceExpr1<_Cont, _Rg, _Args...>>( std::forward<_Rg>(__r), std::forward<_Args>(__args)...); else if constexpr (requires { typename _DeduceExpr2<_Cont, _Rg, _Args...>; }) return ranges::to<_DeduceExpr2<_Cont, _Rg, _Args...>>( std::forward<_Rg>(__r), std::forward<_Args>(__args)...); else if constexpr (requires { typename _DeduceExpr3<_Cont, _Rg, _Args...>; }) return ranges::to<_DeduceExpr3<_Cont, _Rg, _Args...>>( std::forward<_Rg>(__r), std::forward<_Args>(__args)...); else static_assert(false); // Cannot deduce container specialization. } /// @cond undocumented namespace __detail { template struct _To { template requires requires { ranges::to<_Cont>(std::declval<_Range>(), std::declval<_Args>()...); } constexpr auto operator()(_Range&& __r, _Args&&... __args) const { return ranges::to<_Cont>(std::forward<_Range>(__r), std::forward<_Args>(__args)...); } }; } // namespace __detail /// @endcond /// ranges::to adaptor for converting a range to a container type /** * @tparam _Cont A container type. * @param __args... Arguments to pass to the container constructor. * @since C++23 * * This range adaptor returns a range adaptor closure object that converts * a range to the `_Cont` type. * * For example, `some_view | std::ranges::to>()` * will convert the view to `std::vector`. * * Additional constructor arguments for the container can be supplied, e.g. * `r | std::ranges::to>>(an_allocator)`. */ template requires (!view<_Cont>) constexpr auto to [[nodiscard]] (_Args&&... __args) { using __detail::_To; using views::__adaptor::_Partial; return _Partial<_To<_Cont>, decay_t<_Args>...>{std::forward<_Args>(__args)...}; } /// @cond undocumented namespace __detail { template typename _Cont> struct _To2 { template requires requires { ranges::to<_Cont>(std::declval<_Range>(), std::declval<_Args>()...); } constexpr auto operator()(_Range&& __r, _Args&&... __args) const { return ranges::to<_Cont>(std::forward<_Range>(__r), std::forward<_Args>(__args)...); } }; } // namespace __detail /// @endcond /// ranges::to adaptor for converting a range to a deduced container type. /** * @tparam _Cont A container template. * @param __args... Arguments to pass to the container constructor. * @since C++23 * * This range adaptor returns a range adaptor closure object that converts * a range to a specialization of the `_Cont` class template. The specific * specialization of `_Cont` to be used is deduced automatically. * * For example, `some_view | std::ranges::to(Alloc{})` * will convert the view to `std::vector>`, where `T` is the * view's value type, i.e. `std::ranges::range_value_t`. * * Additional constructor arguments for the container can be supplied, e.g. * `r | std::ranges::to(an_allocator)`. */ template typename _Cont, typename... _Args> constexpr auto to [[nodiscard]] (_Args&&... __args) { using __detail::_To2; using views::__adaptor::_Partial; return _Partial<_To2<_Cont>, decay_t<_Args>...>{std::forward<_Args>(__args)...}; } } // namespace ranges #endif // __cpp_lib_ranges_to_container _GLIBCXX_END_NAMESPACE_VERSION } // namespace std #endif // library concepts #endif // C++2a #endif /* _GLIBCXX_RANGES */