c++ - 如何将迭代器传递给 std::lower_bound() 比较函数？

Question

在以下声明中借自 cplusplus.com

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

comp() 应该像这样:

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

问题是我不想在那里传递值类型。我想将迭代器传递给它，然后 shift them 好的，在取消引用之前，只需在 comp() 中静静地盯着它们看。 (更不用说 - 记录它们。)是否有任何解决方法？

当然，我可以编写自己的容器类，它有自己的迭代器，当然我也可以编写自己的std::lower_bound()实现。这两种选择都令人不快。

Answer 1

来自std::lower_bound doc ，可以阅读 bool comp(const Type1 &a, const Type2 &b);:

The type Type1 must be such that an object of type ForwardIt can be dereferenced and then implicitly converted to Type1. The type Type2 must be such that an object of type T can be implicitly converted to Type2. ​

这意味着，std::lower_bound 将始终调用 comp 并将范围中的元素作为左侧参数，并且 value作为右侧参数。如果您的搜索范围是连续范围(意味着您正在处理 std::vector、std::array、std::valarray , std::string, ..., or C-style arrays), 你可以根据范围的开始和 comp 的左边之间的距离设计一个迭代器参数:

auto v = std::vector<int>{0, 1, 2, 3, 4, 5};

auto comp = [&v](const int &lhs, const int &rhs)
{
    auto it_lhs = cbegin(v) + std::distance(std::addressof(*cbegin(v)), &lhs);
    return *it_lhs < rhs;
};

std::cout << *std::lower_bound(begin(v), end(v), 2, comp) << "\n";