如何对向量进行二分查找以找到具有特定id的元素？

Question

我有一个已排序的向量,现在我想从该向量中找到具有特定id的元素.std::binary_search只是告诉我元素是否存在,所以我使用std::lower_bound:

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

struct Foo {
    int id; 
    // ... more members ... //
    Foo(int id) : id(id) {} 
};

bool compareById(const Foo& a,const Foo& b) { return a.id < b.id; }

int main(){
    std::vector<Foo> vect;
    vect.push_back(10);
    vect.push_back(123);
    vect.push_back(0);
    std::sort(vect.begin(),vect.end(),compareById);
    int id_to_find = 1;
    std::vector<Foo>::iterator f = std::lower_bound(vect.begin(),vect.end(),Foo(id_to_find),compareById);
    if (f != vect.end() && f->id == id_to_find) { std::cout << "FOUND"; }
}

这种方式有效,但我强烈不喜欢它,我必须创建一个Foo(id_to_find)传递给它std::lower_bound,然后我必须仔细检查我得到的元素是否真的是我正在寻找的元素.

我想我可以find_if用来避免创建那个多余的实例,但据我所知,find_if它只是线性的,并没有使用被排序的向量.我有点惊讶,我找不到正确的任务算法,我已经在考虑编写自己的算法了.

这样做的人是什么？

Answer 1

你可以做几件事让你的生活更轻松.第一件事是比较器不需要为第一和第二参数提供相同的参数.要求是第一个参数必须可以隐式转换为解除引用的迭代器,第二个参数需要隐式转换为传递给的第三个参数的类型lower_bound.

我们可以利用这个,只需将a int作为第二个参数,这样就不必构造一个Foo.这允许我们做出compareFooById类似的:

bool compareFooById(const Foo& a,const int& b) { return a.id < b; }

然后我们现在就可以使用它:

std::vector<Foo>::iterator f = std::lower_bound(vect.begin(), vect.end(), id_to_find, compareFooById);

^{请注意,我在这里添加了一个新功能.你使用compareById,std::sort所以我不能只是改变它,因为这将打破调用sort.}

现在,只要检查你是否有一个有效的迭代器,你有几个选择.您可以编写一个包装器函数,该函数接受一个迭代器的引用来填充,如果找到一个项目则返回.那看起来像

template<typename It, typename Value, typename Comp
bool my_binary_search(It begin, It end, Value val, Comp c, It& ret)
{
    ret = std::lower_bound(begin, end, val, c);
    return ret != end;
}

然后你称之为

std::vector<Foo>::iterator f;
if(my_binary_search(vect.begin(), vect.end(), id_to_find, compareFooById, f))
    //do something with f.

另一个选项是如果找不到该项,则抛出异常.在我看来,这不是你想要做的事情,除非没有找到该项目是一个真正的例外情况.