From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wr1-x429.google.com (mail-wr1-x429.google.com [IPv6:2a00:1450:4864:20::429]) by sourceware.org (Postfix) with ESMTPS id 31DCB385800F for ; Wed, 23 Jun 2021 20:34:16 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 31DCB385800F Received: by mail-wr1-x429.google.com with SMTP id i94so4079598wri.4 for ; Wed, 23 Jun 2021 13:34:16 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:from:subject:message-id:date:user-agent :mime-version:content-language; bh=h6Bg7CyH0B+AgckcisZT9S7bSmMOCfXHFqwwGZQYV08=; b=FWyoQ9ysB7994qszGGMEmaQWrtTSbF3jEbUH6y0I2xtqDwQjI8jvL2ri5XkvU21IKa G6TIuXoynKzpbFcATlC7m6eGZGSFk2TS12K4OEWTKREgSw3YtBHCUcc2stoBo0n+4Fe+ IJRNUfH0txtbSae82plQxMDpGbJxVV8JgnF2EJciCTwSb9QJApyTzaJ6/N47i0m0LZ09 1gHnIzN0kS2BM9qHIgBi8cqrfFEp+Jk27C2J+B9IuVAXePrj3yECSimoC6PlzA7PKlLS XxwgNj8yBabVw0/3/bUMwkx+MUBHtV5oferhS0mBT3R1tUA5coFt99CBgSV2MaPwG5Ht LIEA== X-Gm-Message-State: AOAM5307Zk/fWihGOdzSMTt51qtGjIYd6iDRn58CxkCkurS0Z9qOzuYb 3fX06qyFrrl3PsCtlXhQJjFlL/Di3aZlZg== X-Google-Smtp-Source: ABdhPJwnHByFwew4ZobYXX1RR443QvkPmCL5aRCj39YFp3sSQ13ZFOSyjBKpGlny+GZnd5LAWromtQ== X-Received: by 2002:adf:c50c:: with SMTP id q12mr2274071wrf.158.1624480454916; Wed, 23 Jun 2021 13:34:14 -0700 (PDT) Received: from ?IPv6:2a01:e0a:1dc:b1c0:416d:5a26:c211:c343? ([2a01:e0a:1dc:b1c0:416d:5a26:c211:c343]) by smtp.googlemail.com with ESMTPSA id c133sm6481432wmf.0.2021.06.23.13.34.14 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 23 Jun 2021 13:34:14 -0700 (PDT) To: "libstdc++@gcc.gnu.org" From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Subject: Add three way lower_bound Message-ID: Date: Wed, 23 Jun 2021 22:34:13 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.8.1 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------------9E016B8860E4F93B05027174" Content-Language: fr X-Spam-Status: No, score=-11.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 23 Jun 2021 20:34:17 -0000 This is a multi-part message in MIME format. --------------9E016B8860E4F93B05027174 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Hi Following the message to propose an alternative lower_bound and the reply to use three way comparison I try to implement this. Before going further I wonder if this is something possible ? The purpose of the: if constexpr (three_way_comparable<>) is to make sure that we use it only if there is a proper <=> operator defined. Afai understood what is in we can have the __synth3way for any type as long as < exist. But I think that if <=> is implemented in terms of < then it might be too expensive, the actual lower_bound might already be implemented this way. My main concerns is of course Standard conformity, could it be ok ? François --------------9E016B8860E4F93B05027174 Content-Type: text/x-patch; charset=UTF-8; name="lower_bound_three_way.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="lower_bound_three_way.patch" diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index d001b5f9dae..3ccb3c0301b 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -1473,6 +1473,48 @@ _GLIBCXX_END_NAMESPACE_CONTAINER return __first; } +#if __cpp_lib_three_way_comparison + template + _GLIBCXX20_CONSTEXPR + _ForwardIterator + __lower_bound_three_way(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __val, _Compare __comp) + { + auto __len = std::distance(__first, __last); + + while (__len > 0) + { + auto __half = __len >> 1; + if (__half == 0) + { + if (auto __c = __comp(*__first, __val); __c < 0) + return std::next(__first); + return __first; + } + + _ForwardIterator __prev_mid = __first; + std::advance(__prev_mid, __half - 1); + _ForwardIterator __middle = std::next(__prev_mid); + if (auto __c = __comp(*__middle, __val); __c != 0) + { + if (__c < 0) + { + __first = __middle; + ++__first; + __len = __len - __half - 1; + } + else + __len = __half; + } + else if (__c = __comp(*__prev_mid, __val); __c != 0) + return __middle; + else // __c == 0. + __len = __half - 1; + } + return __first; + } +#endif + /** * @brief Finds the first position in which @a val could be inserted * without changing the ordering. @@ -1496,6 +1538,13 @@ _GLIBCXX_END_NAMESPACE_CONTAINER typename iterator_traits<_ForwardIterator>::value_type, _Tp>) __glibcxx_requires_partitioned_lower(__first, __last, __val); +#if __cpp_lib_three_way_comparison + if constexpr (three_way_comparable_with< + typename iterator_traits<_ForwardIterator>::reference, + const _Tp&>) + return std::__lower_bound_three_way(__first, __last, __val, + compare_three_way{}); +#endif return std::__lower_bound(__first, __last, __val, __gnu_cxx::__ops::__iter_less_val()); } --------------9E016B8860E4F93B05027174--