lower_bound для выполнения двоичного поиска

Question

Здесь я создал функцию бинарного поиска, используя std::lower_bound(). Как показано ниже. Это отлично работает, если я передаю std::pair, однако я хочу просто выполнить бинарный поиск по первому значению pair. Я думаю, что в параметре Complower_bound() это можно сделать, но не совсем точно.

i.e мой вектор выглядит следующим образом.

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; 

} 

Answer 1

Второе определение от std::lower_bound:

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

Итак, вы можете просто написать свою собственную функцию сравнения пар и использовать ее. Ваша функция шаблона будет выглядеть следующим образом:

template<class ForwardIt, class T, class Compare> 
ForwardIt binary_searcht(ForwardIt first, ForwardIt last, const T& value, Compare comp) 
{ 
    ForwardIt i = std::lower_bound(first, last, value, comp); 
    if (i != last && !(value < *i)) 
     return i; 
    else 
     return last; 
} 

И, если вы хотите использовать его для элементов std::vector< std::pair<int,double> >, вы должны назвать его таким образом:

bool compare(std::pair<int, double> a, std::pair<int, double> b) { 
    return a.first < b.first; 
} 
binary_searcht(v.begin(), v.end(), value, compare); 

Или в гиковской -std=c++11 пути с лямбда-выражениями, если вы хотите иметь чистый код и не хотите объявлять дополнительные функции:

typedef std::pair<int, double> tuple2; 
auto result = binary_searcht(v.begin(), v.end(), 
    [](tuple2 &a, tuple2 &b) { return a.first < b.first; }); 

Answer 2

Используйте пользовательскую функцию сравнения comp и использовать его с std::lower_bound

bool comp(std::pair<int , double> &x , std::pair<int , double> &y) 
{ 
    return x.second < y.second; 
} 
std::lower_bound(v.begin(),v.end(),value, comp); 

Answer 3

Вам нужно добавить сравнивать класс к вашей функции, как это сделано в 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; });