Why don't lambda expressions require <functional>, but function<void()> does?

Question

I have some code use lambda expression like it:

#include <vector> #include <algorithm> int main(){     std::vector<int> vi={3,1};     std::sort(vi.begin(),vi.end(),[](int x,int y){         return x<y;     });     return 0; } 

Which doesn't require #include< functional> to compile, but if I use a variable to store the lambda function:

#include <vector> #include <algorithm> #include <functional> int main(){     std::vector<int> vi={3,1};     std::function<void()> compf=[](int x,int y){         return x<y;     };     std::sort(vi.begin(),vi.end(),compf);     return 0; } 

Then I need to include <functional> to compile, why? And why sort() doesn't also include <functional> already?

Answer 1

Because a lambda expression is a core language feature, provided by the compiler. std::function is a library feature, implemented in code. Note that you don't need to include anything to store the lambda in a variable.

auto f = [](int x, int y){ return x < y; }; 

You only need to include <functional> if you plan to store it in a std::function (because that's where it's implemented).

You seem to be under the impression that the type of a lambda is a std::function. It is not. Every lambda expression has its own unique, unnameable type. I captured that type above, with auto. std::function is a more general type that can store any function-like object with the appropriate signature. For example, I can create a std::function<int(int,int)> object, and assign to it a normal function, a function object, and a lambda.

#include <functional> int minus_func(int a, int b) { return a - b; }  struct plus_t {     int operator()(int a, int b) const { return a + b; } };  int main() {     auto mult_lambda = [](int a, int b) { return a * b; };      std::function<int(int,int)> func;     func = minus_func;     func = plus_t{};     func = mult_lambda; } 

There's also a cost to that generality, in the form of dynamic allocation, and indirection. Whereas using a lambda through a variable of its actual type is very often inlined.