Write a function that accepts a lambda expression as argument

Your function is expecting a function pointer, not a lambda.

In C++, there are, in general, 3 types of “callable objects”.

1. Function pointers.
2. Function objects.
3. Lambda functions.

If you want to be able to use all of these in your function interface, then you could use std::function:

template<typename T, typename U> 
map<T,U> mapMapValues(map<T,U> old, std::function<T(T, U)> f)
{
    ...
}

This will allow the function to be called using any of the three types of callable objects above. However, the price for this convenience is a small amount of overhead on invokations on the function (usually a null pointer check, then a call through a function pointer). This means that the function is almost certainly not inlined (except maybe with advanced WPO/LTO).

Alternatively, you could add an additional template parameter to take an arbitrary type for the second parameter. This will be more efficient, but you lose type-safety on the function used, and could lead to more code bloat.

template<typename T, typename U, typename F> 
map<T,U> mapMapValues(map<T,U> old, F f)