From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x636.google.com (mail-ej1-x636.google.com [IPv6:2a00:1450:4864:20::636]) by sourceware.org (Postfix) with ESMTPS id 390253853558 for ; Thu, 1 Sep 2022 06:48:08 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 390253853558 Received: by mail-ej1-x636.google.com with SMTP id p16so29533301ejb.9 for ; Wed, 31 Aug 2022 23:48:08 -0700 (PDT) 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; bh=AN0t94/kRZz/YbtHPAafShB5ICNpWSLa6+9T0ihhvOs=; b=7IUDPkotMgJgN8EhXp8chWGm3vvBQe8Yn4FINevk2zzjWVfICJ8mAefO8jUrZrhPRi wRVuFSz1y5hrnPEVz57i5O4BsiBmdbBm7ChkhO9RA+mk1exW3rhVz8EN0inBF9zJS41t Yz/YEGso/JfImRfA3veDAOzYHNsy6EWV1GSpLPkZloyXKVuXqn9krg0DSSZiAC3VJjPz SLCWgoMHVedCc3577t/8zaOCuXvDhkZvF12RsRl4fN0EEIOt6mGcpji7hyV9Zka0kzAI pzWik8a2kWgI+SGROeMX8fITtmniWFSLKeSie3QiEQng7a5foOnqrCF9zstAA6eJWVmc mUdA== X-Gm-Message-State: ACgBeo2L5wPP530p8YVUni4gSnD1RXEAdwDl43dWgwoaFol2p4JLLHF1 91BdgmpCp+YebD1DW03PErSSJ7WE2Lq6Ak4UKFI= X-Google-Smtp-Source: AA6agR4vq9RxkgAkXxnWpGF+r4zQMeCEpcixvQEMgjtR2QxA6IFg7zBotabolLt/fA4jcEyZuANGl7sNpZJhZS1R0d4= X-Received: by 2002:a17:906:4fd0:b0:73d:be5b:291d with SMTP id i16-20020a1709064fd000b0073dbe5b291dmr22568873ejw.506.1662014886930; Wed, 31 Aug 2022 23:48:06 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Jonathan Wakely Date: Thu, 1 Sep 2022 07:47:55 +0100 Message-ID: Subject: Re: Add three way lower_bound To: =?UTF-8?Q?Fran=C3=A7ois_Dumont?= Cc: "libstdc++" X-Spam-Status: No, score=-0.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Content-Filtered-By: Mailman/MimeDel 2.1.29 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: Thu, 01 Sep 2022 06:48:10 -0000 On Wed, 23 Jun 2021, 21:34 Fran=C3=A7ois Dumont via Libstdc++, < libstdc++@gcc.gnu.org> wrote: > 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 <=3D> operator > defined. Afai understood what is in we can have the > __synth3way for any type as long as < exist. But I think that if <=3D> 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 ? > I don't think so. For a built-in type like int I don't think using <=3D> wi= ll be faster. For a class type type with overloaded operator< it's observable whether it gets called or not, so this patch would be a change in observable behaviour. I think we have to use < instead. > Fran=C3=A7ois > > From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x636.google.com (mail-ej1-x636.google.com [IPv6:2a00:1450:4864:20::636]) by sourceware.org (Postfix) with ESMTPS id 390253853558 for ; Thu, 1 Sep 2022 06:48:08 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 390253853558 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-ej1-x636.google.com with SMTP id p16so29533301ejb.9 for ; Wed, 31 Aug 2022 23:48:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc; bh=AN0t94/kRZz/YbtHPAafShB5ICNpWSLa6+9T0ihhvOs=; b=WxaWYhIP23nrJOi5FZnPuBAKMutewCUpAb4fhABcvPVQlUSgNH5468vVUIoucN5U+b QDgpsr6jOyxtMcUL1QdyVYWNBMgvnxrS6mTHV5BwSb2snRlUn90f7mjpZcI82fdd4jI0 oKTnosfFMdqEgxjNYkAjMPEpWkqEkmzVnHy6XVQbfLFckZeYEM3OyHdLkW06AKk7cJT4 6mRal8jVkmxsE9z5AMMlNNS1gs9eM+0oYHvIdC8jEFcMy3ooguDbHop8DlFwYvfDMEjy eSiCUuvtAspqhzhsOmG/SZkjl1eQNLSFoP/C3XeZ1LADoD3xg4AasOWFmNQTl8JpoaVv OQnA== 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; bh=AN0t94/kRZz/YbtHPAafShB5ICNpWSLa6+9T0ihhvOs=; b=7IUDPkotMgJgN8EhXp8chWGm3vvBQe8Yn4FINevk2zzjWVfICJ8mAefO8jUrZrhPRi wRVuFSz1y5hrnPEVz57i5O4BsiBmdbBm7ChkhO9RA+mk1exW3rhVz8EN0inBF9zJS41t Yz/YEGso/JfImRfA3veDAOzYHNsy6EWV1GSpLPkZloyXKVuXqn9krg0DSSZiAC3VJjPz SLCWgoMHVedCc3577t/8zaOCuXvDhkZvF12RsRl4fN0EEIOt6mGcpji7hyV9Zka0kzAI pzWik8a2kWgI+SGROeMX8fITtmniWFSLKeSie3QiEQng7a5foOnqrCF9zstAA6eJWVmc mUdA== X-Gm-Message-State: ACgBeo2L5wPP530p8YVUni4gSnD1RXEAdwDl43dWgwoaFol2p4JLLHF1 91BdgmpCp+YebD1DW03PErSSJ7WE2Lq6Ak4UKFI= X-Google-Smtp-Source: AA6agR4vq9RxkgAkXxnWpGF+r4zQMeCEpcixvQEMgjtR2QxA6IFg7zBotabolLt/fA4jcEyZuANGl7sNpZJhZS1R0d4= X-Received: by 2002:a17:906:4fd0:b0:73d:be5b:291d with SMTP id i16-20020a1709064fd000b0073dbe5b291dmr22568873ejw.506.1662014886930; Wed, 31 Aug 2022 23:48:06 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Jonathan Wakely Date: Thu, 1 Sep 2022 07:47:55 +0100 Message-ID: Subject: Re: Add three way lower_bound To: =?UTF-8?Q?Fran=C3=A7ois_Dumont?= Cc: "libstdc++" Content-Type: multipart/alternative; boundary="000000000000f270aa05e797febe" X-Spam-Status: No, score=-0.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE 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: Message-ID: <20220901064755.PuMx_IFpvtxM-gQaQ160fBVEY1gZGaXvNqytAQtJXtg@z> --000000000000f270aa05e797febe Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Wed, 23 Jun 2021, 21:34 Fran=C3=A7ois Dumont via Libstdc++, < libstdc++@gcc.gnu.org> wrote: > 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 <=3D> operator > defined. Afai understood what is in we can have the > __synth3way for any type as long as < exist. But I think that if <=3D> 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 ? > I don't think so. For a built-in type like int I don't think using <=3D> wi= ll be faster. For a class type type with overloaded operator< it's observable whether it gets called or not, so this patch would be a change in observable behaviour. I think we have to use < instead. > Fran=C3=A7ois > > --000000000000f270aa05e797febe--