std :: vector中的二進制搜索

我正在尋找向量元素到另一個向量中的位置。在這裏，我有興趣使用與binary search一樣快的實現。我有不同的長度爲100萬或更多的矢量，所以我試圖更快地實現。在我的情況std :: vector中的二進制搜索

以下幾種情況：

1）vector在我尋找排序。

2）元素我正在尋找將永遠存在即我沒有的not found的情況下，我想獲得向量元素的索引以更快的方式。

我試過下面的代碼來獲取向量元素的索引。

#include <iostream> 
#include <vector> 
#include <algorithm> 

template<class Iter, class T> 
Iter binary_find(Iter begin, Iter end, T val) 
{ 
    Iter i = std::lower_bound(begin, end, val); 
    return i; 
} 

int main() { 
    std::vector<std::string> values = {"AAAAAA","AB", "AD" ,"BCD","CD", "DD" }; 
    std::vector<std::string> tests = {"AB", "CD","AD", "DD"}; 
    for(int i=0 ; i < tests.size(); i++) { 
     int pos = binary_find(values.begin(), values.end(), tests.at(i))- values.begin(); 
    std::cout << tests.at(i) << " found at: " << pos <<std::endl; 
    } 
    return 0; 
}

我想知道如果代碼與二進制搜索實現匹配。??

有沒有更快的方法來獲得向量元素的索引？

有任何進一步的建議，以改善此代碼。

來源

2016-05-12 Aaghaz Hussain

如果您發現自己在做這麼多關鍵性能的搜索，您可能需要考慮某種關聯容器。 – TartanLlama

~~binary_find儘管沒有宣佈重返 void不返回任何東西，所以它不確定的行爲。~~

~~修復之後，假設除了排序之外沒有關於向量內容的具體知識，並且~~ 二分法搜索非常理想。

然而，其他數據結構對於基於謂詞的查找比矢量更快。如果性能至關重要，則應查看搜索樹和散列映射。由於您的密鑰是字符串，特別嘗試和指導非循環字圖可能會有效。你可能想要測量哪一個最適合你的用例。

來源

2016-05-12 10:53:37 user2079303

@AaghazHussain簡單。從函數返回一些東西。你寫了這個函數，所以你應該知道你想要返回的最好的東西。也許你打算回到'我'？ – user2079303

Do U的意思是'auto it = binary_find（values.begin（），values.end（），tests.at（i））;'然後通過'it -values.begin（）獲得位置'' –

什麼是如果我在一行中做這個問題。 –

Q1：我想知道代碼是否與二進制搜索實現匹配。（almost）是。檢查std::lower_bound，其中指出：

複雜性：

平均來說，在對數的第一和最後之間的距離：約執行LOG2（N）+1元件比較（其中，N是這個距離）。在非隨機訪問迭代器上，迭代器前進平均產生N個額外的線性複雜度。

Q2：是否有快速的方式來獲得向量元素的索引??。

這是一個相當廣泛的問題。

Q3：有任何進一步的建議，以改善此代碼。

Hello world，Code Review！

PS - 你是否編譯過代碼？它給出了一些信息，如：

warning: no return statement in function returning non-void [-Wreturn-type]

編譯啓用了警告，就像這樣：

g++ -Wall main.cpp

來源

2016-05-12 10:52:28 gsamaras

是的，我做了，我沒有得到Linux終端上的任何'警告' –

@AaghazHussain，檢查我的更新！謝謝。 – gsamaras

U R right，thanks。 –

http://www.cpluplus.com說的binary_search的行爲等同於：

template <class ForwardIterator, class T> 
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val) { 
    first = std::lower_bound(first, last, val); 
    return (first != last && !(val < *first)); 
}

所以，是的，lower_bound是您的首選武器。但是，當你採取差異時，你應該使用distance。原因是，如果有更快的方式獲取頭寸，它將被捲入該函數。

至於其他方面的改進，我建議使用C++ 14的begin和end，而不是調用一個函數，它僅用於包裝一個lower_bound（和無法正常返回值。）所以這樣我會寫下如下代碼：

auto pos = distance(lower_bound(begin(values), end(values), tests[i]), begin(values));

來源

2016-05-12 11:01:13

std :: vector中的二進制搜索

回答

相關問題