Note: In view of the actual circumstances of algorithmic contests, this article will not study the syntax comprehensively, but will only discuss the parts that may be used in algorithmic contests.
This article follows the C++11 standard for syntax. Syntax from other, higher versions of the standard will be mentioned as appropriate and specially marked.
Lambda Expressions
Lambda expressions are named after the calculus in mathematics and directly correspond to lambda abstractions in it. During compilation, the compiler generates an anonymous function object according to the syntax, using the captured variables as its members and the parameters and function body to implement an overload of operator().
Function Object
A function object is a class object, generally implemented by overloading operator(), so it can be called like a function. Compared with using an ordinary function, function objects have many advantages, such as being able to store state and being passed as arguments to other functions.
The following is one syntax for a lambda:
[capture] (parameters) mutable -> return-type {statement}
A lambda expression is itself a class. After expansion, it has the following form:
<!-- scripts.linter.preprocess.fix_details off -->class Lambda_1 {
private:
Lambda_1() : capture-list(init-value) { }
public:
return-type operator()(parameters) const { statement }
private:
mutable capture-list
};
An empty capture can be implicitly converted to a function pointer, for example:
void (*f)(int, int) = [](int, int) -> void {};
We now introduce the various parts of the syntax separately.
statement: Function Body
The function body of a lambda expression is similar to that of an ordinary function. In addition to accessing parameters and global variables, it can also access variables captured.
capture: Capture Clause
A lambda begins with a capture clause. It specifies which variables are captured. The capture list may be empty, or it may specify a capture method: variables prefixed with the & symbol are accessed by reference, while variables without this prefix are accessed by value.
We can also use a default capture mode to capture all variables mentioned in the lambda: & means that all captured variables are accessed by reference, while = means that all captured variables are accessed by value.
After a default capture, a capture mode can still be specified explicitly for particular variables.
If external variable a needs to be accessed by reference and external variable b by value, all of the following capture clauses can do so:
[&a, b][b, &a][&, b][b, &][=, &a]
The capture list can also be used to declare variables. Their types are deduced from their initializers, similarly to declaring variables with auto.
Here are some common examples:
int a = 0;
auto f0 = []() { return a * 9; }; // Error, cannot access 'a'
auto f1 = [a]() { return a * 9; }; // OK, 'a' is captured by value
auto f2 = [&a]() { return a++; }; // OK, 'a' is captured by reference
auto f3 = [v = a + 1]() {
return v + 1;
}; // OK, declare variable v using the initializer; its type is the same as a
// When using reference capture, ensure that a has not been destroyed when it is called
auto b = f2(); // f2 obtains the value of a from the capture list, so a need not be passed as a parameter
generalized capture: Capture with Initialization (C++14)
Since C++14, capture can be used not only to capture external variables, but also to declare and initialize new variables, for example:
auto f1 = [val = 520]() {
return val;
}; // OK, define val as int, with initial value 520 and return type int
auto f2 = [val = 520LL]() {
return val;
}; // OK, define val as long long, with initial value 520 and return type long long
auto f3 = [val = "520"]() {
return val;
}; // OK, define val as const char*, with initial value "520" and return type const char*
auto f4 = [val = "520"s]() {
return val;
}; // OK, since C++14, using namespace std; or using namespace std::literals; is required
// Define val as std::string, with initial value std::string("520") and return type
// std::string
auto f5 = [val = std::string("520")]() {
return val;
}; // OK, define val as std::string, with initial value std::string("520") and return type
// std::string
auto f6 = [val = std::vector<int>(3, 6)]() {
return val;
}; // OK, define val as std::vector<int>, of size 3 and filled with 6, with return type
// std::vector<int>
auto f7 = [val = 520]() -> int {
return val;
}; // OK, define val as int, with initial value 520 and return type int
auto f8 = [val = 520]() -> long long {
return val;
}; // OK, define val as int, with initial value 520 and return type long long
When defining a new variable, the initial value cannot be omitted. The variable's type is determined by the type of the initial value, equivalent to:
auto val = init-value;
The following is incorrect:
auto f = [val]() { return val; }; // Error: 'val' was not declared in this
// scope, identifier "val" is undefined
The initial value can also be an external variable, for example:
int value = 520;
auto f = [val = value]() { return val; };
std::cout << f(); // Output: 520
val can also be a reference type that refers to an external variable. In this way, an alias can be given to an external variable captured by reference, for example:
int value = 520;
auto f = [&val = value]() {
return val;
}; // OK, define val as int&, with return type int, equivalent to int& val = value;
std::cout << f() << '\n'; // Output: 520
value = 1314;
std::cout << f() << '\n'; // Output: 1314
Capturing external variables and defining new variables can be used at the same time.
If you want to modify a new variable defined in the capture inside a Lambda expression, you need to use the mutable keyword; if it is a reference, this is not necessary, for example:
int value = 520;
{
auto f = [val = value]() mutable -> int {
return val = 1314;
}; // mutable is required
auto val_f = f();
std::cout << value << ' ' << val_f << std::endl; // Output: 520 1314
}
{
auto f = [&val = value]() -> int { return val = 1314; }; // mutable is not required
auto val_f = f();
std::cout << value << ' ' << val_f << std::endl; // Output: 1314 1314
}
See mutable: Mutable Specifier for details.
The lifetime of a variable defined in the capture follows the recipient of the Lambda expression, which is the variable in the examples above. This is because a Lambda is actually a class, and everything in the capture is a private member variable of this class, for example:
int main() {
auto f = [val = 0]() mutable -> int { return ++val; }; // val is constructed and initialized
std::cout << f() << '\n'; // Output: 1
std::cout << f() << '\n'; // Output: 2
std::cout << f() << '\n'; // Output: 3
} // val is destroyed along with f
parameters: Parameter List
In most cases, this is similar to a function's parameter list, for example:
int x[] = {5, 1, 7, 6, 1, 4, 2};
std::sort(x, x + 7, [](int a, int b) { return (a > b); });
for (auto i : x) std::cout << i << " ";
This prints the x array sorted from largest to smallest.
Because the parameters parameter list is optional, if no parameters are passed to the lambda, its declaration does not contain mutable, and it has no trailing return type, the empty parentheses can be omitted.
Parameters Declared with auto
After C++14, if a parameter's type is declared with auto, a generic lambda is constructed.
Explicit Object Parameter (C++23)
Starting with C++23, an explicit object parameter can be used among a lambda's parameters.
auto nth_fibonacci = [](this auto self, unsigned n) -> unsigned {
return n < 2 ? n : self(n - 1) + self(n - 2);
};
cout << nth_fibonacci(10u);
mutable: Mutable Specifier
This allows the function body to modify variables captured by value.
int a = 0;
auto by_value = [a]() mutable { ++a; };
auto by_ref = [&a] { ++a; };
by_value();
by_ref();
After by_value() has been executed, the captured member a of by_value is 1, but the external variable a is still 0. After by_ref() has been executed, the value of external a becomes 1.
return-type: Return Type
This is used to specify the return type of a lambda expression. If omitted, the return type is deduced automatically (the behavior is the same as that of a function whose return value is declared with auto).
When there are multiple return statements and their deduced types are inconsistent, a compilation error occurs.
auto lam = [](int a, int b) -> int { return 0; };
auto x1 = [](int i) { return i; };
auto x2 = [](bool condition) {
if (condition) return 1;
return 1.0;
}; // Error, the deduced types are inconsistent
Generic Lambda (C++14)
A generic lambda can be constructed by using auto as the parameter type.
auto add = [](auto a, auto b) { return a + b; };
In cpp insights, you can observe the lambda class definition generated by the compiler:
class add_lambda {
public:
template <class T, class U>
auto operator()(T a, U b) const {
return a + b;
}
};
add_lambda add{};
Both parameters of add are declared with auto, corresponding to the two template parameters T and U of the function template operator() in the add_lambda class.
Recursion in Lambdas
First, consider an example that fails to compile:
int n = 10;
auto dfs = [&](int i) -> void {
if (i == n)
return;
else
dfs(i + 1); // Error: a variable declared with an auto type specifier
// cannot appear in its own initializer
};
Here we try to capture in the capture list, but there is a problem: the type of is auto, and the type of will be deduced only after the type on the right-hand side of the equals sign has been deduced. To capture , the Lambda must determine the type of before it can create its reference variable. This becomes a nesting process.
How can this problem be solved?
-
Explicitly specify the type of , using
std::functioninstead.???+ example "Modify the code above as follows:" ```cpp int n = 10;
std::function<void(int)> dfs = [&](int i) -> void { if (i == n) return; else dfs(i + 1); // OK }; dfs(1); ```??? warning "Using
std::functionfor recursion is not recommended" Type erasure instd::functionusually requires additional memory allocation, and the addressing operation introduced by indirect calls further reduces performance.In the [Benchmark](https://quick-bench.com/q/U5qf_dHHKsSyVU83jmt0p_U541c) test, using the Clang 17 compiler and libc++ as the standard library, recursion implemented with `std::function` was about 2.5 times slower than recursion implemented with a lambda. ??? note "Test Code" ```cpp #include <algorithm> #include <functional> #include <numeric> #include <random> using namespace std; const auto& nums = [] { random_device rd; mt19937 gen{rd()}; array<unsigned, 32> arr{}; std::iota(arr.begin(), arr.end(), 0u); ranges::shuffle(arr, gen); return arr; }(); static void std_function_fib(benchmark::State& state) { std::function<int(int)> fib; fib = [&](int n) { return n <= 2 ? 1 : fib(n - 1) + fib(n - 2); }; unsigned i = 0; for (auto _ : state) { auto res = fib(nums[i]); benchmark::DoNotOptimize(res); ++i; if (i == nums.size()) i = 0; } } BENCHMARK(std_function_fib); static void template_lambda_fib(benchmark::State& state) { auto n_fibonacci = [](const auto& self, int n) -> int { return n <= 2 ? 1 : self(self, n - 1) + self(self, n - 2); }; unsigned i = 0; for (auto _ : state) { auto res = n_fibonacci(n_fibonacci, nums[i]); benchmark::DoNotOptimize(res); ++i; if (i == nums.size()) i = 0; } } BENCHMARK(template_lambda_fib); ``` -
Obtain without capturing it, by passing it as a function parameter.
???+ example "Modify the code above as follows:" ```cpp int n = 10;
// If the parameter list contains a parameter whose type is auto, the operator() // function in this Lambda class will be defined as a template function; it can be instantiated later when called auto dfs = [&](auto& self, int i) -> void // [&] only captures variables that are used, so it will not capture auto dfs { if (i == n) return; else self(self, i + 1); // OK }; dfs(dfs, 1); ```???+ note "The differences between
auto self,auto& self, andauto&& self:" In theory, bothauto& selfandauto&& selfuse only bytes (the size of a pointer) for parameter passing, and no other copying occurs. The details depend on the compiler's implementation of the Lambda and the corresponding optimizations. Usingauto selfcauses an object copy. The size of the copy depends on the elements in the capture list, because they are all private member variables of this Lambda class. -
You can manually expand the Lambda class, or use a similar approach, so that the type of can be declared directly.
???+ example "Modify the code above as follows:" ```cpp int n = 10;
class Lambda_1 { public: auto operator()(int i) const -> void { if (i == n) return; else (*this)(i + 1); // OK } explicit Lambda_1(int& __n) : n(__n) {} private: int& n; } dfs(n); dfs(1); ``` -
If the lambda does not capture any variables, we can also use a function pointer.
If a lambda does not capture any variables, it can be implicitly converted to a function pointer. A lambda can also be declared
staticin this case, and the function pointer type can also be declaredstatic. In this way, the lambda can access the function pointer without capturing it, thereby implementing recursion.???+ example "Example" ```cpp static unsigned (*fptr)(unsigned);
static const auto lambda = [](const unsigned a) { return a < 2 ? a : (*fptr)(a - 2) + (*fptr)(a - 1); }; static auto init = [] { fptr = +lambda; // Or // fptr = static_cast<unsigned (*)(unsigned)>(lambda); return 0; }(); cout << lambda(10); ```
Applications of Lambda Expressions
As a Predicate for Standard-library Algorithms
Sort from largest to smallest:
std::vector<int> v = {1, 2, 3, 4, 5};
std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
Use std::find_if to find the first element greater than 3:
std::vector<int> v = {1, 2, 3, 4, 5};
auto it = std::find_if(v.begin(), v.end(), [](int a) { return a > 3; });
Controlling the Lifetime of Intermediate Variables
In algorithmic contests, we encounter situations where initializing a variable requires previously declared variables, and the initialization process also generates a large intermediate variable that occupies considerable space.
We want to destroy these intermediate variables as soon as possible to reduce memory consumption. In this case, we can use a lambda to control the lifetime of these intermediate variables.
void solution(const vector<int>& input) {
int b = [&] {
vector<int> large_objects(input.size());
int c = 0;
for (int i = 0; i < large_objects.size(); ++i)
large_objects[i] = i + input[i];
for (int i = 0; i < input.size(); ++i) c += large_objects[input[i]];
return c;
}();
// ...
}
Compared with using a block scope, a lambda allows us to use a return value, making the code more concise. Compared with a function, we do not need to give an additional name or declare the various captured parameters, making the code more compact.