c++ - C++二分查找中的比较仿函数

Question

我正在开发一个 C++ 程序，其中指向类(航空公司类)的指针是排序 vector 中的对象。我想确定航空公司是否已经是 vector 中的指向对象。首先我用 lambda 应用 lower_bound，它是成功的。然后我用相同的 lambda 实现 binary_search，但是它失败了。错误信息如下，

__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp&     __value_, _Compare __comp)
{
   __first = __lower_bound<_Compare>(__first, __last, __value_, __comp);
   return __first != __last && !__comp(__value_, *__first);
}
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/algorithm:4139:13: No matching function for call to object of type '(lambda at /Users/.../Desktop/Programming/C++/trial/trial/main.cpp:188:61)'

看起来 lambda 在二进制搜索中不起作用。你能帮我弄清楚为什么它没有吗？非常感谢!

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

using namespace std;

class vector_test{
public:
    vector_test(string name_) : name(name_) {}
    const string get_name() const {return name;}
private:
    string name;
};

typedef vector<vector_test*> vector_container;

int main()
{
    vector_container test;
    string name = "Delta";
    vector_test *vt1 = new vector_test{"Sothwest"};
    vector_test *vt2 = new vector_test{"Delta"};
    vector_test *vt3 = new vector_test{"Hawaii"};
    vector_test *vt4 = new vector_test{"United"};
    test = {vt2, vt3, vt1, vt4};
    auto iter = lower_bound(test.begin(), test.end(), name, [](vector_test* ptr, string name) {
        return  ptr->get_name()< name;});
    if (iter != test.end() && (**iter).get_name() == name)
        cout << "It exits!\n";
    else
        cout << "It doesn't exit!\n"
    auto it = binary_search(test.begin(), test.end(), name, [](vector_test* ptr, string name) {
        return name < ptr->get_name();});
    if (it)
        cout << "It exits!\n";
    else
        cout << "It doesn't exit!\n"
 }

Answer 1

您对 lower_bound 的调用会构建，但对 binary_search 的调用不会。这是因为预期比较仿函数的不同。

对于 lower_bound，它 is :

The type Type1 must be such that an object of type ForwardIt can be dereferenced and then implicitly converted to Type1. The type Type2 must be such that an object of type T can be implicitly converted to Type2. ​

对于binary_search，它是is :

The types Type1 and Type2 must be such that an object of type T can be implicitly converted to both Type1 and Type2, and an object of type ForwardIt can be dereferenced and then implicitly converted to both Type1 and Type2. ​

您的比较仿函数符合第一个要求，但不符合第二个要求。

---

您似乎错过的另一件事是 lower_bound 返回一个迭代器，但 binary_search 仅返回一个 bool。

---

综合考虑，您最好在此处使用 lower_bound。只需使用生成的迭代器来查看元素是否在逻辑上在序列中。您可以使用已接受的答案 this question为此。

最后，正如 BeyelerStudios 在下面的评论中非常正确地指出的那样，您应该确保您的 lambda 的内容与您的序列顺序一致。