将 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

捕获列表为空的lambda expression可以隐式转换为函数指针。但是函数指针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] A positive lambda: '+[]{}' - What sorcery is this?}

Answer 2

你的函数binsearch接受一个函数指针作为参数。 lambda 和函数指针是不同的类型：lambda 可以被视为实现 operator().

的结构的实例

请注意，无状态 lambda（不捕获任何变量的 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{};
}

从 standard algorithms library 中汲取灵感。

Answer 3

如果您对 binsearch 有任何控制权，我建议您重构它：

template <typename T, typename Predicate>
int binsearch(std::vector<T> const& vec, Predicate&& pred) {
    // This is just to illustrate how to call pred
    for (auto const& el : vec) {
        if (pred(el)) {
            // Do something
        }
    }
    return 0; // Or anything meaningful
}

另一种方法是对仿函数 objects/function pointers/whatever... 执行类型擦除，方法是将它们嵌入到 std::function<bool(T const&)> 中。为此，只需将上面的函数重写为：

template <typename T>
int binsearch(std::vector<T> const& vec, std::function<bool(T const&)> pred);

但是由于模板参数推导不进行任何转换，您需要像下面这样显式地提供您的函数：

auto my_predicate = [](int x) { return true; }; // Replace with actual predicate
std::vector<int> my_vector = {1, 2, 3, 4};
binsearch(my_vector, std::function<bool (int const&)>(my_predicate));

但是根据您对函数的描述，它的作用似乎与 std::find_if 相同。

std::vector<int> my_vector = {1, 12, 15, 13, 16};
auto it = std::find_if(std::begin(my_vector), std::end(my_vector),
                       [](int vec_el) { return !vec_el%5; });
// it holds the first element in my_vector that is a multiple of 5.
if (it != std::end(my_vector)) {
    std::cout << *it << std::endl; // prints 15 in this case
}

请注意，要进行二分查找，您需要的不仅仅是一个谓词：您需要一个定义范围顺序和目标值的谓词。

Answer 4

函数指针和 lambda 函数不是一回事。

无法将对象 t 分配给谓词 where:

 bool (*predicate)(int)

和

auto t = [](int e) -> bool { return e >= 5; });

还不如用std::function<bool(int)>。您的签名将如下所示：

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

现在这不是函数指针，如果需要的话，您需要绑定函数指针，（我假设您只使用 lambdas 没问题）

Answer 5

Why is the compiler not convinced that my lambda has the right type?

模板函数被告知推导它们的模板参数不进行转换。 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)

可选，同时用 std::function<bool(T)>.

替换函数指针

您可以在调用站点修复它。

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

您可以将 lambda 衰减为函数指针，方法是在其前面放置 + +[](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

可以在 C++14 中删除 -> typename std::decay ... 尾部 return 类型部分。

这样做的一个好处是，如果主体还使用 std::begin 和 std::end 来查找 begin/end 迭代器，binsearch 现在支持 deques，平面 C 样式数组、std::arrays、std::strings、std::vectors，甚至一些自定义类型。

将 lambda 传递给函数模板

Passing a lambda into a function template

c++

lambda

templates

function-pointers

c++11