// <ranges> -*- C++ -*-
-// Copyright (C) 2019-2020 Free Software Foundation, Inc.
+// Copyright (C) 2019-2022 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
// 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;
+// 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
// <http://www.gnu.org/licenses/>.
#if __cpp_lib_concepts
-#include <bits/refwrap.h>
#include <compare>
#include <initializer_list>
#include <iterator>
#include <optional>
+#include <span>
#include <tuple>
+#if __cplusplus > 202002L
+#include <variant>
+#endif
+#include <bits/ranges_util.h>
+#include <bits/refwrap.h>
/**
* @defgroup ranges Ranges
_GLIBCXX_BEGIN_NAMESPACE_VERSION
namespace ranges
{
- // [range.range] The range concept.
- // [range.sized] The sized_range concept.
- // Defined in <bits/range_access.h>
-
- // [range.refinements]
- // Defined in <bits/range_access.h>
-
- struct view_base { };
-
- template<typename _Tp>
- inline constexpr bool enable_view = derived_from<_Tp, view_base>;
-
- template<typename _Tp>
- concept view
- = range<_Tp> && movable<_Tp> && default_initializable<_Tp>
- && enable_view<_Tp>;
-
- /// A range which can be safely converted to a view.
- template<typename _Tp>
- concept viewable_range = range<_Tp>
- && (borrowed_range<_Tp> || view<remove_cvref_t<_Tp>>);
-
- namespace __detail
- {
- template<typename _Range>
- concept __simple_view = view<_Range> && range<const _Range>
- && same_as<iterator_t<_Range>, iterator_t<const _Range>>
- && same_as<sentinel_t<_Range>, sentinel_t<const _Range>>;
-
- template<typename _It>
- concept __has_arrow = input_iterator<_It>
- && (is_pointer_v<_It> || requires(_It __it) { __it.operator->(); });
-
- template<typename _Tp, typename _Up>
- concept __not_same_as
- = !same_as<remove_cvref_t<_Tp>, remove_cvref_t<_Up>>;
- } // namespace __detail
-
- template<typename _Derived>
- requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
- class view_interface : public view_base
- {
- private:
- constexpr _Derived& _M_derived() noexcept
- {
- static_assert(derived_from<_Derived, view_interface<_Derived>>);
- static_assert(view<_Derived>);
- return static_cast<_Derived&>(*this);
- }
-
- constexpr const _Derived& _M_derived() const noexcept
- {
- static_assert(derived_from<_Derived, view_interface<_Derived>>);
- static_assert(view<_Derived>);
- return static_cast<const _Derived&>(*this);
- }
-
- public:
- constexpr bool
- empty() requires forward_range<_Derived>
- { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }
-
- constexpr bool
- empty() const requires forward_range<const _Derived>
- { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }
-
- constexpr explicit
- operator bool() requires requires { ranges::empty(_M_derived()); }
- { return !ranges::empty(_M_derived()); }
-
- constexpr explicit
- operator bool() const requires requires { ranges::empty(_M_derived()); }
- { return !ranges::empty(_M_derived()); }
-
- constexpr auto
- data() requires contiguous_iterator<iterator_t<_Derived>>
- { return to_address(ranges::begin(_M_derived())); }
-
- constexpr auto
- data() const
- requires range<const _Derived>
- && contiguous_iterator<iterator_t<const _Derived>>
- { return to_address(ranges::begin(_M_derived())); }
-
- constexpr auto
- size()
- requires forward_range<_Derived>
- && sized_sentinel_for<sentinel_t<_Derived>, iterator_t<_Derived>>
- { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }
-
- constexpr auto
- size() const
- requires forward_range<const _Derived>
- && sized_sentinel_for<sentinel_t<const _Derived>,
- iterator_t<const _Derived>>
- { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }
-
- constexpr decltype(auto)
- front() requires forward_range<_Derived>
- {
- __glibcxx_assert(!empty());
- return *ranges::begin(_M_derived());
- }
-
- constexpr decltype(auto)
- front() const requires forward_range<const _Derived>
- {
- __glibcxx_assert(!empty());
- return *ranges::begin(_M_derived());
- }
-
- constexpr decltype(auto)
- back()
- requires bidirectional_range<_Derived> && common_range<_Derived>
- {
- __glibcxx_assert(!empty());
- return *ranges::prev(ranges::end(_M_derived()));
- }
-
- constexpr decltype(auto)
- back() const
- requires bidirectional_range<const _Derived>
- && common_range<const _Derived>
- {
- __glibcxx_assert(!empty());
- return *ranges::prev(ranges::end(_M_derived()));
- }
-
- template<random_access_range _Range = _Derived>
- constexpr decltype(auto)
- operator[](range_difference_t<_Range> __n)
- { return ranges::begin(_M_derived())[__n]; }
-
- template<random_access_range _Range = const _Derived>
- constexpr decltype(auto)
- operator[](range_difference_t<_Range> __n) const
- { return ranges::begin(_M_derived())[__n]; }
- };
-
- namespace __detail
- {
- template<class _From, class _To>
- concept __convertible_to_non_slicing = convertible_to<_From, _To>
- && !(is_pointer_v<decay_t<_From>> && is_pointer_v<decay_t<_To>>
- && __not_same_as<remove_pointer_t<decay_t<_From>>,
- remove_pointer_t<decay_t<_To>>>);
-
- template<typename _Tp>
- concept __pair_like
- = !is_reference_v<_Tp> && requires(_Tp __t)
- {
- typename tuple_size<_Tp>::type;
- requires derived_from<tuple_size<_Tp>, integral_constant<size_t, 2>>;
- typename tuple_element_t<0, remove_const_t<_Tp>>;
- typename tuple_element_t<1, remove_const_t<_Tp>>;
- { get<0>(__t) } -> convertible_to<const tuple_element_t<0, _Tp>&>;
- { get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>;
- };
-
- template<typename _Tp, typename _Up, typename _Vp>
- concept __pair_like_convertible_from
- = !range<_Tp> && __pair_like<_Tp>
- && constructible_from<_Tp, _Up, _Vp>
- && __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>>
- && convertible_to<_Vp, tuple_element_t<1, _Tp>>;
-
- template<typename _Tp>
- concept __iterator_sentinel_pair
- = !range<_Tp> && __pair_like<_Tp>
- && sentinel_for<tuple_element_t<1, _Tp>, tuple_element_t<0, _Tp>>;
-
- } // namespace __detail
-
- enum class subrange_kind : bool { unsized, sized };
-
- template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
- subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
- ? subrange_kind::sized : subrange_kind::unsized>
- requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>)
- class subrange : public view_interface<subrange<_It, _Sent, _Kind>>
- {
- private:
- // XXX: gcc complains when using constexpr here
- static const bool _S_store_size
- = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>;
-
- _It _M_begin = _It();
- _Sent _M_end = _Sent();
-
- template<typename, bool = _S_store_size>
- struct _Size
- { };
-
- template<typename _Tp>
- struct _Size<_Tp, true>
- { __detail::__make_unsigned_like_t<_Tp> _M_size; };
-
- [[no_unique_address]] _Size<iter_difference_t<_It>> _M_size = {};
-
- public:
- subrange() = default;
-
- constexpr
- subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s)
- requires (!_S_store_size)
- : _M_begin(std::move(__i)), _M_end(__s)
- { }
-
- constexpr
- subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s,
- __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
- requires (_Kind == subrange_kind::sized)
- : _M_begin(std::move(__i)), _M_end(__s)
- {
- using __detail::__to_unsigned_like;
- __glibcxx_assert(__n == __to_unsigned_like(ranges::distance(__i, __s)));
- if constexpr (_S_store_size)
- _M_size._M_size = __n;
- }
-
- template<__detail::__not_same_as<subrange> _Rng>
- requires borrowed_range<_Rng>
- && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
- && convertible_to<sentinel_t<_Rng>, _Sent>
- constexpr
- subrange(_Rng&& __r) requires _S_store_size && sized_range<_Rng>
- : subrange{__r, ranges::size(__r)}
- { }
-
- template<__detail::__not_same_as<subrange> _Rng>
- requires borrowed_range<_Rng>
- && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
- && convertible_to<sentinel_t<_Rng>, _Sent>
- constexpr
- subrange(_Rng&& __r) requires (!_S_store_size)
- : subrange{ranges::begin(__r), ranges::end(__r)}
- { }
-
- template<borrowed_range _Rng>
- requires __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
- && convertible_to<sentinel_t<_Rng>, _Sent>
- constexpr
- subrange(_Rng&& __r,
- __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
- requires (_Kind == subrange_kind::sized)
- : subrange{ranges::begin(__r), ranges::end(__r), __n}
- { }
-
- template<__detail::__not_same_as<subrange> _PairLike>
- requires __detail::__pair_like_convertible_from<_PairLike, const _It&,
- const _Sent&>
- constexpr
- operator _PairLike() const
- { return _PairLike(_M_begin, _M_end); }
-
- constexpr _It
- begin() const requires copyable<_It>
- { return _M_begin; }
-
- [[nodiscard]] constexpr _It
- begin() requires (!copyable<_It>)
- { return std::move(_M_begin); }
-
- constexpr _Sent end() const { return _M_end; }
-
- constexpr bool empty() const { return _M_begin == _M_end; }
-
- constexpr __detail::__make_unsigned_like_t<iter_difference_t<_It>>
- size() const requires (_Kind == subrange_kind::sized)
- {
- if constexpr (_S_store_size)
- return _M_size._M_size;
- else
- return __detail::__to_unsigned_like(_M_end - _M_begin);
- }
-
- [[nodiscard]] constexpr subrange
- next(iter_difference_t<_It> __n = 1) const &
- requires forward_iterator<_It>
- {
- auto __tmp = *this;
- __tmp.advance(__n);
- return __tmp;
- }
-
- [[nodiscard]] constexpr subrange
- next(iter_difference_t<_It> __n = 1) &&
- {
- advance(__n);
- return std::move(*this);
- }
-
- [[nodiscard]] constexpr subrange
- prev(iter_difference_t<_It> __n = 1) const
- requires bidirectional_iterator<_It>
- {
- auto __tmp = *this;
- __tmp.advance(-__n);
- return __tmp;
- }
-
- constexpr subrange&
- advance(iter_difference_t<_It> __n)
- {
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // 3433. subrange::advance(n) has UB when n < 0
- if constexpr (bidirectional_iterator<_It>)
- if (__n < 0)
- {
- ranges::advance(_M_begin, __n);
- if constexpr (_S_store_size)
- _M_size._M_size += __detail::__to_unsigned_like(-__n);
- return *this;
- }
-
- __glibcxx_assert(__n >= 0);
- auto __d = __n - ranges::advance(_M_begin, __n, _M_end);
- if constexpr (_S_store_size)
- _M_size._M_size -= __detail::__to_unsigned_like(__d);
- return *this;
- }
- };
-
- template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
- subrange(_It, _Sent) -> subrange<_It, _Sent>;
-
- template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
- subrange(_It, _Sent,
- __detail::__make_unsigned_like_t<iter_difference_t<_It>>)
- -> subrange<_It, _Sent, subrange_kind::sized>;
-
- template<__detail::__iterator_sentinel_pair _Pr>
- subrange(_Pr)
- -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>>;
-
- template<__detail::__iterator_sentinel_pair _Pr>
- subrange(_Pr, __detail::__make_unsigned_like_t<iter_difference_t<
- tuple_element_t<0, _Pr>>>)
- -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>,
- subrange_kind::sized>;
-
- template<borrowed_range _Rng>
- subrange(_Rng&&)
- -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>,
- (sized_range<_Rng>
- || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>)
- ? subrange_kind::sized : subrange_kind::unsized>;
-
- template<borrowed_range _Rng>
- subrange(_Rng&&,
- __detail::__make_unsigned_like_t<range_difference_t<_Rng>>)
- -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>;
-
- template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
- requires (_Num < 2)
- constexpr auto
- get(const subrange<_It, _Sent, _Kind>& __r)
- {
- if constexpr (_Num == 0)
- return __r.begin();
- else
- return __r.end();
- }
-
- template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
- requires (_Num < 2)
- constexpr auto
- get(subrange<_It, _Sent, _Kind>&& __r)
- {
- if constexpr (_Num == 0)
- return __r.begin();
- else
- return __r.end();
- }
-
- template<input_or_output_iterator _It, sentinel_for<_It> _Sent,
- subrange_kind _Kind>
- inline constexpr bool
- enable_borrowed_range<subrange<_It, _Sent, _Kind>> = true;
-
-} // namespace ranges
-
- using ranges::get;
-
-namespace ranges
-{
- /// Type returned by algorithms instead of a dangling iterator or subrange.
- struct dangling
- {
- constexpr dangling() noexcept = default;
- template<typename... _Args>
- constexpr dangling(_Args&&...) noexcept { }
- };
+ // [range.access] customization point objects
+ // [range.req] range and view concepts
+ // [range.dangling] dangling iterator handling
+ // Defined in <bits/ranges_base.h>
- template<range _Range>
- using borrowed_iterator_t = conditional_t<borrowed_range<_Range>,
- iterator_t<_Range>,
- dangling>;
+ // [view.interface] View interface
+ // [range.subrange] Sub-ranges
+ // Defined in <bits/ranges_util.h>
- template<range _Range>
- using borrowed_subrange_t = conditional_t<borrowed_range<_Range>,
- subrange<iterator_t<_Range>>,
- dangling>;
+ // C++20 24.6 [range.factories] Range factories
+ /// A view that contains no elements.
template<typename _Tp> requires is_object_v<_Tp>
class empty_view
: public view_interface<empty_view<_Tp>>
namespace __detail
{
- template<copy_constructible _Tp> requires is_object_v<_Tp>
+ template<typename _Tp>
+ concept __boxable = copy_constructible<_Tp> && is_object_v<_Tp>;
+
+ template<__boxable _Tp>
struct __box : std::optional<_Tp>
{
using std::optional<_Tp>::optional;
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 3477. Simplify constraints for semiregular-box
- __box&
+ // 3572. copyable-box should be fully constexpr
+ constexpr __box&
operator=(const __box& __that)
noexcept(is_nothrow_copy_constructible_v<_Tp>)
requires (!copyable<_Tp>)
{
- if ((bool)__that)
- this->emplace(*__that);
- else
- this->reset();
+ if (this != std::__addressof(__that))
+ {
+ if ((bool)__that)
+ this->emplace(*__that);
+ else
+ this->reset();
+ }
return *this;
}
- __box&
+ constexpr __box&
operator=(__box&& __that)
noexcept(is_nothrow_move_constructible_v<_Tp>)
requires (!movable<_Tp>)
{
- if ((bool)__that)
- this->emplace(std::move(*__that));
- else
- this->reset();
+ if (this != std::__addressof(__that))
+ {
+ if ((bool)__that)
+ this->emplace(std::move(*__that));
+ else
+ this->reset();
+ }
return *this;
}
};
+ // For types which are already copyable, this specialization of the
+ // copyable 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 copyable<_Tp> || (is_nothrow_move_constructible_v<_Tp>
+ && is_nothrow_copy_constructible_v<_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>)
+ : _M_value(__t)
+ { }
+
+ constexpr explicit
+ __box(_Tp&& __t)
+ noexcept(is_nothrow_move_constructible_v<_Tp>)
+ : _M_value(std::move(__t))
+ { }
+
+ template<typename... _Args>
+ 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 copyable<_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
+ {
+ 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
+ {
+ 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::__addressof(_M_value); }
+
+ constexpr const _Tp*
+ operator->() const noexcept
+ { return std::__addressof(_M_value); }
+ };
} // namespace __detail
/// A view that contains exactly one element.
class single_view : public view_interface<single_view<_Tp>>
{
public:
- single_view() = default;
+ single_view() requires default_initializable<_Tp> = default;
constexpr explicit
single_view(const _Tp& __t)
+ noexcept(is_nothrow_copy_constructible_v<_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<typename... _Args>
requires constructible_from<_Tp, _Args...>
- constexpr
+ constexpr explicit
single_view(in_place_t, _Args&&... __args)
+ noexcept(is_nothrow_constructible_v<_Tp, _Args...>)
: _M_value{in_place, std::forward<_Args>(__args)...}
{ }
{ return _M_value.operator->(); }
private:
- __detail::__box<_Tp> _M_value;
+ [[no_unique_address]] __detail::__box<_Tp> _M_value;
};
+ template<typename _Tp>
+ single_view(_Tp) -> single_view<_Tp>;
+
namespace __detail
{
template<typename _Wp>
{ __j - __j } -> convertible_to<__iota_diff_t<_It>>;
};
+ template<typename _Winc>
+ struct __iota_view_iter_cat
+ { };
+
+ template<incrementable _Winc>
+ struct __iota_view_iter_cat<_Winc>
+ { using iterator_category = input_iterator_tag; };
} // namespace __detail
template<weakly_incrementable _Winc,
semiregular _Bound = unreachable_sentinel_t>
requires std::__detail::__weakly_eq_cmp_with<_Winc, _Bound>
- && semiregular<_Winc>
+ && copyable<_Winc>
class iota_view : public view_interface<iota_view<_Winc, _Bound>>
{
private:
struct _Sentinel;
- struct _Iterator
+ struct _Iterator : __detail::__iota_view_iter_cat<_Winc>
{
private:
static auto
- _S_iter_cat()
+ _S_iter_concept()
{
using namespace __detail;
if constexpr (__advanceable<_Winc>)
}
public:
- using iterator_category = decltype(_S_iter_cat());
+ 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() = default;
+ _Iterator() requires default_initializable<_Winc> = default;
constexpr explicit
_Iterator(_Winc __value)
friend constexpr _Iterator
operator+(_Iterator __i, difference_type __n)
requires __detail::__advanceable<_Winc>
- { return __i += __n; }
+ {
+ __i += __n;
+ return __i;
+ }
friend constexpr _Iterator
operator+(difference_type __n, _Iterator __i)
friend constexpr _Iterator
operator-(_Iterator __i, difference_type __n)
requires __detail::__advanceable<_Winc>
- { return __i -= __n; }
+ {
+ __i -= __n;
+ return __i;
+ }
friend constexpr difference_type
operator-(const _Iterator& __x, const _Iterator& __y)
private:
_Winc _M_value = _Winc();
+ friend iota_view;
friend _Sentinel;
};
_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:
friend constexpr iter_difference_t<_Winc>
operator-(const _Iterator& __x, const _Sentinel& __y)
requires sized_sentinel_for<_Bound, _Winc>
- { return __x._M_value - __y._M_bound; }
+ { 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 -(__y - __x); }
+ { return __x._M_distance_from(__y); }
+
+ friend iota_view;
};
_Winc _M_value = _Winc();
- _Bound _M_bound = _Bound();
+ [[no_unique_address]] _Bound _M_bound = _Bound();
public:
- iota_view() = default;
+ iota_view() requires default_initializable<_Winc> = default;
constexpr explicit
iota_view(_Winc __value)
__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}; }
== __detail::__is_signed_integer_like<_Bound>))
iota_view(_Winc, _Bound) -> iota_view<_Winc, _Bound>;
- template<weakly_incrementable _Winc, semiregular _Bound>
+ template<typename _Winc, typename _Bound>
inline constexpr bool
enable_borrowed_range<iota_view<_Winc, _Bound>> = true;
struct _Single
{
template<typename _Tp>
+ [[nodiscard]]
constexpr auto
operator()(_Tp&& __e) const
- { return single_view{std::forward<_Tp>(__e)}; }
+ noexcept(noexcept(single_view<decay_t<_Tp>>(std::forward<_Tp>(__e))))
+ { return single_view<decay_t<_Tp>>(std::forward<_Tp>(__e)); }
};
inline constexpr _Single single{};
struct _Iota
{
template<typename _Tp>
+ [[nodiscard]]
constexpr auto
operator()(_Tp&& __e) const
- { return iota_view{std::forward<_Tp>(__e)}; }
+ { return iota_view(std::forward<_Tp>(__e)); }
template<typename _Tp, typename _Up>
+ [[nodiscard]]
constexpr auto
operator()(_Tp&& __e, _Up&& __f) const
- { return iota_view{std::forward<_Tp>(__e), std::forward<_Up>(__f)}; }
+ { return iota_view(std::forward<_Tp>(__e), std::forward<_Up>(__f)); }
};
inline constexpr _Iota iota{};
} // namespace views
+#if _GLIBCXX_HOSTED
namespace __detail
{
template<typename _Val, typename _CharT, typename _Traits>
= requires(basic_istream<_CharT, _Traits>& is, _Val& t) { is >> t; };
} // namespace __detail
- template<movable _Val, typename _CharT, typename _Traits>
+ template<movable _Val, typename _CharT,
+ typename _Traits = char_traits<_CharT>>
requires default_initializable<_Val>
&& __detail::__stream_extractable<_Val, _CharT, _Traits>
class basic_istream_view
: public view_interface<basic_istream_view<_Val, _CharT, _Traits>>
{
public:
- basic_istream_view() = default;
-
constexpr explicit
basic_istream_view(basic_istream<_CharT, _Traits>& __stream)
: _M_stream(std::__addressof(__stream))
constexpr auto
begin()
{
- if (_M_stream != nullptr)
- *_M_stream >> _M_object;
- return _Iterator{*this};
+ *_M_stream >> _M_object;
+ return _Iterator{this};
}
constexpr default_sentinel_t
{ return default_sentinel; }
private:
- basic_istream<_CharT, _Traits>* _M_stream = nullptr;
+ basic_istream<_CharT, _Traits>* _M_stream;
_Val _M_object = _Val();
struct _Iterator
using difference_type = ptrdiff_t;
using value_type = _Val;
- _Iterator() = default;
-
constexpr explicit
- _Iterator(basic_istream_view& __parent) noexcept
- : _M_parent(std::__addressof(__parent))
+ _Iterator(basic_istream_view* __parent) noexcept
+ : _M_parent(__parent)
{ }
_Iterator(const _Iterator&) = delete;
_Iterator&
operator++()
{
- __glibcxx_assert(_M_parent->_M_stream != nullptr);
*_M_parent->_M_stream >> _M_parent->_M_object;
return *this;
}
_Val&
operator*() const
- {
- __glibcxx_assert(_M_parent->_M_stream != nullptr);
- return _M_parent->_M_object;
- }
+ { 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 = nullptr;
+ basic_istream_view* _M_parent;
bool
_M_at_end() const
- { return _M_parent == nullptr || !*_M_parent->_M_stream; }
+ { return !*_M_parent->_M_stream; }
};
friend _Iterator;
};
- template<typename _Val, typename _CharT, typename _Traits>
- basic_istream_view<_Val, _CharT, _Traits>
- istream_view(basic_istream<_CharT, _Traits>& __s)
- { return basic_istream_view<_Val, _CharT, _Traits>{__s}; }
+ template<typename _Val>
+ using istream_view = basic_istream_view<_Val, char>;
+
+ template<typename _Val>
+ using wistream_view = basic_istream_view<_Val, wchar_t>;
+
+namespace views
+{
+ template<typename _Tp>
+ struct _Istream
+ {
+ template<typename _CharT, typename _Traits>
+ [[nodiscard]]
+ constexpr auto
+ operator()(basic_istream<_CharT, _Traits>& __e) const
+ { return basic_istream_view<_Tp, _CharT, _Traits>(__e); }
+ };
+
+ template<typename _Tp>
+ inline constexpr _Istream<_Tp> istream;
+}
+#endif // HOSTED
+
+ // C++20 24.7 [range.adaptors] Range adaptors
namespace __detail
{
// Data members using this alias should use [[no_unique_address]] so that
// they take no space when not needed.
template<bool _Present, typename _Tp>
- using __maybe_present_t = conditional_t<_Present, _Tp, _Empty>;
+ using __maybe_present_t = __conditional_t<_Present, _Tp, _Empty>;
// Alias for a type that is conditionally const.
template<bool _Const, typename _Tp>
- using __maybe_const_t = conditional_t<_Const, const _Tp, _Tp>;
+ using __maybe_const_t = __conditional_t<_Const, const _Tp, _Tp>;
} // namespace __detail
-namespace views
+namespace views::__adaptor
{
- namespace __adaptor
+ // True if the range adaptor _Adaptor can be applied with _Args.
+ template<typename _Adaptor, typename... _Args>
+ concept __adaptor_invocable
+ = requires { std::declval<_Adaptor>()(declval<_Args>()...); };
+
+ // True if the range adaptor non-closure _Adaptor can be partially applied
+ // with _Args.
+ template<typename _Adaptor, typename... _Args>
+ concept __adaptor_partial_app_viable = (_Adaptor::_S_arity > 1)
+ && (sizeof...(_Args) == _Adaptor::_S_arity - 1)
+ && (constructible_from<decay_t<_Args>, _Args> && ...);
+
+ template<typename _Adaptor, typename... _Args>
+ struct _Partial;
+
+ template<typename _Lhs, typename _Rhs>
+ 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.
+ struct _RangeAdaptorClosure
{
- template<typename _Tp>
- inline constexpr auto
- __maybe_refwrap(_Tp& __arg)
- { return reference_wrapper<_Tp>{__arg}; }
-
- template<typename _Tp>
- inline constexpr auto
- __maybe_refwrap(const _Tp& __arg)
- { return reference_wrapper<const _Tp>{__arg}; }
-
- template<typename _Tp>
- inline constexpr decltype(auto)
- __maybe_refwrap(_Tp&& __arg)
- { return std::forward<_Tp>(__arg); }
-
- template<typename _Callable>
- struct _RangeAdaptorClosure;
+ // range | adaptor is equivalent to adaptor(range).
+ template<typename _Self, typename _Range>
+ requires derived_from<remove_cvref_t<_Self>, _RangeAdaptorClosure>
+ && __adaptor_invocable<_Self, _Range>
+ friend 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<typename _Lhs, typename _Rhs>
+ requires derived_from<_Lhs, _RangeAdaptorClosure>
+ && derived_from<_Rhs, _RangeAdaptorClosure>
+ friend constexpr auto
+ operator|(_Lhs __lhs, _Rhs __rhs)
+ { return _Pipe<_Lhs, _Rhs>{std::move(__lhs), std::move(__rhs)}; }
+ };
- template<typename _Callable>
- struct _RangeAdaptor
- {
- protected:
- [[no_unique_address]]
- __detail::__maybe_present_t<!is_default_constructible_v<_Callable>,
- _Callable> _M_callable;
+ // 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<typename _Derived>
+ struct _RangeAdaptor
+ {
+ // Partially apply the arguments __args to the range adaptor _Derived,
+ // returning a range adaptor closure object.
+ template<typename... _Args>
+ requires __adaptor_partial_app_viable<_Derived, _Args...>
+ constexpr auto
+ operator()(_Args&&... __args) const
+ {
+ return _Partial<_Derived, decay_t<_Args>...>{std::forward<_Args>(__args)...};
+ }
+ };
- public:
- constexpr
- _RangeAdaptor(const _Callable& = {})
- requires is_default_constructible_v<_Callable>
- { }
+ // 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<typename _Adaptor>
+ 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<typename _Adaptor, typename... _Args>
+ 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<typename _Adaptor, typename... _Args>
+ struct _Partial : _RangeAdaptorClosure
+ {
+ tuple<_Args...> _M_args;
- constexpr
- _RangeAdaptor(_Callable __callable)
- requires (!is_default_constructible_v<_Callable>)
- : _M_callable(std::move(__callable))
- { }
+ constexpr
+ _Partial(_Args... __args)
+ : _M_args(std::move(__args)...)
+ { }
- template<typename... _Args>
- requires (sizeof...(_Args) >= 1)
- constexpr auto
- operator()(_Args&&... __args) const
- {
- // [range.adaptor.object]: If a range adaptor object accepts more
- // than one argument, then the following expressions are equivalent:
- //
- // (1) adaptor(range, args...)
- // (2) adaptor(args...)(range)
- // (3) range | adaptor(args...)
- //
- // In this case, adaptor(args...) is a range adaptor closure object.
- //
- // We handle (1) and (2) here, and (3) is just a special case of a
- // more general case already handled by _RangeAdaptorClosure.
- if constexpr (is_invocable_v<_Callable, _Args...>)
- {
- static_assert(sizeof...(_Args) != 1,
- "a _RangeAdaptor that accepts only one argument "
- "should be defined as a _RangeAdaptorClosure");
- // Here we handle adaptor(range, args...) -- just forward all
- // arguments to the underlying adaptor routine.
- return _Callable{}(std::forward<_Args>(__args)...);
- }
- else
- {
- // Here we handle adaptor(args...)(range).
- // Given args..., we return a _RangeAdaptorClosure that takes a
- // range argument, such that (2) is equivalent to (1).
- //
- // We need to be careful about how we capture args... in this
- // closure. By using __maybe_refwrap, we capture lvalue
- // references by reference (through a reference_wrapper) and
- // otherwise capture by value.
- auto __closure
- = [...__args(__maybe_refwrap(std::forward<_Args>(__args)))]
- <typename _Range> (_Range&& __r) {
- // This static_cast has two purposes: it forwards a
- // reference_wrapper<T> capture as a T&, and otherwise
- // forwards the captured argument as an rvalue.
- return _Callable{}(std::forward<_Range>(__r),
- (static_cast<unwrap_reference_t
- <remove_const_t<decltype(__args)>>>
- (__args))...);
- };
- using _ClosureType = decltype(__closure);
- return _RangeAdaptorClosure<_ClosureType>(std::move(__closure));
- }
- }
- };
+ // Invoke _Adaptor with arguments __r, _M_args... according to the
+ // value category of this _Partial object.
+ template<typename _Range>
+ 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<typename _Callable>
- _RangeAdaptor(_Callable) -> _RangeAdaptor<_Callable>;
+ template<typename _Range>
+ 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<typename _Callable>
- struct _RangeAdaptorClosure : public _RangeAdaptor<_Callable>
- {
- using _RangeAdaptor<_Callable>::_RangeAdaptor;
+ template<typename _Range>
+ constexpr auto
+ operator()(_Range&& __r) const && = delete;
+ };
- template<viewable_range _Range>
- requires requires { declval<_Callable>()(declval<_Range>()); }
- constexpr auto
- operator()(_Range&& __r) const
- {
- if constexpr (is_default_constructible_v<_Callable>)
- return _Callable{}(std::forward<_Range>(__r));
- else
- return this->_M_callable(std::forward<_Range>(__r));
- }
+ // A lightweight specialization of the above primary template for
+ // the common case where _Adaptor accepts a single extra argument.
+ template<typename _Adaptor, typename _Arg>
+ struct _Partial<_Adaptor, _Arg> : _RangeAdaptorClosure
+ {
+ _Arg _M_arg;
- template<viewable_range _Range>
- requires requires { declval<_Callable>()(declval<_Range>()); }
- friend constexpr auto
- operator|(_Range&& __r, const _RangeAdaptorClosure& __o)
- { return __o(std::forward<_Range>(__r)); }
+ constexpr
+ _Partial(_Arg __arg)
+ : _M_arg(std::move(__arg))
+ { }
- template<typename _Tp>
- friend constexpr auto
- operator|(const _RangeAdaptorClosure<_Tp>& __x,
- const _RangeAdaptorClosure& __y)
- {
- if constexpr (is_default_constructible_v<_Tp>
- && is_default_constructible_v<_Callable>)
- {
- auto __closure = [] <typename _Up> (_Up&& __e) {
- return std::forward<_Up>(__e) | decltype(__x){} | decltype(__y){};
- };
- return _RangeAdaptorClosure<decltype(__closure)>(__closure);
- }
- else if constexpr (is_default_constructible_v<_Tp>
- && !is_default_constructible_v<_Callable>)
- {
- auto __closure = [__y] <typename _Up> (_Up&& __e) {
- return std::forward<_Up>(__e) | decltype(__x){} | __y;
- };
- return _RangeAdaptorClosure<decltype(__closure)>(__closure);
- }
- else if constexpr (!is_default_constructible_v<_Tp>
- && is_default_constructible_v<_Callable>)
- {
- auto __closure = [__x] <typename _Up> (_Up&& __e) {
- return std::forward<_Up>(__e) | __x | decltype(__y){};
- };
- return _RangeAdaptorClosure<decltype(__closure)>(__closure);
- }
- else
- {
- auto __closure = [__x, __y] <typename _Up> (_Up&& __e) {
- return std::forward<_Up>(__e) | __x | __y;
- };
- return _RangeAdaptorClosure<decltype(__closure)>(__closure);
- }
- }
- };
+ template<typename _Range>
+ requires __adaptor_invocable<_Adaptor, _Range, const _Arg&>
+ constexpr auto
+ operator()(_Range&& __r) const &
+ { return _Adaptor{}(std::forward<_Range>(__r), _M_arg); }
+
+ template<typename _Range>
+ requires __adaptor_invocable<_Adaptor, _Range, _Arg>
+ constexpr auto
+ operator()(_Range&& __r) &&
+ { return _Adaptor{}(std::forward<_Range>(__r), std::move(_M_arg)); }
+
+ template<typename _Range>
+ constexpr auto
+ operator()(_Range&& __r) const && = delete;
+ };
- template<typename _Callable>
- _RangeAdaptorClosure(_Callable) -> _RangeAdaptorClosure<_Callable>;
- } // namespace __adaptor
-} // namespace views
+ // 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<typename _Adaptor, typename... _Args>
+ requires __adaptor_has_simple_extra_args<_Adaptor, _Args...>
+ && (is_trivially_copyable_v<_Args> && ...)
+ struct _Partial<_Adaptor, _Args...> : _RangeAdaptorClosure
+ {
+ 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<typename _Range>
+ 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<typename _Adaptor, typename _Arg>
+ requires __adaptor_has_simple_extra_args<_Adaptor, _Arg>
+ && is_trivially_copyable_v<_Arg>
+ struct _Partial<_Adaptor, _Arg> : _RangeAdaptorClosure
+ {
+ _Arg _M_arg;
+
+ constexpr
+ _Partial(_Arg __arg)
+ : _M_arg(std::move(__arg))
+ { }
+
+ template<typename _Range>
+ 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<typename _Lhs, typename _Rhs, typename _Range>
+ 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<typename _Lhs, typename _Rhs>
+ struct _Pipe : _RangeAdaptorClosure
+ {
+ [[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.
+ template<typename _Range>
+ requires __pipe_invocable<const _Lhs&, const _Rhs&, _Range>
+ constexpr auto
+ operator()(_Range&& __r) const &
+ { return _M_rhs(_M_lhs(std::forward<_Range>(__r))); }
+
+ template<typename _Range>
+ 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<typename _Range>
+ 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<typename _Lhs, typename _Rhs>
+ requires __closure_has_simple_call_op<_Lhs>
+ && __closure_has_simple_call_op<_Rhs>
+ struct _Pipe<_Lhs, _Rhs> : _RangeAdaptorClosure
+ {
+ [[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<typename _Range>
+ requires __pipe_invocable<const _Lhs&, const _Rhs&, _Range>
+ 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
template<range _Range> requires is_object_v<_Range>
class ref_view : public view_interface<ref_view<_Range>>
{
private:
- _Range* _M_r = nullptr;
+ _Range* _M_r;
static void _S_fun(_Range&); // not defined
static void _S_fun(_Range&&) = delete;
public:
- constexpr
- ref_view() noexcept = default;
-
- template<__detail::__not_same_as<ref_view> _Tp>
+ template<__detail::__different_from<ref_view> _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))))
{ }
template<typename _Tp>
inline constexpr bool enable_borrowed_range<ref_view<_Tp>> = true;
+ template<range _Range>
+ requires movable<_Range>
+ && (!__detail::__is_initializer_list<remove_cv_t<_Range>>)
+ class owning_view : public view_interface<owning_view<_Range>>
+ {
+ 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<const _Range>
+ { return ranges::begin(_M_r); }
+
+ constexpr auto
+ end() const requires range<const _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<const _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<const _Range>
+ { return ranges::data(_M_r); }
+ };
+
+ template<typename _Tp>
+ inline constexpr bool enable_borrowed_range<owning_view<_Tp>>
+ = enable_borrowed_range<_Tp>;
+
namespace views
{
- inline constexpr __adaptor::_RangeAdaptorClosure all
- = [] <viewable_range _Range> (_Range&& __r)
- {
- if constexpr (view<decay_t<_Range>>)
- return std::forward<_Range>(__r);
- else if constexpr (requires { ref_view{std::forward<_Range>(__r)}; })
- return ref_view{std::forward<_Range>(__r)};
- else
- return subrange{std::forward<_Range>(__r)};
- };
+ namespace __detail
+ {
+ template<typename _Range>
+ concept __can_ref_view = requires { ref_view{std::declval<_Range>()}; };
+
+ template<typename _Range>
+ concept __can_owning_view = requires { owning_view{std::declval<_Range>()}; };
+ } // namespace __detail
+
+ struct _All : __adaptor::_RangeAdaptorClosure
+ {
+ template<typename _Range>
+ static constexpr bool
+ _S_noexcept()
+ {
+ if constexpr (view<decay_t<_Range>>)
+ return is_nothrow_constructible_v<decay_t<_Range>, _Range>;
+ else if constexpr (__detail::__can_ref_view<_Range>)
+ return true;
+ else
+ return noexcept(owning_view{std::declval<_Range>()});
+ }
+
+ template<viewable_range _Range>
+ requires view<decay_t<_Range>>
+ || __detail::__can_ref_view<_Range>
+ || __detail::__can_owning_view<_Range>
+ constexpr auto
+ operator() [[nodiscard]] (_Range&& __r) const
+ noexcept(_S_noexcept<_Range>())
+ {
+ if constexpr (view<decay_t<_Range>>)
+ 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<viewable_range _Range>
using all_t = decltype(all(std::declval<_Range>()));
-
} // namespace views
- // XXX: the following algos are copied from ranges_algo.h to avoid a circular
- // dependency with that header.
namespace __detail
{
- template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
- typename _Proj = identity,
- indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
- constexpr _Iter
- find_if(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
+ template<typename _Tp>
+ struct __non_propagating_cache
{
- while (__first != __last
- && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
- ++__first;
- return __first;
- }
+ // 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<input_iterator _Iter, sentinel_for<_Iter> _Sent,
- typename _Proj = identity,
- indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
- constexpr _Iter
- find_if_not(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
+ template<typename _Tp>
+ requires is_object_v<_Tp>
+ struct __non_propagating_cache<_Tp>
+ : protected _Optional_base<_Tp>
{
- while (__first != __last
- && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
- ++__first;
- return __first;
- }
+ __non_propagating_cache() = default;
- template<typename _Tp, typename _Proj = identity,
- indirect_strict_weak_order<projected<const _Tp*, _Proj>>
- _Comp = ranges::less>
- constexpr const _Tp&
- min(const _Tp& __a, const _Tp& __b, _Comp __comp = {}, _Proj __proj = {})
- {
- if (std::__invoke(std::move(__comp),
- std::__invoke(__proj, __b),
- std::__invoke(__proj, __a)))
- return __b;
- else
- return __a;
- }
+ constexpr
+ __non_propagating_cache(const __non_propagating_cache&) noexcept
+ { }
- template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
- input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
- typename _Pred = ranges::equal_to,
- typename _Proj1 = identity, typename _Proj2 = identity>
- requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
- constexpr pair<_Iter1, _Iter2>
- mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
- _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
- {
- while (__first1 != __last1 && __first2 != __last2
- && (bool)std::__invoke(__pred,
- std::__invoke(__proj1, *__first1),
- std::__invoke(__proj2, *__first2)))
+ 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
{
- ++__first1;
- ++__first2;
+ this->_M_reset();
+ __other._M_reset();
+ return *this;
}
- return { std::move(__first1), std::move(__first2) };
- }
- } // namespace __detail
- namespace __detail
- {
+ 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<typename _Iter>
+ 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<range _Range>
struct _CachedPosition
{
_M_get(const _Range&) const
{
__glibcxx_assert(false);
- return {};
+ __builtin_unreachable();
}
constexpr void
template<forward_range _Range>
struct _CachedPosition<_Range>
+ : protected __non_propagating_cache<iterator_t<_Range>>
{
- private:
- iterator_t<_Range> _M_iter{};
-
- public:
constexpr bool
_M_has_value() const
- { return _M_iter != iterator_t<_Range>{}; }
+ { return this->_M_is_engaged(); }
constexpr iterator_t<_Range>
_M_get(const _Range&) const
{
__glibcxx_assert(_M_has_value());
- return _M_iter;
+ return **this;
}
constexpr void
_M_set(const _Range&, const iterator_t<_Range>& __it)
{
__glibcxx_assert(!_M_has_value());
- _M_iter = __it;
+ std::construct_at(std::__addressof(this->_M_payload._M_payload),
+ in_place, __it);
+ this->_M_payload._M_engaged = true;
}
};
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; }
_M_offset = __it - ranges::begin(__r);
}
};
+ } // namespace __detail
+
+ namespace __detail
+ {
+ template<typename _Base>
+ struct __filter_view_iter_cat
+ { };
+ template<forward_range _Base>
+ struct __filter_view_iter_cat<_Base>
+ {
+ private:
+ static auto
+ _S_iter_cat()
+ {
+ using _Cat = typename iterator_traits<iterator_t<_Base>>::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<input_range _Vp,
private:
struct _Sentinel;
- struct _Iterator
+ struct _Iterator : __detail::__filter_view_iter_cat<_Vp>
{
private:
static constexpr auto
return input_iterator_tag{};
}
- static constexpr auto
- _S_iter_cat()
- {
- using _Cat = typename iterator_traits<_Vp_iter>::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{};
- }
-
friend filter_view;
using _Vp_iter = iterator_t<_Vp>;
public:
using iterator_concept = decltype(_S_iter_concept());
- using iterator_category = decltype(_S_iter_cat());
+ // iterator_category defined in __filter_view_iter_cat
using value_type = range_value_t<_Vp>;
using difference_type = range_difference_t<_Vp>;
- _Iterator() = default;
+ _Iterator() requires default_initializable<_Vp_iter> = default;
constexpr
- _Iterator(filter_view& __parent, _Vp_iter __current)
+ _Iterator(filter_view* __parent, _Vp_iter __current)
: _M_current(std::move(__current)),
- _M_parent(std::__addressof(__parent))
+ _M_parent(__parent)
{ }
- constexpr _Vp_iter
- base() const &
- requires copyable<_Vp_iter>
+ constexpr const _Vp_iter&
+ base() const & noexcept
{ return _M_current; }
constexpr _Vp_iter
constexpr _Iterator&
operator++()
{
- _M_current = __detail::find_if(std::move(++_M_current),
- ranges::end(_M_parent->_M_base),
- std::ref(*_M_parent->_M_pred));
+ _M_current = ranges::find_if(std::move(++_M_current),
+ ranges::end(_M_parent->_M_base),
+ std::ref(*_M_parent->_M_pred));
return *this;
}
_Sentinel() = default;
constexpr explicit
- _Sentinel(filter_view& __parent)
- : _M_end(ranges::end(__parent._M_base))
+ _Sentinel(filter_view* __parent)
+ : _M_end(ranges::end(__parent->_M_base))
{ }
constexpr sentinel_t<_Vp>
};
_Vp _M_base = _Vp();
- __detail::__box<_Pred> _M_pred;
+ [[no_unique_address]] __detail::__box<_Pred> _M_pred;
[[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
public:
- filter_view() = default;
+ filter_view() requires (default_initializable<_Vp>
+ && default_initializable<_Pred>)
+ = default;
constexpr
filter_view(_Vp __base, _Pred __pred)
begin()
{
if (_M_cached_begin._M_has_value())
- return {*this, _M_cached_begin._M_get(_M_base)};
+ return {this, _M_cached_begin._M_get(_M_base)};
__glibcxx_assert(_M_pred.has_value());
- auto __it = __detail::find_if(ranges::begin(_M_base),
- ranges::end(_M_base),
- std::ref(*_M_pred));
+ 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)};
+ return {this, std::move(__it)};
}
constexpr auto
end()
{
if constexpr (common_range<_Vp>)
- return _Iterator{*this, ranges::end(_M_base)};
+ return _Iterator{this, ranges::end(_M_base)};
else
- return _Sentinel{*this};
+ return _Sentinel{this};
}
};
namespace views
{
- inline constexpr __adaptor::_RangeAdaptor filter
- = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p)
- {
- return filter_view{std::forward<_Range>(__r), std::forward<_Pred>(__p)};
- };
+ namespace __detail
+ {
+ template<typename _Range, typename _Pred>
+ concept __can_filter_view
+ = requires { filter_view(std::declval<_Range>(), std::declval<_Pred>()); };
+ } // namespace __detail
+
+ struct _Filter : __adaptor::_RangeAdaptor<_Filter>
+ {
+ template<viewable_range _Range, typename _Pred>
+ 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
template<input_range _Vp, copy_constructible _Fp>
{
private:
template<bool _Const>
- struct _Sentinel;
+ using _Base = __detail::__maybe_const_t<_Const, _Vp>;
+
+ template<bool _Const>
+ struct __iter_cat
+ { };
template<bool _Const>
- struct _Iterator
+ requires forward_range<_Base<_Const>>
+ struct __iter_cat<_Const>
{
private:
- using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
- using _Base = __detail::__maybe_const_t<_Const, _Vp>;
-
- static constexpr auto
- _S_iter_concept()
- {
- if constexpr (random_access_range<_Vp>)
- return random_access_iterator_tag{};
- else if constexpr (bidirectional_range<_Vp>)
- return bidirectional_iterator_tag{};
- else if constexpr (forward_range<_Vp>)
- return forward_iterator_tag{};
- else
- return input_iterator_tag{};
- }
-
- static constexpr auto
- _S_iter_cat()
+ 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<_Base_iter>::iterator_category;
+ = typename iterator_traits<iterator_t<_Base>>::iterator_category;
if constexpr (derived_from<_Cat, contiguous_iterator_tag>)
return random_access_iterator_tag{};
else
else
return input_iterator_tag{};
}
+ public:
+ using iterator_category = decltype(_S_iter_cat());
+ };
+
+ template<bool _Const>
+ struct _Sentinel;
+
+ template<bool _Const>
+ 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>;
public:
using iterator_concept = decltype(_S_iter_concept());
- using iterator_category = decltype(_S_iter_cat());
+ // iterator_category defined in __transform_view_iter_cat
using value_type
= remove_cvref_t<invoke_result_t<_Fp&, range_reference_t<_Base>>>;
using difference_type = range_difference_t<_Base>;
- _Iterator() = default;
+ _Iterator() requires default_initializable<_Base_iter> = default;
constexpr
- _Iterator(_Parent& __parent, _Base_iter __current)
+ _Iterator(_Parent* __parent, _Base_iter __current)
: _M_current(std::move(__current)),
- _M_parent(std::__addressof(__parent))
+ _M_parent(__parent)
{ }
constexpr
: _M_current(std::move(__i._M_current)), _M_parent(__i._M_parent)
{ }
- constexpr _Base_iter
- base() const &
- requires copyable<_Base_iter>
+ constexpr const _Base_iter&
+ base() const & noexcept
{ return _M_current; }
constexpr _Base_iter
friend constexpr _Iterator
operator+(_Iterator __i, difference_type __n)
requires random_access_range<_Base>
- { return {*__i._M_parent, __i._M_current + __n}; }
+ { 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}; }
+ { 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}; }
+ { 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 random_access_range<_Base>
+ requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
{ return __x._M_current - __y._M_current; }
friend constexpr decltype(auto)
return *__i;
}
- 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<_Base_iter>
- { return ranges::iter_swap(__x._M_current, __y._M_current); }
-
friend _Iterator<!_Const>;
template<bool> friend struct _Sentinel;
};
{
private:
using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
- using _Base = __detail::__maybe_const_t<_Const, _Vp>;
+ using _Base = transform_view::_Base<_Const>;
template<bool _Const2>
constexpr auto
};
_Vp _M_base = _Vp();
- __detail::__box<_Fp> _M_fun;
+ [[no_unique_address]] __detail::__box<_Fp> _M_fun;
public:
- transform_view() = default;
+ transform_view() requires (default_initializable<_Vp>
+ && default_initializable<_Fp>)
+ = default;
constexpr
transform_view(_Vp __base, _Fp __fun)
constexpr _Iterator<false>
begin()
- { return _Iterator<false>{*this, ranges::begin(_M_base)}; }
+ { return _Iterator<false>{this, ranges::begin(_M_base)}; }
constexpr _Iterator<true>
begin() const
requires range<const _Vp>
&& regular_invocable<const _Fp&, range_reference_t<const _Vp>>
- { return _Iterator<true>{*this, ranges::begin(_M_base)}; }
+ { return _Iterator<true>{this, ranges::begin(_M_base)}; }
constexpr _Sentinel<false>
end()
constexpr _Iterator<false>
end() requires common_range<_Vp>
- { return _Iterator<false>{*this, ranges::end(_M_base)}; }
+ { return _Iterator<false>{this, ranges::end(_M_base)}; }
constexpr _Sentinel<true>
end() const
end() const
requires common_range<const _Vp>
&& regular_invocable<const _Fp&, range_reference_t<const _Vp>>
- { return _Iterator<true>{*this, ranges::end(_M_base)}; }
+ { return _Iterator<true>{this, ranges::end(_M_base)}; }
constexpr auto
size() requires sized_range<_Vp>
namespace views
{
- inline constexpr __adaptor::_RangeAdaptor transform
- = [] <viewable_range _Range, typename _Fp> (_Range&& __r, _Fp&& __f)
- {
- return transform_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)};
- };
+ namespace __detail
+ {
+ template<typename _Range, typename _Fp>
+ concept __can_transform_view
+ = requires { transform_view(std::declval<_Range>(), std::declval<_Fp>()); };
+ } // namespace __detail
+
+ struct _Transform : __adaptor::_RangeAdaptor<_Transform>
+ {
+ template<viewable_range _Range, typename _Fp>
+ 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<view _Vp>
class take_view : public view_interface<take_view<_Vp>>
{
private:
+ template<bool _Const>
+ using _CI = counted_iterator<
+ iterator_t<__detail::__maybe_const_t<_Const, _Vp>>>;
+
template<bool _Const>
struct _Sentinel
{
private:
using _Base = __detail::__maybe_const_t<_Const, _Vp>;
- using _CI = counted_iterator<iterator_t<_Base>>;
-
sentinel_t<_Base> _M_end = sentinel_t<_Base>();
public:
base() const
{ return _M_end; }
- friend constexpr bool operator==(const _CI& __y, const _Sentinel& __x)
+ friend constexpr bool
+ operator==(const _CI<_Const>& __y, const _Sentinel& __x)
+ { return __y.count() == 0 || __y.base() == __x._M_end; }
+
+ template<bool _OtherConst = !_Const,
+ typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
+ requires sentinel_for<sentinel_t<_Base>, 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<!_Const>;
range_difference_t<_Vp> _M_count = 0;
public:
- take_view() = default;
+ 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))
+ take_view(_Vp __base, range_difference_t<_Vp> __count)
+ : _M_base(std::move(__base)), _M_count(std::move(__count))
{ }
constexpr _Vp
else
{
auto __sz = size();
- return counted_iterator{ranges::begin(_M_base), __sz};
+ return counted_iterator(ranges::begin(_M_base), __sz);
}
}
else
- return counted_iterator{ranges::begin(_M_base), _M_count};
+ return counted_iterator(ranges::begin(_M_base), _M_count);
}
constexpr auto
else
{
auto __sz = size();
- return counted_iterator{ranges::begin(_M_base), __sz};
+ return counted_iterator(ranges::begin(_M_base), __sz);
}
}
else
- return counted_iterator{ranges::begin(_M_base), _M_count};
+ return counted_iterator(ranges::begin(_M_base), _M_count);
}
constexpr auto
size() requires sized_range<_Vp>
{
auto __n = ranges::size(_M_base);
- return __detail::min(__n, static_cast<decltype(__n)>(_M_count));
+ return std::min(__n, static_cast<decltype(__n)>(_M_count));
}
constexpr auto
size() const requires sized_range<const _Vp>
{
auto __n = ranges::size(_M_base);
- return __detail::min(__n, static_cast<decltype(__n)>(_M_count));
+ return std::min(__n, static_cast<decltype(__n)>(_M_count));
}
};
- template<range _Range>
+ // _GLIBCXX_RESOLVE_LIB_DEFECTS
+ // 3447. Deduction guides for take_view and drop_view have different
+ // constraints
+ template<typename _Range>
take_view(_Range&&, range_difference_t<_Range>)
-> take_view<views::all_t<_Range>>;
+ template<typename _Tp>
+ inline constexpr bool enable_borrowed_range<take_view<_Tp>>
+ = enable_borrowed_range<_Tp>;
+
namespace views
{
- inline constexpr __adaptor::_RangeAdaptor take
- = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n)
- {
- return take_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
- };
+ namespace __detail
+ {
+ template<typename _Range>
+ inline constexpr bool __is_empty_view = false;
+
+ template<typename _Tp>
+ inline constexpr bool __is_empty_view<empty_view<_Tp>> = true;
+
+ template<typename _Range>
+ inline constexpr bool __is_basic_string_view = false;
+
+#if _GLIBCXX_HOSTED
+ template<typename _CharT, typename _Traits>
+ inline constexpr bool __is_basic_string_view<basic_string_view<_CharT, _Traits>>
+ = true;
+#endif
+
+ template<typename _Range>
+ inline constexpr bool __is_subrange = false;
+
+ template<typename _Iter, typename _Sent, subrange_kind _Kind>
+ inline constexpr bool __is_subrange<subrange<_Iter, _Sent, _Kind>> = true;
+
+ template<typename _Range>
+ inline constexpr bool __is_iota_view = false;
+
+ template<typename _Winc, typename _Bound>
+ inline constexpr bool __is_iota_view<iota_view<_Winc, _Bound>> = true;
+
+ template<typename _Range, typename _Dp>
+ concept __can_take_view
+ = requires { take_view(std::declval<_Range>(), std::declval<_Dp>()); };
+ } // namespace __detail
+
+ struct _Take : __adaptor::_RangeAdaptor<_Take>
+ {
+ template<viewable_range _Range, typename _Dp = range_difference_t<_Range>>
+ 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<typename _Tp::element_type>(__begin, __end);
+ else if constexpr (__detail::__is_basic_string_view<_Tp>)
+ return _Tp(__begin, __end);
+ else if constexpr (__detail::__is_subrange<_Tp>)
+ return subrange<iterator_t<_Tp>>(__begin, __end);
+ else
+ return iota_view(*__begin, *__end);
+ }
+ 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<typename _Tp>
+ static constexpr bool _S_has_simple_extra_args
+ = ranges::__detail::__is_integer_like<_Tp>;
+ };
+
+ inline constexpr _Take take;
} // namespace views
template<view _Vp, typename _Pred>
operator==(const iterator_t<_Base>& __x, const _Sentinel& __y)
{ return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
+ template<bool _OtherConst = !_Const,
+ typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
+ requires sentinel_for<sentinel_t<_Base>, 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<!_Const>;
};
_Vp _M_base = _Vp();
- __detail::__box<_Pred> _M_pred;
+ [[no_unique_address]] __detail::__box<_Pred> _M_pred;
public:
- take_while_view() = default;
+ 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))
- {
- }
+ 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>
constexpr auto
begin() const requires range<const _Vp>
+ && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
{ return ranges::begin(_M_base); }
constexpr auto
constexpr auto
end() const requires range<const _Vp>
+ && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
{ return _Sentinel<true>(ranges::end(_M_base),
std::__addressof(*_M_pred)); }
};
namespace views
{
- inline constexpr __adaptor::_RangeAdaptor take_while
- = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p)
- {
- return take_while_view{std::forward<_Range>(__r), std::forward<_Pred>(__p)};
- };
+ namespace __detail
+ {
+ template<typename _Range, typename _Pred>
+ concept __can_take_while_view
+ = requires { take_while_view(std::declval<_Range>(), std::declval<_Pred>()); };
+ } // namespace __detail
+
+ struct _TakeWhile : __adaptor::_RangeAdaptor<_TakeWhile>
+ {
+ template<viewable_range _Range, typename _Pred>
+ 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<view _Vp>
_Vp _M_base = _Vp();
range_difference_t<_Vp> _M_count = 0;
- static constexpr bool _S_needs_cached_begin = !random_access_range<_Vp>;
+ // 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<const _Vp> && sized_range<const _Vp>);
[[no_unique_address]]
__detail::__maybe_present_t<_S_needs_cached_begin,
__detail::_CachedPosition<_Vp>>
_M_cached_begin;
public:
- drop_view() = default;
+ drop_view() requires default_initializable<_Vp> = default;
constexpr
drop_view(_Vp __base, range_difference_t<_Vp> __count)
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<_Vp>))
+ begin()
+ requires (!(__detail::__simple_view<_Vp>
+ && random_access_range<const _Vp>
+ && sized_range<const _Vp>))
{
if constexpr (_S_needs_cached_begin)
if (_M_cached_begin._M_has_value())
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<const _Vp>
+ begin() const
+ requires random_access_range<const _Vp> && sized_range<const _Vp>
{
return ranges::next(ranges::begin(_M_base), _M_count,
ranges::end(_M_base));
drop_view(_Range&&, range_difference_t<_Range>)
-> drop_view<views::all_t<_Range>>;
+ template<typename _Tp>
+ inline constexpr bool enable_borrowed_range<drop_view<_Tp>>
+ = enable_borrowed_range<_Tp>;
+
namespace views
{
- inline constexpr __adaptor::_RangeAdaptor drop
- = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n)
- {
- return drop_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
- };
+ namespace __detail
+ {
+ template<typename _Range, typename _Dp>
+ concept __can_drop_view
+ = requires { drop_view(std::declval<_Range>(), std::declval<_Dp>()); };
+ } // namespace __detail
+
+ struct _Drop : __adaptor::_RangeAdaptor<_Drop>
+ {
+ template<viewable_range _Range, typename _Dp = range_difference_t<_Range>>
+ 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<typename _Tp::element_type>(__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
+ return drop_view(std::forward<_Range>(__r), __n);
+ }
+
+ using _RangeAdaptor<_Drop>::operator();
+ static constexpr int _S_arity = 2;
+ template<typename _Tp>
+ static constexpr bool _S_has_simple_extra_args
+ = _Take::_S_has_simple_extra_args<_Tp>;
+ };
+
+ inline constexpr _Drop drop;
} // namespace views
template<view _Vp, typename _Pred>
{
private:
_Vp _M_base = _Vp();
- __detail::__box<_Pred> _M_pred;
+ [[no_unique_address]] __detail::__box<_Pred> _M_pred;
[[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
public:
- drop_while_view() = default;
+ drop_while_view() requires (default_initializable<_Vp>
+ && default_initializable<_Pred>)
+ = default;
constexpr
drop_while_view(_Vp __base, _Pred __pred)
if (_M_cached_begin._M_has_value())
return _M_cached_begin._M_get(_M_base);
- auto __it = __detail::find_if_not(ranges::begin(_M_base),
- ranges::end(_M_base),
- std::cref(*_M_pred));
+ __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;
}
drop_while_view(_Range&&, _Pred)
-> drop_while_view<views::all_t<_Range>, _Pred>;
+ template<typename _Tp, typename _Pred>
+ inline constexpr bool enable_borrowed_range<drop_while_view<_Tp, _Pred>>
+ = enable_borrowed_range<_Tp>;
+
namespace views
{
- inline constexpr __adaptor::_RangeAdaptor drop_while
- = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p)
- {
- return drop_while_view{std::forward<_Range>(__r),
- std::forward<_Pred>(__p)};
- };
+ namespace __detail
+ {
+ template<typename _Range, typename _Pred>
+ concept __can_drop_while_view
+ = requires { drop_while_view(std::declval<_Range>(), std::declval<_Pred>()); };
+ } // namespace __detail
+
+ struct _DropWhile : __adaptor::_RangeAdaptor<_DropWhile>
+ {
+ template<viewable_range _Range, typename _Pred>
+ 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
template<input_range _Vp>
requires view<_Vp> && input_range<range_reference_t<_Vp>>
- && (is_reference_v<range_reference_t<_Vp>>
- || view<range_value_t<_Vp>>)
class join_view : public view_interface<join_view<_Vp>>
{
private:
using _InnerRange = range_reference_t<_Vp>;
+ template<bool _Const>
+ using _Base = __detail::__maybe_const_t<_Const, _Vp>;
+
+ template<bool _Const>
+ using _Outer_iter = iterator_t<_Base<_Const>>;
+
+ template<bool _Const>
+ using _Inner_iter = iterator_t<range_reference_t<_Base<_Const>>>;
+
+ template<bool _Const>
+ static constexpr bool _S_ref_is_glvalue
+ = is_reference_v<range_reference_t<_Base<_Const>>>;
+
+ template<bool _Const>
+ struct __iter_cat
+ { };
+
+ template<bool _Const>
+ requires _S_ref_is_glvalue<_Const>
+ && forward_range<_Base<_Const>>
+ && forward_range<range_reference_t<_Base<_Const>>>
+ 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<range_reference_t<_Base<_Const>>>)
+ 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<bool _Const>
struct _Sentinel;
template<bool _Const>
- struct _Iterator
+ struct _Iterator : __iter_cat<_Const>
{
private:
using _Parent = __detail::__maybe_const_t<_Const, join_view>;
- using _Base = __detail::__maybe_const_t<_Const, _Vp>;
+ using _Base = join_view::_Base<_Const>;
static constexpr bool _S_ref_is_glvalue
- = is_reference_v<range_reference_t<_Base>>;
+ = join_view::_S_ref_is_glvalue<_Const>;
constexpr void
_M_satisfy()
{
- auto __update_inner = [this] (range_reference_t<_Base> __x) -> auto&
- {
+ auto __update_inner = [this] (const iterator_t<_Base>& __x) -> auto&& {
if constexpr (_S_ref_is_glvalue)
- return __x;
+ return *__x;
else
- return (_M_parent->_M_inner = views::all(std::move(__x)));
+ return _M_parent->_M_inner._M_emplace_deref(__x);
};
for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer)
{
- auto& inner = __update_inner(*_M_outer);
- _M_inner = ranges::begin(inner);
- if (_M_inner != ranges::end(inner))
+ auto&& __inner = __update_inner(_M_outer);
+ _M_inner = ranges::begin(__inner);
+ if (_M_inner != ranges::end(__inner))
return;
}
if constexpr (_S_ref_is_glvalue)
- _M_inner = _Inner_iter();
+ _M_inner.reset();
}
static constexpr auto
{
if constexpr (_S_ref_is_glvalue
&& bidirectional_range<_Base>
- && bidirectional_range<range_reference_t<_Base>>)
+ && bidirectional_range<range_reference_t<_Base>>
+ && common_range<range_reference_t<_Base>>)
return bidirectional_iterator_tag{};
else if constexpr (_S_ref_is_glvalue
&& forward_range<_Base>
return input_iterator_tag{};
}
- static constexpr auto
- _S_iter_cat()
- {
- using _OuterCat
- = typename iterator_traits<_Outer_iter>::iterator_category;
- using _InnerCat
- = typename iterator_traits<_Inner_iter>::iterator_category;
- if constexpr (_S_ref_is_glvalue
- && derived_from<_OuterCat, bidirectional_iterator_tag>
- && derived_from<_InnerCat, bidirectional_iterator_tag>)
- return bidirectional_iterator_tag{};
- else if constexpr (_S_ref_is_glvalue
- && derived_from<_OuterCat, forward_iterator_tag>
- && derived_from<_InnerCat, forward_iterator_tag>)
- return forward_iterator_tag{};
- else if constexpr (derived_from<_OuterCat, input_iterator_tag>
- && derived_from<_InnerCat, input_iterator_tag>)
- return input_iterator_tag{};
- else
- return output_iterator_tag{};
- }
-
- using _Outer_iter = iterator_t<_Base>;
- using _Inner_iter = iterator_t<range_reference_t<_Base>>;
+ using _Outer_iter = join_view::_Outer_iter<_Const>;
+ using _Inner_iter = join_view::_Inner_iter<_Const>;
_Outer_iter _M_outer = _Outer_iter();
- _Inner_iter _M_inner = _Inner_iter();
+ optional<_Inner_iter> _M_inner;
_Parent* _M_parent = nullptr;
public:
using iterator_concept = decltype(_S_iter_concept());
- using iterator_category = decltype(_S_iter_cat());
+ // iterator_category defined in __join_view_iter_cat
using value_type = range_value_t<range_reference_t<_Base>>;
using difference_type
= common_type_t<range_difference_t<_Base>,
range_difference_t<range_reference_t<_Base>>>;
- _Iterator() = default;
+ _Iterator() requires default_initializable<_Outer_iter> = default;
constexpr
- _Iterator(_Parent& __parent, _Outer_iter __outer)
+ _Iterator(_Parent* __parent, _Outer_iter __outer)
: _M_outer(std::move(__outer)),
- _M_parent(std::__addressof(__parent))
+ _M_parent(__parent)
{ _M_satisfy(); }
constexpr
requires _Const
&& convertible_to<iterator_t<_Vp>, _Outer_iter>
&& convertible_to<iterator_t<_InnerRange>, _Inner_iter>
- : _M_outer(std::move(__i._M_outer)), _M_inner(__i._M_inner),
+ : _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; }
+ { return **_M_inner; }
- constexpr _Outer_iter
+ // _GLIBCXX_RESOLVE_LIB_DEFECTS
+ // 3500. join_view::iterator::operator->() is bogus
+ constexpr _Inner_iter
operator->() const
- requires __detail::__has_arrow<_Outer_iter>
- && copyable<_Outer_iter>
- { return _M_inner; }
+ requires __detail::__has_arrow<_Inner_iter>
+ && copyable<_Inner_iter>
+ { return *_M_inner; }
constexpr _Iterator&
operator++()
{
- auto&& __inner_range = [this] () -> decltype(auto) {
+ auto&& __inner_range = [this] () -> auto&& {
if constexpr (_S_ref_is_glvalue)
return *_M_outer;
else
- return _M_parent->_M_inner;
+ return *_M_parent->_M_inner;
}();
- if (++_M_inner == ranges::end(__inner_range))
+ if (++*_M_inner == ranges::end(__inner_range))
{
++_M_outer;
_M_satisfy();
{
if (_M_outer == ranges::end(_M_parent->_M_base))
_M_inner = ranges::end(*--_M_outer);
- while (_M_inner == ranges::begin(*_M_outer))
- _M_inner = ranges::end(*--_M_outer);
- --_M_inner;
+ while (*_M_inner == ranges::begin(*_M_outer))
+ *_M_inner = ranges::end(*--_M_outer);
+ --*_M_inner;
return *this;
}
friend constexpr decltype(auto)
iter_move(const _Iterator& __i)
- noexcept(noexcept(ranges::iter_move(__i._M_inner)))
- { return ranges::iter_move(__i._M_inner); }
+ 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)))
- { return ranges::iter_swap(__x._M_inner, __y._M_inner); }
+ 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<!_Const>;
template<bool> friend struct _Sentinel;
{
private:
using _Parent = __detail::__maybe_const_t<_Const, join_view>;
- using _Base = __detail::__maybe_const_t<_Const, _Vp>;
+ using _Base = join_view::_Base<_Const>;
template<bool _Const2>
constexpr bool
_Sentinel() = default;
constexpr explicit
- _Sentinel(_Parent& __parent)
- : _M_end(ranges::end(__parent._M_base))
+ _Sentinel(_Parent* __parent)
+ : _M_end(ranges::end(__parent->_M_base))
{ }
constexpr
};
_Vp _M_base = _Vp();
-
- // XXX: _M_inner is "present only when !is_reference_v<_InnerRange>"
[[no_unique_address]]
- __detail::__maybe_present_t<!is_reference_v<_InnerRange>,
- views::all_t<_InnerRange>> _M_inner;
+ __detail::__non_propagating_cache<remove_cv_t<_InnerRange>> _M_inner;
public:
- join_view() = default;
+ join_view() requires default_initializable<_Vp> = default;
constexpr explicit
join_view(_Vp __base)
constexpr bool __use_const
= (__detail::__simple_view<_Vp>
&& is_reference_v<range_reference_t<_Vp>>);
- return _Iterator<__use_const>{*this, ranges::begin(_M_base)};
+ return _Iterator<__use_const>{this, ranges::begin(_M_base)};
}
constexpr auto
requires input_range<const _Vp>
&& is_reference_v<range_reference_t<const _Vp>>
{
- return _Iterator<true>{*this, ranges::begin(_M_base)};
+ return _Iterator<true>{this, ranges::begin(_M_base)};
}
constexpr auto
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,
+ return _Iterator<__detail::__simple_view<_Vp>>{this,
ranges::end(_M_base)};
else
- return _Sentinel<__detail::__simple_view<_Vp>>{*this};
+ return _Sentinel<__detail::__simple_view<_Vp>>{this};
}
constexpr auto
&& forward_range<range_reference_t<const _Vp>>
&& common_range<const _Vp>
&& common_range<range_reference_t<const _Vp>>)
- return _Iterator<true>{*this, ranges::end(_M_base)};
+ return _Iterator<true>{this, ranges::end(_M_base)};
else
- return _Sentinel<true>{*this};
+ return _Sentinel<true>{this};
}
};
template<typename _Range>
explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // 3474. Nesting join_views is broken because of CTAD
- template<typename _View>
- explicit join_view(join_view<_View>) -> join_view<join_view<_View>>;
-
namespace views
{
- inline constexpr __adaptor::_RangeAdaptorClosure join
- = [] <viewable_range _Range> (_Range&& __r)
- {
- return join_view{std::forward<_Range>(__r)};
- };
+ namespace __detail
+ {
+ template<typename _Range>
+ concept __can_join_view
+ = requires { join_view<all_t<_Range>>{std::declval<_Range>()}; };
+ } // namespace __detail
+
+ struct _Join : __adaptor::_RangeAdaptorClosure
+ {
+ template<viewable_range _Range>
+ 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<all_t<_Range>>{std::forward<_Range>(__r)};
+ }
+
+ static constexpr bool _S_has_simple_call_op = true;
+ };
+
+ inline constexpr _Join join;
} // namespace views
namespace __detail
&& requires
{ typename __require_constant<remove_reference_t<_Range>::size()>; }
&& (remove_reference_t<_Range>::size() <= 1);
+
+ template<typename _Base>
+ struct __lazy_split_view_outer_iter_cat
+ { };
+
+ template<forward_range _Base>
+ struct __lazy_split_view_outer_iter_cat<_Base>
+ { using iterator_category = input_iterator_tag; };
+
+ template<typename _Base>
+ struct __lazy_split_view_inner_iter_cat
+ { };
+
+ template<forward_range _Base>
+ struct __lazy_split_view_inner_iter_cat<_Base>
+ {
+ private:
+ static constexpr auto
+ _S_iter_cat()
+ {
+ using _Cat = typename iterator_traits<iterator_t<_Base>>::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<input_range _Vp, forward_range _Pattern>
&& indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
ranges::equal_to>
&& (forward_range<_Vp> || __detail::__tiny_range<_Pattern>)
- class split_view : public view_interface<split_view<_Vp, _Pattern>>
+ class lazy_split_view : public view_interface<lazy_split_view<_Vp, _Pattern>>
{
private:
+ template<bool _Const>
+ using _Base = __detail::__maybe_const_t<_Const, _Vp>;
+
template<bool _Const>
struct _InnerIter;
template<bool _Const>
struct _OuterIter
+ : __detail::__lazy_split_view_outer_iter_cat<_Base<_Const>>
{
private:
- using _Parent = __detail::__maybe_const_t<_Const, split_view>;
- using _Base = __detail::__maybe_const_t<_Const, _Vp>;
+ 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); }
+ { return __current() == ranges::end(_M_parent->_M_base) && !_M_trailing_empty; }
- // [range.split.outer] p1
+ // [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.
if constexpr (forward_range<_Vp>)
return _M_current;
else
- return _M_parent->_M_current;
+ return *_M_parent->_M_current;
}
constexpr auto&
if constexpr (forward_range<_Vp>)
return _M_current;
else
- return _M_parent->_M_current;
+ return *_M_parent->_M_current;
}
_Parent* _M_parent = nullptr;
- // XXX: _M_current is present only if "V models forward_range"
[[no_unique_address]]
__detail::__maybe_present_t<forward_range<_Vp>,
iterator_t<_Base>> _M_current;
+ bool _M_trailing_empty = false;
public:
- using iterator_concept = conditional_t<forward_range<_Base>,
- forward_iterator_tag,
- input_iterator_tag>;
- using iterator_category = input_iterator_tag;
+ using iterator_concept = __conditional_t<forward_range<_Base>,
+ 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<value_type>
constexpr _InnerIter<_Const>
begin() const
- requires copyable<_OuterIter>
{ return _InnerIter<_Const>{_M_i}; }
- constexpr _InnerIter<_Const>
- begin()
- requires (!copyable<_OuterIter>)
- { return _InnerIter<_Const>{std::move(_M_i)}; }
-
constexpr default_sentinel_t
- end() const
+ end() const noexcept
{ return default_sentinel; }
};
_OuterIter() = default;
constexpr explicit
- _OuterIter(_Parent& __parent) requires (!forward_range<_Base>)
- : _M_parent(std::__addressof(__parent))
+ _OuterIter(_Parent* __parent) requires (!forward_range<_Base>)
+ : _M_parent(__parent)
{ }
constexpr
- _OuterIter(_Parent& __parent, iterator_t<_Base> __current)
+ _OuterIter(_Parent* __parent, iterator_t<_Base> __current)
requires forward_range<_Base>
- : _M_parent(std::__addressof(__parent)),
+ : _M_parent(__parent),
_M_current(std::move(__current))
{ }
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)
- return *this;
+ {
+ _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]
- = __detail::mismatch(std::move(__current()), __end,
- __pbegin, __pend);
- __current() = std::move(__b);
+ = ranges::mismatch(__current(), __end, __pbegin, __pend);
if (__p == __pend)
- break;
+ {
+ __current() = __b;
+ if (__current() == __end)
+ _M_trailing_empty = true;
+ break;
+ }
} while (++__current() != __end);
return *this;
}
friend constexpr bool
operator==(const _OuterIter& __x, const _OuterIter& __y)
requires forward_range<_Base>
- { return __x._M_current == __y._M_current; }
+ {
+ 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)
template<bool _Const>
struct _InnerIter
+ : __detail::__lazy_split_view_inner_iter_cat<_Base<_Const>>
{
private:
- using _Base = __detail::__maybe_const_t<_Const, _Vp>;
+ using _Base = lazy_split_view::_Base<_Const>;
constexpr bool
__at_end() const
}
}
- static constexpr auto
- _S_iter_cat()
- {
- using _Cat
- = typename iterator_traits<iterator_t<_Base>>::iterator_category;
- if constexpr (derived_from<_Cat, forward_iterator_tag>)
- return forward_iterator_tag{};
- else
- return _Cat{};
- }
-
constexpr auto&
_M_i_current() noexcept
{ return _M_i.__current(); }
public:
using iterator_concept
= typename _OuterIter<_Const>::iterator_concept;
- using iterator_category = decltype(_S_iter_cat());
+ // iterator_category defined in __lazy_split_view_inner_iter_cat
using value_type = range_value_t<_Base>;
using difference_type = range_difference_t<_Base>;
: _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 decltype(auto)
operator++(int)
{
- if constexpr (forward_range<_Vp>)
+ if constexpr (forward_range<_Base>)
{
auto __tmp = *this;
++*this;
_Vp _M_base = _Vp();
_Pattern _M_pattern = _Pattern();
-
- // XXX: _M_current is "present only if !forward_range<V>"
[[no_unique_address]]
- __detail::__maybe_present_t<!forward_range<_Vp>, iterator_t<_Vp>>
- _M_current;
+ __detail::__maybe_present_t<!forward_range<_Vp>,
+ __detail::__non_propagating_cache<iterator_t<_Vp>>> _M_current;
public:
- split_view() = default;
+ lazy_split_view() requires (default_initializable<_Vp>
+ && default_initializable<_Pattern>)
+ = default;
constexpr
- split_view(_Vp __base, _Pattern __pattern)
+ lazy_split_view(_Vp __base, _Pattern __pattern)
: _M_base(std::move(__base)), _M_pattern(std::move(__pattern))
{ }
requires constructible_from<_Vp, views::all_t<_Range>>
&& constructible_from<_Pattern, single_view<range_value_t<_Range>>>
constexpr
- split_view(_Range&& __r, range_value_t<_Range> __e)
+ lazy_split_view(_Range&& __r, range_value_t<_Range> __e)
: _M_base(views::all(std::forward<_Range>(__r))),
- _M_pattern(std::move(__e))
+ _M_pattern(views::single(std::move(__e)))
{ }
constexpr _Vp
begin()
{
if constexpr (forward_range<_Vp>)
- return _OuterIter<__detail::__simple_view<_Vp>>{
- *this, ranges::begin(_M_base)};
+ {
+ 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<false>{*this};
+ return _OuterIter<false>{this};
}
}
constexpr auto
begin() const requires forward_range<_Vp> && forward_range<const _Vp>
{
- return _OuterIter<true>{*this, ranges::begin(_M_base)};
+ return _OuterIter<true>{this, ranges::begin(_M_base)};
}
constexpr auto
end() requires forward_range<_Vp> && common_range<_Vp>
{
- return _OuterIter<__detail::__simple_view<_Vp>>{
- *this, ranges::end(_M_base)};
+ constexpr bool __simple
+ = __detail::__simple_view<_Vp> && __detail::__simple_view<_Pattern>;
+ return _OuterIter<__simple>{this, ranges::end(_M_base)};
}
constexpr auto
if constexpr (forward_range<_Vp>
&& forward_range<const _Vp>
&& common_range<const _Vp>)
- return _OuterIter<true>{*this, ranges::end(_M_base)};
+ return _OuterIter<true>{this, ranges::end(_M_base)};
else
return default_sentinel;
}
};
- template<typename _Range, typename _Pred>
- split_view(_Range&&, _Pred&&)
- -> split_view<views::all_t<_Range>, views::all_t<_Pred>>;
+ template<typename _Range, typename _Pattern>
+ lazy_split_view(_Range&&, _Pattern&&)
+ -> lazy_split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
template<input_range _Range>
- split_view(_Range&&, range_value_t<_Range>)
- -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
+ lazy_split_view(_Range&&, range_value_t<_Range>)
+ -> lazy_split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
namespace views
{
- inline constexpr __adaptor::_RangeAdaptor split
- = [] <viewable_range _Range, typename _Fp> (_Range&& __r, _Fp&& __f)
- {
- return split_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)};
- };
- } // namespace views
+ namespace __detail
+ {
+ template<typename _Range, typename _Pattern>
+ concept __can_lazy_split_view
+ = requires { lazy_split_view(std::declval<_Range>(), std::declval<_Pattern>()); };
+ } // namespace __detail
- namespace views
- {
+ struct _LazySplit : __adaptor::_RangeAdaptor<_LazySplit>
+ {
+ template<viewable_range _Range, typename _Pattern>
+ 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<typename _Pattern>
+ 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<forward_range _Vp, forward_range _Pattern>
+ requires view<_Vp> && view<_Pattern>
+ && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
+ ranges::equal_to>
+ class split_view : public view_interface<split_view<_Vp, _Pattern>>
+ {
+ private:
+ _Vp _M_base = _Vp();
+ _Pattern _M_pattern = _Pattern();
+ __detail::__non_propagating_cache<subrange<iterator_t<_Vp>>> _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<forward_range _Range>
+ requires constructible_from<_Vp, views::all_t<_Range>>
+ && constructible_from<_Pattern, single_view<range_value_t<_Range>>>
+ 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<iterator_t<_Vp>>
+ _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<iterator_t<_Vp>> _M_next = subrange<iterator_t<_Vp>>();
+ 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<iterator_t<_Vp>>;
+ using difference_type = range_difference_t<_Vp>;
+
+ _Iterator() = default;
+
+ constexpr
+ _Iterator(split_view* __parent,
+ iterator_t<_Vp> __current,
+ subrange<iterator_t<_Vp>> __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<typename _Range, typename _Pattern>
+ split_view(_Range&&, _Pattern&&)
+ -> split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
+
+ template<forward_range _Range>
+ split_view(_Range&&, range_value_t<_Range>)
+ -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
+
+ namespace views
+ {
+ namespace __detail
+ {
+ template<typename _Range, typename _Pattern>
+ concept __can_split_view
+ = requires { split_view(std::declval<_Range>(), std::declval<_Pattern>()); };
+ } // namespace __detail
+
+ struct _Split : __adaptor::_RangeAdaptor<_Split>
+ {
+ template<viewable_range _Range, typename _Pattern>
+ 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<typename _Pattern>
+ 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<input_or_output_iterator _Iter>
constexpr auto
- operator()(_Iter __i, iter_difference_t<_Iter> __n) const
+ operator() [[nodiscard]] (_Iter __i, iter_difference_t<_Iter> __n) const
{
- if constexpr (random_access_iterator<_Iter>)
- return subrange{__i, __i + __n};
+ 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};
+ return subrange(counted_iterator(std::move(__i), __n),
+ default_sentinel);
}
};
_Vp _M_base = _Vp();
public:
- common_view() = default;
+ common_view() requires default_initializable<_Vp> = default;
constexpr explicit
common_view(_Vp __r)
: _M_base(std::move(__r))
{ }
- /* XXX: LWG 3280 didn't remove this constructor, but I think it should?
- template<viewable_range _Range>
- requires (!common_range<_Range>)
- && constructible_from<_Vp, views::all_t<_Range>>
- constexpr explicit
- common_view(_Range&& __r)
- : _M_base(views::all(std::forward<_Range>(__r)))
- { }
- */
-
constexpr _Vp
base() const& requires copy_constructible<_Vp>
{ return _M_base; }
template<typename _Range>
common_view(_Range&&) -> common_view<views::all_t<_Range>>;
+ template<typename _Tp>
+ inline constexpr bool enable_borrowed_range<common_view<_Tp>>
+ = enable_borrowed_range<_Tp>;
+
namespace views
{
- inline constexpr __adaptor::_RangeAdaptorClosure common
- = [] <viewable_range _Range> (_Range&& __r)
- {
- if constexpr (common_range<_Range>
- && requires { views::all(std::forward<_Range>(__r)); })
- return views::all(std::forward<_Range>(__r));
- else
- return common_view{std::forward<_Range>(__r)};
- };
+ namespace __detail
+ {
+ template<typename _Range>
+ concept __already_common = common_range<_Range>
+ && requires { views::all(std::declval<_Range>()); };
+
+ template<typename _Range>
+ concept __can_common_view
+ = requires { common_view{std::declval<_Range>()}; };
+ } // namespace __detail
+
+ struct _Common : __adaptor::_RangeAdaptorClosure
+ {
+ template<viewable_range _Range>
+ 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<view _Vp>
class reverse_view : public view_interface<reverse_view<_Vp>>
{
private:
- _Vp _M_base = _Vp();
-
static constexpr bool _S_needs_cached_begin
- = !common_range<_Vp> && !random_access_range<_Vp>;
+ = !common_range<_Vp> && !(random_access_range<_Vp>
+ && sized_sentinel_for<sentinel_t<_Vp>,
+ 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() = default;
+ reverse_view() requires default_initializable<_Vp> = default;
constexpr explicit
reverse_view(_Vp __r)
{
if constexpr (_S_needs_cached_begin)
if (_M_cached_begin._M_has_value())
- return make_reverse_iterator(_M_cached_begin._M_get(_M_base));
+ 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 make_reverse_iterator(std::move(__it));
+ return std::make_reverse_iterator(std::move(__it));
}
constexpr auto
begin() requires common_range<_Vp>
- { return make_reverse_iterator(ranges::end(_M_base)); }
+ { return std::make_reverse_iterator(ranges::end(_M_base)); }
constexpr auto
begin() const requires common_range<const _Vp>
- { return make_reverse_iterator(ranges::end(_M_base)); }
+ { return std::make_reverse_iterator(ranges::end(_M_base)); }
constexpr reverse_iterator<iterator_t<_Vp>>
end()
- { return make_reverse_iterator(ranges::begin(_M_base)); }
+ { return std::make_reverse_iterator(ranges::begin(_M_base)); }
constexpr auto
end() const requires common_range<const _Vp>
- { return make_reverse_iterator(ranges::begin(_M_base)); }
+ { return std::make_reverse_iterator(ranges::begin(_M_base)); }
constexpr auto
size() requires sized_range<_Vp>
template<typename _Range>
reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>;
+ template<typename _Tp>
+ inline constexpr bool enable_borrowed_range<reverse_view<_Tp>>
+ = enable_borrowed_range<_Tp>;
+
namespace views
{
namespace __detail
template<typename _Vp>
inline constexpr bool __is_reverse_view<reverse_view<_Vp>> = true;
- }
- inline constexpr __adaptor::_RangeAdaptorClosure reverse
- = [] <viewable_range _Range> (_Range&& __r)
- {
- 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)};
- };
+ template<typename _Range>
+ concept __can_reverse_view
+ = requires { reverse_view{std::declval<_Range>()}; };
+ } // namespace __detail
+
+ struct _Reverse : __adaptor::_RangeAdaptorClosure
+ {
+ template<viewable_range _Range>
+ requires __detail::__is_reverse_view<remove_cvref_t<_Range>>
+ || __detail::__is_reversible_subrange<remove_cvref_t<_Range>>
+ || __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
{ std::get<_Nm>(__t) }
-> convertible_to<const tuple_element_t<_Nm, _Tp>&>;
};
+
+ template<typename _Tp, size_t _Nm>
+ concept __returnable_element
+ = is_reference_v<_Tp> || move_constructible<tuple_element_t<_Nm, _Tp>>;
}
template<input_range _Vp, size_t _Nm>
&& __detail::__has_tuple_element<range_value_t<_Vp>, _Nm>
&& __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>,
_Nm>
+ && __detail::__returnable_element<range_reference_t<_Vp>, _Nm>
class elements_view : public view_interface<elements_view<_Vp, _Nm>>
{
public:
- elements_view() = default;
+ elements_view() requires default_initializable<_Vp> = default;
constexpr explicit
- elements_view(_Vp base)
- : _M_base(std::move(base))
+ elements_view(_Vp __base)
+ : _M_base(std::move(__base))
{ }
constexpr _Vp
{ return ranges::size(_M_base); }
private:
+ template<bool _Const>
+ using _Base = __detail::__maybe_const_t<_Const, _Vp>;
+
+ template<bool _Const>
+ struct __iter_cat
+ { };
+
+ template<bool _Const>
+ 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_t<_Base>>::iterator_category;
+ using _Res = decltype((std::get<_Nm>(*std::declval<iterator_t<_Base>>())));
+ 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<bool _Const>
struct _Sentinel;
template<bool _Const>
- struct _Iterator
+ struct _Iterator : __iter_cat<_Const>
{
- using _Base = __detail::__maybe_const_t<_Const, _Vp>;
+ 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<range_reference_t<_Base>>)
+ return std::get<_Nm>(*__i);
+ else
+ {
+ using _Et = remove_cv_t<tuple_element_t<_Nm, range_reference_t<_Base>>>;
+ 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<!_Const>;
public:
- using iterator_category
- = typename iterator_traits<iterator_t<_Base>>::iterator_category;
+ using iterator_concept = decltype(_S_iter_concept());
+ // iterator_category defined in elements_view::__iter_cat
using value_type
= remove_cvref_t<tuple_element_t<_Nm, range_value_t<_Base>>>;
using difference_type = range_difference_t<_Base>;
- _Iterator() = default;
+ _Iterator() requires default_initializable<iterator_t<_Base>> = default;
constexpr explicit
- _Iterator(iterator_t<_Base> current)
- : _M_current(std::move(current))
+ _Iterator(iterator_t<_Base> __current)
+ : _M_current(std::move(__current))
{ }
constexpr
- _Iterator(_Iterator<!_Const> i)
+ _Iterator(_Iterator<!_Const> __i)
requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
- : _M_current(std::move(i._M_current))
+ : _M_current(std::move(__i._M_current))
{ }
- constexpr iterator_t<_Base>
- base() const&
- requires copyable<iterator_t<_Base>>
+ constexpr const iterator_t<_Base>&
+ base() const& noexcept
{ return _M_current; }
constexpr iterator_t<_Base>
{ return std::move(_M_current); }
constexpr decltype(auto)
- operator*() const
- { return std::get<_Nm>(*_M_current); }
+ operator*() const
+ { return _S_get_element(_M_current); }
constexpr _Iterator&
operator++()
}
constexpr void
- operator++(int) requires (!forward_range<_Base>)
+ operator++(int)
{ ++_M_current; }
constexpr _Iterator
constexpr decltype(auto)
operator[](difference_type __n) const
requires random_access_range<_Base>
- { return std::get<_Nm>(*(_M_current + __n)); }
+ { return _S_get_element(_M_current + __n); }
friend constexpr bool
operator==(const _Iterator& __x, const _Iterator& __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 random_access_range<_Base>
+ requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
{ return __x._M_current - __y._M_current; }
- friend _Sentinel<_Const>;
+ template <bool> friend struct _Sentinel;
};
template<bool _Const>
struct _Sentinel
{
private:
- constexpr bool
- _M_equal(const _Iterator<_Const>& __x) const
- { return __x._M_current == _M_end; }
+ template<bool _Const2>
+ constexpr bool
+ _M_equal(const _Iterator<_Const2>& __x) const
+ { return __x._M_current == _M_end; }
- using _Base = __detail::__maybe_const_t<_Const, _Vp>;
+ template<bool _Const2>
+ 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:
requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
friend constexpr range_difference_t<_Base2>
operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
- { return __x._M_current - __y._M_end; }
+ { return -__y._M_distance_from(__x); }
template<bool _Const2,
typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
- friend constexpr range_difference_t<_Base>
+ friend constexpr range_difference_t<_Base2>
operator-(const _Sentinel& __x, const _Iterator<_Const2>& __y)
- { return __x._M_end - __y._M_current; }
+ { return __x._M_distance_from(__y); }
friend _Sentinel<!_Const>;
};
_Vp _M_base = _Vp();
};
+ template<typename _Tp, size_t _Nm>
+ inline constexpr bool enable_borrowed_range<elements_view<_Tp, _Nm>>
+ = enable_borrowed_range<_Tp>;
+
template<typename _Range>
using keys_view = elements_view<views::all_t<_Range>, 0>;
namespace views
{
+ namespace __detail
+ {
+ template<size_t _Nm, typename _Range>
+ concept __can_elements_view
+ = requires { elements_view<all_t<_Range>, _Nm>{std::declval<_Range>()}; };
+ } // namespace __detail
+
template<size_t _Nm>
- inline constexpr __adaptor::_RangeAdaptorClosure elements
- = [] <viewable_range _Range> (_Range&& __r)
+ struct _Elements : __adaptor::_RangeAdaptorClosure
{
- using _El = elements_view<views::all_t<_Range>, _Nm>;
- return _El{std::forward<_Range>(__r)};
+ template<viewable_range _Range>
+ requires __detail::__can_elements_view<_Nm, _Range>
+ constexpr auto
+ operator() [[nodiscard]] (_Range&& __r) const
+ {
+ return elements_view<all_t<_Range>, _Nm>{std::forward<_Range>(__r)};
+ }
+
+ static constexpr bool _S_has_simple_call_op = true;
};
- inline constexpr __adaptor::_RangeAdaptorClosure keys = elements<0>;
- inline constexpr __adaptor::_RangeAdaptorClosure values = elements<1>;
+ template<size_t _Nm>
+ inline constexpr _Elements<_Nm> elements;
+ inline constexpr auto keys = elements<0>;
+ inline constexpr auto values = elements<1>;
} // namespace views
-} // namespace ranges
+#if __cplusplus > 202002L
+ namespace __detail
+ {
+ template<typename... _Rs>
+ concept __zip_is_common = (sizeof...(_Rs) == 1 && (common_range<_Rs> && ...))
+ || (!(bidirectional_range<_Rs> && ...) && (common_range<_Rs> && ...))
+ || ((random_access_range<_Rs> && ...) && (sized_range<_Rs> && ...));
- namespace views = ranges::views;
+ template<typename... _Ts>
+ struct __tuple_or_pair
+ { using type = std::tuple<_Ts...>; };
- template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
- struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>>
- : integral_constant<size_t, 2>
- { };
+ template<typename _Tp, typename _Up>
+ struct __tuple_or_pair<_Tp, _Up>
+ { using type = pair<_Tp, _Up>; };
+
+ template<typename... _Ts>
+ using __tuple_or_pair_t = typename __tuple_or_pair<_Ts...>::type;
+
+ template<typename _Fp, typename _Tuple>
+ constexpr auto
+ __tuple_transform(_Fp&& __f, _Tuple&& __tuple)
+ {
+ return std::apply([&]<typename... _Ts>(_Ts&&... __elts) {
+ return __tuple_or_pair_t<invoke_result_t<_Fp&, _Ts>...>
+ (std::__invoke(__f, std::forward<_Ts>(__elts))...);
+ }, std::forward<_Tuple>(__tuple));
+ }
+
+ template<typename _Fp, typename _Tuple>
+ constexpr void
+ __tuple_for_each(_Fp&& __f, _Tuple&& __tuple)
+ {
+ std::apply([&]<typename... _Ts>(_Ts&&... __elts) {
+ (std::__invoke(__f, std::forward<_Ts>(__elts)), ...);
+ }, std::forward<_Tuple>(__tuple));
+ }
+ } // namespace __detail
+
+ template<input_range... _Vs>
+ requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0)
+ class zip_view : public view_interface<zip_view<_Vs...>>
+ {
+ tuple<_Vs...> _M_views;
+
+ template<bool> class _Iterator;
+ template<bool> 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<false>(__detail::__tuple_transform(ranges::begin, _M_views)); }
+
+ constexpr auto
+ begin() const requires (range<const _Vs> && ...)
+ { return _Iterator<true>(__detail::__tuple_transform(ranges::begin, _M_views)); }
+
+ constexpr auto
+ end() requires (!(__detail::__simple_view<_Vs> && ...))
+ {
+ if constexpr (!__detail::__zip_is_common<_Vs...>)
+ return _Sentinel<false>(__detail::__tuple_transform(ranges::end, _M_views));
+ else if constexpr ((random_access_range<_Vs> && ...))
+ return begin() + iter_difference_t<_Iterator<false>>(size());
+ else
+ return _Iterator<false>(__detail::__tuple_transform(ranges::end, _M_views));
+ }
+
+ constexpr auto
+ end() const requires (range<const _Vs> && ...)
+ {
+ if constexpr (!__detail::__zip_is_common<const _Vs...>)
+ return _Sentinel<true>(__detail::__tuple_transform(ranges::end, _M_views));
+ else if constexpr ((random_access_range<const _Vs> && ...))
+ return begin() + iter_difference_t<_Iterator<true>>(size());
+ else
+ return _Iterator<true>(__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<common_type_t<decltype(sizes)...>>;
+ return ranges::min({_CT(sizes)...});
+ }, __detail::__tuple_transform(ranges::size, _M_views));
+ }
+
+ constexpr auto
+ size() const requires (sized_range<const _Vs> && ...)
+ {
+ return std::apply([](auto... sizes) {
+ using _CT = __detail::__make_unsigned_like_t<common_type_t<decltype(sizes)...>>;
+ return ranges::min({_CT(sizes)...});
+ }, __detail::__tuple_transform(ranges::size, _M_views));
+ }
+ };
+
+ template<typename... _Rs>
+ zip_view(_Rs&&...) -> zip_view<views::all_t<_Rs>...>;
+
+ template<typename... _Views>
+ inline constexpr bool enable_borrowed_range<zip_view<_Views...>>
+ = (enable_borrowed_range<_Views> && ...);
- template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
- struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>>
- { using type = _Iter; };
+ namespace __detail
+ {
+ template<bool _Const, typename... _Vs>
+ concept __all_random_access
+ = (random_access_range<__maybe_const_t<_Const, _Vs>> && ...);
+
+ template<bool _Const, typename... _Vs>
+ concept __all_bidirectional
+ = (bidirectional_range<__maybe_const_t<_Const, _Vs>> && ...);
+
+ template<bool _Const, typename... _Vs>
+ concept __all_forward
+ = (forward_range<__maybe_const_t<_Const, _Vs>> && ...);
+
+ template<bool _Const, typename... _Views>
+ struct __zip_view_iter_cat
+ { };
+
+ template<bool _Const, typename... _Views>
+ requires __all_forward<_Const, _Views...>
+ struct __zip_view_iter_cat<_Const, _Views...>
+ { using iterator_category = input_iterator_tag; };
+ } // namespace __detail
+
+ template<input_range... _Vs>
+ requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0)
+ template<bool _Const>
+ class zip_view<_Vs...>::_Iterator
+ : public __detail::__zip_view_iter_cat<_Const, _Vs...>
+ {
+ __detail::__tuple_or_pair_t<iterator_t<__detail::__maybe_const_t<_Const, _Vs>>...> _M_current;
- template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
- struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>>
- { using type = _Sent; };
+ constexpr explicit
+ _Iterator(decltype(_M_current) __current)
+ : _M_current(std::move(__current))
+ { }
- template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
- struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>>
- { using type = _Iter; };
+ 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{};
+ }
- template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
- struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>>
- { using type = _Sent; };
+ template<copy_constructible _Fp, input_range... _Ws>
+ requires (view<_Ws> && ...) && (sizeof...(_Ws) > 0) && is_object_v<_Fp>
+ && regular_invocable<_Fp&, range_reference_t<_Ws>...>
+ && std::__detail::__can_reference<invoke_result_t<_Fp&, range_reference_t<_Ws>...>>
+ friend class zip_transform_view;
+
+ public:
+ // iterator_category defined in __zip_view_iter_cat
+ using iterator_concept = decltype(_S_iter_concept());
+ using value_type
+ = __detail::__tuple_or_pair_t<range_value_t<__detail::__maybe_const_t<_Const, _Vs>>...>;
+ using difference_type
+ = common_type_t<range_difference_t<__detail::__maybe_const_t<_Const, _Vs>>...>;
+
+ _Iterator() = default;
+
+ constexpr
+ _Iterator(_Iterator<!_Const> __i)
+ requires _Const
+ && (convertible_to<iterator_t<_Vs>,
+ 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 = [&]<typename _It>(_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 = [&]<typename _It>(_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 = [&]<typename _It>(_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<iterator_t<__detail::__maybe_const_t<_Const, _Vs>>> && ...)
+ {
+ if constexpr (__detail::__all_bidirectional<_Const, _Vs...>)
+ return __x._M_current == __y._M_current;
+ else
+ return [&]<size_t... _Is>(index_sequence<_Is...>) {
+ return ((std::get<_Is>(__x._M_current) == std::get<_Is>(__y._M_current)) || ...);
+ }(make_index_sequence<sizeof...(_Vs)>{});
+ }
+
+ 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>>,
+ iterator_t<__detail::__maybe_const_t<_Const, _Vs>>> && ...)
+ {
+ return [&]<size_t... _Is>(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<sizeof...(_Vs)>{});
+ }
+
+ 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<iterator_t<__detail::__maybe_const_t<_Const, _Vs>>> && ...)
+ {
+ [&]<size_t... _Is>(index_sequence<_Is...>) {
+ (ranges::iter_swap(std::get<_Is>(__l._M_current), std::get<_Is>(__r._M_current)), ...);
+ }(make_index_sequence<sizeof...(_Vs)>{});
+ }
+
+ friend class zip_view;
+ };
+
+ template<input_range... _Vs>
+ requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0)
+ template<bool _Const>
+ class zip_view<_Vs...>::_Sentinel
+ {
+ __detail::__tuple_or_pair_t<sentinel_t<__detail::__maybe_const_t<_Const, _Vs>>...> _M_end;
+
+ constexpr explicit
+ _Sentinel(decltype(_M_end) __end)
+ : _M_end(__end)
+ { }
+
+ friend class zip_view;
+
+ public:
+ _Sentinel() = default;
+
+ constexpr
+ _Sentinel(_Sentinel<!_Const> __i)
+ requires _Const
+ && (convertible_to<sentinel_t<_Vs>,
+ sentinel_t<__detail::__maybe_const_t<_Const, _Vs>>> && ...)
+ : _M_end(std::move(__i._M_end))
+ { }
+
+ template<bool _OtherConst>
+ requires (sentinel_for<sentinel_t<__detail::__maybe_const_t<_Const, _Vs>>,
+ iterator_t<__detail::__maybe_const_t<_OtherConst, _Vs>>> && ...)
+ friend constexpr bool
+ operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y)
+ {
+ return [&]<size_t... _Is>(index_sequence<_Is...>) {
+ return ((std::get<_Is>(__x._M_current) == std::get<_Is>(__y._M_end)) || ...);
+ }(make_index_sequence<sizeof...(_Vs)>{});
+ }
+
+ template<bool _OtherConst>
+ requires (sized_sentinel_for<sentinel_t<__detail::__maybe_const_t<_Const, _Vs>>,
+ iterator_t<__detail::__maybe_const_t<_OtherConst, _Vs>>> && ...)
+ friend constexpr auto
+ operator-(const _Iterator<_OtherConst>& __x, const _Sentinel& __y)
+ {
+ using _Ret
+ = common_type_t<range_difference_t<__detail::__maybe_const_t<_OtherConst, _Vs>>...>;
+ return [&]<size_t... _Is>(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<sizeof...(_Vs)>{});
+ }
+
+ template<bool _OtherConst>
+ requires (sized_sentinel_for<sentinel_t<__detail::__maybe_const_t<_Const, _Vs>>,
+ 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<typename... _Ts>
+ concept __can_zip_view
+ = requires { zip_view<all_t<_Ts>...>(std::declval<_Ts>()...); };
+ }
+
+ struct _Zip
+ {
+ template<typename... _Ts>
+ requires (sizeof...(_Ts) == 0 || __detail::__can_zip_view<_Ts...>)
+ constexpr auto
+ operator() [[nodiscard]] (_Ts&&... __ts) const
+ {
+ if constexpr (sizeof...(_Ts) == 0)
+ return views::empty<tuple<>>;
+ else
+ return zip_view<all_t<_Ts>...>(std::forward<_Ts>(__ts)...);
+ }
+ };
+
+ inline constexpr _Zip zip;
+ }
+
+ namespace __detail
+ {
+ template<typename _Range, bool _Const>
+ using __range_iter_cat
+ = typename iterator_traits<iterator_t<__maybe_const_t<_Const, _Range>>>::iterator_category;
+ }
+
+ template<copy_constructible _Fp, input_range... _Vs>
+ requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) && is_object_v<_Fp>
+ && regular_invocable<_Fp&, range_reference_t<_Vs>...>
+ && std::__detail::__can_reference<invoke_result_t<_Fp&, range_reference_t<_Vs>...>>
+ class zip_transform_view : public view_interface<zip_transform_view<_Fp, _Vs...>>
+ {
+ [[no_unique_address]] __detail::__box<_Fp> _M_fun;
+ zip_view<_Vs...> _M_zip;
+
+ using _InnerView = zip_view<_Vs...>;
+
+ template<bool _Const>
+ using __ziperator = iterator_t<__detail::__maybe_const_t<_Const, _InnerView>>;
+
+ template<bool _Const>
+ using __zentinel = sentinel_t<__detail::__maybe_const_t<_Const, _InnerView>>;
+
+ template<bool _Const>
+ using _Base = __detail::__maybe_const_t<_Const, _InnerView>;
+
+ template<bool _Const>
+ struct __iter_cat
+ { };
+
+ template<bool _Const>
+ 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<bool> class _Iterator;
+ template<bool> 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<false>(*this, _M_zip.begin()); }
+
+ constexpr auto
+ begin() const
+ requires range<const _InnerView>
+ && regular_invocable<const _Fp&, range_reference_t<const _Vs>...>
+ { return _Iterator<true>(*this, _M_zip.begin()); }
+
+ constexpr auto
+ end()
+ {
+ if constexpr (common_range<_InnerView>)
+ return _Iterator<false>(*this, _M_zip.end());
+ else
+ return _Sentinel<false>(_M_zip.end());
+ }
+
+ constexpr auto
+ end() const
+ requires range<const _InnerView>
+ && regular_invocable<const _Fp&, range_reference_t<const _Vs>...>
+ {
+ if constexpr (common_range<const _InnerView>)
+ return _Iterator<true>(*this, _M_zip.end());
+ else
+ return _Sentinel<true>(_M_zip.end());
+ }
+
+ constexpr auto
+ size() requires sized_range<_InnerView>
+ { return _M_zip.size(); }
+
+ constexpr auto
+ size() const requires sized_range<const _InnerView>
+ { return _M_zip.size(); }
+ };
+
+ template<class _Fp, class... Rs>
+ zip_transform_view(_Fp, Rs&&...) -> zip_transform_view<_Fp, views::all_t<Rs>...>;
+
+ template<copy_constructible _Fp, input_range... _Vs>
+ requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) && is_object_v<_Fp>
+ && regular_invocable<_Fp&, range_reference_t<_Vs>...>
+ && std::__detail::__can_reference<invoke_result_t<_Fp&, range_reference_t<_Vs>...>>
+ template<bool _Const>
+ 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<invoke_result_t<__detail::__maybe_const_t<_Const, _Fp>&,
+ range_reference_t<__detail::__maybe_const_t<_Const, _Vs>>...>>;
+ using difference_type = range_difference_t<_Base<_Const>>;
+
+ _Iterator() = default;
+
+ constexpr
+ _Iterator(_Iterator<!_Const> __i)
+ requires _Const && convertible_to<__ziperator<false>, __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([&]<typename... _Is>(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<copy_constructible _Fp, input_range... _Vs>
+ requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) && is_object_v<_Fp>
+ && regular_invocable<_Fp&, range_reference_t<_Vs>...>
+ && std::__detail::__can_reference<invoke_result_t<_Fp&, range_reference_t<_Vs>...>>
+ template<bool _Const>
+ 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<!_Const> __i)
+ requires _Const && convertible_to<__zentinel<false>, __zentinel<_Const>>
+ : _M_inner(std::move(__i._M_inner))
+ { }
+
+ template<bool _OtherConst>
+ 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<bool _OtherConst>
+ 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<bool _OtherConst>
+ 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<typename _Fp, typename... _Ts>
+ concept __can_zip_transform_view
+ = requires { zip_transform_view(std::declval<_Fp>(), std::declval<_Ts>()...); };
+ }
+
+ struct _ZipTransform
+ {
+ template<typename _Fp, typename... _Ts>
+ 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<decay_t<invoke_result_t<decay_t<_Fp>&>>>;
+ else
+ return zip_transform_view(std::forward<_Fp>(__f), std::forward<_Ts>(__ts)...);
+ }
+ };
+
+ inline constexpr _ZipTransform zip_transform;
+ }
+
+ template<forward_range _Vp, size_t _Nm>
+ requires view<_Vp> && (_Nm > 0)
+ class adjacent_view : public view_interface<adjacent_view<_Vp, _Nm>>
+ {
+ _Vp _M_base = _Vp();
+
+ template<bool> class _Iterator;
+ template<bool> 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<false>(ranges::begin(_M_base), ranges::end(_M_base)); }
+
+ constexpr auto
+ begin() const requires range<const _Vp>
+ { return _Iterator<true>(ranges::begin(_M_base), ranges::end(_M_base)); }
+
+ constexpr auto
+ end() requires (!__detail::__simple_view<_Vp>)
+ {
+ if constexpr (common_range<_Vp>)
+ return _Iterator<false>(__as_sentinel{}, ranges::begin(_M_base), ranges::end(_M_base));
+ else
+ return _Sentinel<false>(ranges::end(_M_base));
+ }
+
+ constexpr auto
+ end() const requires range<const _Vp>
+ {
+ if constexpr (common_range<const _Vp>)
+ return _Iterator<true>(__as_sentinel{}, ranges::begin(_M_base), ranges::end(_M_base));
+ else
+ return _Sentinel<true>(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<const _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);
+ }
+ };
+
+ template<typename _Vp, size_t _Nm>
+ inline constexpr bool enable_borrowed_range<adjacent_view<_Vp, _Nm>>
+ = enable_borrowed_range<_Vp>;
+
+ namespace __detail
+ {
+ // Yields tuple<_Tp, ..., _Tp> with _Nm elements.
+ template<typename _Tp, size_t _Nm>
+ using __repeated_tuple = decltype(std::tuple_cat(std::declval<array<_Tp, _Nm>>()));
+
+ // For a functor F that is callable with N arguments, the expression
+ // declval<__unarize<F, N>>(x) is equivalent to declval<F>(x, ..., x).
+ template<typename _Fp, size_t _Nm>
+ struct __unarize
+ {
+ template<typename... _Ts>
+ static invoke_result_t<_Fp, _Ts...>
+ __tuple_apply(const tuple<_Ts...>&); // not defined
+
+ template<typename _Tp>
+ decltype(__tuple_apply(std::declval<__repeated_tuple<_Tp, _Nm>>()))
+ operator()(_Tp&&); // not defined
+ };
+ }
+
+ template<forward_range _Vp, size_t _Nm>
+ requires view<_Vp> && (_Nm > 0)
+ template<bool _Const>
+ class adjacent_view<_Vp, _Nm>::_Iterator
+ {
+ using _Base = __detail::__maybe_const_t<_Const, _Vp>;
+ array<iterator_t<_Base>, _Nm> _M_current = array<iterator_t<_Base>, _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;
+
+ template<forward_range _Wp, copy_constructible _Fp, size_t _Mm>
+ requires view<_Wp> && (_Mm > 0) && is_object_v<_Fp>
+ && regular_invocable<__detail::__unarize<_Fp&, _Mm>, range_reference_t<_Wp>>
+ && std::__detail::__can_reference<invoke_result_t<__detail::__unarize<_Fp&, _Mm>,
+ range_reference_t<_Wp>>>
+ friend class adjacent_transform_view;
+
+ 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>, range_value_t<_Base>>,
+ __detail::__repeated_tuple<range_value_t<_Base>, _Nm>>;
+ using difference_type = range_difference_t<_Base>;
+
+ _Iterator() = default;
+
+ constexpr
+ _Iterator(_Iterator<!_Const> __i)
+ requires _Const && convertible_to<iterator_t<_Vp>, 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<iterator_t<_Base>>
+ { 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>, 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<iterator_t<_Base>>
+ {
+ for (size_t __i = 0; __i < _Nm; __i++)
+ ranges::iter_swap(__l._M_current[__i], __r._M_current[__i]);
+ }
+ };
+
+ template<forward_range _Vp, size_t _Nm>
+ requires view<_Vp> && (_Nm > 0)
+ template<bool _Const>
+ 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<!_Const> __i)
+ requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
+ : _M_end(std::move(__i._M_end))
+ { }
+
+ template<bool _OtherConst>
+ requires sentinel_for<sentinel_t<_Base>,
+ 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<bool _OtherConst>
+ requires sized_sentinel_for<sentinel_t<_Base>,
+ 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<bool _OtherConst>
+ requires sized_sentinel_for<sentinel_t<_Base>,
+ 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<size_t _Nm, typename _Range>
+ concept __can_adjacent_view
+ = requires { adjacent_view<all_t<_Range>, _Nm>(std::declval<_Range>()); };
+ }
+
+ template<size_t _Nm>
+ struct _Adjacent : __adaptor::_RangeAdaptorClosure
+ {
+ template<viewable_range _Range>
+ requires (_Nm == 0) || __detail::__can_adjacent_view<_Nm, _Range>
+ constexpr auto
+ operator() [[nodiscard]] (_Range&& __r) const
+ {
+ if constexpr (_Nm == 0)
+ return views::empty<tuple<>>;
+ else
+ return adjacent_view<all_t<_Range>, _Nm>(std::forward<_Range>(__r));
+ }
+ };
+
+ template<size_t _Nm>
+ inline constexpr _Adjacent<_Nm> adjacent;
+
+ inline constexpr auto pairwise = adjacent<2>;
+ }
+
+ template<forward_range _Vp, copy_constructible _Fp, size_t _Nm>
+ requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp>
+ && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>>
+ && std::__detail::__can_reference<invoke_result_t<__detail::__unarize<_Fp&, _Nm>,
+ range_reference_t<_Vp>>>
+ class adjacent_transform_view : public view_interface<adjacent_transform_view<_Vp, _Fp, _Nm>>
+ {
+ [[no_unique_address]] __detail::__box<_Fp> _M_fun;
+ adjacent_view<_Vp, _Nm> _M_inner;
+
+ using _InnerView = adjacent_view<_Vp, _Nm>;
+
+ template<bool _Const>
+ using _InnerIter = iterator_t<__detail::__maybe_const_t<_Const, _InnerView>>;
+
+ template<bool _Const>
+ using _InnerSent = sentinel_t<__detail::__maybe_const_t<_Const, _InnerView>>;
+
+ template<bool> class _Iterator;
+ template<bool> 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<false>(*this, _M_inner.begin()); }
+
+ constexpr auto
+ begin() const
+ requires range<const _InnerView>
+ && regular_invocable<__detail::__unarize<const _Fp&, _Nm>,
+ range_reference_t<const _Vp>>
+ { return _Iterator<true>(*this, _M_inner.begin()); }
+
+ constexpr auto
+ end()
+ {
+ if constexpr (common_range<_InnerView>)
+ return _Iterator<false>(*this, _M_inner.end());
+ else
+ return _Sentinel<false>(_M_inner.end());
+ }
+
+ constexpr auto
+ end() const
+ requires range<const _InnerView>
+ && regular_invocable<__detail::__unarize<const _Fp&, _Nm>,
+ range_reference_t<const _Vp>>
+ {
+ if constexpr (common_range<const _InnerView>)
+ return _Iterator<true>(*this, _M_inner.end());
+ else
+ return _Sentinel<true>(_M_inner.end());
+ }
+
+ constexpr auto
+ size() requires sized_range<_InnerView>
+ { return _M_inner.size(); }
+
+ constexpr auto
+ size() const requires sized_range<const _InnerView>
+ { return _M_inner.size(); }
+ };
+
+ template<forward_range _Vp, copy_constructible _Fp, size_t _Nm>
+ requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp>
+ && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>>
+ && std::__detail::__can_reference<invoke_result_t<__detail::__unarize<_Fp&, _Nm>,
+ range_reference_t<_Vp>>>
+ template<bool _Const>
+ 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_t<_Base>>::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<invoke_result_t
+ <__detail::__unarize<__detail::__maybe_const_t<_Const, _Fp>&, _Nm>,
+ range_reference_t<_Base>>>;
+ using difference_type = range_difference_t<_Base>;
+
+ _Iterator() = default;
+
+ constexpr
+ _Iterator(_Iterator<!_Const> __i)
+ requires _Const && convertible_to<_InnerIter<false>, _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<forward_range _Vp, copy_constructible _Fp, size_t _Nm>
+ requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp>
+ && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>>
+ && std::__detail::__can_reference<invoke_result_t<__detail::__unarize<_Fp&, _Nm>,
+ range_reference_t<_Vp>>>
+ template<bool _Const>
+ 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<!_Const> __i)
+ requires _Const && convertible_to<_InnerSent<false>, _InnerSent<_Const>>
+ : _M_inner(std::move(__i._M_inner))
+ { }
+
+ template<bool _OtherConst>
+ 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<bool _OtherConst>
+ 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<bool _OtherConst>
+ 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<size_t _Nm, typename _Range, typename _Fp>
+ concept __can_adjacent_transform_view
+ = requires { adjacent_transform_view<all_t<_Range>, decay_t<_Fp>, _Nm>
+ (std::declval<_Range>(), std::declval<_Fp>()); };
+ }
+
+ template<size_t _Nm>
+ struct _AdjacentTransform : __adaptor::_RangeAdaptor<_AdjacentTransform<_Nm>>
+ {
+ template<viewable_range _Range, typename _Fp>
+ 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<all_t<_Range>, 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<size_t _Nm>
+ inline constexpr _AdjacentTransform<_Nm> adjacent_transform;
+
+ inline constexpr auto pairwise_transform = adjacent_transform<2>;
+ }
+
+ namespace __detail
+ {
+ template<typename _Tp>
+ constexpr _Tp __div_ceil(_Tp __num, _Tp __denom)
+ {
+ _Tp __r = __num / __denom;
+ if (__num % __denom)
+ ++__r;
+ return __r;
+ }
+ }
+
+ template<view _Vp>
+ requires input_range<_Vp>
+ class chunk_view : public view_interface<chunk_view<_Vp>>
+ {
+ _Vp _M_base;
+ range_difference_t<_Vp> _M_n;
+ range_difference_t<_Vp> _M_remainder = 0;
+ __detail::__non_propagating_cache<iterator_t<_Vp>> _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<const _Vp>
+ {
+ return __detail::__to_unsigned_like(__detail::__div_ceil
+ (ranges::distance(_M_base), _M_n));
+ }
+ };
+
+ template<typename _Range>
+ chunk_view(_Range&&, range_difference_t<_Range>) -> chunk_view<views::all_t<_Range>>;
+
+ template<view _Vp>
+ 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<sentinel_t<_Vp>, 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<sentinel_t<_Vp>, iterator_t<_Vp>>
+ { return -(__y - __x); }
+ };
+
+ template<view _Vp>
+ requires input_range<_Vp>
+ struct chunk_view<_Vp>::_OuterIter::value_type : view_interface<value_type>
+ {
+ 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<sentinel_t<_Vp>, 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<view _Vp>
+ 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<sentinel_t<_Vp>, 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<sentinel_t<_Vp>, iterator_t<_Vp>>
+ { return -(__y - __x); }
+ };
+
+ template<view _Vp>
+ requires forward_range<_Vp>
+ class chunk_view<_Vp> : public view_interface<chunk_view<_Vp>>
+ {
+ _Vp _M_base;
+ range_difference_t<_Vp> _M_n;
+ template<bool> 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<false>(this, ranges::begin(_M_base)); }
+
+ constexpr auto
+ begin() const requires forward_range<const _Vp>
+ { return _Iterator<true>(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<false>(this, ranges::end(_M_base), __missing);
+ }
+ else if constexpr (common_range<_Vp> && !bidirectional_range<_Vp>)
+ return _Iterator<false>(this, ranges::end(_M_base));
+ else
+ return default_sentinel;
+ }
+
+ constexpr auto
+ end() const requires forward_range<const _Vp>
+ {
+ if constexpr (common_range<const _Vp> && sized_range<const _Vp>)
+ {
+ auto __missing = (_M_n - ranges::distance(_M_base) % _M_n) % _M_n;
+ return _Iterator<true>(this, ranges::end(_M_base), __missing);
+ }
+ else if constexpr (common_range<const _Vp> && !bidirectional_range<const _Vp>)
+ return _Iterator<true>(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<const _Vp>
+ {
+ return __detail::__to_unsigned_like(__detail::__div_ceil
+ (ranges::distance(_M_base), _M_n));
+ }
+ };
+
+ template<typename _Vp>
+ inline constexpr bool enable_borrowed_range<chunk_view<_Vp>>
+ = forward_range<_Vp> && enable_borrowed_range<_Vp>;
+
+ template<view _Vp>
+ requires forward_range<_Vp>
+ template<bool _Const>
+ 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<!_Const> __i)
+ requires _Const
+ && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
+ && convertible_to<sentinel_t<_Vp>, 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<iterator_t<_Base>>
+ { 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>, 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<sentinel_t<_Base>, 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<sentinel_t<_Base>, iterator_t<_Base>>
+ { return -(__y - __x); }
+ };
+
+ namespace views
+ {
+ namespace __detail
+ {
+ template<typename _Range, typename _Dp>
+ concept __can_chunk_view
+ = requires { chunk_view(std::declval<_Range>(), std::declval<_Dp>()); };
+ }
+
+ struct _Chunk : __adaptor::_RangeAdaptor<_Chunk>
+ {
+ template<viewable_range _Range, typename _Dp = range_difference_t<_Range>>
+ 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;
+ }
+
+ namespace __detail
+ {
+ template<typename _Vp>
+ concept __slide_caches_nothing = random_access_range<_Vp> && sized_range<_Vp>;
+
+ template<typename _Vp>
+ concept __slide_caches_last
+ = !__slide_caches_nothing<_Vp> && bidirectional_range<_Vp> && common_range<_Vp>;
+
+ template<typename _Vp>
+ concept __slide_caches_first
+ = !__slide_caches_nothing<_Vp> && !__slide_caches_last<_Vp>;
+ }
+
+ template<forward_range _Vp>
+ requires view<_Vp>
+ class slide_view : public view_interface<slide_view<_Vp>>
+ {
+ _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<bool> 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<const _Vp>))
+ {
+ 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<false>(ranges::begin(_M_base), std::move(__it), _M_n);
+ }
+ else
+ return _Iterator<false>(ranges::begin(_M_base), _M_n);
+ }
+
+ constexpr auto
+ begin() const requires __detail::__slide_caches_nothing<const _Vp>
+ { return _Iterator<true>(ranges::begin(_M_base), _M_n); }
+
+ constexpr auto
+ end() requires (!(__detail::__simple_view<_Vp>
+ && __detail::__slide_caches_nothing<const _Vp>))
+ {
+ if constexpr (__detail::__slide_caches_nothing<_Vp>)
+ return _Iterator<false>(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<false>(std::move(__it), _M_n);
+ }
+ else if constexpr (common_range<_Vp>)
+ return _Iterator<false>(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<const _Vp>
+ { return begin() + range_difference_t<const _Vp>(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<const _Vp>
+ {
+ auto __sz = ranges::distance(_M_base) - _M_n + 1;
+ if (__sz < 0)
+ __sz = 0;
+ return __detail::__to_unsigned_like(__sz);
+ }
+ };
+
+ template<typename _Range>
+ slide_view(_Range&&, range_difference_t<_Range>) -> slide_view<views::all_t<_Range>>;
+
+ template<typename _Vp>
+ inline constexpr bool enable_borrowed_range<slide_view<_Vp>>
+ = enable_borrowed_range<_Vp>;
+
+ template<forward_range _Vp>
+ requires view<_Vp>
+ template<bool _Const>
+ 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<!_Const> __i)
+ requires _Const && convertible_to<iterator_t<_Vp>, 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<iterator_t<_Base>>
+ { 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>, 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<forward_range _Vp>
+ 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<false>& __x, const _Sentinel& __y)
+ { return __x._M_last_elt == __y._M_end; }
+
+ friend constexpr range_difference_t<_Vp>
+ operator-(const _Iterator<false>& __x, const _Sentinel& __y)
+ requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
+ { return __x._M_last_elt - __y._M_end; }
+
+ friend constexpr range_difference_t<_Vp>
+ operator-(const _Sentinel& __y, const _Iterator<false>& __x)
+ requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
+ { return __y._M_end -__x._M_last_elt; }
+ };
+
+ namespace views
+ {
+ namespace __detail
+ {
+ template<typename _Range, typename _Dp>
+ concept __can_slide_view
+ = requires { slide_view(std::declval<_Range>(), std::declval<_Dp>()); };
+ }
+
+ struct _Slide : __adaptor::_RangeAdaptor<_Slide>
+ {
+ template<viewable_range _Range, typename _Dp = range_difference_t<_Range>>
+ 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;
+ }
+
+ template<forward_range _Vp,
+ indirect_binary_predicate<iterator_t<_Vp>, iterator_t<_Vp>> _Pred>
+ requires view<_Vp> && is_object_v<_Pred>
+ class chunk_by_view : public view_interface<chunk_by_view<_Vp, _Pred>>
+ {
+ _Vp _M_base = _Vp();
+ __detail::__box<_Pred> _M_pred = _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]<typename _Tp>(_Tp&& __x, _Tp&& __y) {
+ return !bool((*_M_pred)(std::forward<_Tp>(__x), std::forward<_Tp>(__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]<typename _Tp>(_Tp&& __x, _Tp&& __y) {
+ return !bool((*_M_pred)(std::forward<_Tp>(__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<typename _Range, typename _Pred>
+ chunk_by_view(_Range&&, _Pred) -> chunk_by_view<views::all_t<_Range>, _Pred>;
+
+ template<forward_range _Vp,
+ indirect_binary_predicate<iterator_t<_Vp>, 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<iterator_t<_Vp>>;
+ 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<typename _Range, typename _Pred>
+ concept __can_chunk_by_view
+ = requires { chunk_by_view(std::declval<_Range>(), std::declval<_Pred>()); };
+ }
+
+ struct _ChunkBy : __adaptor::_RangeAdaptor<_ChunkBy>
+ {
+ template<viewable_range _Range, typename _Pred>
+ 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;
+ }
+
+ namespace __detail
+ {
+ template<typename _Range, typename _Pattern>
+ concept __compatible_joinable_ranges
+ = common_with<range_value_t<_Range>, range_value_t<_Pattern>>
+ && common_reference_with<range_reference_t<_Range>,
+ range_reference_t<_Pattern>>
+ && common_reference_with<range_rvalue_reference_t<_Range>,
+ range_rvalue_reference_t<_Pattern>>;
+
+ template<typename _Range>
+ concept __bidirectional_common = bidirectional_range<_Range> && common_range<_Range>;
+ }
+
+ template<input_range _Vp, forward_range _Pattern>
+ requires view<_Vp> && view<_Pattern>
+ && input_range<range_reference_t<_Vp>>
+ && __detail::__compatible_joinable_ranges<range_reference_t<_Vp>, _Pattern>
+ class join_with_view : public view_interface<join_with_view<_Vp, _Pattern>>
+ {
+ using _InnerRange = range_reference_t<_Vp>;
+
+ _Vp _M_base = _Vp();
+ __detail::__non_propagating_cache<remove_cv_t<_InnerRange>> _M_inner;
+ _Pattern _M_pattern = _Pattern();
+
+ template<bool _Const> using _Base = __detail::__maybe_const_t<_Const, _Vp>;
+ template<bool _Const> using _InnerBase = range_reference_t<_Base<_Const>>;
+ template<bool _Const> using _PatternBase = __detail::__maybe_const_t<_Const, _Pattern>;
+
+ template<bool _Const> using _OuterIter = iterator_t<_Base<_Const>>;
+ template<bool _Const> using _InnerIter = iterator_t<_InnerBase<_Const>>;
+ template<bool _Const> using _PatternIter = iterator_t<_PatternBase<_Const>>;
+
+ template<bool _Const>
+ static constexpr bool _S_ref_is_glvalue = is_reference_v<_InnerBase<_Const>>;
+
+ template<bool _Const>
+ struct __iter_cat
+ { };
+
+ template<bool _Const>
+ 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<common_reference_t<iter_reference_t<_InnerIter>,
+ 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<bool> struct _Iterator;
+ template<bool> 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<input_range _Range>
+ requires constructible_from<_Vp, views::all_t<_Range>>
+ && constructible_from<_Pattern, single_view<range_value_t<_InnerRange>>>
+ 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()
+ {
+ 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)};
+ }
+
+ constexpr auto
+ begin() const
+ requires input_range<const _Vp>
+ && forward_range<const _Pattern>
+ && is_reference_v<range_reference_t<const _Vp>>
+ { return _Iterator<true>{*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 input_range<const _Vp>
+ && forward_range<const _Pattern>
+ && is_reference_v<range_reference_t<const _Vp>>
+ {
+ using _InnerConstRange = range_reference_t<const _Vp>;
+ if constexpr (forward_range<const _Vp>
+ && forward_range<_InnerConstRange>
+ && common_range<const _Vp>
+ && common_range<_InnerConstRange>)
+ return _Iterator<true>{*this, ranges::end(_M_base)};
+ else
+ return _Sentinel<true>{*this};
+ }
+ };
+
+ template<typename _Range, typename _Pattern>
+ join_with_view(_Range&&, _Pattern&&)
+ -> join_with_view<views::all_t<_Range>, views::all_t<_Pattern>>;
+
+ template<input_range _Range>
+ join_with_view(_Range&&, range_value_t<range_reference_t<_Range>>)
+ -> join_with_view<views::all_t<_Range>,
+ single_view<range_value_t<range_reference_t<_Range>>>>;
+
+ template<input_range _Vp, forward_range _Pattern>
+ requires view<_Vp> && view<_Pattern>
+ && input_range<range_reference_t<_Vp>>
+ && __detail::__compatible_joinable_ranges<range_reference_t<_Vp>, _Pattern>
+ template<bool _Const>
+ 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;
+ _OuterIter _M_outer_it = _OuterIter();
+ variant<_PatternIter, _InnerIter> _M_inner_it;
+
+ constexpr
+ _Iterator(_Parent& __parent, iterator_t<_Base> __outer)
+ : _M_parent(std::__addressof(__parent)), _M_outer_it(std::move(__outer))
+ {
+ if (_M_outer_it != ranges::end(_M_parent->_M_base))
+ {
+ auto&& __inner = _M_update_inner(_M_outer_it);
+ _M_inner_it.template emplace<1>(ranges::begin(__inner));
+ _M_satisfy();
+ }
+ }
+
+ constexpr auto&&
+ _M_update_inner(const _OuterIter& __x)
+ {
+ if constexpr (_S_ref_is_glvalue)
+ return *__x;
+ else
+ return _M_parent->_M_inner._M_emplace_deref(__x);
+ }
+
+ constexpr auto&&
+ _M_get_inner(const _OuterIter& __x)
+ {
+ if constexpr (_S_ref_is_glvalue)
+ return *__x;
+ 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_outer_it);
+ _M_inner_it.template emplace<1>(ranges::begin(__inner));
+ }
+ else
+ {
+ auto&& __inner = _M_get_inner(_M_outer_it);
+ if (std::get<1>(_M_inner_it) != ranges::end(__inner))
+ break;
+
+ if (++_M_outer_it == 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<_InnerIter>,
+ iter_value_t<_PatternIter>>;
+ using difference_type = common_type_t<iter_difference_t<_OuterIter>,
+ iter_difference_t<_InnerIter>,
+ iter_difference_t<_PatternIter>>;
+
+ _Iterator() requires default_initializable<_OuterIter> = default;
+
+ constexpr
+ _Iterator(_Iterator<!_Const> __i)
+ requires _Const
+ && convertible_to<iterator_t<_Vp>, _OuterIter>
+ && convertible_to<iterator_t<_InnerRange>, _InnerIter>
+ && convertible_to<iterator_t<_Pattern>, _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 decltype(auto)
+ operator*() const
+ {
+ using reference = common_reference_t<iter_reference_t<_InnerIter>,
+ iter_reference_t<_PatternIter>>;
+ return std::visit([](auto& __it) -> reference { return *__it; }, _M_inner_it);
+ }
+
+ constexpr _Iterator&
+ operator++()
+ {
+ std::visit([](auto& __it){ ++__it; }, _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;
+ }
+ }
+
+ std::visit([](auto& __it){ --__it; }, _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
+ && equality_comparable<_OuterIter> && equality_comparable<_InnerIter>
+ { return __x._M_outer_it == __y._M_outer_it && __x._M_inner_it ==__y._M_inner_it; }
+
+ friend constexpr decltype(auto)
+ iter_move(const _Iterator& __x)
+ {
+ using __rval_ref = common_reference_t<iter_rvalue_reference_t<_InnerIter>,
+ iter_rvalue_reference_t<_PatternIter>>;
+ return std::visit<__rval_ref>(ranges::iter_move, __x._M_inner_it);
+ }
+
+ friend constexpr void
+ iter_swap(const _Iterator& __x, const _Iterator& __y)
+ requires indirectly_swappable<_InnerIter, _PatternIter>
+ { std::visit(ranges::iter_swap, __x._M_inner_it, __y._M_inner_it); }
+ };
+
+ template<input_range _Vp, forward_range _Pattern>
+ requires view<_Vp> && view<_Pattern>
+ && input_range<range_reference_t<_Vp>>
+ && __detail::__compatible_joinable_ranges<range_reference_t<_Vp>, _Pattern>
+ template<bool _Const>
+ 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<!_Const> __s)
+ requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
+ : _M_end(std::move(__s._M_end))
+ { }
+
+ template<bool _OtherConst>
+ requires sentinel_for<sentinel_t<_Base>,
+ iterator_t<__detail::__maybe_const_t<_OtherConst, _Vp>>>
+ friend constexpr bool
+ operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y)
+ { return __x._M_outer_it == __y._M_end; }
+ };
+
+ namespace views
+ {
+ namespace __detail
+ {
+ template<typename _Range, typename _Pattern>
+ concept __can_join_with_view
+ = requires { join_with_view(std::declval<_Range>(), std::declval<_Pattern>()); };
+ } // namespace __detail
+
+ struct _JoinWith : __adaptor::_RangeAdaptor<_JoinWith>
+ {
+ template<viewable_range _Range, typename _Pattern>
+ 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<typename _Pattern>
+ static constexpr bool _S_has_simple_extra_args
+ = _LazySplit::_S_has_simple_extra_args<_Pattern>;
+ };
+
+ inline constexpr _JoinWith join_with;
+ } // namespace views
+#endif // C++23
+} // namespace ranges
+
+ namespace views = ranges::views;
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace