Binary search over function results in C++

Question

I am looking for a way to do a binary search over function results with a signature close to the following:

template <class ArgT,
          class ResultT,
          class TransformFunc,
          class Compare = std::less<ResultT>>
ArgT
result_upper_bound(ResultT searched, ArgT begin, ArgT end, TransformFunc tf, Compare comp);

The function is expected to return a first arg in the range [begin, end) which gives TransformFunc result that does not satisfy result > searched.

I have succeded in doing this task by implementing iterator over integers and using std::ranges::views::transform and std::ranges::upper_bound. The problim is that this solution does not work with clang becuse ranges library is not correctly supported by this compiler and will not be until clang 16 is released. By the way, the code is close to this:

...
auto argsRng = std::ranges::subrange<MyIntIt<uint64_t>>(
    MyIntIt<uint64_t>(0), MyIntIt<uint64_t>(Conditions::bigNumber));
const auto func = [](uint64_t index) {
    return Conditions::func(index);
};
auto transformed =
    std::ranges::views::transform(argsRng, func);
auto it = std::ranges::upper_bound(transformed, searchedArg);
...

boost::transform_iterator and boost::range::adaptors::transform are not exactly RandomAccess. That means their usage instead of std::ranges::views::transform makes std::lower_bound non-effective.

What are other ways of implementing this without writing binary search?

Answer 1

The following solution both compiles in clang++14 and gcc-12:

...
using IntIter = IntegerRandomAccessIterator<uint64_t>;
auto argsRng = boost::make_iterator_range<IntTter>(0, Conditions::bigNumber);
const auto func = [](uint64_t index) {
    return Conditions::func(index);
};
auto it = std::ranges::upper_bound(transformed, searchedArg, {}, func);
...

Implementation of IntegerRandomAccessIterator looks like this:

#include <boost/iterator/iterator_facade.hpp>

template <std::integral T>
class IntegerRandomAccessIterator
        : public boost::iterator_facade<
            IntegerRandomAccessIterator<T>, T,
            boost::random_access_traversal_tag, T> {
public:
    using type = IntegerRandomAccessIterator<T>;
public:
    IntegerRandomAccessIterator(T initial = 0) : _val(initial) {};
    IntegerRandomAccessIterator(const type& other) = default;
protected:
    std::ptrdiff_t
    distance_to(const type& rhs) const   { return rhs._val - _val; };
    void advance(std::ptrdiff_t n)       { _val += n; };
    T dereference() const                { return _val; };
    bool equal(const type& other) const  { return _val == other._val; };
    void increment()                     { ++_val; };
    void decrement()                     { --_val; };
public:
    T operator[](std::ptrdiff_t n) const { return _val + n; }
private:
    T _val;
private:
    friend class boost::iterators::iterator_core_access;
};

template <std::integral T>
struct std::iterator_traits<IntegerRandomAccessIterator<T>> {
    using iterator_category = std::random_access_iterator_tag;
    using difference_type = std::ptrdiff_t;
    using value_type = T;
    using reference = T;
};

It models std::random_access_iterator.

Standard library solution is

...
auto argsRng = std::ranges::iota_view(uint64_t{0}, Conditions::bigNumber);
const auto func = [](uint64_t index) {
    return Conditions::func(index);
};
auto it = std::ranges::upper_bound(transformed, searchedArg, {}, func);
...

So I prefer using first variant with IntegerRandomAccessIterator<uint64_t> and boost::make_iterator_range and to remove this replacing with std::ranges::iota_view when ranges will finally work in clang.