* [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 @ 2022-11-14 4:50 Patrick Palka 2022-11-14 4:50 ` [PATCH 2/3] libstdc++: Implement ranges::iota from P2440R1 Patrick Palka ` (2 more replies) 0 siblings, 3 replies; 12+ messages in thread From: Patrick Palka @ 2022-11-14 4:50 UTC (permalink / raw) To: gcc-patches; +Cc: libstdc++, Patrick Palka Tested on x86_64-pc-linux-gnu, does this look OK for trunk? libstdc++-v3/ChangeLog: * include/bits/ranges_algo.h (__contains_fn, contains): Define. (__contains_subrange_fn, contains_subrange): Define. * testsuite/25_algorithms/contains/1.cc: New test. * testsuite/25_algorithms/contains_subrange/1.cc: New test. --- libstdc++-v3/include/bits/ranges_algo.h | 54 +++++++++++++++++++ .../testsuite/25_algorithms/contains/1.cc | 33 ++++++++++++ .../25_algorithms/contains_subrange/1.cc | 35 ++++++++++++ 3 files changed, 122 insertions(+) create mode 100644 libstdc++-v3/testsuite/25_algorithms/contains/1.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index de71bd07a2f..da0ca981dc3 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -3464,6 +3464,60 @@ namespace ranges inline constexpr __prev_permutation_fn prev_permutation{}; +#if __cplusplus > 202002L + struct __contains_fn + { + template<input_iterator _Iter, sentinel_for<_Iter> _Sent, + typename _Tp, typename _Proj = identity> + requires indirect_binary_predicate<ranges::equal_to, + projected<_Iter, _Proj>, const _Tp*> + constexpr bool + operator()(_Iter __first, _Sent __last, const _Tp& __value, _Proj __proj = {}) const + { return ranges::find(std::move(__first), __last, __value, __proj) != __last; } + + template<input_range _Range, typename _Tp, typename _Proj = identity> + requires indirect_binary_predicate<ranges::equal_to, + projected<iterator_t<_Range>, _Proj>, const _Tp*> + constexpr bool + operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const + { return (*this)(ranges::begin(__r), ranges::end(__r), __value, std::move(__proj)); } + }; + + inline constexpr __contains_fn contains{}; + + struct __contains_subrange_fn + { + template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1, + forward_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 bool + operator()(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, Proj1 __proj1 = {}, Proj2 __proj2 = {}) const + { + return __first2 == __last2 + || !ranges::search(__first1, __last1, __first2, __last2, + std::move(__pred), std::move(__proj1), std::move(__proj2)).empty(); + } + + template<forward_range _Range1, forward_range _Range2, + typename _Pred = ranges::equal_to, + typename _Proj1 = identity, typename _Proj2 = identity> + requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, + _Pred, _Proj1, _Proj2> + constexpr bool + operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const + { + return (*this)(ranges::begin(__r1), ranges::end(__r1), + ranges::begin(__r2), ranges::end(__r2), + std::move(__pred), std::move(__proj1), std::move(__proj2)); + } + }; + + inline constexpr __contains_subrange_fn contains_subrange{}; +#endif // C++23 } // namespace ranges #define __cpp_lib_shift 201806L diff --git a/libstdc++-v3/testsuite/25_algorithms/contains/1.cc b/libstdc++-v3/testsuite/25_algorithms/contains/1.cc new file mode 100644 index 00000000000..146ab593b70 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/contains/1.cc @@ -0,0 +1,33 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; + +void +test01() +{ + int x[] = {1,2,3}; + using to_input = __gnu_test::test_input_range<int>; + VERIFY( ranges::contains(to_input(x), 1) ); + VERIFY( ranges::contains(to_input(x), 2) ); + VERIFY( ranges::contains(to_input(x), 3) ); + VERIFY( !ranges::contains(to_input(x), 4) ); + VERIFY( !ranges::contains(x, x+2, 3) ); + auto neg = [](int n) { return -n; }; + VERIFY( ranges::contains(to_input(x), -1, neg) ); + VERIFY( ranges::contains(to_input(x), -2, neg) ); + VERIFY( ranges::contains(to_input(x), -3, neg) ); + VERIFY( !ranges::contains(to_input(x), -4, neg) ); + + VERIFY( !ranges::contains(x, x+2, -3, neg) ); +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc b/libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc new file mode 100644 index 00000000000..62b92795f94 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc @@ -0,0 +1,35 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; + +void +test01() +{ + int x[] = {1,2,3,4,5}; + int y[] = {2,3,4}; + int z[] = {4,5,6}; + __gnu_test::test_forward_range<int> rx(x); + __gnu_test::test_forward_range<int> ry(y); + __gnu_test::test_forward_range<int> rz(z); + VERIFY( ranges::contains_subrange(rx, ry) ); + VERIFY( !ranges::contains_subrange(rx, rz) ); + VERIFY( ranges::contains_subrange(rx, ry, ranges::less{}) ); + VERIFY( ranges::contains_subrange(rx, rz, ranges::less{}) ); + auto plus3 = [](int n) { return n+3; }; + VERIFY( !ranges::contains_subrange(rx, ry, ranges::equal_to{}, plus3) ); + VERIFY( ranges::contains_subrange(rx, rz, ranges::equal_to{}, plus3) ); + + VERIFY( ranges::contains_subrange(x, x+2, y, y+1) ); + VERIFY( !ranges::contains_subrange(x, x+2, y, y+2) ); +} + +int +main() +{ + test01(); +} -- 2.38.1.420.g319605f8f0 ^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH 2/3] libstdc++: Implement ranges::iota from P2440R1 2022-11-14 4:50 [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 Patrick Palka @ 2022-11-14 4:50 ` Patrick Palka 2022-11-14 10:08 ` Jonathan Wakely 2022-11-14 4:50 ` [PATCH 3/3] libstdc++: Implement ranges::find_last{,_if,_if_not} from P1223R5 Patrick Palka 2022-11-14 9:04 ` [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 Jonathan Wakely 2 siblings, 1 reply; 12+ messages in thread From: Patrick Palka @ 2022-11-14 4:50 UTC (permalink / raw) To: gcc-patches; +Cc: libstdc++, Patrick Palka Tested on x86_64-pc-linux-gnu, does this look OK for trunk? libstdc++-v3/ChangeLog: * include/bits/ranges_algo.h (out_value_result): Define. (iota_result): Define. (__iota_fn, iota): Define. * testsuite/25_algorithms/iota/1.cc: New test. --- libstdc++-v3/include/bits/ranges_algo.h | 48 +++++++++++++++++++ .../testsuite/25_algorithms/iota/1.cc | 29 +++++++++++ 2 files changed, 77 insertions(+) create mode 100644 libstdc++-v3/testsuite/25_algorithms/iota/1.cc diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index da0ca981dc3..f003117c569 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -3517,6 +3517,54 @@ namespace ranges }; inline constexpr __contains_subrange_fn contains_subrange{}; + + template<typename _Out, typename _Tp> + struct out_value_result + { + [[no_unique_address]] _Out out; + [[no_unique_address]] _Tp value; + + template<typename _Out2, typename _Tp2> + requires convertible_to<const _Out&, _Out2> + && convertible_to<const _Tp&, _Tp2> + constexpr + operator out_value_result<_Out2, _Tp2>() const & + { return {out, value}; } + + template<typename _Out2, typename _Tp2> + requires convertible_to<_Out, _Out2> + && convertible_to<_Tp, _Tp2> + constexpr + operator out_value_result<_Out2, _Tp2>() && + { return {std::move(out), std::move(value)}; } + }; + + template<typename _Out, typename _Tp> + using iota_result = out_value_result<_Out, _Tp>; + + struct __iota_fn + { + template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent, weakly_incrementable _Tp> + requires indirectly_writable<_Out, const _Tp&> + constexpr iota_result<_Out, _Tp> + operator()(_Out __first, _Sent __last, _Tp __value) const + { + while (__first != __last) + { + *__first = static_cast<add_const_t<_Tp>&>(__value); + ++__first; + ++__value; + } + return {std::move(__first), std::move(__value)}; + } + + template<weakly_incrementable _Tp, output_range<const _Tp&> _Range> + constexpr iota_result<borrowed_iterator_t<_Range>, _Tp> + operator()(_Range&& __r, _Tp __value) const + { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__value)); } + }; + + inline constexpr __iota_fn iota{}; #endif // C++23 } // namespace ranges diff --git a/libstdc++-v3/testsuite/25_algorithms/iota/1.cc b/libstdc++-v3/testsuite/25_algorithms/iota/1.cc new file mode 100644 index 00000000000..ad2bf08adf5 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/iota/1.cc @@ -0,0 +1,29 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; + +void +test01() +{ + int x[3] = {}; + __gnu_test::test_output_range<int> rx(x); + auto r0 = ranges::iota(rx, 0); + VERIFY( r0.out.ptr == x+3 ); + VERIFY( r0.value == 3 ); + VERIFY( ranges::equal(x, (int[]){0,1,2}) ); + auto r1 = ranges::iota(x, x+2, 5); + VERIFY( r1.out == x+2 ); + VERIFY( r1.value == 7 ); + VERIFY( ranges::equal(x, (int[]){5,6,2}) ); +} + +int +main() +{ + test01(); +} -- 2.38.1.420.g319605f8f0 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2/3] libstdc++: Implement ranges::iota from P2440R1 2022-11-14 4:50 ` [PATCH 2/3] libstdc++: Implement ranges::iota from P2440R1 Patrick Palka @ 2022-11-14 10:08 ` Jonathan Wakely 2022-11-14 10:17 ` Daniel Krügler 0 siblings, 1 reply; 12+ messages in thread From: Jonathan Wakely @ 2022-11-14 10:08 UTC (permalink / raw) To: Patrick Palka; +Cc: gcc-patches, libstdc++ On Mon, 14 Nov 2022 at 04:52, Patrick Palka via Libstdc++ <libstdc++@gcc.gnu.org> wrote: > > Tested on x86_64-pc-linux-gnu, does this look OK for trunk? > > libstdc++-v3/ChangeLog: > > * include/bits/ranges_algo.h (out_value_result): Define. > (iota_result): Define. > (__iota_fn, iota): Define. > * testsuite/25_algorithms/iota/1.cc: New test. > --- > libstdc++-v3/include/bits/ranges_algo.h | 48 +++++++++++++++++++ > .../testsuite/25_algorithms/iota/1.cc | 29 +++++++++++ > 2 files changed, 77 insertions(+) > create mode 100644 libstdc++-v3/testsuite/25_algorithms/iota/1.cc > > diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h > index da0ca981dc3..f003117c569 100644 > --- a/libstdc++-v3/include/bits/ranges_algo.h > +++ b/libstdc++-v3/include/bits/ranges_algo.h > @@ -3517,6 +3517,54 @@ namespace ranges > }; > > inline constexpr __contains_subrange_fn contains_subrange{}; > + > + template<typename _Out, typename _Tp> > + struct out_value_result > + { > + [[no_unique_address]] _Out out; > + [[no_unique_address]] _Tp value; > + > + template<typename _Out2, typename _Tp2> > + requires convertible_to<const _Out&, _Out2> > + && convertible_to<const _Tp&, _Tp2> > + constexpr > + operator out_value_result<_Out2, _Tp2>() const & > + { return {out, value}; } > + > + template<typename _Out2, typename _Tp2> > + requires convertible_to<_Out, _Out2> > + && convertible_to<_Tp, _Tp2> > + constexpr > + operator out_value_result<_Out2, _Tp2>() && > + { return {std::move(out), std::move(value)}; } > + }; > + > + template<typename _Out, typename _Tp> > + using iota_result = out_value_result<_Out, _Tp>; > + > + struct __iota_fn > + { > + template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent, weakly_incrementable _Tp> > + requires indirectly_writable<_Out, const _Tp&> > + constexpr iota_result<_Out, _Tp> > + operator()(_Out __first, _Sent __last, _Tp __value) const > + { > + while (__first != __last) > + { > + *__first = static_cast<add_const_t<_Tp>&>(__value); Is this any different to const_cast<const _Tp&>(__value) ? We know _Tp must be the same as decay_t<_Tp> and non-void, because it's passed by value, and therefore I think is_same_v<const _Tp, add_const_t<_Tp>> is always true, isn't it? We don't need to care about people saying ranges::iota.operator()<O,S,T&>(o,s,t), those people are animals. We would just change the function parameter to const _Tp which would mean that *_first = __value; always uses a const lvalue, but maybe that's a bit too subtle. The cast makes it more explicit what's happening, especially the const_cast version. > + ++__first; > + ++__value; > + } > + return {std::move(__first), std::move(__value)}; > + } > + > + template<weakly_incrementable _Tp, output_range<const _Tp&> _Range> > + constexpr iota_result<borrowed_iterator_t<_Range>, _Tp> > + operator()(_Range&& __r, _Tp __value) const > + { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__value)); } > + }; > + > + inline constexpr __iota_fn iota{}; > #endif // C++23 > } // namespace ranges > > diff --git a/libstdc++-v3/testsuite/25_algorithms/iota/1.cc b/libstdc++-v3/testsuite/25_algorithms/iota/1.cc > new file mode 100644 > index 00000000000..ad2bf08adf5 > --- /dev/null > +++ b/libstdc++-v3/testsuite/25_algorithms/iota/1.cc > @@ -0,0 +1,29 @@ > +// { dg-options "-std=gnu++23" } > +// { dg-do run { target c++23 } } > + > +#include <algorithm> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > + > +namespace ranges = std::ranges; > + > +void > +test01() > +{ > + int x[3] = {}; > + __gnu_test::test_output_range<int> rx(x); > + auto r0 = ranges::iota(rx, 0); > + VERIFY( r0.out.ptr == x+3 ); > + VERIFY( r0.value == 3 ); > + VERIFY( ranges::equal(x, (int[]){0,1,2}) ); > + auto r1 = ranges::iota(x, x+2, 5); > + VERIFY( r1.out == x+2 ); > + VERIFY( r1.value == 7 ); > + VERIFY( ranges::equal(x, (int[]){5,6,2}) ); > +} > + > +int > +main() > +{ > + test01(); > +} > -- > 2.38.1.420.g319605f8f0 > ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2/3] libstdc++: Implement ranges::iota from P2440R1 2022-11-14 10:08 ` Jonathan Wakely @ 2022-11-14 10:17 ` Daniel Krügler 2022-11-14 10:20 ` Jonathan Wakely 0 siblings, 1 reply; 12+ messages in thread From: Daniel Krügler @ 2022-11-14 10:17 UTC (permalink / raw) To: Jonathan Wakely; +Cc: Patrick Palka, gcc-patches, libstdc++ Am Mo., 14. Nov. 2022 um 11:09 Uhr schrieb Jonathan Wakely via Libstdc++ <libstdc++@gcc.gnu.org>: > > On Mon, 14 Nov 2022 at 04:52, Patrick Palka via Libstdc++ > <libstdc++@gcc.gnu.org> wrote: > > > > Tested on x86_64-pc-linux-gnu, does this look OK for trunk? > > > > libstdc++-v3/ChangeLog: > > > > * include/bits/ranges_algo.h (out_value_result): Define. > > (iota_result): Define. > > (__iota_fn, iota): Define. > > * testsuite/25_algorithms/iota/1.cc: New test. > > --- > > libstdc++-v3/include/bits/ranges_algo.h | 48 +++++++++++++++++++ > > .../testsuite/25_algorithms/iota/1.cc | 29 +++++++++++ > > 2 files changed, 77 insertions(+) > > create mode 100644 libstdc++-v3/testsuite/25_algorithms/iota/1.cc > > > > diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h > > index da0ca981dc3..f003117c569 100644 > > --- a/libstdc++-v3/include/bits/ranges_algo.h > > +++ b/libstdc++-v3/include/bits/ranges_algo.h > > @@ -3517,6 +3517,54 @@ namespace ranges > > }; > > > > inline constexpr __contains_subrange_fn contains_subrange{}; > > + > > + template<typename _Out, typename _Tp> > > + struct out_value_result > > + { > > + [[no_unique_address]] _Out out; > > + [[no_unique_address]] _Tp value; > > + > > + template<typename _Out2, typename _Tp2> > > + requires convertible_to<const _Out&, _Out2> > > + && convertible_to<const _Tp&, _Tp2> > > + constexpr > > + operator out_value_result<_Out2, _Tp2>() const & > > + { return {out, value}; } > > + > > + template<typename _Out2, typename _Tp2> > > + requires convertible_to<_Out, _Out2> > > + && convertible_to<_Tp, _Tp2> > > + constexpr > > + operator out_value_result<_Out2, _Tp2>() && > > + { return {std::move(out), std::move(value)}; } > > + }; > > + > > + template<typename _Out, typename _Tp> > > + using iota_result = out_value_result<_Out, _Tp>; > > + > > + struct __iota_fn > > + { > > + template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent, weakly_incrementable _Tp> > > + requires indirectly_writable<_Out, const _Tp&> > > + constexpr iota_result<_Out, _Tp> > > + operator()(_Out __first, _Sent __last, _Tp __value) const > > + { > > + while (__first != __last) > > + { > > + *__first = static_cast<add_const_t<_Tp>&>(__value); > > Is this any different to const_cast<const _Tp&>(__value) ? I think it is. const_cast<const _Tp&> can potentially mean the removal of volatile, so I would always look with suspicion on const_cast<const _Tp&>, while static_cast is clearer. Alternatively, as_const could be used, which does add_const_t. - Daniel ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2/3] libstdc++: Implement ranges::iota from P2440R1 2022-11-14 10:17 ` Daniel Krügler @ 2022-11-14 10:20 ` Jonathan Wakely 2022-11-14 15:11 ` Patrick Palka 0 siblings, 1 reply; 12+ messages in thread From: Jonathan Wakely @ 2022-11-14 10:20 UTC (permalink / raw) To: Daniel Krügler; +Cc: Patrick Palka, gcc-patches, libstdc++ On Mon, 14 Nov 2022 at 10:17, Daniel Krügler <daniel.kruegler@gmail.com> wrote: > > Am Mo., 14. Nov. 2022 um 11:09 Uhr schrieb Jonathan Wakely via > Libstdc++ <libstdc++@gcc.gnu.org>: > > > > On Mon, 14 Nov 2022 at 04:52, Patrick Palka via Libstdc++ > > <libstdc++@gcc.gnu.org> wrote: > > > > > > Tested on x86_64-pc-linux-gnu, does this look OK for trunk? > > > > > > libstdc++-v3/ChangeLog: > > > > > > * include/bits/ranges_algo.h (out_value_result): Define. > > > (iota_result): Define. > > > (__iota_fn, iota): Define. > > > * testsuite/25_algorithms/iota/1.cc: New test. > > > --- > > > libstdc++-v3/include/bits/ranges_algo.h | 48 +++++++++++++++++++ > > > .../testsuite/25_algorithms/iota/1.cc | 29 +++++++++++ > > > 2 files changed, 77 insertions(+) > > > create mode 100644 libstdc++-v3/testsuite/25_algorithms/iota/1.cc > > > > > > diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h > > > index da0ca981dc3..f003117c569 100644 > > > --- a/libstdc++-v3/include/bits/ranges_algo.h > > > +++ b/libstdc++-v3/include/bits/ranges_algo.h > > > @@ -3517,6 +3517,54 @@ namespace ranges > > > }; > > > > > > inline constexpr __contains_subrange_fn contains_subrange{}; > > > + > > > + template<typename _Out, typename _Tp> > > > + struct out_value_result > > > + { > > > + [[no_unique_address]] _Out out; > > > + [[no_unique_address]] _Tp value; > > > + > > > + template<typename _Out2, typename _Tp2> > > > + requires convertible_to<const _Out&, _Out2> > > > + && convertible_to<const _Tp&, _Tp2> > > > + constexpr > > > + operator out_value_result<_Out2, _Tp2>() const & > > > + { return {out, value}; } > > > + > > > + template<typename _Out2, typename _Tp2> > > > + requires convertible_to<_Out, _Out2> > > > + && convertible_to<_Tp, _Tp2> > > > + constexpr > > > + operator out_value_result<_Out2, _Tp2>() && > > > + { return {std::move(out), std::move(value)}; } > > > + }; > > > + > > > + template<typename _Out, typename _Tp> > > > + using iota_result = out_value_result<_Out, _Tp>; > > > + > > > + struct __iota_fn > > > + { > > > + template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent, weakly_incrementable _Tp> > > > + requires indirectly_writable<_Out, const _Tp&> > > > + constexpr iota_result<_Out, _Tp> > > > + operator()(_Out __first, _Sent __last, _Tp __value) const > > > + { > > > + while (__first != __last) > > > + { > > > + *__first = static_cast<add_const_t<_Tp>&>(__value); > > > > Is this any different to const_cast<const _Tp&>(__value) ? > > I think it is. const_cast<const _Tp&> can potentially mean the removal > of volatile, True. > so I would always look with suspicion on const_cast<const > _Tp&>, while static_cast is clearer. Alternatively, as_const could be > used, which does add_const_t. Which means evaluating the add_const trait *and* overload resolution for as_const* *and* a runtime function call. Let's go with static_cast<const _Tp&>. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2/3] libstdc++: Implement ranges::iota from P2440R1 2022-11-14 10:20 ` Jonathan Wakely @ 2022-11-14 15:11 ` Patrick Palka 2022-11-14 15:12 ` Jonathan Wakely 0 siblings, 1 reply; 12+ messages in thread From: Patrick Palka @ 2022-11-14 15:11 UTC (permalink / raw) To: Jonathan Wakely Cc: Daniel Krügler, Patrick Palka, gcc-patches, libstdc++ [-- Attachment #1: Type: text/plain, Size: 6639 bytes --] On Mon, 14 Nov 2022, Jonathan Wakely wrote: > On Mon, 14 Nov 2022 at 10:17, Daniel Krügler <daniel.kruegler@gmail.com> wrote: > > > > Am Mo., 14. Nov. 2022 um 11:09 Uhr schrieb Jonathan Wakely via > > Libstdc++ <libstdc++@gcc.gnu.org>: > > > > > > On Mon, 14 Nov 2022 at 04:52, Patrick Palka via Libstdc++ > > > <libstdc++@gcc.gnu.org> wrote: > > > > > > > > Tested on x86_64-pc-linux-gnu, does this look OK for trunk? > > > > > > > > libstdc++-v3/ChangeLog: > > > > > > > > * include/bits/ranges_algo.h (out_value_result): Define. > > > > (iota_result): Define. > > > > (__iota_fn, iota): Define. > > > > * testsuite/25_algorithms/iota/1.cc: New test. > > > > --- > > > > libstdc++-v3/include/bits/ranges_algo.h | 48 +++++++++++++++++++ > > > > .../testsuite/25_algorithms/iota/1.cc | 29 +++++++++++ > > > > 2 files changed, 77 insertions(+) > > > > create mode 100644 libstdc++-v3/testsuite/25_algorithms/iota/1.cc > > > > > > > > diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h > > > > index da0ca981dc3..f003117c569 100644 > > > > --- a/libstdc++-v3/include/bits/ranges_algo.h > > > > +++ b/libstdc++-v3/include/bits/ranges_algo.h > > > > @@ -3517,6 +3517,54 @@ namespace ranges > > > > }; > > > > > > > > inline constexpr __contains_subrange_fn contains_subrange{}; > > > > + > > > > + template<typename _Out, typename _Tp> > > > > + struct out_value_result > > > > + { > > > > + [[no_unique_address]] _Out out; > > > > + [[no_unique_address]] _Tp value; > > > > + > > > > + template<typename _Out2, typename _Tp2> > > > > + requires convertible_to<const _Out&, _Out2> > > > > + && convertible_to<const _Tp&, _Tp2> > > > > + constexpr > > > > + operator out_value_result<_Out2, _Tp2>() const & > > > > + { return {out, value}; } > > > > + > > > > + template<typename _Out2, typename _Tp2> > > > > + requires convertible_to<_Out, _Out2> > > > > + && convertible_to<_Tp, _Tp2> > > > > + constexpr > > > > + operator out_value_result<_Out2, _Tp2>() && > > > > + { return {std::move(out), std::move(value)}; } > > > > + }; > > > > + > > > > + template<typename _Out, typename _Tp> > > > > + using iota_result = out_value_result<_Out, _Tp>; > > > > + > > > > + struct __iota_fn > > > > + { > > > > + template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent, weakly_incrementable _Tp> > > > > + requires indirectly_writable<_Out, const _Tp&> > > > > + constexpr iota_result<_Out, _Tp> > > > > + operator()(_Out __first, _Sent __last, _Tp __value) const > > > > + { > > > > + while (__first != __last) > > > > + { > > > > + *__first = static_cast<add_const_t<_Tp>&>(__value); > > > > > > Is this any different to const_cast<const _Tp&>(__value) ? > > > > I think it is. const_cast<const _Tp&> can potentially mean the removal > > of volatile, > > True. > > > so I would always look with suspicion on const_cast<const > > _Tp&>, while static_cast is clearer. Alternatively, as_const could be > > used, which does add_const_t. > > Which means evaluating the add_const trait *and* overload resolution > for as_const* *and* a runtime function call. > > Let's go with static_cast<const _Tp&>. Sounds good, like so? -- >8 -- Subject: [PATCH 2/3] libstdc++: Implement ranges::iota from P2440R1 libstdc++-v3/ChangeLog: * include/bits/ranges_algo.h (out_value_result): Define. (iota_result): Define. (__iota_fn, iota): Define. * testsuite/25_algorithms/iota/1.cc: New test. --- libstdc++-v3/include/bits/ranges_algo.h | 48 +++++++++++++++++++ .../testsuite/25_algorithms/iota/1.cc | 29 +++++++++++ 2 files changed, 77 insertions(+) create mode 100644 libstdc++-v3/testsuite/25_algorithms/iota/1.cc diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index 11206bdbcaa..f75735f02cb 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -3517,6 +3517,54 @@ namespace ranges }; inline constexpr __contains_subrange_fn contains_subrange{}; + + template<typename _Out, typename _Tp> + struct out_value_result + { + [[no_unique_address]] _Out out; + [[no_unique_address]] _Tp value; + + template<typename _Out2, typename _Tp2> + requires convertible_to<const _Out&, _Out2> + && convertible_to<const _Tp&, _Tp2> + constexpr + operator out_value_result<_Out2, _Tp2>() const & + { return {out, value}; } + + template<typename _Out2, typename _Tp2> + requires convertible_to<_Out, _Out2> + && convertible_to<_Tp, _Tp2> + constexpr + operator out_value_result<_Out2, _Tp2>() && + { return {std::move(out), std::move(value)}; } + }; + + template<typename _Out, typename _Tp> + using iota_result = out_value_result<_Out, _Tp>; + + struct __iota_fn + { + template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent, weakly_incrementable _Tp> + requires indirectly_writable<_Out, const _Tp&> + constexpr iota_result<_Out, _Tp> + operator()(_Out __first, _Sent __last, _Tp __value) const + { + while (__first != __last) + { + *__first = static_cast<const _Tp&>(__value); + ++__first; + ++__value; + } + return {std::move(__first), std::move(__value)}; + } + + template<weakly_incrementable _Tp, output_range<const _Tp&> _Range> + constexpr iota_result<borrowed_iterator_t<_Range>, _Tp> + operator()(_Range&& __r, _Tp __value) const + { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__value)); } + }; + + inline constexpr __iota_fn iota{}; #endif // C++23 } // namespace ranges diff --git a/libstdc++-v3/testsuite/25_algorithms/iota/1.cc b/libstdc++-v3/testsuite/25_algorithms/iota/1.cc new file mode 100644 index 00000000000..ad2bf08adf5 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/iota/1.cc @@ -0,0 +1,29 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; + +void +test01() +{ + int x[3] = {}; + __gnu_test::test_output_range<int> rx(x); + auto r0 = ranges::iota(rx, 0); + VERIFY( r0.out.ptr == x+3 ); + VERIFY( r0.value == 3 ); + VERIFY( ranges::equal(x, (int[]){0,1,2}) ); + auto r1 = ranges::iota(x, x+2, 5); + VERIFY( r1.out == x+2 ); + VERIFY( r1.value == 7 ); + VERIFY( ranges::equal(x, (int[]){5,6,2}) ); +} + +int +main() +{ + test01(); +} -- 2.38.1.420.g319605f8f0 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2/3] libstdc++: Implement ranges::iota from P2440R1 2022-11-14 15:11 ` Patrick Palka @ 2022-11-14 15:12 ` Jonathan Wakely 0 siblings, 0 replies; 12+ messages in thread From: Jonathan Wakely @ 2022-11-14 15:12 UTC (permalink / raw) To: Patrick Palka; +Cc: Daniel Krügler, gcc-patches, libstdc++ On Mon, 14 Nov 2022 at 15:11, Patrick Palka <ppalka@redhat.com> wrote: > > On Mon, 14 Nov 2022, Jonathan Wakely wrote: > > > On Mon, 14 Nov 2022 at 10:17, Daniel Krügler <daniel.kruegler@gmail.com> wrote: > > > > > > Am Mo., 14. Nov. 2022 um 11:09 Uhr schrieb Jonathan Wakely via > > > Libstdc++ <libstdc++@gcc.gnu.org>: > > > > > > > > On Mon, 14 Nov 2022 at 04:52, Patrick Palka via Libstdc++ > > > > <libstdc++@gcc.gnu.org> wrote: > > > > > > > > > > Tested on x86_64-pc-linux-gnu, does this look OK for trunk? > > > > > > > > > > libstdc++-v3/ChangeLog: > > > > > > > > > > * include/bits/ranges_algo.h (out_value_result): Define. > > > > > (iota_result): Define. > > > > > (__iota_fn, iota): Define. > > > > > * testsuite/25_algorithms/iota/1.cc: New test. > > > > > --- > > > > > libstdc++-v3/include/bits/ranges_algo.h | 48 +++++++++++++++++++ > > > > > .../testsuite/25_algorithms/iota/1.cc | 29 +++++++++++ > > > > > 2 files changed, 77 insertions(+) > > > > > create mode 100644 libstdc++-v3/testsuite/25_algorithms/iota/1.cc > > > > > > > > > > diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h > > > > > index da0ca981dc3..f003117c569 100644 > > > > > --- a/libstdc++-v3/include/bits/ranges_algo.h > > > > > +++ b/libstdc++-v3/include/bits/ranges_algo.h > > > > > @@ -3517,6 +3517,54 @@ namespace ranges > > > > > }; > > > > > > > > > > inline constexpr __contains_subrange_fn contains_subrange{}; > > > > > + > > > > > + template<typename _Out, typename _Tp> > > > > > + struct out_value_result > > > > > + { > > > > > + [[no_unique_address]] _Out out; > > > > > + [[no_unique_address]] _Tp value; > > > > > + > > > > > + template<typename _Out2, typename _Tp2> > > > > > + requires convertible_to<const _Out&, _Out2> > > > > > + && convertible_to<const _Tp&, _Tp2> > > > > > + constexpr > > > > > + operator out_value_result<_Out2, _Tp2>() const & > > > > > + { return {out, value}; } > > > > > + > > > > > + template<typename _Out2, typename _Tp2> > > > > > + requires convertible_to<_Out, _Out2> > > > > > + && convertible_to<_Tp, _Tp2> > > > > > + constexpr > > > > > + operator out_value_result<_Out2, _Tp2>() && > > > > > + { return {std::move(out), std::move(value)}; } > > > > > + }; > > > > > + > > > > > + template<typename _Out, typename _Tp> > > > > > + using iota_result = out_value_result<_Out, _Tp>; > > > > > + > > > > > + struct __iota_fn > > > > > + { > > > > > + template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent, weakly_incrementable _Tp> > > > > > + requires indirectly_writable<_Out, const _Tp&> > > > > > + constexpr iota_result<_Out, _Tp> > > > > > + operator()(_Out __first, _Sent __last, _Tp __value) const > > > > > + { > > > > > + while (__first != __last) > > > > > + { > > > > > + *__first = static_cast<add_const_t<_Tp>&>(__value); > > > > > > > > Is this any different to const_cast<const _Tp&>(__value) ? > > > > > > I think it is. const_cast<const _Tp&> can potentially mean the removal > > > of volatile, > > > > True. > > > > > so I would always look with suspicion on const_cast<const > > > _Tp&>, while static_cast is clearer. Alternatively, as_const could be > > > used, which does add_const_t. > > > > Which means evaluating the add_const trait *and* overload resolution > > for as_const* *and* a runtime function call. > > > > Let's go with static_cast<const _Tp&>. > > Sounds good, like so? OK for trunk, thanks. > > -- >8 -- > > > Subject: [PATCH 2/3] libstdc++: Implement ranges::iota from P2440R1 > > libstdc++-v3/ChangeLog: > > * include/bits/ranges_algo.h (out_value_result): Define. > (iota_result): Define. > (__iota_fn, iota): Define. > * testsuite/25_algorithms/iota/1.cc: New test. > --- > libstdc++-v3/include/bits/ranges_algo.h | 48 +++++++++++++++++++ > .../testsuite/25_algorithms/iota/1.cc | 29 +++++++++++ > 2 files changed, 77 insertions(+) > create mode 100644 libstdc++-v3/testsuite/25_algorithms/iota/1.cc > > diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h > index 11206bdbcaa..f75735f02cb 100644 > --- a/libstdc++-v3/include/bits/ranges_algo.h > +++ b/libstdc++-v3/include/bits/ranges_algo.h > @@ -3517,6 +3517,54 @@ namespace ranges > }; > > inline constexpr __contains_subrange_fn contains_subrange{}; > + > + template<typename _Out, typename _Tp> > + struct out_value_result > + { > + [[no_unique_address]] _Out out; > + [[no_unique_address]] _Tp value; > + > + template<typename _Out2, typename _Tp2> > + requires convertible_to<const _Out&, _Out2> > + && convertible_to<const _Tp&, _Tp2> > + constexpr > + operator out_value_result<_Out2, _Tp2>() const & > + { return {out, value}; } > + > + template<typename _Out2, typename _Tp2> > + requires convertible_to<_Out, _Out2> > + && convertible_to<_Tp, _Tp2> > + constexpr > + operator out_value_result<_Out2, _Tp2>() && > + { return {std::move(out), std::move(value)}; } > + }; > + > + template<typename _Out, typename _Tp> > + using iota_result = out_value_result<_Out, _Tp>; > + > + struct __iota_fn > + { > + template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent, weakly_incrementable _Tp> > + requires indirectly_writable<_Out, const _Tp&> > + constexpr iota_result<_Out, _Tp> > + operator()(_Out __first, _Sent __last, _Tp __value) const > + { > + while (__first != __last) > + { > + *__first = static_cast<const _Tp&>(__value); > + ++__first; > + ++__value; > + } > + return {std::move(__first), std::move(__value)}; > + } > + > + template<weakly_incrementable _Tp, output_range<const _Tp&> _Range> > + constexpr iota_result<borrowed_iterator_t<_Range>, _Tp> > + operator()(_Range&& __r, _Tp __value) const > + { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__value)); } > + }; > + > + inline constexpr __iota_fn iota{}; > #endif // C++23 > } // namespace ranges > > diff --git a/libstdc++-v3/testsuite/25_algorithms/iota/1.cc b/libstdc++-v3/testsuite/25_algorithms/iota/1.cc > new file mode 100644 > index 00000000000..ad2bf08adf5 > --- /dev/null > +++ b/libstdc++-v3/testsuite/25_algorithms/iota/1.cc > @@ -0,0 +1,29 @@ > +// { dg-options "-std=gnu++23" } > +// { dg-do run { target c++23 } } > + > +#include <algorithm> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > + > +namespace ranges = std::ranges; > + > +void > +test01() > +{ > + int x[3] = {}; > + __gnu_test::test_output_range<int> rx(x); > + auto r0 = ranges::iota(rx, 0); > + VERIFY( r0.out.ptr == x+3 ); > + VERIFY( r0.value == 3 ); > + VERIFY( ranges::equal(x, (int[]){0,1,2}) ); > + auto r1 = ranges::iota(x, x+2, 5); > + VERIFY( r1.out == x+2 ); > + VERIFY( r1.value == 7 ); > + VERIFY( ranges::equal(x, (int[]){5,6,2}) ); > +} > + > +int > +main() > +{ > + test01(); > +} > -- > 2.38.1.420.g319605f8f0 ^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH 3/3] libstdc++: Implement ranges::find_last{,_if,_if_not} from P1223R5 2022-11-14 4:50 [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 Patrick Palka 2022-11-14 4:50 ` [PATCH 2/3] libstdc++: Implement ranges::iota from P2440R1 Patrick Palka @ 2022-11-14 4:50 ` Patrick Palka 2022-11-14 15:12 ` [PATCH 3/3] libstdc++: Implement ranges::find_last{, _if, _if_not} " Jonathan Wakely 2022-11-14 9:04 ` [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 Jonathan Wakely 2 siblings, 1 reply; 12+ messages in thread From: Patrick Palka @ 2022-11-14 4:50 UTC (permalink / raw) To: gcc-patches; +Cc: libstdc++, Patrick Palka Tested on x86_64-pc-linux-gnu, does this look OK for trunk? libstdc++-v3/ChangeLog: * include/bits/ranges_algo.h (__find_last_fn, find_last): Define. (__find_last_if_fn, find_last_if): Define. (__find_last_if_not_fn, find_last_if_not): Define. * testsuite/25_algorithms/find_last/1.cc: New test. * testsuite/25_algorithms/find_last_if/1.cc: New test. * testsuite/25_algorithms/find_last_if_not/1.cc: New test. --- libstdc++-v3/include/bits/ranges_algo.h | 123 ++++++++++++++++++ .../testsuite/25_algorithms/find_last/1.cc | 90 +++++++++++++ .../testsuite/25_algorithms/find_last_if/1.cc | 92 +++++++++++++ .../25_algorithms/find_last_if_not/1.cc | 92 +++++++++++++ 4 files changed, 397 insertions(+) create mode 100644 libstdc++-v3/testsuite/25_algorithms/find_last/1.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/find_last_if/1.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/find_last_if_not/1.cc diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index f003117c569..0e4329382eb 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -3565,6 +3565,129 @@ namespace ranges }; inline constexpr __iota_fn iota{}; + + struct __find_last_fn + { + template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename T, typename _Proj = identity> + requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const T*> + constexpr subrange<_Iter> + operator()(_Iter __first, _Sent __last, const T& __value, _Proj __proj = {}) const + { + if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>) + { + _Iter __found = ranges::find(reverse_iterator<_Iter>{__last}, + reverse_iterator<_Iter>{__first}, + __value, __proj).base(); + if (__found == __first) + return {__last, __last}; + else + return {ranges::prev(__found), __last}; + } + else + { + _Iter __found = ranges::find(__first, __last, __value, __proj); + if (__found == __last) + return {__found, __found}; + for (;;) + { + __first = ranges::find(ranges::next(__first), __last, __value, __proj); + if (__first == __last) + return {__found, __first}; + __found = __first; + } + } + } + + template<forward_range _Range, typename T, typename _Proj = identity> + requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const T*> + constexpr borrowed_subrange_t<_Range> + operator()(_Range&& __r, const T& __value, _Proj __proj = {}) const + { return (*this)(ranges::begin(__r), ranges::end(__r), __value, std::move(__proj)); } + }; + + inline constexpr __find_last_fn find_last{}; + + struct __find_last_if_fn + { + template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Proj = identity, + indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> + constexpr subrange<_Iter> + operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const + { + if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>) + { + _Iter __found = ranges::find_if(reverse_iterator<_Iter>{__last}, + reverse_iterator<_Iter>{__first}, + __pred, __proj).base(); + if (__found == __first) + return {__last, __last}; + else + return {ranges::prev(__found), __last}; + } + else + { + _Iter __found = ranges::find_if(__first, __last, __pred, __proj); + if (__found == __last) + return {__found, __found}; + for (;;) + { + __first = ranges::find_if(ranges::next(__first), __last, __pred, __proj); + if (__first == __last) + return {__found, __first}; + __found = __first; + } + } + } + + template<forward_range _Range, typename _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> + constexpr borrowed_subrange_t<_Range> + operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const + { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__pred), std::move(__proj)); } + }; + + inline constexpr __find_last_if_fn find_last_if{}; + + struct __find_last_if_not_fn + { + template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Proj = identity, + indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> + constexpr subrange<_Iter> + operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const + { + if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>) + { + _Iter __found = ranges::find_if_not(reverse_iterator<_Iter>{__last}, + reverse_iterator<_Iter>{__first}, + __pred, __proj).base(); + if (__found == __first) + return {__last, __last}; + else + return {ranges::prev(__found), __last}; + } + else + { + _Iter __found = ranges::find_if_not(__first, __last, __pred, __proj); + if (__found == __last) + return {__found, __found}; + for (;;) + { + __first = ranges::find_if_not(ranges::next(__first), __last, __pred, __proj); + if (__first == __last) + return {__found, __first}; + __found = __first; + } + } + } + + template<forward_range _Range, typename _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> + constexpr borrowed_subrange_t<_Range> + operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const + { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__pred), std::move(__proj)); } + }; + + inline constexpr __find_last_if_not_fn find_last_if_not{}; #endif // C++23 } // namespace ranges diff --git a/libstdc++-v3/testsuite/25_algorithms/find_last/1.cc b/libstdc++-v3/testsuite/25_algorithms/find_last/1.cc new file mode 100644 index 00000000000..ef5844c8afd --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/find_last/1.cc @@ -0,0 +1,90 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; + +constexpr bool +test01() +{ + int x[] = {1, 2, 1, 2, 1, 2, 1, 2}; + + auto sr0 = ranges::find_last(x, 0); + VERIFY( ranges::empty(sr0) ); + VERIFY( sr0.begin() == ranges::end(x) ); + + auto sr1 = ranges::find_last(x, 1); + VERIFY( ranges::equal(sr1, (int[]){1, 2}) ); + VERIFY( sr1.begin() == &x[6] ); + + auto sr2 = ranges::find_last(x, 2); + VERIFY( ranges::equal(sr2, (int[]){2}) ); + VERIFY( sr2.begin() == &x[7] ); + + auto plus3 = [](int n) { return n+3; }; + + auto sr3 = ranges::find_last(x, 3, plus3); + VERIFY( ranges::empty(sr3) ); + VERIFY( sr3.begin() == ranges::end(x) ); + + auto sr4 = ranges::find_last(x, 4, plus3); + VERIFY( ranges::equal(sr4, (int[]){1, 2}) ); + VERIFY( sr4.begin() == &x[6] ); + + auto sr5 = ranges::find_last(x, 5, plus3); + VERIFY( ranges::equal(sr5, (int[]){2}) ); + VERIFY( sr5.begin() == &x[7] ); + + return true; +} + +void +test02() +{ + int x[] = {1, 2, 3, 1, 2, 3, 1, 2, 3}; + __gnu_test::test_forward_range<int> rx(x); + + auto sr0 = ranges::find_last(rx, 0); + VERIFY( ranges::empty(sr0) ); + VERIFY( sr0.begin() == ranges::end(rx) ); + + auto sr1 = ranges::find_last(rx, 1); + VERIFY( ranges::equal(sr1, (int[]){1, 2, 3}) ); + VERIFY( sr1.begin().ptr == &x[6] ); + + auto sr2 = ranges::find_last(rx, 2); + VERIFY( ranges::equal(sr2, (int[]){2, 3}) ); + VERIFY( sr2.begin().ptr == &x[7] ); + + auto sr3 = ranges::find_last(rx, 3); + VERIFY( ranges::equal(sr3, (int[]){3}) ); + VERIFY( sr3.begin().ptr == &x[8] ); + + auto plus4 = [](int n) { return n+4; }; + + auto sr4 = ranges::find_last(rx, 4, plus4); + VERIFY( ranges::empty(sr4) ); + VERIFY( sr4.begin() == ranges::end(rx) ); + + auto sr5 = ranges::find_last(rx, 5, plus4); + VERIFY( ranges::equal(sr5, (int[]){1, 2, 3}) ); + VERIFY( sr5.begin().ptr == &x[6] ); + + auto sr6 = ranges::find_last(rx, 6, plus4); + VERIFY( ranges::equal(sr6, (int[]){2, 3}) ); + VERIFY( sr6.begin().ptr == &x[7] ); + + auto sr7 = ranges::find_last(rx, 7, plus4); + VERIFY( ranges::equal(sr7, (int[]){3}) ); + VERIFY( sr7.begin().ptr == &x[8] ); +} + +int +main() +{ + static_assert(test01()); + test02(); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/find_last_if/1.cc b/libstdc++-v3/testsuite/25_algorithms/find_last_if/1.cc new file mode 100644 index 00000000000..0a723475dec --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/find_last_if/1.cc @@ -0,0 +1,92 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; + +template<int N> constexpr auto eq = [](int m) { return m == N; }; + +constexpr bool +test01() +{ + int x[] = {1, 2, 1, 2, 1, 2, 1, 2}; + + auto sr0 = ranges::find_last_if(x, eq<0>); + VERIFY( ranges::empty(sr0) ); + VERIFY( sr0.begin() == ranges::end(x) ); + + auto sr1 = ranges::find_last_if(x, eq<1>); + VERIFY( ranges::equal(sr1, (int[]){1, 2}) ); + VERIFY( sr1.begin() == &x[6] ); + + auto sr2 = ranges::find_last_if(x, eq<2>); + VERIFY( ranges::equal(sr2, (int[]){2}) ); + VERIFY( sr2.begin() == &x[7] ); + + auto plus3 = [](int n) { return n+3; }; + + auto sr3 = ranges::find_last_if(x, eq<3>, plus3); + VERIFY( ranges::empty(sr3) ); + VERIFY( sr3.begin() == ranges::end(x) ); + + auto sr4 = ranges::find_last_if(x, eq<4>, plus3); + VERIFY( ranges::equal(sr4, (int[]){1, 2}) ); + VERIFY( sr4.begin() == &x[6] ); + + auto sr5 = ranges::find_last_if(x, eq<5>, plus3); + VERIFY( ranges::equal(sr5, (int[]){2}) ); + VERIFY( sr5.begin() == &x[7] ); + + return true; +} + +void +test02() +{ + int x[] = {1, 2, 3, 1, 2, 3, 1, 2, 3}; + __gnu_test::test_forward_range<int> rx(x); + + auto sr0 = ranges::find_last_if(rx, eq<0>); + VERIFY( ranges::empty(sr0) ); + VERIFY( sr0.begin() == ranges::end(rx) ); + + auto sr1 = ranges::find_last_if(rx, eq<1>); + VERIFY( ranges::equal(sr1, (int[]){1, 2, 3}) ); + VERIFY( sr1.begin().ptr == &x[6] ); + + auto sr2 = ranges::find_last_if(rx, eq<2>); + VERIFY( ranges::equal(sr2, (int[]){2, 3}) ); + VERIFY( sr2.begin().ptr == &x[7] ); + + auto sr3 = ranges::find_last_if(rx, eq<3>); + VERIFY( ranges::equal(sr3, (int[]){3}) ); + VERIFY( sr3.begin().ptr == &x[8] ); + + auto plus4 = [](int n) { return n+4; }; + + auto sr4 = ranges::find_last_if(rx, eq<4>, plus4); + VERIFY( ranges::empty(sr4) ); + VERIFY( sr4.begin() == ranges::end(rx) ); + + auto sr5 = ranges::find_last_if(rx, eq<5>, plus4); + VERIFY( ranges::equal(sr5, (int[]){1, 2, 3}) ); + VERIFY( sr5.begin().ptr == &x[6] ); + + auto sr6 = ranges::find_last_if(rx, eq<6>, plus4); + VERIFY( ranges::equal(sr6, (int[]){2, 3}) ); + VERIFY( sr6.begin().ptr == &x[7] ); + + auto sr7 = ranges::find_last_if(rx, eq<7>, plus4); + VERIFY( ranges::equal(sr7, (int[]){3}) ); + VERIFY( sr7.begin().ptr == &x[8] ); +} + +int +main() +{ + static_assert(test01()); + test02(); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/find_last_if_not/1.cc b/libstdc++-v3/testsuite/25_algorithms/find_last_if_not/1.cc new file mode 100644 index 00000000000..98aa94b7f2c --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/find_last_if_not/1.cc @@ -0,0 +1,92 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; + +template<int N> constexpr auto ne = [](int m) { return m != N; }; + +constexpr bool +test01() +{ + int x[] = {1, 2, 1, 2, 1, 2, 1, 2}; + + auto sr0 = ranges::find_last_if_not(x, ne<0>); + VERIFY( ranges::empty(sr0) ); + VERIFY( sr0.begin() == ranges::end(x) ); + + auto sr1 = ranges::find_last_if_not(x, ne<1>); + VERIFY( ranges::equal(sr1, (int[]){1, 2}) ); + VERIFY( sr1.begin() == &x[6] ); + + auto sr2 = ranges::find_last_if_not(x, ne<2>); + VERIFY( ranges::equal(sr2, (int[]){2}) ); + VERIFY( sr2.begin() == &x[7] ); + + auto plus3 = [](int n) { return n+3; }; + + auto sr3 = ranges::find_last_if_not(x, ne<3>, plus3); + VERIFY( ranges::empty(sr3) ); + VERIFY( sr3.begin() == ranges::end(x) ); + + auto sr4 = ranges::find_last_if_not(x, ne<4>, plus3); + VERIFY( ranges::equal(sr4, (int[]){1, 2}) ); + VERIFY( sr4.begin() == &x[6] ); + + auto sr5 = ranges::find_last_if_not(x, ne<5>, plus3); + VERIFY( ranges::equal(sr5, (int[]){2}) ); + VERIFY( sr5.begin() == &x[7] ); + + return true; +} + +void +test02() +{ + int x[] = {1, 2, 3, 1, 2, 3, 1, 2, 3}; + __gnu_test::test_forward_range<int> rx(x); + + auto sr0 = ranges::find_last_if_not(rx, ne<0>); + VERIFY( ranges::empty(sr0) ); + VERIFY( sr0.begin() == ranges::end(rx) ); + + auto sr1 = ranges::find_last_if_not(rx, ne<1>); + VERIFY( ranges::equal(sr1, (int[]){1, 2, 3}) ); + VERIFY( sr1.begin().ptr == &x[6] ); + + auto sr2 = ranges::find_last_if_not(rx, ne<2>); + VERIFY( ranges::equal(sr2, (int[]){2, 3}) ); + VERIFY( sr2.begin().ptr == &x[7] ); + + auto sr3 = ranges::find_last_if_not(rx, ne<3>); + VERIFY( ranges::equal(sr3, (int[]){3}) ); + VERIFY( sr3.begin().ptr == &x[8] ); + + auto plus4 = [](int n) { return n+4; }; + + auto sr4 = ranges::find_last_if_not(rx, ne<4>, plus4); + VERIFY( ranges::empty(sr4) ); + VERIFY( sr4.begin() == ranges::end(rx) ); + + auto sr5 = ranges::find_last_if_not(rx, ne<5>, plus4); + VERIFY( ranges::equal(sr5, (int[]){1, 2, 3}) ); + VERIFY( sr5.begin().ptr == &x[6] ); + + auto sr6 = ranges::find_last_if_not(rx, ne<6>, plus4); + VERIFY( ranges::equal(sr6, (int[]){2, 3}) ); + VERIFY( sr6.begin().ptr == &x[7] ); + + auto sr7 = ranges::find_last_if_not(rx, ne<7>, plus4); + VERIFY( ranges::equal(sr7, (int[]){3}) ); + VERIFY( sr7.begin().ptr == &x[8] ); +} + +int +main() +{ + static_assert(test01()); + test02(); +} -- 2.38.1.420.g319605f8f0 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 3/3] libstdc++: Implement ranges::find_last{, _if, _if_not} from P1223R5 2022-11-14 4:50 ` [PATCH 3/3] libstdc++: Implement ranges::find_last{,_if,_if_not} from P1223R5 Patrick Palka @ 2022-11-14 15:12 ` Jonathan Wakely 0 siblings, 0 replies; 12+ messages in thread From: Jonathan Wakely @ 2022-11-14 15:12 UTC (permalink / raw) To: Patrick Palka; +Cc: gcc-patches, libstdc++ On Mon, 14 Nov 2022 at 04:51, Patrick Palka via Libstdc++ <libstdc++@gcc.gnu.org> wrote: > > Tested on x86_64-pc-linux-gnu, does this look OK for trunk? > > libstdc++-v3/ChangeLog: > > * include/bits/ranges_algo.h (__find_last_fn, find_last): > Define. > (__find_last_if_fn, find_last_if): Define. > (__find_last_if_not_fn, find_last_if_not): Define. > * testsuite/25_algorithms/find_last/1.cc: New test. > * testsuite/25_algorithms/find_last_if/1.cc: New test. > * testsuite/25_algorithms/find_last_if_not/1.cc: New test. > --- > libstdc++-v3/include/bits/ranges_algo.h | 123 ++++++++++++++++++ > .../testsuite/25_algorithms/find_last/1.cc | 90 +++++++++++++ > .../testsuite/25_algorithms/find_last_if/1.cc | 92 +++++++++++++ > .../25_algorithms/find_last_if_not/1.cc | 92 +++++++++++++ > 4 files changed, 397 insertions(+) > create mode 100644 libstdc++-v3/testsuite/25_algorithms/find_last/1.cc > create mode 100644 libstdc++-v3/testsuite/25_algorithms/find_last_if/1.cc > create mode 100644 libstdc++-v3/testsuite/25_algorithms/find_last_if_not/1.cc > > diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h > index f003117c569..0e4329382eb 100644 > --- a/libstdc++-v3/include/bits/ranges_algo.h > +++ b/libstdc++-v3/include/bits/ranges_algo.h > @@ -3565,6 +3565,129 @@ namespace ranges > }; > > inline constexpr __iota_fn iota{}; > + > + struct __find_last_fn > + { > + template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename T, typename _Proj = identity> > + requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const T*> > + constexpr subrange<_Iter> > + operator()(_Iter __first, _Sent __last, const T& __value, _Proj __proj = {}) const > + { > + if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>) > + { > + _Iter __found = ranges::find(reverse_iterator<_Iter>{__last}, > + reverse_iterator<_Iter>{__first}, > + __value, __proj).base(); > + if (__found == __first) > + return {__last, __last}; > + else > + return {ranges::prev(__found), __last}; > + } > + else > + { > + _Iter __found = ranges::find(__first, __last, __value, __proj); std::move(__proj) here too, for consistency. > + if (__found == __last) > + return {__found, __found}; > + for (;;) > + { > + __first = ranges::find(ranges::next(__first), __last, __value, __proj); And here. > + if (__first == __last) > + return {__found, __first}; > + __found = __first; > + } > + } > + } > + > + template<forward_range _Range, typename T, typename _Proj = identity> > + requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const T*> > + constexpr borrowed_subrange_t<_Range> > + operator()(_Range&& __r, const T& __value, _Proj __proj = {}) const > + { return (*this)(ranges::begin(__r), ranges::end(__r), __value, std::move(__proj)); } > + }; > + > + inline constexpr __find_last_fn find_last{}; > + > + struct __find_last_if_fn > + { > + template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Proj = identity, > + indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> > + constexpr subrange<_Iter> > + operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const > + { > + if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>) > + { > + _Iter __found = ranges::find_if(reverse_iterator<_Iter>{__last}, > + reverse_iterator<_Iter>{__first}, > + __pred, __proj).base(); And here, and std::move(__pred) too, I think. OK for trunk with those changes here (and the later cases). ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 2022-11-14 4:50 [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 Patrick Palka 2022-11-14 4:50 ` [PATCH 2/3] libstdc++: Implement ranges::iota from P2440R1 Patrick Palka 2022-11-14 4:50 ` [PATCH 3/3] libstdc++: Implement ranges::find_last{,_if,_if_not} from P1223R5 Patrick Palka @ 2022-11-14 9:04 ` Jonathan Wakely 2022-11-14 15:07 ` Patrick Palka 2 siblings, 1 reply; 12+ messages in thread From: Jonathan Wakely @ 2022-11-14 9:04 UTC (permalink / raw) To: Patrick Palka; +Cc: gcc-patches, libstdc++ On Mon, 14 Nov 2022 at 04:51, Patrick Palka via Libstdc++ <libstdc++@gcc.gnu.org> wrote: > > Tested on x86_64-pc-linux-gnu, does this look OK for trunk? > > libstdc++-v3/ChangeLog: > > * include/bits/ranges_algo.h (__contains_fn, contains): Define. > (__contains_subrange_fn, contains_subrange): Define. > * testsuite/25_algorithms/contains/1.cc: New test. > * testsuite/25_algorithms/contains_subrange/1.cc: New test. > --- > libstdc++-v3/include/bits/ranges_algo.h | 54 +++++++++++++++++++ > .../testsuite/25_algorithms/contains/1.cc | 33 ++++++++++++ > .../25_algorithms/contains_subrange/1.cc | 35 ++++++++++++ > 3 files changed, 122 insertions(+) > create mode 100644 libstdc++-v3/testsuite/25_algorithms/contains/1.cc > create mode 100644 libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc > > diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h > index de71bd07a2f..da0ca981dc3 100644 > --- a/libstdc++-v3/include/bits/ranges_algo.h > +++ b/libstdc++-v3/include/bits/ranges_algo.h > @@ -3464,6 +3464,60 @@ namespace ranges > > inline constexpr __prev_permutation_fn prev_permutation{}; > > +#if __cplusplus > 202002L > + struct __contains_fn > + { > + template<input_iterator _Iter, sentinel_for<_Iter> _Sent, > + typename _Tp, typename _Proj = identity> > + requires indirect_binary_predicate<ranges::equal_to, > + projected<_Iter, _Proj>, const _Tp*> > + constexpr bool > + operator()(_Iter __first, _Sent __last, const _Tp& __value, _Proj __proj = {}) const > + { return ranges::find(std::move(__first), __last, __value, __proj) != __last; } Should this use std::move(__proj)? > + > + template<input_range _Range, typename _Tp, typename _Proj = identity> > + requires indirect_binary_predicate<ranges::equal_to, > + projected<iterator_t<_Range>, _Proj>, const _Tp*> > + constexpr bool > + operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const > + { return (*this)(ranges::begin(__r), ranges::end(__r), __value, std::move(__proj)); } > + }; > + > + inline constexpr __contains_fn contains{}; > + > + struct __contains_subrange_fn > + { > + template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1, > + forward_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 bool > + operator()(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, > + _Pred __pred = {}, Proj1 __proj1 = {}, Proj2 __proj2 = {}) const > + { > + return __first2 == __last2 > + || !ranges::search(__first1, __last1, __first2, __last2, > + std::move(__pred), std::move(__proj1), std::move(__proj2)).empty(); > + } > + > + template<forward_range _Range1, forward_range _Range2, > + typename _Pred = ranges::equal_to, > + typename _Proj1 = identity, typename _Proj2 = identity> > + requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, > + _Pred, _Proj1, _Proj2> > + constexpr bool > + operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, > + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const > + { > + return (*this)(ranges::begin(__r1), ranges::end(__r1), > + ranges::begin(__r2), ranges::end(__r2), > + std::move(__pred), std::move(__proj1), std::move(__proj2)); > + } > + }; > + > + inline constexpr __contains_subrange_fn contains_subrange{}; > +#endif // C++23 > } // namespace ranges > > #define __cpp_lib_shift 201806L > diff --git a/libstdc++-v3/testsuite/25_algorithms/contains/1.cc b/libstdc++-v3/testsuite/25_algorithms/contains/1.cc > new file mode 100644 > index 00000000000..146ab593b70 > --- /dev/null > +++ b/libstdc++-v3/testsuite/25_algorithms/contains/1.cc > @@ -0,0 +1,33 @@ > +// { dg-options "-std=gnu++23" } > +// { dg-do run { target c++23 } } > + > +#include <algorithm> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > + > +namespace ranges = std::ranges; > + > +void > +test01() > +{ > + int x[] = {1,2,3}; > + using to_input = __gnu_test::test_input_range<int>; > + VERIFY( ranges::contains(to_input(x), 1) ); > + VERIFY( ranges::contains(to_input(x), 2) ); > + VERIFY( ranges::contains(to_input(x), 3) ); > + VERIFY( !ranges::contains(to_input(x), 4) ); > + VERIFY( !ranges::contains(x, x+2, 3) ); > + auto neg = [](int n) { return -n; }; > + VERIFY( ranges::contains(to_input(x), -1, neg) ); > + VERIFY( ranges::contains(to_input(x), -2, neg) ); > + VERIFY( ranges::contains(to_input(x), -3, neg) ); > + VERIFY( !ranges::contains(to_input(x), -4, neg) ); > + > + VERIFY( !ranges::contains(x, x+2, -3, neg) ); > +} > + > +int > +main() > +{ > + test01(); > +} > diff --git a/libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc b/libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc > new file mode 100644 > index 00000000000..62b92795f94 > --- /dev/null > +++ b/libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc > @@ -0,0 +1,35 @@ > +// { dg-options "-std=gnu++23" } > +// { dg-do run { target c++23 } } > + > +#include <algorithm> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > + > +namespace ranges = std::ranges; > + > +void > +test01() > +{ > + int x[] = {1,2,3,4,5}; > + int y[] = {2,3,4}; > + int z[] = {4,5,6}; > + __gnu_test::test_forward_range<int> rx(x); > + __gnu_test::test_forward_range<int> ry(y); > + __gnu_test::test_forward_range<int> rz(z); > + VERIFY( ranges::contains_subrange(rx, ry) ); > + VERIFY( !ranges::contains_subrange(rx, rz) ); > + VERIFY( ranges::contains_subrange(rx, ry, ranges::less{}) ); > + VERIFY( ranges::contains_subrange(rx, rz, ranges::less{}) ); > + auto plus3 = [](int n) { return n+3; }; > + VERIFY( !ranges::contains_subrange(rx, ry, ranges::equal_to{}, plus3) ); > + VERIFY( ranges::contains_subrange(rx, rz, ranges::equal_to{}, plus3) ); > + > + VERIFY( ranges::contains_subrange(x, x+2, y, y+1) ); > + VERIFY( !ranges::contains_subrange(x, x+2, y, y+2) ); > +} > + > +int > +main() > +{ > + test01(); > +} > -- > 2.38.1.420.g319605f8f0 > ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 2022-11-14 9:04 ` [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 Jonathan Wakely @ 2022-11-14 15:07 ` Patrick Palka 2022-11-14 15:09 ` Jonathan Wakely 0 siblings, 1 reply; 12+ messages in thread From: Patrick Palka @ 2022-11-14 15:07 UTC (permalink / raw) To: Jonathan Wakely; +Cc: Patrick Palka, gcc-patches, libstdc++ On Mon, 14 Nov 2022, Jonathan Wakely wrote: > On Mon, 14 Nov 2022 at 04:51, Patrick Palka via Libstdc++ > <libstdc++@gcc.gnu.org> wrote: > > > > Tested on x86_64-pc-linux-gnu, does this look OK for trunk? > > > > libstdc++-v3/ChangeLog: > > > > * include/bits/ranges_algo.h (__contains_fn, contains): Define. > > (__contains_subrange_fn, contains_subrange): Define. > > * testsuite/25_algorithms/contains/1.cc: New test. > > * testsuite/25_algorithms/contains_subrange/1.cc: New test. > > --- > > libstdc++-v3/include/bits/ranges_algo.h | 54 +++++++++++++++++++ > > .../testsuite/25_algorithms/contains/1.cc | 33 ++++++++++++ > > .../25_algorithms/contains_subrange/1.cc | 35 ++++++++++++ > > 3 files changed, 122 insertions(+) > > create mode 100644 libstdc++-v3/testsuite/25_algorithms/contains/1.cc > > create mode 100644 libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc > > > > diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h > > index de71bd07a2f..da0ca981dc3 100644 > > --- a/libstdc++-v3/include/bits/ranges_algo.h > > +++ b/libstdc++-v3/include/bits/ranges_algo.h > > @@ -3464,6 +3464,60 @@ namespace ranges > > > > inline constexpr __prev_permutation_fn prev_permutation{}; > > > > +#if __cplusplus > 202002L > > + struct __contains_fn > > + { > > + template<input_iterator _Iter, sentinel_for<_Iter> _Sent, > > + typename _Tp, typename _Proj = identity> > > + requires indirect_binary_predicate<ranges::equal_to, > > + projected<_Iter, _Proj>, const _Tp*> > > + constexpr bool > > + operator()(_Iter __first, _Sent __last, const _Tp& __value, _Proj __proj = {}) const > > + { return ranges::find(std::move(__first), __last, __value, __proj) != __last; } > > Should this use std::move(__proj)? Oops yes, IIUC std::move'ing projections isn't necessary since they're copyable and equality preserving, but doing so is consistent with the rest of the ranges algos which tend to std::move function objects. -- >8 -- Subject: [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 libstdc++-v3/ChangeLog: * include/bits/ranges_algo.h (__contains_fn, contains): Define. (__contains_subrange_fn, contains_subrange): Define. * testsuite/25_algorithms/contains/1.cc: New test. * testsuite/25_algorithms/contains_subrange/1.cc: New test. --- libstdc++-v3/include/bits/ranges_algo.h | 54 +++++++++++++++++++ .../testsuite/25_algorithms/contains/1.cc | 33 ++++++++++++ .../25_algorithms/contains_subrange/1.cc | 37 +++++++++++++ 3 files changed, 124 insertions(+) create mode 100644 libstdc++-v3/testsuite/25_algorithms/contains/1.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index de71bd07a2f..11206bdbcaa 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -3464,6 +3464,60 @@ namespace ranges inline constexpr __prev_permutation_fn prev_permutation{}; +#if __cplusplus > 202002L + struct __contains_fn + { + template<input_iterator _Iter, sentinel_for<_Iter> _Sent, + typename _Tp, typename _Proj = identity> + requires indirect_binary_predicate<ranges::equal_to, + projected<_Iter, _Proj>, const _Tp*> + constexpr bool + operator()(_Iter __first, _Sent __last, const _Tp& __value, _Proj __proj = {}) const + { return ranges::find(std::move(__first), __last, __value, std::move(__proj)) != __last; } + + template<input_range _Range, typename _Tp, typename _Proj = identity> + requires indirect_binary_predicate<ranges::equal_to, + projected<iterator_t<_Range>, _Proj>, const _Tp*> + constexpr bool + operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const + { return (*this)(ranges::begin(__r), ranges::end(__r), __value, std::move(__proj)); } + }; + + inline constexpr __contains_fn contains{}; + + struct __contains_subrange_fn + { + template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1, + forward_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 bool + operator()(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, Proj1 __proj1 = {}, Proj2 __proj2 = {}) const + { + return __first2 == __last2 + || !ranges::search(__first1, __last1, __first2, __last2, + std::move(__pred), std::move(__proj1), std::move(__proj2)).empty(); + } + + template<forward_range _Range1, forward_range _Range2, + typename _Pred = ranges::equal_to, + typename _Proj1 = identity, typename _Proj2 = identity> + requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, + _Pred, _Proj1, _Proj2> + constexpr bool + operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const + { + return (*this)(ranges::begin(__r1), ranges::end(__r1), + ranges::begin(__r2), ranges::end(__r2), + std::move(__pred), std::move(__proj1), std::move(__proj2)); + } + }; + + inline constexpr __contains_subrange_fn contains_subrange{}; +#endif // C++23 } // namespace ranges #define __cpp_lib_shift 201806L diff --git a/libstdc++-v3/testsuite/25_algorithms/contains/1.cc b/libstdc++-v3/testsuite/25_algorithms/contains/1.cc new file mode 100644 index 00000000000..146ab593b70 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/contains/1.cc @@ -0,0 +1,33 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; + +void +test01() +{ + int x[] = {1,2,3}; + using to_input = __gnu_test::test_input_range<int>; + VERIFY( ranges::contains(to_input(x), 1) ); + VERIFY( ranges::contains(to_input(x), 2) ); + VERIFY( ranges::contains(to_input(x), 3) ); + VERIFY( !ranges::contains(to_input(x), 4) ); + VERIFY( !ranges::contains(x, x+2, 3) ); + auto neg = [](int n) { return -n; }; + VERIFY( ranges::contains(to_input(x), -1, neg) ); + VERIFY( ranges::contains(to_input(x), -2, neg) ); + VERIFY( ranges::contains(to_input(x), -3, neg) ); + VERIFY( !ranges::contains(to_input(x), -4, neg) ); + + VERIFY( !ranges::contains(x, x+2, -3, neg) ); +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc b/libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc new file mode 100644 index 00000000000..6c3c99c0fd6 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc @@ -0,0 +1,37 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; + +void +test01() +{ + int x[] = {1,2,3,4,5}; + int y[] = {2,3,4}; + int z[] = {4,5,6}; + __gnu_test::test_forward_range<int> rx(x); + __gnu_test::test_forward_range<int> ry(y); + __gnu_test::test_forward_range<int> rz(z); + VERIFY( ranges::contains_subrange(rx, ry) ); + VERIFY( !ranges::contains_subrange(rx, rz) ); + VERIFY( ranges::contains_subrange(rx, ry, ranges::less{}) ); + VERIFY( ranges::contains_subrange(rx, rz, ranges::less{}) ); + auto plus3 = [](int n) { return n+3; }; + VERIFY( !ranges::contains_subrange(rx, ry, {}, plus3) ); + VERIFY( ranges::contains_subrange(rx, rz, {}, plus3) ); + VERIFY( ranges::contains_subrange(rx, ry, {}, plus3, plus3) ); + VERIFY( !ranges::contains_subrange(rx, rz, {}, plus3, plus3) ); + + VERIFY( ranges::contains_subrange(x, x+2, y, y+1) ); + VERIFY( !ranges::contains_subrange(x, x+2, y, y+2) ); +} + +int +main() +{ + test01(); +} -- 2.38.1.420.g319605f8f0 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 2022-11-14 15:07 ` Patrick Palka @ 2022-11-14 15:09 ` Jonathan Wakely 0 siblings, 0 replies; 12+ messages in thread From: Jonathan Wakely @ 2022-11-14 15:09 UTC (permalink / raw) To: Patrick Palka; +Cc: gcc-patches, libstdc++ On Mon, 14 Nov 2022 at 15:07, Patrick Palka <ppalka@redhat.com> wrote: > > On Mon, 14 Nov 2022, Jonathan Wakely wrote: > > > On Mon, 14 Nov 2022 at 04:51, Patrick Palka via Libstdc++ > > <libstdc++@gcc.gnu.org> wrote: > > > > > > Tested on x86_64-pc-linux-gnu, does this look OK for trunk? > > > > > > libstdc++-v3/ChangeLog: > > > > > > * include/bits/ranges_algo.h (__contains_fn, contains): Define. > > > (__contains_subrange_fn, contains_subrange): Define. > > > * testsuite/25_algorithms/contains/1.cc: New test. > > > * testsuite/25_algorithms/contains_subrange/1.cc: New test. > > > --- > > > libstdc++-v3/include/bits/ranges_algo.h | 54 +++++++++++++++++++ > > > .../testsuite/25_algorithms/contains/1.cc | 33 ++++++++++++ > > > .../25_algorithms/contains_subrange/1.cc | 35 ++++++++++++ > > > 3 files changed, 122 insertions(+) > > > create mode 100644 libstdc++-v3/testsuite/25_algorithms/contains/1.cc > > > create mode 100644 libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc > > > > > > diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h > > > index de71bd07a2f..da0ca981dc3 100644 > > > --- a/libstdc++-v3/include/bits/ranges_algo.h > > > +++ b/libstdc++-v3/include/bits/ranges_algo.h > > > @@ -3464,6 +3464,60 @@ namespace ranges > > > > > > inline constexpr __prev_permutation_fn prev_permutation{}; > > > > > > +#if __cplusplus > 202002L > > > + struct __contains_fn > > > + { > > > + template<input_iterator _Iter, sentinel_for<_Iter> _Sent, > > > + typename _Tp, typename _Proj = identity> > > > + requires indirect_binary_predicate<ranges::equal_to, > > > + projected<_Iter, _Proj>, const _Tp*> > > > + constexpr bool > > > + operator()(_Iter __first, _Sent __last, const _Tp& __value, _Proj __proj = {}) const > > > + { return ranges::find(std::move(__first), __last, __value, __proj) != __last; } > > > > Should this use std::move(__proj)? > > Oops yes, IIUC std::move'ing projections isn't necessary since they're > copyable and equality preserving, but doing so is consistent with the > rest of the ranges algos which tend to std::move function objects. Revised patch is OK for trunk, thanks. > > -- >8 -- > > Subject: [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange > from P2302R4 > > libstdc++-v3/ChangeLog: > > * include/bits/ranges_algo.h (__contains_fn, contains): Define. > (__contains_subrange_fn, contains_subrange): Define. > * testsuite/25_algorithms/contains/1.cc: New test. > * testsuite/25_algorithms/contains_subrange/1.cc: New test. > --- > libstdc++-v3/include/bits/ranges_algo.h | 54 +++++++++++++++++++ > .../testsuite/25_algorithms/contains/1.cc | 33 ++++++++++++ > .../25_algorithms/contains_subrange/1.cc | 37 +++++++++++++ > 3 files changed, 124 insertions(+) > create mode 100644 libstdc++-v3/testsuite/25_algorithms/contains/1.cc > create mode 100644 libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc > > diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h > index de71bd07a2f..11206bdbcaa 100644 > --- a/libstdc++-v3/include/bits/ranges_algo.h > +++ b/libstdc++-v3/include/bits/ranges_algo.h > @@ -3464,6 +3464,60 @@ namespace ranges > > inline constexpr __prev_permutation_fn prev_permutation{}; > > +#if __cplusplus > 202002L > + struct __contains_fn > + { > + template<input_iterator _Iter, sentinel_for<_Iter> _Sent, > + typename _Tp, typename _Proj = identity> > + requires indirect_binary_predicate<ranges::equal_to, > + projected<_Iter, _Proj>, const _Tp*> > + constexpr bool > + operator()(_Iter __first, _Sent __last, const _Tp& __value, _Proj __proj = {}) const > + { return ranges::find(std::move(__first), __last, __value, std::move(__proj)) != __last; } > + > + template<input_range _Range, typename _Tp, typename _Proj = identity> > + requires indirect_binary_predicate<ranges::equal_to, > + projected<iterator_t<_Range>, _Proj>, const _Tp*> > + constexpr bool > + operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const > + { return (*this)(ranges::begin(__r), ranges::end(__r), __value, std::move(__proj)); } > + }; > + > + inline constexpr __contains_fn contains{}; > + > + struct __contains_subrange_fn > + { > + template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1, > + forward_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 bool > + operator()(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, > + _Pred __pred = {}, Proj1 __proj1 = {}, Proj2 __proj2 = {}) const > + { > + return __first2 == __last2 > + || !ranges::search(__first1, __last1, __first2, __last2, > + std::move(__pred), std::move(__proj1), std::move(__proj2)).empty(); > + } > + > + template<forward_range _Range1, forward_range _Range2, > + typename _Pred = ranges::equal_to, > + typename _Proj1 = identity, typename _Proj2 = identity> > + requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, > + _Pred, _Proj1, _Proj2> > + constexpr bool > + operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, > + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const > + { > + return (*this)(ranges::begin(__r1), ranges::end(__r1), > + ranges::begin(__r2), ranges::end(__r2), > + std::move(__pred), std::move(__proj1), std::move(__proj2)); > + } > + }; > + > + inline constexpr __contains_subrange_fn contains_subrange{}; > +#endif // C++23 > } // namespace ranges > > #define __cpp_lib_shift 201806L > diff --git a/libstdc++-v3/testsuite/25_algorithms/contains/1.cc b/libstdc++-v3/testsuite/25_algorithms/contains/1.cc > new file mode 100644 > index 00000000000..146ab593b70 > --- /dev/null > +++ b/libstdc++-v3/testsuite/25_algorithms/contains/1.cc > @@ -0,0 +1,33 @@ > +// { dg-options "-std=gnu++23" } > +// { dg-do run { target c++23 } } > + > +#include <algorithm> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > + > +namespace ranges = std::ranges; > + > +void > +test01() > +{ > + int x[] = {1,2,3}; > + using to_input = __gnu_test::test_input_range<int>; > + VERIFY( ranges::contains(to_input(x), 1) ); > + VERIFY( ranges::contains(to_input(x), 2) ); > + VERIFY( ranges::contains(to_input(x), 3) ); > + VERIFY( !ranges::contains(to_input(x), 4) ); > + VERIFY( !ranges::contains(x, x+2, 3) ); > + auto neg = [](int n) { return -n; }; > + VERIFY( ranges::contains(to_input(x), -1, neg) ); > + VERIFY( ranges::contains(to_input(x), -2, neg) ); > + VERIFY( ranges::contains(to_input(x), -3, neg) ); > + VERIFY( !ranges::contains(to_input(x), -4, neg) ); > + > + VERIFY( !ranges::contains(x, x+2, -3, neg) ); > +} > + > +int > +main() > +{ > + test01(); > +} > diff --git a/libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc b/libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc > new file mode 100644 > index 00000000000..6c3c99c0fd6 > --- /dev/null > +++ b/libstdc++-v3/testsuite/25_algorithms/contains_subrange/1.cc > @@ -0,0 +1,37 @@ > +// { dg-options "-std=gnu++23" } > +// { dg-do run { target c++23 } } > + > +#include <algorithm> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > + > +namespace ranges = std::ranges; > + > +void > +test01() > +{ > + int x[] = {1,2,3,4,5}; > + int y[] = {2,3,4}; > + int z[] = {4,5,6}; > + __gnu_test::test_forward_range<int> rx(x); > + __gnu_test::test_forward_range<int> ry(y); > + __gnu_test::test_forward_range<int> rz(z); > + VERIFY( ranges::contains_subrange(rx, ry) ); > + VERIFY( !ranges::contains_subrange(rx, rz) ); > + VERIFY( ranges::contains_subrange(rx, ry, ranges::less{}) ); > + VERIFY( ranges::contains_subrange(rx, rz, ranges::less{}) ); > + auto plus3 = [](int n) { return n+3; }; > + VERIFY( !ranges::contains_subrange(rx, ry, {}, plus3) ); > + VERIFY( ranges::contains_subrange(rx, rz, {}, plus3) ); > + VERIFY( ranges::contains_subrange(rx, ry, {}, plus3, plus3) ); > + VERIFY( !ranges::contains_subrange(rx, rz, {}, plus3, plus3) ); > + > + VERIFY( ranges::contains_subrange(x, x+2, y, y+1) ); > + VERIFY( !ranges::contains_subrange(x, x+2, y, y+2) ); > +} > + > +int > +main() > +{ > + test01(); > +} > -- > 2.38.1.420.g319605f8f0 > ^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2022-11-14 15:13 UTC | newest] Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2022-11-14 4:50 [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 Patrick Palka 2022-11-14 4:50 ` [PATCH 2/3] libstdc++: Implement ranges::iota from P2440R1 Patrick Palka 2022-11-14 10:08 ` Jonathan Wakely 2022-11-14 10:17 ` Daniel Krügler 2022-11-14 10:20 ` Jonathan Wakely 2022-11-14 15:11 ` Patrick Palka 2022-11-14 15:12 ` Jonathan Wakely 2022-11-14 4:50 ` [PATCH 3/3] libstdc++: Implement ranges::find_last{,_if,_if_not} from P1223R5 Patrick Palka 2022-11-14 15:12 ` [PATCH 3/3] libstdc++: Implement ranges::find_last{, _if, _if_not} " Jonathan Wakely 2022-11-14 9:04 ` [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 Jonathan Wakely 2022-11-14 15:07 ` Patrick Palka 2022-11-14 15:09 ` Jonathan Wakely
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).