在这里,我使用 std::lower_bound()
创建了一个二进制搜索函数。如下图。如果我传递 std::pair
,这会很好地工作,但是我只想对 pair
的第一个值执行二进制搜索。我认为在 lower_bound()
的 Comp
参数中可以做到这一点,但不完全确定如何做到。
即我的 vector 如下所示。
std::vector<std::pair<int,double>> v;
我只想比较第一个值,即 int
。
template<class ForwardIt, class T>
ForwardIt binary_searcht(ForwardIt first, ForwardIt last, const T& value)
{
ForwardIt i = std::lower_bound(first, last, value);
if (i != last && !(value < *i))
return i;
else
return last;
}
最佳答案
您需要像在 std::lower_bound
中那样向您的函数添加比较类:
template<class ForwardIt, class T, class Compare>
ForwardIt binary_searcht(ForwardIt first, ForwardIt last, const T& value, Compare cmp)
{
ForwardIt i = std::lower_bound(first, last, value, cmp);
if (i != last && !cmp(value, *i))
return i;
else
return last;
}
typedef std::pair<int,double> mypair;
std::vector<mypair> v;
auto f = binary_searcht( v.begin(), v.end(), value,
[]( const mypair &p1, const mypair &p2 ) { return p1.first < p2.first; } );
关于c++ - lower_bound 执行二进制搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30352231/