Can I use std::upper_bound without an underlying container?

Question

I have a range of integers [start, end] and a non-decreasing monotonic function f(i). So conceptually, I have a non-decreasing sequence [f(start), f(start + 1), .. , f(end)]. Can I use std::upper_bound on that sequence to find the first element i in the range that holds f(i) > some_value ?

Conceptually, I'd like something like this:

std::upper_bound(start, end + 1, some_value, [&](int lhs, int rhs) { 
    return f(lhs) < f(rhs);
});

But this doesn't compile because start and end + 1 do not meet the requirements of forward iterators.

Answer 1

The short answer is yes, since std::upper_bound works on iterators, not on containers. But iterators themselves are instances of corresponding class (for example, std::vector<int>::iterator or whatnot).

If you construct some specific class that will meet the requirements of ForwardIterator not being actually bound to some sort of container, while still meaning something (for example, if you want to generate your sequence procedurally), it should work just fine.

Note that simple integer will not do the trick. On the other hand, a class, whose objects hold the value of your function for a particular argument value (with some additional batteries), will.

Answer 2

There are basically two answers:
Would it work by the standard or would it work with all practical implementations of the STL?

By the standard, as T.C. pointed out already, there are some strict requirements on iterators, especially that *it has to return a (possibly const) reference to value_type (which we would satisfy by returning the reference to a member of the iterator), but we also need that for it1 == it2, *it1 and *it2 are references bound to the same object, which is only possible if we have a distinct object for every number in the range.

If you want to do use this idea in practice, I don't believe any implementation of std::upper_bound or similar methods actually relies on this reference equality, so you could just use a class that encapsulates an integer as an iterator, only overloading the necessary methods. As far as I can see, boost::irange fulfills these requirements

As you can see, this is not strictly standard-compliant, but I see no reason why any implementation of binary search should rely on such strong requirements for the iterator, if the underlying 'storage' is const anyway.