Date: Fri, 19 Jan 2024 16:28:24 -0500
On Fri, Jan 19, 2024 at 4:00 PM Iúri Chaer via Std-Proposals
<std-proposals_at_[hidden]> wrote:
>
> Wouldn't that go counter to the design philosophy of the STL? lower_bound is not the name of an algorithm, but of the action -- the algorithm behind it in all the mainline implementations is the classic binary search, but that's not explicit in its name. What I'm proposing is loosening the complexity guarantees to allow implementing it with a different algorithm which scales better.
"Scales better" in certain situations. That's why it ought to be a
different function; so that people can pick what they want.
> Less importantly, but still relevant and slightly aggravating, the specific algorithm I was proposing has the same average complexity in terms of comparisons as classic binary search. The complexity guarantee in the standard is so strict that neither of these facts -- that it has the same average complexity in terms of comparisons, or that it offers better overall worst-case complexity -- make it acceptable.
>
> The crux of the problem is the fact that the complexity guarantee is defined in terms of comparisons, while for non-random-access iterators that complexity is dominated by iterator mutations.
>
> I would argue that the strictness in terms of constant factors is, in itself, not meaningful in practice: there is no enforcement of the level of optimisation for C++ compilers, nor of the specific way in which each step is implemented by a library, so the constants involved are _already_ implementation-dependent.
And yet, you couldn't get your change into a standard library
implementation precisely because they enforced what the standard
requires. That sounds like the standard is at least someone
"meaningful in practice".
<std-proposals_at_[hidden]> wrote:
>
> Wouldn't that go counter to the design philosophy of the STL? lower_bound is not the name of an algorithm, but of the action -- the algorithm behind it in all the mainline implementations is the classic binary search, but that's not explicit in its name. What I'm proposing is loosening the complexity guarantees to allow implementing it with a different algorithm which scales better.
"Scales better" in certain situations. That's why it ought to be a
different function; so that people can pick what they want.
> Less importantly, but still relevant and slightly aggravating, the specific algorithm I was proposing has the same average complexity in terms of comparisons as classic binary search. The complexity guarantee in the standard is so strict that neither of these facts -- that it has the same average complexity in terms of comparisons, or that it offers better overall worst-case complexity -- make it acceptable.
>
> The crux of the problem is the fact that the complexity guarantee is defined in terms of comparisons, while for non-random-access iterators that complexity is dominated by iterator mutations.
>
> I would argue that the strictness in terms of constant factors is, in itself, not meaningful in practice: there is no enforcement of the level of optimisation for C++ compilers, nor of the specific way in which each step is implemented by a library, so the constants involved are _already_ implementation-dependent.
And yet, you couldn't get your change into a standard library
implementation precisely because they enforced what the standard
requires. That sounds like the standard is at least someone
"meaningful in practice".
Received on 2024-01-19 21:28:34