From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 2B4303858D32 for ; Mon, 14 Nov 2022 09:04:53 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 2B4303858D32 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1668416692; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=4u7vCzygqX9ZTJpHLtVLBnfrNguSOQbTQtYqg/T6/JM=; b=X7QEaosSdhgt9gD627tRuTF61DWGlSvjG6zr7euH16zUND4VUY/h/W3875HNw8X2rVaLS9 ohyw/KxCpx2wktCo1hOob/6hk0QsXTzQh4sdFRyX2NKjvI/5FRwWFHyX+CUU666jXPewed E6CW5E1x6oWjyilmL1KKJPF7LbTApjA= Received: from mail-ed1-f71.google.com (mail-ed1-f71.google.com [209.85.208.71]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-651-x0IGnbDfMBOvHg0ewxqb6w-1; Mon, 14 Nov 2022 04:04:51 -0500 X-MC-Unique: x0IGnbDfMBOvHg0ewxqb6w-1 Received: by mail-ed1-f71.google.com with SMTP id w17-20020a056402269100b00461e28a75ccso7770254edd.8 for ; Mon, 14 Nov 2022 01:04:51 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=4u7vCzygqX9ZTJpHLtVLBnfrNguSOQbTQtYqg/T6/JM=; b=WSsfLjVtgcopGK8QCL+AuEtTeOrvae0D9ma9rrEHGxbXiDPh0s1BH5G3eoev3eWimq NTC9Pahmqfw8jcInwei7NwXcHpCo+fMfH/6eWUupEDzIpcDfSicK7Wqr+ZrJqAphdMaP 3Qp1cBFl0oX7Y4tfEfyLdOoAwIw421KgStLa9mVUOcp5YtkbEI6o/e5a2IxtnLvIJHuY vSHI0SloQiXzyFJ0sZB995NhW4OnC9d5xY9iyzWvrgQLUbNY4xeHjEXnlnGkbWq0QZ3S MZfW2uVcDv7H20M6Prz21YfXpMBkT0vfeFsfTfERTqOPLIskiFWpCIfPV9sAW4W/tYM+ VAEA== X-Gm-Message-State: ANoB5pmwvUjQe7J3tk/rsIE7EMsrk/HhVxz2tsjjOXWYUy6ZjNjtMqKj sDWUwKtjql3CHuL2byUYprUf1KyDihPIuonr5xKcOMrwVvigndgweGnHBZEMNKYg3lkcWgZSNj+ CwLVpxJ01BKRgWmiSd9zdFW0jyWcz0zo= X-Received: by 2002:a05:6402:229b:b0:457:d794:f5ee with SMTP id cw27-20020a056402229b00b00457d794f5eemr10699916edb.227.1668416690377; Mon, 14 Nov 2022 01:04:50 -0800 (PST) X-Google-Smtp-Source: AA0mqf4fy4ugn7mdL1mZzFn11ItZ5NnG/gUc41qgLc8r50Ob5x/7yVCokwjPoeRIXXD3qh7HecpjbuaERF7ZKNvprzg= X-Received: by 2002:a05:6402:229b:b0:457:d794:f5ee with SMTP id cw27-20020a056402229b00b00457d794f5eemr10699907edb.227.1668416690144; Mon, 14 Nov 2022 01:04:50 -0800 (PST) MIME-Version: 1.0 References: <20221114045047.362745-1-ppalka@redhat.com> In-Reply-To: <20221114045047.362745-1-ppalka@redhat.com> From: Jonathan Wakely Date: Mon, 14 Nov 2022 09:04:39 +0000 Message-ID: Subject: Re: [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 To: Patrick Palka Cc: gcc-patches@gcc.gnu.org, libstdc++@gcc.gnu.org X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-12.1 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,KAM_NUMSUBJECT,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,SPF_NONE,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Mon, 14 Nov 2022 at 04:51, Patrick Palka via Libstdc++ 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 _Sent, > + typename _Tp, typename _Proj = identity> > + requires indirect_binary_predicate + 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 > + requires indirect_binary_predicate + projected, _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 _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 + typename _Pred = ranges::equal_to, > + typename _Proj1 = identity, typename _Proj2 = identity> > + requires indirectly_comparable, 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 > +#include > +#include > + > +namespace ranges = std::ranges; > + > +void > +test01() > +{ > + int x[] = {1,2,3}; > + using to_input = __gnu_test::test_input_range; > + 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 > +#include > +#include > + > +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 rx(x); > + __gnu_test::test_forward_range ry(y); > + __gnu_test::test_forward_range 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 >