Myth: Lambda expressions can cause heap allocations.
I see this myth coming up a lot. People think that lambdas can cause a heap allocation – on Reddit, on StackOverflow, on Channel9 comments, in personal conversations. I don’t blame people for thinking this – C++ is complex. But it always seems to be some vague notion of “heap allocations can happen under some circumstances”. So let’s think about it more clearly.
Lambdas are a language feature. The compiler will create a closure object representing the function literal you write. The closure object is a value type, created as a prvalue and with automatic storage when assigned to auto (as you must, because its type is unutterable). The only way heap allocation can occur is if you by-value capture a variable whose copy constructor does heap allocation (and this isn’t a consequence of the lambda per se, as I hope you can see).
You can use lambdas all day long on the stack, assigned to auto variables, and never incur a heap allocation. Since lambdas are a language feature, it’s unclear if they could do allocation even if it were desirable – in C++, allocation is in the realm of library code, and I think it would almost certainly entail semantic difficulties for the language, as well as difficulties with exceptions and the like.
Where the confusion comes from, perhaps, is a conflation of lambdas with std::function. (Because lambdas are commonly assigned to std::function for storage and passing around?) std::function is a library construct that wraps a callable using type erasure, and may very well incur heap allocation. In order to wrap any callable, it has to create an internal class in the standard type-erasure way, and that might involve an allocation.
However, std::function does have a couple of common optimizations up its sleeve. First is the so-called “small functor optimization” – a buffer inside a std::function object that is typically big enough to store a few pointers and can be used to store the internal object, assuming it will fit. This allows std::function to avoid heap allocation in common cases (typically just one or maybe two captures).
The second optimization is a space optimization. The typical type-erasure pattern involves calling a virtual function on an internal base class, whose derived class is parametrized on the actual type passed in. But every lambda has a different type, so a naive implementation of this could result in many vtables being generated. So std::function commonly optimizes the call machinery, basically by supplanting the normal C++ virtual call process with a free function implementation that doesn’t cause vtable bloat.
And that’s about it. Lambdas don’t (intrinsically) cause any heap allocation. Ever. When you assign to a std::function, that may cause an allocation, but for a small number of captures, the small functor optimization will probably apply.