如何将迭代器传递给 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);

问题是我不想在那里传递值类型。我想将迭代器传递给它然后 ~~移动它们~~ 好吧，在取消引用之前在 comp() 中静静地盯着它们看。（更不用说 - 记录它们。）对此有任何解决方法吗？

当然，我可以写自己的容器class，有自己的迭代器，当然也可以写自己的实现std::lower_bound()。两种选择都比较不愉快。

Answer 1

来自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.

所以你不能也不应该这样做。 std::lower_bound 具有特定用途，不应以任何方式修改输入。为此目的编写您自己的函数。

如果您只需要索引，并且您的容器将其元素存储在线性、连续的内存块中，您可以这样做（以 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
});

Answer 2

来自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、...或 C 样式数组），您可以根据范围的开始和 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";

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

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

c++

std

stl-algorithm