According to the sources I have found, a lambda expression is essentially implemented by the compiler creating a class with overloaded function call operator and the referenced variables as members. This suggests that the size of lambda expressions varies, and given enough references variables that size can be arbitrarily large.
An std::function
should have a fixed size, but it must be able to wrap any kind of callables, including any lambdas of the same kind. How is it implemented? If std::function
internally uses a pointer to its target, then what happens, when the std::function
instance is copied or moved? Are there any heap allocations involved?
The implementation of std::function
can differ from one implementation to another, but the core idea is that it uses type-erasure. While there are multiple ways of doing it, you can imagine a trivial (not optimal) solution could be like this (simplified for the specific case of std::function<int (double)>
for the sake of simplicity):
struct callable_base {
virtual int operator()(double d) = 0;
virtual ~callable_base() {}
};
template <typename F>
struct callable : callable_base {
F functor;
callable(F functor) : functor(functor) {}
virtual int operator()(double d) { return functor(d); }
};
class function_int_double {
std::unique_ptr<callable_base> c;
public:
template <typename F>
function(F f) {
c.reset(new callable<F>(f));
}
int operator()(double d) { return c(d); }
// ...
};
In this simple approach the function
object would store just a unique_ptr
to a base type. For each different functor used with the function
, a new type derived from the base is created and an object of that type instantiated dynamically. The std::function
object is always of the same size and will allocate space as needed for the different functors in the heap.
In real life there are different optimizations that provide performance advantages but would complicate the answer. The type could use small object optimizations, the dynamic dispatch can be replaced by a free-function pointer that takes the functor as argument to avoid one level of indirection... but the idea is basically the same.
Regarding the issue of how copies of the std::function
behave, a quick test indicates that copies of the internal callable object are done, rather than sharing the state.
// g++4.8
int main() {
int value = 5;
typedef std::function<void()> fun;
fun f1 = [=]() mutable { std::cout << value++ << '\n' };
fun f2 = f1;
f1(); // prints 5
fun f3 = f1;
f2(); // prints 5
f3(); // prints 6 (copy after first increment)
}
The test indicates that f2
gets a copy of the callable entity, rather than a reference. If the callable entity was shared by the different std::function<>
objects, the output of the program would have been 5, 6, 7.
@Cole"Cole9"Johnson: This is an oversimplification of the real code, I just typed it into the browser, so it might have typos and/or fail to compile for different reasons. The code in the answer is just there to present how type erasure is/can be implemented, this is clearly not production quality code.
@MiklósHomolya: It's a clear oversimplification, so I don't think that needs to change for this answer.
@MooingDuck: I do believe lambdas are copiable (5.1.2/19), but that is not the question, rather whether the semantics of
std::function
would be correct if the internal object was copied, and I don't think that to be the case (think a lambda that captures a value and is mutable, stored inside astd::function
, if the function state was copied the number of copies ofstd::function
inside a standard algorithm could result in different outcomes, which is undesired.@MiklósHomolya: I tested with g++ 4.8 and the implementation does copy the internal state. If the callable entity is large enough to require a dynamic allocation, then the copy of the
std::function
will trigger an allocation.@DavidRodríguez-dribeas shared state would be undesireable, because the small object optimization would mean that you'd go from shared state to unshared state at a compiler and compiler version determined size threshold (as small object optimization would block shared state). That seems problematic.