How to to pass iterators to the std::lower_bound() comparison function?

Question

In the following declaration borrowed from cplusplus.com

template<class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

comp() should resemble something like this:

template<class T>
bool comp(const T& v1, const T& v2);

The problem is that I don't want to pass the value type there. I want to pass iterators to it and then shift them okay, just stare at them silently inside comp() before dereferencing. (Not to mention - log them.) Is there any workaround for this?

Of course, I can write my own container class with its own iterators, and of course I can write my own implementation of std::lower_bound(). Both options are rather unpleasant.

Answer 1

From the doc:

The signature of the predicate function should be equivalent to the following:

bool pred(const Type1 &a, const Type2 &b);

The signature does not need to have const &, but the function must not modify the objects passed to it.

So you can not, and should not, do this. std::lower_bound has specific purpose and it should not modify the input in any way. Write your own function for this purpose.

---

If you need indices only, and your container stores its elements in linear, continuous block of memory, you could do this (example with std::vector):

std::vector<...> vec;
...
const auto* firstElemPtr = &vec[0];
std::lower_bound(vec.begin(), vec.end(), key, [firstElemPtr](const auto& left, const auto& right) -> bool {
  size_t index = &left - firstElemPtr;
  // now do the comparison
});