lower_bound執行二進制搜索

這裏我使用std::lower_bound()創建了一個二進制搜索功能。如下所示。這工作正常，如果我通過std::pair，但我只想執行二進制搜索pair的第一個值。我在考慮在lower_bound()的Comp參數中可以做到這一點，但不能完全確定如何。lower_bound執行二進制搜索

即我的向量看起來像下面。

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; 

}

來源

2015-05-20 CodersSC

任何你爲什麼定義函數作爲模板時，類型kn擁有？這只是使問題複雜化。 –

@MarkRansom因爲我需要返回一個iterator.noramal二分查找返回一個bool – CodersSC

夫婦備註：1）'lower_bound'預計'vector'預先被排序（匹配比較函數），2）標準庫支持比較如果'a.first :: min（）}）;'沒有定義自己的比較（但它會被我懷疑的NaN拋出）。 –

第二個定義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方式與lambda表達式，如果你想有一個乾淨的代碼，並且不想聲明附加功能：

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

來源

2015-05-20 14:49:00 FalconUA

是的，你的正確謝謝你。 – CodersSC

@TonyD哦，謝謝你的建議，我已經將這個名字編輯爲'tuple2'。 – FalconUA

感謝這一點，我必須做的唯一改變是我必須做'！（（value.first CodersSC

使用自定義比較函數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);

來源

2015-05-20 14:39:34 Steephen

有一個獨立的函數'std :: lower_bound'，爲什麼你說他必須創建一個'std :: set'？ – Slava

它的確如此：http://en.cppreference.com/w/cpp/algorithm/lower_bound – Slava

@Slava我將頁面引用爲'std :: set：lower_bound'並且感到困惑。更正了答案。 – Steephen

使用它您需要添加比較類的功能，因爲它在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; });

來源

2015-05-20 14:48:31 Slava

lower_bound執行二進制搜索

回答

相關問題