How to make ranges::binary_search (heterogeneous search in particualar) work with references

Question

I am trying to make reference wrappers work with heterogeneous search, and make it ranges-compliant. Here is the snippet I want to work:

struct addressable { int address; };

template <typename T>
struct ref : std::reference_wrapper<T> {
    // comparisons for heterogeneous search
}

template <typename T>
ref<T> wrap_ref(T& value) { return {value}; }

int main() {
    const std::vector<addressable> nums { {1}, {2}, {3}, {4}, {5}, {6} };
    ref_vec<const addressable> num_refs;
    for (const auto& num : nums) { num_refs.push_back(wrap_ref(num)); }
    const auto found = std::ranges::binary_search(num_refs, 2); // doesn't work
}

The heterogeneous search is working fine for classic std algorithms (for them it is enough to implement < and ==. Now, ranges ones have more stringent requirements, so I tried implementing strong ordering operations in the following manner:

template <typename T>
struct ref : std::reference_wrapper<T> {
    auto operator<=>(const ref<T>& other) const {
        return std::reference_wrapper<T>::get().address <=> other.get().address;
    }
    
    bool operator==(const ref<T>& other) const {
        return std::reference_wrapper<T>::get().address == other.get().address;
    }

    // heterogeneous comparisons
    friend auto operator<=>(const ref<T>& l, const int r) { return l.get().address <=> r; }
    friend auto operator<=>(const int l, const ref<T>& r) { return l <=> r.get().address; }
    friend bool operator==(const ref<T>& l, const int r) { return l.get().address == r; }
    friend bool operator==(const int l, const ref<T>& r) { return l == r.get().address; }
};

This, however, leads to a number of compilation errors, which seem to warn about indirect_strict_weak_order and strict_weak_order concepts not being resolved. I do not understand why aren't they resolved - we have strong order, and references are, to my understanding, properly supported for the indirect part. What am I missing?

Here is compiler explorer example: https://godbolt.org/z/8xaWfah9b.

Answer 1

The heterogeneous search is working fine for classic std algorithms (for them it is enough to implement < and ==. Now, ranges ones have more stringent requirements

The ranges version uses ranges::less for comparison by default, which has stricter syntactic and semantic requirements for comparison types than the std version, but you can still pass std::less as a comparator that only requires expressions lhs < rhs to be valid

const auto found = ra::binary_search(num_refs, 2, std::less{});

Demo

Answer 2

Ranges algorithms don't work with heterogenous comparisons. Use a projection:

std::ranges::binary_search(num_refs, 2, {}, [](ref<const addressable> r) {
    return r.get().address;
});

In this specific case, you can't use ranges::less{}(2, ref<const addressable>(...)), because ranges::less requires the two arguments to be totally_ordered with each other, which requires them to have a common_reference. There is no common reference between const int& and const ref<const addressable>&, unless you add a conversion from ref<const addressable> to const int&.