[1/2] libstdc++: Implement ranges::adjacent_view from P2321R2
Commit Message
Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
libstdc++-v3/ChangeLog:
* include/std/ranges (adjacent_view): Define.
(enable_borrowed_range<adjacent_view>): Define.
(__detail::__repeated_tuple): Define.
(adjacent_view::_Iterator): Define.
(adjacent_view::_Sentinel): Define.
(views::__detail::__can_adjacent_view): Define.
(views::_Adjacent): Define.
(views::adjacent): Define.
(views::pairwise): Define.
* testsuite/std/ranges/adaptors/adjacent/1.cc: New test.
---
libstdc++-v3/include/std/ranges | 359 ++++++++++++++++++
.../std/ranges/adaptors/adjacent/1.cc | 110 ++++++
2 files changed, 469 insertions(+)
create mode 100644 libstdc++-v3/testsuite/std/ranges/adaptors/adjacent/1.cc
Comments
On Tue, 30 Aug 2022 at 18:14, Patrick Palka via Libstdc++
<libstdc++@gcc.gnu.org> wrote:
>
> Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
> + 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 (ssize_t __i = _Nm-1; __i >= 0; --__i)
ssize_t is defined by POSIX in <sys/types.h> but isn't in ISO C or
C++. It looks like MinGW defines it to ... something ... sometimes,
but I don't think we can rely on it for non-POSIX targets.
> + template<size_t _Nm>
> + struct _Adjacent : __adaptor::_RangeAdaptorClosure
> + {
> + template<viewable_range _Range>
> + requires (_Nm == 0) || __detail::__can_adjacent_view<_Nm, _Range>
> + [[nodiscard]]
> + constexpr auto
> + operator()(_Range&& __r) const
Does this attribute actually work here?
I thought we needed to use `operator() [[nodiscard]]` for functions
with a requires-clause, because otherwise the attribute gives a parse
error. Maybe I've misremembered the problem, and it just doesn't give
a -Wunused-result warning. The decl above is setting off my spidey
sense for some reason though.
On Wed, 31 Aug 2022, Jonathan Wakely wrote:
> On Tue, 30 Aug 2022 at 18:14, Patrick Palka via Libstdc++
> <libstdc++@gcc.gnu.org> wrote:
> >
> > Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
>
>
> > + 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 (ssize_t __i = _Nm-1; __i >= 0; --__i)
>
> ssize_t is defined by POSIX in <sys/types.h> but isn't in ISO C or
> C++. It looks like MinGW defines it to ... something ... sometimes,
> but I don't think we can rely on it for non-POSIX targets.
I see. Using ssize_t makes the loop a little cleaner but it's hardly
necessary, so consider it rewritten into:
for (size_t __i = 0; __i < _Nm; ++__i)
{
_M_current[_Nm - 1 - __i] = __last;
ranges::advance(__last, -1, __first);
}
>
>
> > + template<size_t _Nm>
> > + struct _Adjacent : __adaptor::_RangeAdaptorClosure
> > + {
> > + template<viewable_range _Range>
> > + requires (_Nm == 0) || __detail::__can_adjacent_view<_Nm, _Range>
> > + [[nodiscard]]
> > + constexpr auto
> > + operator()(_Range&& __r) const
>
> Does this attribute actually work here?
>
> I thought we needed to use `operator() [[nodiscard]]` for functions
> with a requires-clause, because otherwise the attribute gives a parse
> error. Maybe I've misremembered the problem, and it just doesn't give
> a -Wunused-result warning. The decl above is setting off my spidey
> sense for some reason though.
Oops yeah, it looks like this position of [[nodiscard]] works with
standard concepts, but it's a parse error with -fconcepts-ts due to the
different requires-clause grammar.
Here's v2 which avoids using ssize_t, and puts the [[nodiscard]] after
'operator()' (_Zip and _ZipTransform have the same issue which I can
fix separately):
-- >8 --
libstdc++-v3/ChangeLog:
* include/std/ranges (adjacent_view): Define.
(enable_borrowed_range<adjacent_view>): Define.
(__detail::__repeated_tuple): Define.
(adjacent_view::_Iterator): Define.
(adjacent_view::_Sentinel): Define.
(views::__detail::__can_adjacent_view): Define.
(views::_Adjacent): Define.
(views::adjacent): Define.
(views::pairwise): Define.
* testsuite/std/ranges/adaptors/adjacent/1.cc: New test.
---
libstdc++-v3/include/std/ranges | 358 ++++++++++++++++++
.../std/ranges/adaptors/adjacent/1.cc | 110 ++++++
2 files changed, 468 insertions(+)
create mode 100644 libstdc++-v3/testsuite/std/ranges/adaptors/adjacent/1.cc
diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index 6e2e561ed12..2352aad76fc 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -5081,6 +5081,364 @@ namespace views::__adaptor
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>>()));
+ }
+
+ 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;
+
+ 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[__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>;
+ }
#endif // C++23
} // namespace ranges
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/adjacent/1.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/adjacent/1.cc
new file mode 100644
index 00000000000..9829f79364f
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/adjacent/1.cc
@@ -0,0 +1,110 @@
+// { dg-options "-std=gnu++23" }
+// { dg-do run { target c++23 } }
+
+#include <ranges>
+#include <algorithm>
+#include <utility>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+namespace ranges = std::ranges;
+namespace views = std::views;
+
+constexpr bool
+test01()
+{
+ static_assert(ranges::empty(std::array{1, 2, 3} | views::adjacent<0>));
+
+ auto v1 = std::array{1, 2} | views::adjacent<1>;
+ const auto i0 = v1.begin(), i1 = v1.begin() + 1;
+ VERIFY( i0 + 1 - 1 == i0 );
+ VERIFY( i0 < i1 );
+ VERIFY( i1 < v1.end() );
+ VERIFY( i1 - i0 == 1 );
+ VERIFY( i0 - i1 == -1 );
+ VERIFY( v1.end() - i1 == 1 );
+ VERIFY( i1 - v1.end() == -1 );
+ ranges::iter_swap(i0, i1);
+ VERIFY( ranges::equal(std::move(v1) | views::keys, (int[]){2, 1}) );
+
+ int x[] = {1, 2, 3, 4};
+ auto v2 = x | views::pairwise;
+ auto i2 = v2.begin();
+ i2 += 2;
+ i2 -= -1;
+ VERIFY( i2 == v2.end() );
+ VERIFY( ranges::size(v2) == 3 );
+ VERIFY( ranges::size(std::as_const(v2)) == 3 );
+ VERIFY( ranges::equal(v2 | views::keys, (int[]){1, 2, 3}) );
+ VERIFY( ranges::equal(v2 | views::values, (int[]){2, 3, 4}) );
+
+ int y[] = {1, 2, 3, 4, 5};
+ const auto v3 = y | views::adjacent<3>;
+ VERIFY( ranges::size(v3) == 3 );
+ for (unsigned i = 0; i < ranges::size(x); i++)
+ {
+ VERIFY( &std::get<0>(v3[i]) == &y[i] + 0 );
+ VERIFY( &std::get<1>(v3[i]) == &y[i] + 1 );
+ VERIFY( &std::get<2>(v3[i]) == &y[i] + 2 );
+ }
+
+ const auto v5 = y | views::adjacent<5>;
+ VERIFY( ranges::equal(v5, views::single(std::make_tuple(1, 2, 3, 4, 5))) );
+
+ const auto v6 = y | views::adjacent<6>;
+ VERIFY( ranges::empty(v6) );
+
+ const auto v0 = y | views::adjacent<0>;
+ VERIFY( ranges::empty(v0) );
+
+ return true;
+}
+
+constexpr bool
+test02()
+{
+ using __gnu_test::test_input_range;
+ using __gnu_test::test_forward_range;
+ using __gnu_test::test_random_access_range;
+
+ using ty1 = ranges::adjacent_view<views::all_t<test_forward_range<int>>, 2>;
+ static_assert(ranges::forward_range<ty1>);
+ static_assert(!ranges::bidirectional_range<ty1>);
+ static_assert(!ranges::sized_range<ty1>);
+
+ using ty2 = ranges::adjacent_view<views::all_t<test_random_access_range<int>>, 3>;
+ static_assert(ranges::random_access_range<ty2>);
+ static_assert(ranges::sized_range<ty2>);
+
+ return true;
+}
+
+constexpr bool
+test03()
+{
+ auto v = views::iota(0, 4) | views::filter([](auto) { return true; }) | views::pairwise;
+ using ty = decltype(v);
+ static_assert(ranges::forward_range<ty>);
+ static_assert(ranges::common_range<ty>);
+ static_assert(!ranges::sized_range<ty>);
+ VERIFY( v.begin() == v.begin() );
+ VERIFY( v.begin() != v.end() );
+ VERIFY( ranges::next(v.begin(), 3) == v.end() );
+ auto it = v.begin();
+ ++it;
+ it++;
+ VERIFY( ranges::next(it) == v.end() );
+ it--;
+ --it;
+ VERIFY( it == v.begin() );
+
+ return true;
+}
+
+int
+main()
+{
+ static_assert(test01());
+ static_assert(test02());
+ static_assert(test03());
+}
On Wed, 31 Aug 2022 at 14:30, Patrick Palka <ppalka@redhat.com> wrote:
>
> On Wed, 31 Aug 2022, Jonathan Wakely wrote:
>
> > On Tue, 30 Aug 2022 at 18:14, Patrick Palka via Libstdc++
> > <libstdc++@gcc.gnu.org> wrote:
> > >
> > > Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
> >
> >
> > > + 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 (ssize_t __i = _Nm-1; __i >= 0; --__i)
> >
> > ssize_t is defined by POSIX in <sys/types.h> but isn't in ISO C or
> > C++. It looks like MinGW defines it to ... something ... sometimes,
> > but I don't think we can rely on it for non-POSIX targets.
>
> I see. Using ssize_t makes the loop a little cleaner but it's hardly
> necessary, so consider it rewritten into:
>
> for (size_t __i = 0; __i < _Nm; ++__i)
> {
> _M_current[_Nm - 1 - __i] = __last;
> ranges::advance(__last, -1, __first);
> }
>
> >
> >
> > > + template<size_t _Nm>
> > > + struct _Adjacent : __adaptor::_RangeAdaptorClosure
> > > + {
> > > + template<viewable_range _Range>
> > > + requires (_Nm == 0) || __detail::__can_adjacent_view<_Nm, _Range>
> > > + [[nodiscard]]
> > > + constexpr auto
> > > + operator()(_Range&& __r) const
> >
> > Does this attribute actually work here?
> >
> > I thought we needed to use `operator() [[nodiscard]]` for functions
> > with a requires-clause, because otherwise the attribute gives a parse
> > error. Maybe I've misremembered the problem, and it just doesn't give
> > a -Wunused-result warning. The decl above is setting off my spidey
> > sense for some reason though.
>
> Oops yeah, it looks like this position of [[nodiscard]] works with
> standard concepts, but it's a parse error with -fconcepts-ts due to the
> different requires-clause grammar.
>
> Here's v2 which avoids using ssize_t, and puts the [[nodiscard]] after
> 'operator()' (_Zip and _ZipTransform have the same issue which I can
> fix separately):
OK for trunk with those changes, thanks.
@@ -5081,6 +5081,365 @@ namespace views::__adaptor
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>>()));
+ }
+
+ 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 (ssize_t __i = _Nm-1; __i >= 0; --__i)
+ {
+ _M_current[__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;
+
+ 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[__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>
+ [[nodiscard]]
+ constexpr auto
+ operator()(_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>;
+ }
#endif // C++23
} // namespace ranges
new file mode 100644
@@ -0,0 +1,110 @@
+// { dg-options "-std=gnu++23" }
+// { dg-do run { target c++23 } }
+
+#include <ranges>
+#include <algorithm>
+#include <utility>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+namespace ranges = std::ranges;
+namespace views = std::views;
+
+constexpr bool
+test01()
+{
+ static_assert(ranges::empty(std::array{1, 2, 3} | views::adjacent<0>));
+
+ auto v1 = std::array{1, 2} | views::adjacent<1>;
+ const auto i0 = v1.begin(), i1 = v1.begin() + 1;
+ VERIFY( i0 + 1 - 1 == i0 );
+ VERIFY( i0 < i1 );
+ VERIFY( i1 < v1.end() );
+ VERIFY( i1 - i0 == 1 );
+ VERIFY( i0 - i1 == -1 );
+ VERIFY( v1.end() - i1 == 1 );
+ VERIFY( i1 - v1.end() == -1 );
+ ranges::iter_swap(i0, i1);
+ VERIFY( ranges::equal(std::move(v1) | views::keys, (int[]){2, 1}) );
+
+ int x[] = {1, 2, 3, 4};
+ auto v2 = x | views::pairwise;
+ auto i2 = v2.begin();
+ i2 += 2;
+ i2 -= -1;
+ VERIFY( i2 == v2.end() );
+ VERIFY( ranges::size(v2) == 3 );
+ VERIFY( ranges::size(std::as_const(v2)) == 3 );
+ VERIFY( ranges::equal(v2 | views::keys, (int[]){1, 2, 3}) );
+ VERIFY( ranges::equal(v2 | views::values, (int[]){2, 3, 4}) );
+
+ int y[] = {1, 2, 3, 4, 5};
+ const auto v3 = y | views::adjacent<3>;
+ VERIFY( ranges::size(v3) == 3 );
+ for (unsigned i = 0; i < ranges::size(x); i++)
+ {
+ VERIFY( &std::get<0>(v3[i]) == &y[i] + 0 );
+ VERIFY( &std::get<1>(v3[i]) == &y[i] + 1 );
+ VERIFY( &std::get<2>(v3[i]) == &y[i] + 2 );
+ }
+
+ const auto v5 = y | views::adjacent<5>;
+ VERIFY( ranges::equal(v5, views::single(std::make_tuple(1, 2, 3, 4, 5))) );
+
+ const auto v6 = y | views::adjacent<6>;
+ VERIFY( ranges::empty(v6) );
+
+ const auto v0 = y | views::adjacent<0>;
+ VERIFY( ranges::empty(v0) );
+
+ return true;
+}
+
+constexpr bool
+test02()
+{
+ using __gnu_test::test_input_range;
+ using __gnu_test::test_forward_range;
+ using __gnu_test::test_random_access_range;
+
+ using ty1 = ranges::adjacent_view<views::all_t<test_forward_range<int>>, 2>;
+ static_assert(ranges::forward_range<ty1>);
+ static_assert(!ranges::bidirectional_range<ty1>);
+ static_assert(!ranges::sized_range<ty1>);
+
+ using ty2 = ranges::adjacent_view<views::all_t<test_random_access_range<int>>, 3>;
+ static_assert(ranges::random_access_range<ty2>);
+ static_assert(ranges::sized_range<ty2>);
+
+ return true;
+}
+
+constexpr bool
+test03()
+{
+ auto v = views::iota(0, 4) | views::filter([](auto) { return true; }) | views::pairwise;
+ using ty = decltype(v);
+ static_assert(ranges::forward_range<ty>);
+ static_assert(ranges::common_range<ty>);
+ static_assert(!ranges::sized_range<ty>);
+ VERIFY( v.begin() == v.begin() );
+ VERIFY( v.begin() != v.end() );
+ VERIFY( ranges::next(v.begin(), 3) == v.end() );
+ auto it = v.begin();
+ ++it;
+ it++;
+ VERIFY( ranges::next(it) == v.end() );
+ it--;
+ --it;
+ VERIFY( it == v.begin() );
+
+ return true;
+}
+
+int
+main()
+{
+ static_assert(test01());
+ static_assert(test02());
+ static_assert(test03());
+}