| Message ID | 20221114045047.362745-1-ppalka@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | [1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 | expand |
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 >
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(); +}
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 >
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(); +}