std::upper_bound with iterator hint? about algorithm HOT 3 OPEN

Does boost.algorithm have iterator hints for binary searches?
It does not; in fact, it doesn't have upper_bound at all.

However, that's an interesting idea. I'll think about it.
At the very least, you should be able to bisect the search range based on the hint.

from algorithm.

I've stumbled on a similar issue. I would like to do a binary search, but would like to add a hint as to where to start. However, if you think about it, you could to do the following:

auto new_begin = std::upper_bound(current_begin, current_end, test());
current_begin = new_begin;

So that when you do the next call to std::upper_bound you'd ignore everything before the last search results. This is like stating the initial partition, which I think is the same thing, right?

from algorithm.

In my case, there is no hard guarantee that the desired element is strictly after the hint element. There is only a good reason to believe that the desired element is close to the hint element.

My mental model of this is closer to branch prediction. Fast if it’s right, not a disaster if it’s wrong.

from algorithm.