Skip to content

Lambda Expressions

Note: Considering the practical context of competitive programming, this article will not comprehensively study grammar but will only cover parts that may be applicable in competitive programming.

This article's grammar references the C++11 standard. Grammar from higher standards will be mentioned as appropriate and specially noted.

Lambda Expressions

Lambda expressions are named after λ-calculus in mathematics, directly corresponding to lambda abstraction. During compilation, the compiler generates an anonymous function object based on the syntax, with captured variables as its members, and parameters and function body used to implement the operator() overload.

Function Object

A function object is a class object, typically implemented by overloading operator(), allowing it to be called like a function. Compared to using ordinary functions, function objects have many advantages, such as being able to preserve state and being passed as parameters to other functions.

The following is one syntax for lambda:

1
[capture] (parameters) mutable -> return-type {statement}

A lambda expression itself is a class, which expands to the following form:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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:

1
void (*f)(int, int) = [](int, int) -> void {};

Below, we introduce each part of the syntax separately.

statement Function Body

The function body is similar to that of an ordinary function, except it can access not only parameters and global variables but also variables captured.

capture Clause

A lambda begins with a capture clause, which specifies which variables are captured. The capture list can be empty or specify the capture mode: variables prefixed with & are accessed by reference, and variables without this prefix are accessed by value.

We can also use default capture modes to capture all variables mentioned in the lambda: & means all captured variables are accessed by reference, = means all captured variables are accessed by value.

After a default capture, you can still explicitly specify the capture mode for particular variables.

If you need to access external variable a by reference and external variable b by value, the following capture clauses can all achieve this:

  • [&a, b]
  • [b, &a]
  • [&, b]
  • [b, &]
  • [=, &a]

The capture list can also be used to declare variables, with the type deduced by the initializer, similar to declaring variables with auto.

Here are some common examples:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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, declares variable v using initializer, type same as a

// Note: when using reference capture, ensure 'a' is not destroyed when called
auto b = f2();  // f2 obtains the value of a from the capture list, no need to pass a as a parameter

Generalized Capture with Initialization (C++14)

Since C++14, capture can not only be used to capture external variables but also to declare and initialize new variables, for example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
auto f1 = [val = 520]() {
  return val;
};  // OK, defines val as int with initial value 520, return type int

auto f2 = [val = 520LL]() {
  return val;
};  // OK, defines val as long long with initial value 520, return type long long

auto f3 = [val = "520"]() {
  return val;
};  // OK, defines val as const char* with initial value "520", return type const char*

auto f4 = [val = "520"s]() {
  return val;
};  // OK, requires using namespace std; or using namespace std::literals; since C++14
    // defines val as std::string with initial value std::string("520"), return type
    // std::string

auto f5 = [val = std::string("520")]() {
  return val;
};  // OK, defines val as std::string with initial value std::string("520"), return type
    // std::string

auto f6 = [val = std::vector<int>(3, 6)]() {
  return val;
};  // OK, defines val as std::vector<int> with size 3, elements filled with 6, return type
    // std::vector<int>

auto f7 = [val = 520]() -> int {
  return val;
};  // OK, defines val as int with initial value 520, return type int

auto f8 = [val = 520]() -> long long {
  return val;
};  // OK, defines val as int with initial value 520, return type long long

When declaring a new variable, the initial value cannot be omitted. The variable's type is determined by the type of the initial value, equivalent to:

1
auto val = init-value;

The following is an incorrect writing:

1
2
auto f = [val]() { return val; };  // Error: ‘val’ was not declared in this
                                   // scope, identifier "val" is undefined

The initializer can also be an external variable, for example:

1
2
3
int value = 520;
auto f = [val = value]() { return val; };
std::cout << f();  // Output: 520

val can also be a reference type, referencing an external variable. This way, you can give an alias to an external variable captured by reference, for example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int value = 520;

auto f = [&val = value]() {
  return val;
};  // OK, defines val as int&, 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 simultaneously.

If you want to modify a new variable defined in the capture within the lambda expression, you need to use the mutable keyword; if it's a reference, it's not needed, for example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int value = 520;

{
  auto f = [val = value]() mutable -> int {
    return val = 1314;
  };  // requires mutable
  auto val_f = f();
  std::cout << value << ' ' << val_f << std::endl;  // Output: 520 1314
}

{
  auto f = [&val = value]() -> int { return val = 1314; };  // does not require mutable
  auto val_f = f();
  std::cout << value << ' ' << val_f << std::endl;  // Output: 1314 1314
}

See mutable Specification for details.

The lifetime of variables defined in the capture follows the receiver of the lambda expression, which in the above examples is variable \(f\), because the lambda itself is actually a class, and everything in the capture are private member variables of this class, for example:

