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.