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.

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. An implementation which sleeps for n seconds
prior to running a classic binary search would be compliant. One might
argue that a user could depend on the exact number of steps performed, but
the guarantees aren't sufficiently strict for that either: the standard
says "at most" and not "exactly". I believe we'd be better served by looser
complexity guarantees (why not use Big O notation throughout?) and more
freedom for implementors to optimise.

Having preached all this, what I'm suggesting is much less impactful. I'd
be happy if the wording for the lower_bound guarantees were loosened to
allow the use of algorithms with better overall complexity. Perhaps it
could say something like "at most log(last - first)+O(1) comparisons for
random-access iterators, or O(log(last - first)) comparisons for other
iterator types".

On Fri, 19 Jan 2024 at 19:41, Phil Endecott via Std-Proposals <
std-proposals_at_[hidden]> wrote:

> I?ri Chaer <iuri.chaer_at_[hidden]>
> > The current complexity guarantee for std::lower_bound states "At most
> > log(last - first)+O(1) comparisons and projections" for all iterator
> types,
> > pretty much enforcing the use of vanilla binary search, even if with
> > non-random-access iterators that means 2*n iterator mutations. I've
> > recently had a libc++ proposal for using one-sided binary search to
> reduce
> > that cost to n iterator mutations rejected (
> > https://github.com/llvm/llvm-project/pull/75230#issuecomment-1852637040
> ),
> > because it meant that we'd have at most 2*log(n) comparator calls. I
> have a
> > strong feeling that this is not what the committee had intended.
> >
> > The solution from that proposal would have had a potentially interesting
> > impact even for random-access iterators, because, although the average
> > complexity is log(n) comparisons, it ranges from a single comparison to
> > 2*log(n), and you can do a sequential scan in O(n) instead of the
> > O(n*log(n)) that vanilla binary search would yield. It's not completely
> > clear to me which would be more interesting in general, perhaps allowing
> > implementors to decide even for random access iterators would be a good
> > thing.
> >
> > What do you think of the idea of loosening the std::lower_bound
> comparator
> > complexity requirements for non-random iterators to allow changes like
> the
> > one I proposed?
>
>
> Personally I'd prefer something like this to have a name that told me
> what algorithm it actually is, e.g. one_sided_lower_bound.
>
> I have used something like this to get the O(n) local sequential scan
> that you refer to; it would be useful to have.
>
>
>
> Regards, Phil.
>
>
>
>
> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
>