1
2
3
4
5
6
7
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, it is similar to a function's parameter list, for example:

1
2
3
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 will print the array x sorted in descending order.

Since the parameters parameter list is optional, if no parameters are passed to the lambda, and its declaration does not include mutable, and there is no trailing return type, the empty parentheses can be omitted.

Parameters Declared with auto

Since C++14, if a parameter is declared with auto, a Generic Lambda Expression is constructed.

Explicit Object Parameter (C++23)

Since C++23, explicit object parameters can be used in lambda parameters.

1
2
3
4
5
auto nth_fibonacci = [](this auto self, unsigned n) -> unsigned {
  return n < 2 ? n : self(n - 1) + self(n - 2);
};

cout << nth_fibonacci(10u);

mutable Specification

Allows the function body to modify variables captured by value.

1
2
3
4
5
6
int a = 0;
auto by_value = [a]() mutable { ++a; };
auto by_ref = [&a] { ++a; };

by_value();
by_ref();

After executing by_value(), the captured member a in by_value becomes 1, but the external variable a remains 0. After executing by_ref(), the external a becomes 1.

return-type Return Type

Used to specify the return type of the lambda expression. If omitted, the return type will be automatically deduced (behaving like a function with auto declared return type).

Multiple return statements with inconsistent deduced types will cause a compilation error.

1
2
3
4
5
6
7
8
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, inconsistent deduced types

Generic Lambda (C++14)

Using auto as a parameter type allows constructing a generic lambda.

1
auto add = [](auto a, auto b) { return a + b; };

In cpp insights, you can observe the compiler-generated lambda class definition:

1
2
3
4
5
6
7
8
9
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 operator() function template in the add_lambda class.

Recursion in Lambda

First, consider a compilation failure example:

1
2
3
4
5
6
7
8
9
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 attempt to capture \(dfs\) in the capture list, but there is a problem: the type of \(dfs\) is auto, which will be deduced only after the type on the right side of the equals sign is deduced. However, for the lambda to capture \(dfs\), it must first determine the type of \(dfs\) to create its reference variable. This creates a chicken-and-egg situation.

How to solve this problem?

  1. Explicitly specify the type of \(dfs\), for example, using std::function.

    Modify the above code to: 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
    int n = 10;

std::function<void(int)> dfs = [&](int i) -> void {
  if (i == n)
    return;
  else
    dfs(i + 1);  // OK
};

dfs(1);
    Not recommended to use std::function for recursion

    The type erasure of std::function usually requires allocating extra memory, and the indirect call overhead further reduces performance.

    In Benchmark tests using Clang 17 compiler and libc++ as the standard library, recursion implemented with std::function is about 2.5 times slower than lambda implementation.

    Test code 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
    #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);
    1. Instead of capturing \(dfs\), pass it as a function parameter.
    Modify the above code to: 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
    int n = 10;

// If the parameter list contains a parameter of type auto, then the operator()
// function in this Lambda class will be defined as a template function, which can be instantiated later when called
auto dfs = [&](auto& self,
               int i) -> void  // [&] only captures used variables, so it won't capture auto dfs
{
  if (i == n)
    return;
  else
    self(self, i + 1);  // OK
};

dfs(dfs, 1);
    Difference between auto self, auto& self, and auto&& self:

    Theoretically, both auto& self and auto&& self will only use \(8\) bytes (pointer size) for parameter passing, without additional copying. The actual behavior depends on the compiler's implementation of Lambda and corresponding optimizations. Using auto self will cause object copying, and the copy size depends on the elements in the capture list, as they are all private member variables of this Lambda class.

    1. Manually expand the Lambda class or use a similar approach, allowing direct declaration of \(dfs\)'s type.
    Modify the above code to: 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
    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);
    1. If the lambda does not capture any variables, we can also utilize function pointers.

    If a lambda does not capture any variables, it can be implicitly converted to a function pointer. At the same time, the lambda can also be declared as static, and the function pointer type can also be declared as static. This way, the lambda can access the function pointer without capturing, enabling recursion.

    Example 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
    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 Predicate for Standard Library Algorithms

Sort in descending order:

1
2
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:

1
2
std::vector<int> v = {1, 2, 3, 4, 5};
auto it = std::find_if(v.begin(), v.end(), [](int a) { return a > 3; });

Controlling Lifetime of Intermediate Variables

In competitive programming, we encounter scenarios like: a variable's initialization requires previously declared variables, and its initialization process generates large intermediate variables occupying significant memory.

We hope to destruct these intermediate variables as soon as possible to reduce memory consumption. Here, we can use lambda to control the lifetime of these intermediate variables.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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 to using block scope, lambda allows us to use return values, making the code more concise; compared to functions, we don't need to name and declare various captured parameters separately, making the code more compact.

References

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用