如何对向量进行二进制搜索以查找具有特定 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.

的第三个参数的类型

我们可以利用这一点，只需将 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.}

的调用

现在就必须检查您是否有有效的迭代器而言，您有几个选择。您可以编写一个包装函数，该函数采用对迭代器的引用进行填充，如果它找到了一个项目，则 returns 。那看起来像

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.

另一个选项是在找不到项目时抛出异常。在我看来，这不是你想要做的，除非找不到该项目是一个真正的例外情况。

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

how to do a binary search on a vector to find element with certain id?

c++

vector

binary-search

c++03