C++二分查找中的比较函子
The Comparison Functor inside the Binary Search in C++
我正在开发一个 C++ 程序，其中指向 class、航空公司 class 的指针是排序向量中的对象。我想确定航空公司是否已经是矢量中的指向对象。首先我用 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"
}
您对 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 returns 一个迭代器，但 binary_search returns 只是一个 bool.
综合考虑，您最好在此处使用 lower_bound。只需使用生成的迭代器来查看元素是否在逻辑上在序列中。为此，您可以使用 this question 的已接受答案。
最后，正如 BeyelerStudios 在下面的评论中非常正确地指出的那样，您应该确保 lambda 的 content 与序列的顺序一致。
当我在 IDE VS2015 中对此进行测试并阅读编译器错误时，我注意到 Ami Tavory 抢在我之前回答了这个问题。因此，也许这可以提供一些关于正在发生的事情的见解或清晰度。
在您使用 lower_bound() 进行的第一次搜索中，它确实按照 Ami 所述进行了编译，并且从搜索中返回了指向您的容器的迭代器。
在您使用 binary_search() 进行的第二次搜索中，它没有编译，正如 Ami 所说，它只是 returns 一个布尔值，就好像它是否被发现一样。至于它没有编译这里是来自Visual Studio 2015 CE
的编译器错误
1>------ Build started: Project: LambdaTemplates, Configuration: Debug Win32 ------
1> LambdaTemplates.cpp
1>c:\program files (x86)\microsoft visual studio 14.0\vc\include\algorithm(2709): error C2664: 'bool main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>::operator ()(vector_test *,std::string) const': cannot convert argument 1 from 'const std::string' to 'vector_test *'
1> c:\program files (x86)\microsoft visual studio 14.0\vc\include\algorithm(2709): note: No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called
1> c:\users\skilz80\documents\visual studio 2015\projects\Whosebugsolutions\lambdatemplates\lambdatemplates.cpp(46): note: see reference to function template instantiation 'bool std::binary_search<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<vector_test *>>>,std::string,main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>>(_FwdIt,_FwdIt,const _Ty &,_Pr)' being compiled
1> with
1> [
1> _FwdIt=std::_Vector_iterator<std::_Vector_val<std::_Simple_types<vector_test *>>>,
1> _Ty=std::string,
1> _Pr=main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>
1> ]
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
它说它无法将参数 1 从 const std::string 转换为 vector_test*
那么这里发生了什么？让我们抽象一下，暂时将 lambda 写在搜索函数调用谓词参数列表之外。所以这部分代码看起来像这样：
auto myLambda = []( vector_test* ptr, std::string name ) {
return name < ptr->get_name();
};
auto it = std::binary_search( test.begin(), test.end(), name, myLambda );
if (it)
std::cout << "It is here\n";
else
std::cout << "It is NOT here\n";
现在让我们检查编译器错误：
1>------ Build started: Project: LambdaTemplates, Configuration: Debug Win32 ------
1> stdafx.cpp
1> LambdaTemplates.cpp
1>c:\program files (x86)\microsoft visual studio 14.0\vc\include\algorithm(2709): error C2664: 'bool main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>::operator ()(vector_test *,std::string) const': cannot convert argument 1 from 'const std::string' to 'vector_test *'
1> c:\program files (x86)\microsoft visual studio 14.0\vc\include\algorithm(2709): note: No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called
1> c:\users\skilz80\documents\visual studio 2015\projects\Whosebugsolutions\lambdatemplates\lambdatemplates.cpp(45): note: see reference to function template instantiation 'bool std::binary_search<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<vector_test *>>>,std::string,main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>>(_FwdIt,_FwdIt,const _Ty &,_Pr)' being compiled
1> with
1> [
1> _FwdIt=std::_Vector_iterator<std::_Vector_val<std::_Simple_types<vector_test *>>>,
1> _Ty=std::string,
1> _Pr=main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>
1> ]
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
我们收到一条非常相似的错误消息。因此，让我们注释掉调用二进制搜索的代码行并检查编译器错误消息...
auto myLambda = []( vector_test* ptr, std::string name ) {
return name < ptr->get_name();
};
/*auto it = std::binary_search( test.begin(), test.end(), name, myLambda );
if (it)
std::cout << "It is here\n";
else
std::cout << "It is NOT here\n";
*/
现在我们没有收到任何编译器错误。所以 lambda 本身很好，但是 binary_search() 函数中发生的是这样的：
您正在向它传递 2 个前向迭代器 begin 和 end 一个搜索词或值 name，这是一个 std::string。您的前向迭代器是 vector_test pointers 的向量。并不是说您的 lambda 是错误的，只是该函数无法将 std::string 作为您的搜索查询数据类型转换为包含指向 vector_test 对象的指针的向量从而使它成为错误的 lambda 类型或错误的搜索参数。您的 class of vector_test 对象不提供任何构造函数或转换因子，或重载运算符以转换为 std::string。另请注意，在使用 binary_search 时，您的容器应该预先分类。
您的问题是 binary_search 需要一个对称比较函数，其中 LHS 或 RHS 可以是范围的内容或您要与之比较的值。
这是一道难题，但并不难。这是一个解决方案：
这是一个采用投影函数 F 和目标类型 T 的类型。
然后它隐含地获取任何可以隐式地或通过 F 投影到 T 的东西并将其包装起来：
template<class F, class T>
struct projector_t {
void const*ptr = nullptr;
T(*func)( F const* f, void const* ptr) = nullptr;
// an X that is implicitly convertible to a T:
template<class X,
class dX = std::decay_t<X>,
std::enable_if_t<
!std::is_same<dX, projector_t>{}
&& std::is_convertible<X const&, T>{}
, int> = 0
>
projector_t( X const& x ):
ptr(std::addressof(x)),
func([](F const*, void const* ptr)->T{
return *static_cast<X const*>(ptr);
})
{}
// an X that is not implicitly convertible to a T:
template<class X,
class dX = std::decay_t<X>,
std::enable_if_t<
!std::is_same<dX, projector_t>{}
&& !std::is_convertible<X const&, T>{}
, int> = 0
>
projector_t( X const& x ):
ptr(std::addressof(x)),
func([](F const* f, void const* ptr)->T{
auto px = static_cast<X const*>(ptr);
return (*f)(*px);
})
{}
projector_t( projector_t&& )=default;
projector_t( projector_t const& )=default;
projector_t& operator=( projector_t&& )=default;
projector_t& operator=( projector_t const& )=default;
T get( F const* f ) const {
return func( f, ptr );
}
};
我们现在可以编写采用投影并创建排序的代码：
template<class F, class T>
struct projected_order_t {
F f;
bool operator()( projector_t<F, T> lhs, projector_t<F, T> rhs ) const {
return lhs.get(std::addressof(f)) < rhs.get(std::addressof(f));
}
};
template<class T, class F>
projected_order_t<F, T> projected_order( F fin ) {
return {std::move(fin)};
}
projected_order<T>(lambda) 采用 lambda。它returns 一个比较函数对象。这个对象有两个参数。这些参数中的每一个，如果传递一个可以转换为 T 的对象，只需存储该转换。如果不是，它会尝试调用 lambda 将其转换为 T。然后 < 调用此操作的结果。
得到T的"action"在构造projector_t时存放在成员变量func中，非F的数据保存在成员变量func中操作存储在 void const* ptr 成员变量中。为了得到 T ，成员函数 get 接受一个 F const* 并将它和 ptr 传递给 func.
func 要么将 F 应用于 x，要么隐式转换。
projetec_order_t 提供了一个 operator()，它需要两个 projector_t，然后调用它们的 get，传入它存储的 F。这会提取代表每个参数的 T。然后比较这些T。
这项技术的一个好处是我们只需要提供投影，而不是比较，并且比较是从投影中合理巧妙地得出的。
一个简单的改进是允许它链接到不同的比较函数，默认为 std::less<T>，而不是调用 <.
我正在开发一个 C++ 程序，其中指向 class、航空公司 class 的指针是排序向量中的对象。我想确定航空公司是否已经是矢量中的指向对象。首先我用 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"
}
您对 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 returns 一个迭代器，但 binary_search returns 只是一个 bool.
综合考虑，您最好在此处使用 lower_bound。只需使用生成的迭代器来查看元素是否在逻辑上在序列中。为此，您可以使用 this question 的已接受答案。
最后，正如 BeyelerStudios 在下面的评论中非常正确地指出的那样，您应该确保 lambda 的 content 与序列的顺序一致。
当我在 IDE VS2015 中对此进行测试并阅读编译器错误时，我注意到 Ami Tavory 抢在我之前回答了这个问题。因此，也许这可以提供一些关于正在发生的事情的见解或清晰度。
在您使用 lower_bound() 进行的第一次搜索中，它确实按照 Ami 所述进行了编译，并且从搜索中返回了指向您的容器的迭代器。
在您使用 binary_search() 进行的第二次搜索中，它没有编译，正如 Ami 所说，它只是 returns 一个布尔值，就好像它是否被发现一样。至于它没有编译这里是来自Visual Studio 2015 CE
1>------ Build started: Project: LambdaTemplates, Configuration: Debug Win32 ------
1> LambdaTemplates.cpp
1>c:\program files (x86)\microsoft visual studio 14.0\vc\include\algorithm(2709): error C2664: 'bool main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>::operator ()(vector_test *,std::string) const': cannot convert argument 1 from 'const std::string' to 'vector_test *'
1> c:\program files (x86)\microsoft visual studio 14.0\vc\include\algorithm(2709): note: No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called
1> c:\users\skilz80\documents\visual studio 2015\projects\Whosebugsolutions\lambdatemplates\lambdatemplates.cpp(46): note: see reference to function template instantiation 'bool std::binary_search<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<vector_test *>>>,std::string,main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>>(_FwdIt,_FwdIt,const _Ty &,_Pr)' being compiled
1> with
1> [
1> _FwdIt=std::_Vector_iterator<std::_Vector_val<std::_Simple_types<vector_test *>>>,
1> _Ty=std::string,
1> _Pr=main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>
1> ]
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
它说它无法将参数 1 从 const std::string 转换为 vector_test*
那么这里发生了什么？让我们抽象一下，暂时将 lambda 写在搜索函数调用谓词参数列表之外。所以这部分代码看起来像这样：
auto myLambda = []( vector_test* ptr, std::string name ) {
return name < ptr->get_name();
};
auto it = std::binary_search( test.begin(), test.end(), name, myLambda );
if (it)
std::cout << "It is here\n";
else
std::cout << "It is NOT here\n";
现在让我们检查编译器错误：
1>------ Build started: Project: LambdaTemplates, Configuration: Debug Win32 ------
1> stdafx.cpp
1> LambdaTemplates.cpp
1>c:\program files (x86)\microsoft visual studio 14.0\vc\include\algorithm(2709): error C2664: 'bool main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>::operator ()(vector_test *,std::string) const': cannot convert argument 1 from 'const std::string' to 'vector_test *'
1> c:\program files (x86)\microsoft visual studio 14.0\vc\include\algorithm(2709): note: No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called
1> c:\users\skilz80\documents\visual studio 2015\projects\Whosebugsolutions\lambdatemplates\lambdatemplates.cpp(45): note: see reference to function template instantiation 'bool std::binary_search<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<vector_test *>>>,std::string,main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>>(_FwdIt,_FwdIt,const _Ty &,_Pr)' being compiled
1> with
1> [
1> _FwdIt=std::_Vector_iterator<std::_Vector_val<std::_Simple_types<vector_test *>>>,
1> _Ty=std::string,
1> _Pr=main::<lambda_79759dd0460f5d162e02d2bb1cee5db7>
1> ]
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
我们收到一条非常相似的错误消息。因此，让我们注释掉调用二进制搜索的代码行并检查编译器错误消息...
auto myLambda = []( vector_test* ptr, std::string name ) {
return name < ptr->get_name();
};
/*auto it = std::binary_search( test.begin(), test.end(), name, myLambda );
if (it)
std::cout << "It is here\n";
else
std::cout << "It is NOT here\n";
*/
现在我们没有收到任何编译器错误。所以 lambda 本身很好，但是 binary_search() 函数中发生的是这样的：
您正在向它传递 2 个前向迭代器 begin 和 end 一个搜索词或值 name，这是一个 std::string。您的前向迭代器是 vector_test pointers 的向量。并不是说您的 lambda 是错误的，只是该函数无法将 std::string 作为您的搜索查询数据类型转换为包含指向 vector_test 对象的指针的向量从而使它成为错误的 lambda 类型或错误的搜索参数。您的 class of vector_test 对象不提供任何构造函数或转换因子，或重载运算符以转换为 std::string。另请注意，在使用 binary_search 时，您的容器应该预先分类。
您的问题是 binary_search 需要一个对称比较函数，其中 LHS 或 RHS 可以是范围的内容或您要与之比较的值。
这是一道难题，但并不难。这是一个解决方案：
这是一个采用投影函数 F 和目标类型 T 的类型。
然后它隐含地获取任何可以隐式地或通过 F 投影到 T 的东西并将其包装起来：
template<class F, class T>
struct projector_t {
void const*ptr = nullptr;
T(*func)( F const* f, void const* ptr) = nullptr;
// an X that is implicitly convertible to a T:
template<class X,
class dX = std::decay_t<X>,
std::enable_if_t<
!std::is_same<dX, projector_t>{}
&& std::is_convertible<X const&, T>{}
, int> = 0
>
projector_t( X const& x ):
ptr(std::addressof(x)),
func([](F const*, void const* ptr)->T{
return *static_cast<X const*>(ptr);
})
{}
// an X that is not implicitly convertible to a T:
template<class X,
class dX = std::decay_t<X>,
std::enable_if_t<
!std::is_same<dX, projector_t>{}
&& !std::is_convertible<X const&, T>{}
, int> = 0
>
projector_t( X const& x ):
ptr(std::addressof(x)),
func([](F const* f, void const* ptr)->T{
auto px = static_cast<X const*>(ptr);
return (*f)(*px);
})
{}
projector_t( projector_t&& )=default;
projector_t( projector_t const& )=default;
projector_t& operator=( projector_t&& )=default;
projector_t& operator=( projector_t const& )=default;
T get( F const* f ) const {
return func( f, ptr );
}
};
我们现在可以编写采用投影并创建排序的代码：
template<class F, class T>
struct projected_order_t {
F f;
bool operator()( projector_t<F, T> lhs, projector_t<F, T> rhs ) const {
return lhs.get(std::addressof(f)) < rhs.get(std::addressof(f));
}
};
template<class T, class F>
projected_order_t<F, T> projected_order( F fin ) {
return {std::move(fin)};
}
projected_order<T>(lambda) 采用 lambda。它returns 一个比较函数对象。这个对象有两个参数。这些参数中的每一个，如果传递一个可以转换为 T 的对象，只需存储该转换。如果不是，它会尝试调用 lambda 将其转换为 T。然后 < 调用此操作的结果。
得到T的"action"在构造projector_t时存放在成员变量func中，非F的数据保存在成员变量func中操作存储在 void const* ptr 成员变量中。为了得到 T ，成员函数 get 接受一个 F const* 并将它和 ptr 传递给 func.
func 要么将 F 应用于 x，要么隐式转换。
projetec_order_t 提供了一个 operator()，它需要两个 projector_t，然后调用它们的 get，传入它存储的 F。这会提取代表每个参数的 T。然后比较这些T。
这项技术的一个好处是我们只需要提供投影，而不是比较，并且比较是从投影中合理巧妙地得出的。
一个简单的改进是允许它链接到不同的比较函数，默认为 std::less<T>，而不是调用 <.