将 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有正确的类型？

- rodion

---

将 bool (*predicate)(T) 改为 std::function<bool(T)> - Evgeniy

关于函数参数的小提示 - 你会注意到 std::lower_bound（你正在重新实现它）采用了一对迭代器而不是容器作为其参数。这使得它能够与任何类型的容器一起工作，或者容器的子集，甚至是标准库设计者尚未考虑过的范围。当你让你的代码在 std::vector 上工作后，我强烈建议你朝着这个方向使它更加通用；我保证你会学到一些东西！ - Toby Speight

@TobySpeight 他需要的不仅仅是一个谓词。这个谓词必须是一个有序关系，并且他还需要一个目标值。 - Rerito

额，我的意思是 std::find_if()，而不是 std::lower_bound()。两者都很有教育意义，自己实现也是很好的练习，所以其他部分仍然适用。 - Toby Speight

@Evgeniy 绝对不要这样做。这已经是一个模板，使用类型擦除在这里没有任何收益。 - Quentin

Answer 1

您的函数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{};
}

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

- rocambille

---

谢谢！我认为这比我想象的要宽松一些。例如，您的方法将允许传递一个整数向量和一个将字符（而不是整数）映射到布尔值的谓词。虽然对于我的用例可能没有关系。 - rodion

如果您在将一个 int 传递给一个接受 char 的谓词时出现了这样的情况，您的编译器应该会抱怨精度丢失。如果没有，那就换一个编译器吧 ;) - rocambille

无状态的lambda表达式将转换为函数指针。如果没有模板参数T，问题中的示例将会编译。在这方面，答案是误导性的，我认为。 - ComicSansMS

@ComicSansMS 我编辑了我的回答。现在是否更清晰明了？ - rocambille

@MSalters 已添加 ;) - rocambille

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表达式：'+[]{}' - 这是什么魔法？}

- songyuanyao

---

静态转换为什么更易读？虽然有更多的文字，但所有的文本都在重复旁边所说的内容。可靠的魔法不需要详细解释自己的工作原理。 - Yakk - Adam Nevraumont

阅读内容的增加并不意味着阅读难度的增加。只有C++专家才能理解的神奇特性（例如箭头和lambda函数）并不易于理解。 - David Haim

我非常喜欢"+"的魔力，但我刚刚意识到如果lambda捕获了局部变量，则无法将其转换为函数指针。尽管如此，我从你的答案中学到了很多。 - rodion

@DavidHaim：Lambda不是“只有C++大师才能理解的神奇功能”。任何使用C++编程的人都应该熟悉Lambda。+衰减Lambda确实很神奇，但是如果你不知道它的作用，那就没什么关系了。如果你看一下这行代码，它实际上做了它看起来要做的事情如果你不理解其中的魔法。它是如何做到的是神奇的，但是非大师不需要知道魔法就可以理解这行代码。你写一个快速的for()循环，就像你不需要了解向量化一样，也不需要知道+的工作原理。 - Yakk - Adam Nevraumont

Lambda表达式确实是基础，这一点毋庸置疑。将+用作lambda函数转换器非常特定且不常见。我只是看不出为什么要使用大多数C++开发人员并不真正了解的东西，而不是非常熟悉和常见的static_cast。但我想我无法说服你。 - David Haim

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)

可以选择将函数指针替换为std::function<bool(T)>。

您可以在调用点进行修复。

您可以手动传递Tbinsearch<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

-> typename std::decay ... trailing return type部分在C++14中可以省略。

这样做的好处是，如果函数体还使用了std::begin和std::end来查找起始/结束迭代器，那么binsearch现在支持deque、扁平的C风格数组、std::array、std::string、std::vector甚至一些自定义类型。

- Yakk - Adam Nevraumont

Answer 4

如果您可以控制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
}

---

另一种方法是对你的函数对象/函数指针等进行类型擦除，将它们嵌入到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
}

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

- Rerito

---

转换为std::function在这里无法解决问题。 - ComicSansMS

@ComicSansMS 抱歉，那句话有误导性... 为了更清晰明了，我已经修改了它。 - Rerito

@Rerito 抱歉，但我认为这仍然是误导性的。切换到std::function允许我传递有状态的lambda（就像使用Predicate模板参数的第一种解决方案一样）。但它根本没有解决问题：如果我将T深埋在参数类型中，那么模板参数推断会失败。这在函数指针和std::function方法中都会发生。 - ComicSansMS

@ComicSansMS 我不太明白你的意思。你能提供一个例子给我做参考吗？ - Rerito

@ComicSansMS 是的，你指的是模板参数推导不进行任何转换。我编辑了我的答案以反映这一点。 - Rerito

Answer 5

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

一个对象t不能被分配到谓词中：

 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){
   // ...
}

现在这不是一个函数指针，如果需要的话，你需要绑定你的函数指针（我假设你只需要lambda表达式就可以了）

- Akaedintov

---

这会有一些开销，可能并不理想。请注意，标准库没有这样做是因为没有必要。你可以添加一个谓词的模板参数来实现。 - juanchopanza

当然，您可以像这样将无状态lambda分配给函数指针。在coliru上的证明。它是未指定的模板参数使其失败。转换为std::function也不能解决这个问题，只要您保留T的未指定状态。 - ComicSansMS