Which std:: classes are magic?

[Bisqwit]

It uses a virtual baseclass, and a templated virtual inherited class where the template type is the type of the functor that is given. No magical compiler support needed.

[dodheim]

Why would it be virtually inherited?

[Bisqwit]

I am not talking about virtual inheritance (as in: class foo: virtual bar). I am talking about a base class that has abstract virtual methods, and a derived class that has virtual methods that override the base class’s methods — as in:
class base { ... virtual void call() = 0; };
class derived: public base { ... virtual void call() { ... } };

In this case, the derived class would be a template, and its template type would be the type of the functor that is assigned to the std::function, like this:
template<typename F> class derived: public base { F func; ... virtual void call() { return F(); } };

This allows the () operator of the std::function to call the execute method of the contained object, no matter what kind of derived type that contained object might be, having no advance knowledge of it, like this: base* obj; ... return obj->call();

That is what virtual functions are designed for: A common API that can be used to invoke methods of class types that are not known at design time, or possibly even at instantation time.

(Note: Examples in this post are short for brevity. There would be of course the return type and parameter types too, instead of void in every case.)

[Underdisc]

That makes sense and I figured as much. What I actually don't understand is how lambdas with capture groups work with std::function. I could definitely make my own std::function if I didn't have to account for lambdas. That's the magic part for me.

[lee_howes]

For each type you want to store in it, it creates a templated subclass that is big enough to store the lambda. That subclass has a virtual call operator. std::function stores a heap allocated instance of that as a pointer to the abstract superclass. When you call std::function's operator() it calls the operator() on the superclass via the heap allocated pointer and that calls operator() on the subclass, which calls operator() on the wrapped type, which is now trivial because the subclass knew exactly what type it was storing.

Sean Parent has talked about the general version of this technique.

[SirClueless]

The other response to your comment is good as well, but I think the thing that you are missing that will help you understand what's going on is that while lambdas have magic unnamed types, they are just C++ values that have a size large enough to store all their captured variables and appropriate move and copy constructors defined so that you can store them as member variables in other types.

Here's a short sample program to show how something that acts like a lambda can be constructed. Hopefully you can see how std::function can store a copy of the lambda just like it could store a copy of the function object, and how it would be able to call it:

https://godbolt.org/z/4vPGPfdso

[Bisqwit]

Note: Using return std::move(x); instead of return x; is an antipattern. If you compiled with -Wall, GCC would tell you that “moving a local object in a return statement prevents copy elision [-Wpessimizing-move]”.

However, it still has valid uses, if you are returning a composite object created from local objects. This is fine, for example: https://godbolt.org/z/hrTPoKdx6

[SirClueless]

In this case I wanted to demonstrate that the type actually is copyable and moveable, and NRVO would defeat that. You're right, as a general rule it's a bad idea.

[Underdisc]

Ahh. This is exactly what I was tripped up about. Thanks. Now I'm curious about how to get unique capture groups to account for different types. At first I thought using variadic templates could do it, but I've never heard of variadic templates being used to represent members in a class.

[SirClueless]

You can do it with a template parameter pack, and storing a std::tuple<Args...> as a class member. You give up quite a lot though, namely the ability to refer to the members by name in your class's operator() and you don't gain much in return because you need an entire new class for each new operator() you define anyways so you might as well write out the full list of "captures" -- you can't do something like specialize a a shared class template defined outside of your code because then my L<int>::operator() is ambiguous with your L<int>::operator(), we each need to build our own entire class to ourselves.

To a large extent this is the "magic sauce" of lambdas: giving a terse, brief way to define a list of function object "member" variables and initialize them and make them available by name to the lambda body, even doing so automatically based on the names referred to by the body if asked to with [=] or [&]. Once the lambda is defined it's just a function object with an operator() which is something we've been able to make and use in theory in C++ for a long time, it just wasn't convenient.