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中的二进制搜索

回答

相关问题