将lambda传递给函数模板

Question

我正在学习C++,我正在尝试实现一个二进制搜索函数,它找到谓词所在的第一个元素.函数的第一个参数是向量,第二个参数是一个计算给定元素的谓词的函数.二进制搜索功能如下所示:

template <typename T> int binsearch(const std::vector<T> &ts, bool (*predicate)(T)) {
    ...
}

如果像这样使用,这可以按预期工作:

bool gte(int x) {
    return x >= 5;
}

int main(int argc, char** argv) {
    std::vector<int> a = {1, 2, 3};
    binsearch(a, gte);
    return 0;
}

但是,如果我使用lambda函数作为谓词,我会收到编译器错误:

search-for-a-range.cpp:20:5: error: no matching function for call to 'binsearch'
    binsearch(a, [](int e) -> bool { return e >= 5; });
    ^~~~~~~~~
search-for-a-range.cpp:6:27: note: candidate template ignored: could not match 'bool (*)(T)' against '(lambda at
      search-for-a-range.cpp:20:18)'
template <typename T> int binsearch(const std::vector<T> &ts,
                          ^
1 error generated.

上面的错误是由

binsearch(a, [](int e) -> bool { return e >= 5; });

怎么了？为什么编译器不相信我的lambda具有正确的类型？

Answer 1

您的函数binsearch将函数指针作为参数.甲拉姆达和一个函数指针是不同的类型:一个lambda可以被认为是实现结构的实例operator().

请注意,无状态lambdas(不捕获任何变量的lambda)可以隐式转换为函数指针.由于模板替换,隐式转换不起作用:

#include <iostream>

template <typename T>
void call_predicate(const T& v, void (*predicate)(T)) {
    std::cout << "template" << std::endl;
    predicate(v);
}

void call_predicate(const int& v, void (*predicate)(int)) {
    std::cout << "overload" << std::endl;
    predicate(v);
}

void foo(double v) {
    std::cout << v << std::endl;
}

int main() {
    // compiles and calls template function
    call_predicate(42.0, foo);

    // compiles and calls overload with implicit conversion
    call_predicate(42, [](int v){std::cout << v << std::endl;});

    // doesn't compile because template substitution fails
    //call_predicate(42.0, [](double v){std::cout << v << std::endl;});

    // compiles and calls template function through explicit instantiation
    call_predicate<double>(42.0, [](double v){std::cout << v << std::endl;});
}

您应该使您的功能binsearch更通用,例如:

template <typename T, typename Predicate>
T binsearch(const std::vector<T> &ts, Predicate p) {

    // usage

    for(auto& t : ts)
    {
        if(p(t)) return t;
    }

    // default value if p always returned false

    return T{};
}

从标准算法库中获取灵感.

Answer 2

具有空捕获列表的lambda表达式可以隐式转换为函数指针.但函数指针predicate正在T为它的参数,需要进行推断.模板类型扣除不考虑类型转换,T不能推断; 正如错误消息所述,候选模板(即binsearch)被忽略.

您可以使用它operator+来实现这一点,它将lambda转换为函数指针,它将被传递给binsearch稍后,然后T将成功推导出^[1].

binsearch(a, +[](int e) -> bool { return e >= 5; });
//           ~

当然你可以static_cast明确使用:

binsearch(a, static_cast<bool(*)(int)>([](int e) -> bool { return e >= 5; }));

注意,如果你改变predicate的类型是独立的T,即bool (*predicate)(int)传递具有空捕获列表的lambda也会起作用; lambda表达式将隐式转换为函数指针.

另一个解决方案是将参数类型从函数指针更改为std::function,这对于仿函数更为通用:

template <typename T> int binsearch(const std::vector<T> &ts, std::function<bool (typename std::vector<T>::value_type)> predicate) {
    ...
}

然后

binsearch(a, [](int e) -> bool { return e >= 5; });

^{[1] 一个积极的lambda:'+ [] {}' - 这是什么巫术？}

Answer 3

为什么编译器不相信我的lambda具有正确的类型？

被告知模板函数推断其模板参数不进行转换.lambda不是函数指针,因此无法推断出该T参数.由于所有函数参数都独立地推导出它们的模板参数(除非扣除被扣除),否则会导致错误.

您可以执行许多修复.

您可以修复模板功能.

template <class T>
int binsearch(const std::vector<T> &ts, bool (*predicate)(T))

用一个Predicate predicate或替换函数指针,Predicate&& predicate并保持正文不变.

template <class T, class Predicate>
int binsearch(const std::vector<T> &ts, Predicate&& predicate)

使用扣除阻止:

template<class T>struct tag_t{using type=T;};
template<class T>using block_deduction=typename tag_t<T>::type;
template <class T>
int binsearch(const std::vector<T> &ts, block_deduction<bool (*)(T)> predicate)

可选地用a替换函数指针std::function<bool(T)>.

您可以在呼叫站点修复它.

你可以T手动传递binsearch<T>(vec, [](int x){return x<0;}).

您可以衰减拉姆达函数指针与把一个+在它前面+[](int x)...或static_cast<bool(*)(int)>(... ).

最好的选择是Predicate一个.这也是标准库代码的作用.

我们还可以更进一步,使您的代码更通用:

template <class Range, class Predicate>
auto binsearch(const Range &ts, Predicate&& predicate)
-> typename std::decay< decltype(*std::begin(ts)) >::type

在-> typename std::decay...后返回类型部分可以在C++ 14被消除.

这样做的好处是,如果正文还使用std::begin和std::end查找开始/结束迭代器,binsearch现在支持deques,扁平C样式数组,std::arrays,std::strings,std::vectors,甚至一些自定义类型.