Disclaimer: This blog (and all of my other blogs, unless specified otherwise) is 100% ChatGPT-free — there has been no use of any AI/ML-based application while coming up with the content of this blog.
The reason and an appealThere is a lot of AI-generated content out there these days that sounds plausible and useful but is absolute garbage and contributes nothing beyond a list of superficial sentences — even if it has content that is true (which is a big IF, by the way), it generates content that you could have just looked up on your favorite search engine. The reason why such current AI-generated content is like this is multi-fold, but I won't get into it because I need to write the content of this blog, too, and I don't see copy-pasting this kind of content as anything but a stupid maneuver that wastes everyone's time.
I hope other people who write blogs refrain from using this stuff for generating content that is supposed to be meaningful and realize that the current state of AI is just a memorization machine that is trained to excrete human-sounding sentences. When I saw someone from Div 1 posting useful-sounding content on CF, which was clearly generated by ChatGPT, I couldn't help but despair at what the knowledge-acquiring mechanisms of the future will look like, other than knowledge coming almost entirely from unreliable sources that consist of matrix multiplications at their core.
The contents are as follows:
- Introduction
- Why you should use lambdas
- Some context
- Hand-rolling our own lambdas
- C++ lambda syntax explained
- Using lambdas
- Using lambdas with the STL
- Some useful non-trivial patterns
- Some other interesting patterns
- Examples of competitive programming code using C++ lambdas
Prerequisites: knowing a bit about structs/classes in C++, member functions, knowing that the STL exists.
If you feel something is not very clear, I recommend waiting for a bit, because I tried to ensure that all important ideas are explained at some point or another, and if you don't understand and it doesn't pop up later, it is probably not that important (and should not harm the experience of reading this blog). Nevertheless, if I missed out on explaining something that looks important, please ask me in the comments — I'd be happy to answer your questions!
I would like to thank (in alphabetical order) AlperenT, bestial-42-centroids and kostia244 for discussions that helped improve the presentation and teachability of this blog.
Introduction
A few years back, I co-authored a blog on pragmas because there were very few people who understood what pragmas do. I noticed that the same is true, albeit to a lower extent, for lambdas (C++ and otherwise) — some using them as a minor convenience but nothing more; others having an irrational (and ignorant) disdain for them, mainly arising either out of some experiences that come from not using them properly or a love of all things "minimalistic".
Hence, part of the motivation behind this blog is to show and convince people that lambdas can be very useful, both for your code AND your thought process, and that they will make your life easier if you do any amount of programming in a language that has decent support for lambdas (yes, not only C++). Thus, a significant part of the blog would also talk about some topics related to models of computation and some history. And, of course, I will make a few philosophical arguments along the way, which you can feel free to skip, but they are helpful as a first step to realizing why such a change in perspective is quite important for any learning.
The other reason I am writing this blog is to explain C++ lambdas on a much deeper level than people usually go into, without being as terse and unreadable for a beginner as the cppreference page — this will involve rolling our own lambdas! This activity will also help us understand why certain behaviors are intuitive for C++ lambdas. And in the end, as everyone expects a tutorial on CF to be, we will also show some tricks that are especially useful in the competitive programming context.
Examples of usage of lambdas in code doesn't come until much later in this blog, because we develop an understanding of what role lambdas actually play in a language, instead of just introducing them as nifty tricks that can help you shorten your code. If you want to only look at applications, please skip to the last few sections.
Hopefully, this blog will also get people interested in programming language theory — especially functional programming and parts that deal with language design.
Finally, no matter how experienced you are with lambdas/C++/programming languages, there is a high chance that you will find some piece of code/idea in this blog that will look very new. I recommend checking out the two sections on patterns (in one of them we implement OOP using lambdas, for example), and the discussion on untyped v/s typed lambda calculus and implementing recursion.
Why you should use lambdas
I recommend reading this section again after reading the rest of the blog since it'll make more sense after you understand what lambdas are. But since the reader is probably growing restless about why they should be investing their time in lambdas, here's a list of reasons why you should learn about lambdas:
- Philosophical reasons: Imperfect as it may be, the Blub paradox implies that a programmer's way of problem-solving using code is upper-bounded by the language they use itself to the point that they can correctly realize how limited more primitive languages are, but fail to realize why any feature a higher level language gives them should help them as a programmer, and dismiss higher level languages as just their preferred language + some weird feature that they don't care about. Meanwhile, as people who know math, we probably already realize that thinking on a lower level than necessary is harmful to our development because we don't see the bigger picture. Think of it like having induction as a tool in our toolbox versus having to repeat an argument 1000 times to show that $$$P(1000)$$$ is true for some predicate $$$P$$$ — this is what it feels like to code in a language that does not have for-loops, which a person who exclusively copypastes code to manually implement what a loop could have done would be very proud of. The moral of the story? Think on a higher level, code in whichever language you want to.
- More practical reasons — You can define a lambda anywhere instead of functions that must be defined at namespace (global or otherwise) scope. So lambdas require you to scroll much less, prevent bugs, keep things local, and avoid polluting the namespace — all of which are supposed to be good practices. They also reduce context switching that makes code bug-prone.
- You can store functions in data and pass functions more uniformly. This can be achieved by function pointers, too, but the other features make lambdas much more convenient for this purpose. It bypasses the need to make "tagged" versions of functions and implement your own vtable kind of things.
- You can store data inside functions! Instead of passing a value/reference as a parameter each time a function is called (for example, using the same dfs function for a local graph requires you to pass the local graph by reference to the dfs, which is inconvenient), you can just store (in C++ lambda language, "capture") the reference/value of a variable inside the lambda and be done with it.
- The standard library has a ton of support for lambdas, such as in sorting, binary searching, filtering, aggregating, etc. The usage is as simple as passing a single line lambda into a function provided by the STL.
Some context
The unusual name lambda comes from lambda calculus, which is a mathematical system for expressing computation, much like what a computer program is supposed to be written in. In this computation system, we have only three types of expressions, which are supposed to be the representation of each computation:
- terms of the form $$$x$$$: these correspond to variables.
- terms of the form $$$\lambda x. E$$$: this corresponds to a function that takes input $$$x$$$ and returns the result of evaluating $$$E$$$, which is an expression that may or may not involve $$$x$$$. In C++, this would roughly correspond to a function with parameter $$$x$$$ and function body
return $$$E$$$. - terms of the form $$$(E_1 \, E_2)$$$ where $$$E_1$$$ and $$$E_2$$$ are two expressions: this corresponds to applying the function represented by the expression $$$E_1$$$ to the argument $$$E_2$$$. In C++, this would roughly correspond to a function $$$E_1$$$ being called with $$$E_2$$$ as a parameter, i.e., $$$E_1(E_2)$$$.
And that's it. Note that there are no numbers and no restriction on what $$$E_2$$$ evaluates to. In particular, $$$E_2$$$ can be a function too! The same holds for $$$E$$$ and $$$E_1$$$ as well, so there are many kinds of expressions that you can write that will make sense in this "language". Evaluation of these expressions is done using certain rules called reductions (which resemble simplification of mathematical expressions), though at this stage, it is not really necessary to understand what they do (it is sufficient to take some amount of intuition from any language of your choice to develop an intuition for it, though care should be taken to avoid taking the intuition too far, because there are certain core concepts in languages that are simply not present in this lambda calculus — for instance, types).
It turns out that this system of computation is Turing complete, i.e., any program that can be run on a Turing machine can be simulated using this method of computation. But why is this relevant to the discussion?
The second type of term here is called a lambda term. This is where the lambda terminology comes from — because lambdas play the role of functions in this system. Except in lambda calculus, you're allowed to do a large variety of things by virtue of the lack of constraints in the definition. For example, you can pass around functions to other functions (remember that $$$E_2$$$ is not constrained to be of a particular "type").
NitpickThere is no concept of a type in this system of computation. Even the reduction mechanism for a standard lambda calculus is something that doesn't care about types. It turns out that if we assign types to any of these terms, then it forces all valid reductions to terminate, and some expressions end up being untypable even though there can be a possibly infinite sequence of reductions that can be applied to them.
But note that we are not allowed to manipulate functions in C++ as freely as the above definition dictates. For example, we are not allowed to return functions that depend on the input because function pointers in C/C++ are supposed to be pointers to things known at compile time.
To illustrate this, let's temporarily add numbers and the $$$+$$$ operator to the lambda calculus (by the way, they can be semantically simulated using just lambda expressions using what are called Church numerals, but that is a completely different story for another day). The following is a valid lambda expression:
$$$
\lambda x. \lambda y.(x + y)
$$$This function takes a value $$$x$$$ and returns a lambda that takes an input $$$y$$$ and returns $$$x + y$$$. Note that the output of the inner lambda depends on the value of $$$x$$$. For example, $$$(\lambda x. \lambda y.(x + y)) (42)$$$ is just $$$\lambda y.(42 + y)$$$. So we have something analogous to a function that returns a function, such that the returned function is dependent on the input to the outer function. (By the way, this is what I meant by lambdas reducing the dependence on "tagged" functions, because you have a great tagging mechanism for lambdas — just store the data inside it).
The corresponding in C++ style syntax should be something like (but this isn't legal C++ code, so I took the liberty of using non-standard syntax here):
int(int) lambda1(int x) {
int lambda2(int y) {
return x + y;
}
return lambda2;
}
So, there is a clear difference between C++ functions and lambda terms from the lambda calculus despite all the other semantic similarities. This discussion already hints to us what a lambda function (as we will call it from now on) should look like in C++.
Let's digress for the rest of this section into the discussion of functional programming languages.
Note that the imperative programming model (let's think about C for the sake of concreteness) is largely based on the Turing machine model of computation — you have tapes (memory), pointers, and states. The main focus is on evolving the state of the program and the memory in order to get to an end goal.
The functional programming model, on the other hand, is largely based on lambda calculus. You rarely have any state in a functional programming language like Haskell or OCaml (especially in a purely functional language like Haskell). Instead, you express your code in the form of function applications and some basic inbuilt types (like integral types) and functions (like numerical operators).
Both of them are equally powerful. However, functional programming languages are often at a much higher level than imperative languages because of the power of abstraction and resemblance to mathematics, which rarely talks about state in any of its fundamental parts.
Also, a fun fact — the sharp eyed reader would have noticed that the lambda function we wrote is semantically equivalent to a function that takes two numbers $$$x$$$ and $$$y$$$ and returns their sum, except that we have partial application for free, by "binding" $$$x$$$ to the lambda after the first application and returning a function that adds $$$x$$$ to anything. This style of writing lambda terms is called currying and can be used to implement multi-argument functions in a language where functions only have one argument.
This is just scraping the surface of what is otherwise a crazy set of things that can be done with lambda calculus. For example, one interesting thing you can do with it is to show how weird computation systems like the SKI combinator calculus are in fact Turing complete. Also, since the lambda calculus is Turing complete, there is a way (a quite elegant one at that) to represent recursion called a fixed point combinator, which can be implemented in multiple ways, one of which is the Y-combinator.
Hand-rolling our own lambdas
Since C++ is Turing complete, should we expect there to be a way to implement (a typed variant of) lambda calculus in C++? Definitely, though we probably shouldn't expect it to be very elegant. Or can we? Read on to find out.
Let's think about what a lambda function (shortened to lambda for convenience) should behave like in C++.
It should be what is called a "first-class citizen" of the language in programming language design — i.e., all operations that are supported for other entities should also be supported for lambdas. In other words, it should have the following properties at the very least:
- Should be able to be passed as a function argument
- Should be able to be returned from a function
- Should be able to be assigned to a variable
The most general kind of thing that C++ supports that adheres to these rules is an object. Let's try to implement a lambda as an object in that case.
So for now, a lambda looks like this for us:
struct Lambda {
// ???
};
Lambda lambda{};
Note that since structs can be defined in a local scope, we will be able to do whatever follows inside a local scope as well as a namespace scope.
Now according to its definition, we should be able to call a lambda as well. The most obvious way of associating a function with a struct is to implement a member function, let's say call. However, one cool functionality that C++ provides is the ability to overload operator() for a struct — this is the function call operator, and it will help us reduce the syntactic boundaries between a function and an object. So rather than using the name call, we will overload operator(), which does the same thing but with a better syntax.
So, something like the following prints 2 in a new line:
struct Lambda {
int operator()(int x) const {
return x + 1;
}
};
Lambda lambda;
std::cout << lambda(1) << '\n';
At this point, we should note that such a struct which overloads operator() is called a function object in the C++ standard (and is frequently informally referred to as the horribly named "functor" which has a very different meaning in category theory, so it will irk a lot of people if you call a function object a functor in front of them).
Now that we can wrap functions into objects, we can do whatever an object can — for example, we can now return something that behaves like a function, so it might seem that the story ends here. However, note that we didn't implement anything that allows us to "bind" data to functions, as we wanted to do in our addition example. It is necessary to implement this, in order to make $$$E$$$ aware of the value of $$$x$$$ somehow, when applying $$$\lambda x. E$$$ to some $$$x$$$.
Since we want to emulate a mathematical language, for now we don't really care about C++ semantics, and we will choose value semantics for $$$x$$$ (which will make a lot of copies, but will make reasoning easier). This basically means that whenever we store $$$x$$$, it will be, just like in mathematics, completely independent of wherever its value was taken from.
Let's try our hand again at the $$$\lambda x. \lambda y.(x + y)$$$ example. Let's write it in a more computer-program-style syntax with parentheses at all the right places (which some people might recognize as being one infix-to-prefix transformation away from being Lisp code):
(lambda x.
(lambda y.
(x + y)))
Since there are two $$$\lambda$$$-s, we would need two structs this time — one for the outer lambda and one for the inner lambda. The inner lambda needs to "capture" $$$x$$$, so we store a copy of $$$x$$$ in it whenever it is constructed.
struct LambdaInner {
int x_; // our binding
LambdaInner(int x) : x_{x} {}
int operator()(int y) const {
return x_ + y;
}
};
struct LambdaOuter {
LambdaInner operator()(int x) const {
return LambdaInner(x);
}
} lambda_outer;
LambdaInner lambda_inner = lambda_outer(1);
std::cout << lambda_inner(2) << '\n'; // or lambda_outer(1)(2)
But this starts looking less and less like actual lambda functions now. The trick is to use the fact that we are able to declare structs in local scope.
struct LambdaOuter {
auto operator()(int x) const {
struct LambdaInner {
int x_; // our binding
LambdaInner(int x) : x_{x} {}
int operator()(int y) const {
return x_ + y;
}
};
return LambdaInner(x);
}
} lambda_outer;
std::cout << lambda_outer(1)(2) << '\n';
Okay, this now resembles lambda expressions a bit more than before. But there is still a large amount of noise in the code — for example, having to declare x_ and naming the structs for the lambdas. Turns out that we have exactly the tools for the job with C++ lambdas, which provide syntactic sugar for this kind of a thing:
auto lambda_outer =
[](int x) {
return [x](int y) {
return x + y;
};
};
std::cout << lambda_outer(1)(2) << '\n';
Here, the lambda being returned has "captured" or "bound" the variable x by storing a copy of it inside itself.
Don't worry if you're a bit baffled with the syntax going from that monstrosity of object oriented code to this simple of a code, for now is the time to look at the syntax of a C++ lambda.
C++ lambda syntax explained
A C++ lambda expression (or lambda function), in its simplest form, has the syntax
[capture_list](parameter_list) specifiers -> trailing_return_type {
// function body
};
where the trailing return type and specifiers are both optional (we will get to them in a moment, they're not super critical for now).
Given that lambda functions aim to replicate a lot of C++ function functionality, there is a lot of noise you could introduce here too, with syntax that I have not mentioned in the above — you can make it something as complex as the following as of C++20 (even ignoring the possible *this and variadic captures):
int x = 1;
int y = 0;
auto lambda = [&, x = std::move(x)]
<std::integral T>
requires(sizeof(T) <= 8)
(T a, auto b, int c)
mutable constexpr noexcept [[deprecated]]
-> std::uint64_t {
y = x;
return static_cast<std::uint64_t>(c) + a + sizeof(b) + x + y;
};
However, we won't be really concerned with a lot of this, and will only deal with a few special cases (besides, if you understand the rough correspondence between function objects and lambdas, it becomes more intuitive to guess how this syntax works).
In the syntax mentioned earlier, the lambda roughly corresponds to this struct (don't worry if you don't understand this yet, we will explain the terms used here in detail):
struct UnnamedLambda {
// 1. variables corresponding to the capture list go here
// 2. constructor for storing captured variables
// 3. call operator - with some specifiers if specified:
auto operator()(parameter_list) -> /* trailing_return_type, if any, goes here */ const {
// lambda function body
}
};
Note that the member function is marked const regardless of what we specify for the lambda — this means that it is not allowed to do anything that mutates/is-allowed-to-mutate-but-doesn't the member variables. We can get past this restriction as we will see later.
Warning: this is only a representative correspondence and works well for almost all purposes (for example, the copy-assignment constructor of lambdas is deleted, but we didn't show it for the sake of simplicity). It is possible for the C++ lambda behaviour to diverge in some edge cases from the behaviour of this struct, but I haven't seen any such divergences.
For example, a lambda like the following:
int y = 1, x = 0;
auto lambda = [y, &x](auto a, int b) constexpr mutable -> int {
return sizeof(a) * y + b * x;
};
corresponds to
struct UnnamedLambda {
// captured variables
int y_;
int& x_;
// constructor - constexpr by default if possible
constexpr UnnamedLambda(int y, int& x) : y_{y}, x_{x} {}
// call operator - the constexpr specifier marks this function as constexpr (a bit useless since it is constexpr whenever possible anyway), and the mutable specifier removes the const
constexpr auto operator()(auto a, int b) -> int {
return sizeof(a) * y + b * x;
}
}
It is possible to template a lambda starting from C++20, but it is not something that is very useful for competitive programming, so I will omit it for the sake of simplicity, since the syntax has quite a lot of parts already.
Now let's look at every part in a bit of detail.
The capture list
Firstly, global/static variables and global constants don't need to be captured (and can't be) — they are accessible without any captures and will always be usable inside a lambda like a normal variable. It is similar to being captured by reference by default for those variables.
Let's say we want to capture a variable y by value and x by reference (so in the struct, we store a copy of y and a reference to x). In that case, the capture list becomes y, &x or &x, y. We can do this for any number of variables in any order — &x, y, z, x, &y, &z, w etc.
Now let's say you don't want to manually capture all variables that you're going to be using.
Let's say you want to capture all variables by value. The capture list becomes =.
And if you want to capture all variables by reference, the capture list becomes &.
But you'd say, I don't want to be stuck using the same semantics for all my captured variables. C++ has a way of allowing you to specify variables for which the default semantics are not followed.
If you want to capture all variables by value, but g by reference since it is a large graph, your capture list becomes =, &g (the default should be at the beginning of the capture list).
If you want to do the opposite and capture all variables by reference, but capture g by value, your capture list becomes &, g.
Now let's say that rather than capturing a variable directly, you want to store a value computed by a function, and all other variables should be captured by reference. Then your capture list becomes &, var = func_call(/* as usual */). This can be done for multiple variables. The semantics are the same as if you had done auto var = func_call().
Similarly, if func_call returns a reference, you can also use &var = func_call(). The semantics are the same as if you had done auto& var = func_call().
Note: when capturing a variable by reference and using lambdas after the variable has been destroyed, you will end up with dangling references where accessing that variable in the lambda is undefined behaviour, just like with any other usage of dangling references — this is one of the reasons why I chose to capture by value instead of by reference when showing the 2 lambda example. Keep this in mind while using lambdas.
The parameter list
This is pretty much what you would use for any other function. In particular, there is also support for default parameters.
Also, it is noteworthy that the support for auto parameters was added to lambdas back in C++14, but was added for usual functions only in C++20. This shows how much simpler lambdas are for the language itself, when compared to functions. In the corresponding struct, this corresponds to a templated operator(), one for each instantiation that is needed.
So your lambdas can look like this (while compiling in C++14 as well):
bool f(int a, int b) { return a < b; }
int main() {
int x = 1;
int z = 0;
auto lambda = [&x, y = f(1, z)](int a, auto b, int c = 1) {
if (y) {
x = c;
return a + b;
} else {
return x - b + c;
}
};
}
The specifiers
For this section, it would be helpful to keep in mind our model of structs corresponding to lambdas, in order to understand how the specifier mutable helps, which we will explain below.
You might have noticed that we have not changed the captured value of any variable that we captured by value (the ones we capture by reference can mutate the variables they refer to, so a = b is possible for a being a reference captured variable). The reason is that with the correspondence, the call operator is const by default.
So, how would we mutate these variables? The answer is the usage of the mutable specifier — the same keyword that helps you mutate a variable in a class when you are calling a function that is marked const.
We're now able to do something like this:
auto alternate_even_odd = [i = 0]() mutable {
i ^= 1;
return i;
};
When mutable is specified in a lambda, the const appended to the operator() is removed. This in turn allows us to mutate all captured variables (in this context it means calling functions/operators/member functions on them which require a non-const reference to them).
There are other specifiers — constexpr (since C++17), consteval (since C++20) and static (since C++23), but they would not be very useful in a competitive programming context, so we omit them.
The trailing return type
Notice that the default syntax for a lambda doesn't have a return type, but the syntax for C++ functions has a return type.
In fact, you can have auto return type for C++ functions starting from C++14, and the type is deduced using some type deduction rules. By default, these rules apply for lambdas as well.
However, it is possible to have certain ambiguities/underspecification, like the following:
auto f = [](int64_t x) {
if (x < 0) return 0;
return x;
};
or
auto f = [](auto g, int x) {
return g(g, x);
};
In the first, the compiler is unable to deduce whether the lambda's return type is supposed to be int or int64_t.
In the latter, since the type of g is unknown, it is also unknown what g returns.
In such cases, we must either cast the return values to a certain type, or specify the return type on our own, like the following:
auto f = [](int64_t x) -> int64_t {
if (x < 0) return 0;
return x;
};
auto f = [](auto g, int x) -> int {
return g(g, x);
};
Using lambdas
Okay, now that we have finally shown what the lambda syntax can do in C++, we are yet to use them in any application.
In order to use them, we need to know how to do the following, since the type of the corresponding structs of two different lambdas can be different (and the types of two separately defined lambdas are indeed different in C++):
- Defining lambdas
- Passing lambdas
- Storing lambdas
Defining lambdas
This is very easy, as we have already seen before:
auto f = [](){};
And a cool trick that I didn't mention earlier is that if your parameter list is empty, you can simply drop the ().
So the shortest lambda definition looks like this:
auto f = []{};
Passing lambdas
In C++20, you can do this:
void print_result(int x, auto f) {
std::cout << f(x) << '\n';
}
void print_result_1(int x, auto& f) {
std::cout << f(x) << '\n';
}
void print_result_2(int x, auto&& f) {
std::cout << f(x) << '\n';
}
A small nitpick: the last one is better if you want to pass a lambda by reference if it is an lvalue (informally, something that has an address), but by value if it is not. For example print_result_2(2, [](int x) { return 2 * x; }); and print_result_2(2, some_lambda); both work, but the first of these doesn't work with the print_result_1.
When passing a lambda to a lambda, the above syntax works even for something as old as C++14.
In older standards of C++, like C++11/14/17, you can do this (the & and && variants still work, but I omitted them for the sake of not having too much code):
template <typename Func>
void print_result(int x, Func f) {
std::cout << f(x) << '\n';
}
Storing lambdas
This is something that competitive programmers rarely do, but when they do, a lot of them add unnecessary overheads mostly due to lack of understanding of lambdas/templates.
Firstly I will show how people end up storing lambdas:
struct Storage {
template <typename Func>
Storage(Func f_) : f{f_} {}
// or Storage(auto f_) : f{f_} {}
// or Storage(std::function<int(int)> f_) : f{f_} {}
std::function<int(int)> f;
};
Storage storage([](int x) { return x * 2; });
Other people use this very limited version (we'll get to why it is limited):
struct Storage {
using F = int(*)(int);
Storage(F f_) : f{f_} {}
F f;
};
Storage storage([](int x) { return 2 * x; });
// Storage storage(+[](int x) { return 2 * x; }); also works, relies on decaying from a lambda to function pointer
The most natural way, however, is to do either this:
template <typename F>
struct Storage {
Storage(F f_) : f{f_} {}
F f;
};
Storage f([](int x) { return 2 * x; })
or
auto make_struct = [](auto f_) {
struct Storage {
std::remove_reference_t<decltype(f_)> f;
};
return Storage{f_};
};
auto s = make_struct([](int x) { return 2 * x; });
For the sake of convenience, let's name these v1, v2, v3 and v4.
v1 seems to be the most generic way, but has unnecessary overhead if you don't need to do something like making a vector of lambdas. The reason it works is that std::function "erases" the type of the lambda (with a technique called type erasure), but to do that it needs heap allocation and other overheads, and often is unable to optimize the code in the lambda that interacts with the outside (for instance, recursion). Meanwhile, lambdas are able to be optimized as much as, if not faster than, usual functions, since structs are zero-cost abstractions. I have seen spectacular slowdowns with v1 (50x sometimes) due to lack of optimizations, and I'm of the opinion that unless necessary, type erasure should never be used in a context where performance matters. Of course, no kidding, type erasure is an engineering marvel that deserves its own blog, and std::function, as an extension does so too.
v2 falls back to the concept of a function pointer, which exists since the old days when C was all the rage. It works decently fine in practice, but has a couple of issues:
- It is impossible to cast a lambda that has a capture to a usual function. This should be clear when we think about how a lambda can be represented as a struct. The very fact that a lambda can be converted to a function pointer is a surprise if you know how lambdas are implemented.
- Function pointers suffer from having to use one more indirection than necessary, due to the function call not being known "by the struct". Still better than
std::function in terms of speed, though.
v3 solves all the above problems, in the case you don't need to be able to store the container in a vector. The only drawback is that since it is a templated struct, it can not be defined in local scope, as much as we want to. The reason is that in many implementations, symbols in a template must have external linkage, and this is simply impossible for something in a local scope. There is another minor drawback, which is an inconvenience at best — since partial template specialization is not allowed in C++, you must rely on CTAD (class template argument deduction) to make your code shorter. Otherwise you would have to do something like
auto f = [](int x) { return 2 * x; };
Storage<decltype(f)> s(f); // or std::remove_reference_t<decltype(f)> to remove the reference that comes attached with decltype on an lvalue
Coming to v4 — it does all the things that the other solutions do, and since it is a lambda, it doesn't suffer from the issues that templates do.
As it turns out, v4 is also the most "functional" implementation out of all of them, because you are literally just using functions and nothing object oriented is required.
Is the fact that v4 is the most convenient out of the above 4 just coincidental? I think not.
Anyway, partly since all my library code had been written many years ago, I use v3 for my competitive programming library code — for instance, my implementation that modifies and generalizes the AtCoder library code for lazy segment tree can be found here, starting at line 393. As an aside, it is one of the fastest implementations for that problem, and it used to be the fastest for a very long time until a couple of months ago, and is off from the fastest solution by a few ms. The current fastest solution also uses the v3 pattern for making things generic.
But for anything new, I like using v4 — it is functional and flexible.
The verdict:
- Use v1 whenever you need type erasure but can't do without captures
- Use v2 whenever you need type erasure but can do without captures
- Use v3 whenever you don't need type erasure, but want a classical struct definition somewhere, and want all the performance
- Use v4 whenever you don't want type erasure and want your code to be flexible and not depend on CTAD.
Using lambdas with the STL
As promised, here are some applications of lambdas with some of the STL algorithms/data structures.
Since STL algorithms are implemented mainly as functions or function-like objects, the main use of lambdas is as callbacks to the functions. We are able to pass lambdas as one of the parameters of the STL functions in question, and the lambda is called inside the body, which is why it is a callback.
It is also possible to use them in STL containers during construction.
For the precise functionality of the functions I mention below, I would recommend reading about them on cppreference.
Lambdas are used in multiple forms:
Comparators
A comparator is something that returns the result of comparison of its inputs. It is used in the following:
- sorting:
std::sort(l, r, comparator); where the comparator tells whether $$$a < b$$$ or not for inputs $$$a$$$ and $$$b$$$. - binary_search/lower_bound/upper_bound/heap operations/set intersection etc.: similar to sorting.
- next_permutation: finds the next permutation according to an order provided by a predicate.
- containers (map/set, unordered_map/unordered_set): for the constructor for ordered versions, we can pass a lambda that tells when $$$a < b$$$ for inputs $$$a$$$ and $$$b$$$, and for the unordered versions, we can pass a lambda that tells when $$$a = b$$$ for inputs $$$a$$$ and $$$b$$$.
Predicates
A predicate is something that decides whether some condition is true or not, based on its inputs. It is used in the following:
- partition_point — returns the point $$$p$$$ in a range $$$[l, r)$$$ such that $$$f$$$ is true on $$$[l, p)$$$ and false on $$$[p, r)$$$.
- filtering and filtering-based algorithms:
- find_if/find_if_not — returns the first position where the predicate is true/false (also see find_last_if/find_last_if_not)
- default_searcher, boyer_moore_searcher, boyer_moore_horspool_searcher — used in std::search to search for a pattern based on the predicate
- copy_if/copy_if_not — copies all things on which the predicate evaluates to true/false
- remove_if/remove_if_not — similar to copy_if/copy_if_not but removes elements instead
- and others, which are too numerous to list in a blog post
Generators/transformers
- std::generate expects a function object — usually a lambda — and assigns the result of successive calls to every element in the input range. To implement this, a solution using stateful lambdas is the following:
std::generate(l, r, [i = 0]() mutable { return i++; });
// the same as std::iota(l, r, 0);
There is a more idiomatic solution using coroutines, but coroutines in C++ allocate on the heap.
- std::transform expects a function object and for each $$$x$$$ in a range, updates the corresponding position in another range with $$$f(x)$$$.
Hash functions
- unordered maps/sets, boyer_moore_searcher, boyer_moore_horspool_searcher all expect a hashing function to be implemented (if not, they fall back to std::hash), and this should be passed during construction.
n-ary operators
- std::accumulate and std::reduce expect you to have a binary operator (by default, std::plus) to be able to aggregate over a range
- std::partial_sum does the same, but stores values for every prefix sum
- the multitude of inclusive/exclusive_scans and their transform variants also do something similar.
- std::inner_product allows you to pass two different binary operators (one being an analog for +, the other for *).
- std::adjacent_difference does the opposite of std::partial_sum, but in a different order, and expects a function object to be called as the difference operator.
Some useful non-trivial patterns
Immediately invoked lambdas
Consider this situation: you have to initialize some data (let's say some result of precomputation), but you want to
- keep it local, because global scope usually leads to potentially buggy code
- avoid polluting your scope with unnecessary variables, in order to prevent bugs with the same variable
The concept of an immediately invoked lambda comes in here.
In a nutshell, the idea is that we would like to make a new nested scope for it, but scopes are not expression while lambdas are.
So your solution would earlier look like this:
std::vector<int> a;
{
// process and modify a
}
and it becomes this:
auto a = [&] {
std::vector<int> a;
// process and modify a
return a;
}(); // notice these parentheses
There are a couple more benefits to this, arising out of the fact that we have now managed to convert a scope into an expression.
So we can do the following easily:
- Complicated initialization can easily be done in the constructor like this (more useful for real life code than competitive programming):
struct A {
A(size_t n, int val) :
a{[&] {
std::vector<int> v(n);
std::fill(v.begin(), v.end(), val);
return v;
}()} {}
std::vector<int> a;
};
Make variables with potentially complicated initialization const if mutation is not needed — this is somewhat of an extension of the previous point, and it often leads to optimized code, even if we ignore the number of errors we would save at compile time.
Precompute and assign at compile time — if we have an array to precompute, we can do it at compile time globally like this:
auto precomputed_array = [] {
std::array<int, 10000> a{};
// preprocess
return a;
}();
Since lambdas are constexpr by default, if everything inside the lambda is constexpr-friendly, the compiler will try to perform this lambda call at compile time, which will in general be faster than computing stuff at runtime, and the compiler can also reason about the data that it has generated at compile time, so it even makes the rest of the program faster.
One small drawback (for Codeforces) is that if there are too many operations in the lambda, you will risk getting a compile time error (telling you to increase your compiler's constexpr operations limit — for which I have not yet been able to find a way from within the source code).
The compiler is doing the best it can (and the assembly for constexpr-ed code will be much faster than the assembly for non-constexpr-ed code, simply because what is left to run is the bare minimum possible), and for the compiler, there is no limit on computational resources other than the ones due to the machine. Unfortunately, this doesn't work out for practical purposes like contests, where compile-time and system limitations (which include compiler limits that are built into it, but can be changed).
One hacky workaround is:
auto something = [] {
int a; // note that it is not initialized, only declared, so it is not constexpr friendly. so the compiler will not constexpr it. it is definitely a code smell, but what can we do?
// rest of the function
}();
This is a workaround that I have been using for a long time now, as a way to prevent things from getting constexpr-ed at compile time. Don't do this in real-life code though.
Recursive lambdas
We can implement recursion in a Turing machine, but can we do so with lambdas? Recall that we noted that the Y-combinator is a way to do precisely this thing in an untyped lambda calculus.
We can write a somewhat similar analog for it in C++ lambdas too, using the C++14 feature that allows us to have auto arguments.
auto fib = [](auto self, int n) -> int {
if (n <= 1) return n;
return self(self, n - 1) + self(self, n - 2);
};
std::cout << fib(fib, 10) << '\n';
(If you want to be more efficient in the general case, consider using auto&& instead of auto).
Let's look at how we came up with this implementation.
We don't have a way to refer to the unnamed lambda inside itself with C++ syntax (and the lambda calculus syntax).
So what is the next best thing we can do? Yes, just make a dummy parameter that will (whenever it should be used) be itself, and remember to call the defined lambda with itself whenever it needs to be used. This is precisely what the above code does.
As a fun exercise, let's try writing a function that takes a lambda, which has 2 arguments — one referring to itself, and the other being what it should call (and will eventually become itself). Our target would be to do something like the following:
auto lambda = [](auto self, int n) {
// something
// the recursive call is of the form self(n - 1)
};
auto rec_lambda = add_recursion(lambda);
std::cout << rec_lambda(10) << '\n';
We will ignore all considerations of performance for now, and make copies of everything, for ease of presentation.
Let's make a function object that provides an overload for operator(), and abstracts out the self(self, ...) calls into just self2(...) calls — then we can use self2 as the self parameter in the original lambda's definition, and the double recursion (which should ideally be optimized away) will allow us to do what we want.
template <typename F>
struct add_recursion_t {
F f;
template <typename X>
auto operator()(X x) {
return f(*this, x);
}
};
template <typename F>
auto add_recursion(F f) { // could have as well been implemented as a lambda
return add_recursion_t{f};
}
This is also what the std::y_combinator proposal does, but with better optimizations that sadly renders the code less than readable. This paper is redundant with the C++23 feature called "Deducing this" (which also solves a lot of other problems, not limited to lambdas).
To avoid writing self so many times, it allows us to refer to the lambda itself in its body, and write
auto fib = [](this auto&& self, int n) { // notice that the -> int is gone
if (n <= 1) return n;
return self(n - 1) + self(n - 2);
};
std::cout << fib(10) << '\n';
You can test this code out on the latest Clang release.
But can we do this in just lambdas? The answer is
Yes and noAs we pointed out, the Y-combinator allows us to do this in a lambda calculus (which is untyped by default).
But, there is no way to use C++ lambdas in the exact same manner to implement a Y-combinator, or in fact any fixpoint combinator, because "pure" lambda expressions in C++ follow a simply typed lambda calculus, and simply typed lambda calculus does not admit a fixpoint combinator.
The existence of strong typing is something that prevents recursion to be implemented in C++ lambdas itself (at least without relying on other features in the function body), which is why even though untyped lambda calculus is Turing complete, simply typed lambda calculus is not.
In fact, it can be shown via induction that there are no programs that don't terminate in a simply typed lambda calculus. However, if a fixpoint combinator existed, applying it to itself would lead to infinite recursion, a contradiction. More generally, if there was a general recursion mechanism that could emulate a Turing machine, the existence of an infinite loop would lead to a contradiction to the guaranteed termination of an expression in a simply typed lambda calculus. The keyword here is "strongly normalizing".
If it was allowed to capture this in a lambda, then this would have been possible, and indeed this is how C++23 handles this problem. People use std::function to implement recursive lambdas just because they can capture the std::function that they assign the lambda to. The fact that it is a concrete type but allows us to typecast from a structure that is of an arbitrary type is quite a feat, which is why anyone serious about programming language design should learn about how type erasure is implemented.
This is a great resource on how to implement recursion in OCaml and Haskell.
Stateful lambdas
Have you ever wanted a Python generator in your code? Turns out that with mutable state, you can implement stateful lambdas that work in a similar manner.
It should be abundantly clear with the std::generate example we used a while back that stateful lambdas are nothing but objects with a single member function accessible via the call operator, and some mutable state represented by the data captured by them. It is helpful to remember the struct-to-lambda correspondence here.
For instance, let's say you want to print something that looks like a tuple, and std::apply works on it.
How would you print its space separated members?
std::apply([i = 0ULL] (const auto&... x) mutable -> void {
(((i++ ? (std::cout << ' ') : void()), std::cout << x), ...);
}, tuple_object);
Here we have made abundant use of fold expressions, but the main point is that after expansion, this mutates the state of i inside the body each time there is an i++, and a space is printed before every element except the first element.
Similarly, you can write a random number generator as follows (taking the example from here):
auto next_random = [
splitmix64 = [](uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
},
FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(),
random = 0
] () mutable {
return random = splitmix64(random + FIXED_RANDOM);
};
while (n--) std::cout << next_random() << '\n';
If you want to, it is also possible to write all of your code in a single immediately-invoked lambda, but that is something I discourage you from writing, unless you want to obfuscate code or just want to challenge your brain.
For example, this code for the latest Div2A works, but I definitely do NOT recommend that you write code this way. However, it is quite instructive to understand why this code works and why certain variations do not, so I definitely DO recommend reading and understanding this — it'll help cement your understanding of how captures work, what is called when, and so on.
#include "bits/stdc++.h"
int main() {
[rd = [] {
int x; std::cin >> x;
return x;
},
wt = [](auto x) { return (std::cout << x, 0); },
sorted = [](auto x) {
std::sort(x.begin(), x.end());
return x;
},
forn = [](auto f, int n) {
while (n--) f();
return 0;
}] {
[&, _ = forn(
[&]() {
auto n = rd();
auto k = rd();
[&, a = std::vector<int>(n)]() mutable {
[&, _ = std::generate_n(a.begin(), a.size(), rd)]() {
[&, ans = (k == 1 && a != sorted(a) ? "NO\n" : "YES\n")]() {
[_ = wt(ans)]() {
};
}();
}();
}();
},
rd())]() {
}();
}();
}
Some other interesting patterns
Using lambdas for implementing classes
Note that we claimed that lambda calculus is Turing complete. But can it implement classes? The answer is of course yes.
Can C++ lambdas implement classes? Also yes.
Let's let go of the implementation of lambdas in C++ for now, and think of implementing objects in terms of functions.
For implementing classes, we need data and member functions. For data, we can just store the data as a capture in a lambda. But what does the lambda do? We should be able to call something using the captured data, so the lambda should take as a parameter whatever the implementation of the member function should be.
So, once we have an object, we can call the data with the function, instead of calling the function on the data.
// constructor
auto range = [](size_t l, size_t r) {
return [l, r](auto f) {
return f(l, r);
};
};
// (free) member functions
auto len = [](size_t x, size_t y) { return y - x; };
auto right = [](size_t x, size_t y) { return y; };
auto left = [](size_t x, size_t y) { return x; };
// usage
auto a = range(1, 5); // this is an object
auto len_a = a(len); // compare with a.len() in usual C++ syntax
And if we want to support recursive functions, we can change the definitions a tiny bit.
auto range = [](size_t l, size_t r) {
return [l, r](auto f) {
return f(f, l, r);
};
};
auto len = [](auto self, size_t x, size_t y) { return y - x; };
auto right = [](auto self, size_t x, size_t y) { return y; };
auto left = [](auto self, size_t x, size_t y) { return x; };
auto depth = [](auto self, size_t x, size_t y) {
if (y - x <= 1) return 0;
return 1 + self(self, x, x + (y - x) / 2);
};
auto a = range(1, 5);
auto len_a = a(len);
Mutual recursion can also be implemented similarly, but would require much more effort. Do let me know if you find some way to implement mutual recursion in a clean manner!
Inheriting from lambdas
template <typename... T>
struct S : T... {
template <typename... L>
S(L&&... l) : T(std::forward<L>(l)...) {}
using T::operator()...;
};
This can be used to implement a somewhat generic lambda by providing different implementations like this:
S generic_lambda = {
[](int x) { return 1; },
[](double d) { return 0.0; }
};
std::cout << generic_lambda(0) << '\n';
std::cout << generic_lambda(1.0) << '\n';
But we already have generic lambdas in C++20, and they're pretty interesting in themselves.
Examples of competitive programming code using C++ lambdas
Finally, let's come to some useful code patterns involving lambdas that I use (and used to use) while solving problems.
As a local function
This seems to be the most popular usecase for lambdas, and for good reason — you can avoid code duplication by literally making a code block executable (the & capture does wonders for this usecase). It ends up being particularly useful in the following scenarios:
- When you have to implement a function for a certain query, but it will be used multiple times, perhaps with slightly different behaviours.
- When you are implementing a data structure inline — i.e., when you don't have library code at hand, and want to avoid having to declare a struct for, say, a segment tree or a Fenwick tree or a DSU.
- When you want to avoid rewriting annoying bits of code like when you are writing code for an interactive problem, where the input/output format is complex (even for a very basic format, you need to print, flush, read and return, which deserves a function of its own).
For example, although the intent is not very clear in this example (unless we try solving the problem itself), it is clear that there would have been a lot of code duplication without the use of a lambda — just count the number of calls to the lambda.
DFS and other applications of recursive lambdas
Most people implement DFS as a function, and to do that, they make their graphs global too.
What happens when we want to do a multi-test problem? Clear graphs each time? Of course that has the potential to be buggy.
So what some other people do is to make graphs local, but pass them as a parameter. Similarly, if they want to update any arrays/vectors/integer, like visited/color/component/n_components, they also pass them as a parameter.
Why is this bad? If you swap out two arrays/variables in the references, it would not be a very obvious bug. And it just increases your context switch, because now you have to care about every function call. So if you are implementing a particularly involved DFS, you will end up being more prone to bugs than you could bargain for.
Some smart people realized this and started using local lambdas for DFS, but they used the following trick (which is still not the best trick, I'll explain why in a moment):
std::function<int(int, int)> dfs = [&](int u, int p) {
int sum = 1;
for (auto v : g[u])
if (v != p) sum += dfs(v, u);
return sum;
};
int sz = dfs(0, -1);
Why it is not the best approach:
- Typing the types twice is too much work
- Type erasure (yet again) makes recursive functions quite slow. It might not be visible for DFS, but once you start using it for something like divide and conquer or recursive DP that needs of the order of $$$10^7-10^8$$$ recursive calls, the performance hit would almost invariably make your solution too slow to get AC.
- No support for default parameters — some might see this as a good thing, but the point is that it is abstracting away too much detail from the lambda.
Here's what I use:
auto dfs = [&](auto self, int u, int p = -1) -> int { // can also be auto&& if you want to be careful
int sum = 1;
for (auto v : g[u])
if (v != p) sum += self(self, v, u);
return sum;
};
int sz = dfs(dfs, 0);
Some very high rated programmers use this pattern too, for example, this submission, and for good reason — it pretty much always compiles down to the most optimal code (according to the compiler). The only case I know of this being slower than a usual implementation was because the compiler was vectorizing the DFS(!) and was leading to instruction cache misses. That was a very peculiar case, and I don't expect it to encounter it again in the wild, especially not in a problem with a tight TL.
Others use the idea outlined in the now-redundant std::y_combinator proposal, and do something like this:
// template code
template <class Fun>
class y_combinator_result {
Fun fun_;
public:
template<class T>
explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
// actual code
auto dfs = y_combinator([&](auto self, int u, int p = -1) -> int {
int sum = 1;
for (auto v : g[u])
if (v != p) sum += self(v, u);
return sum;
});
int sz = dfs(0);
For instance, this submission.
In fact, this is such a popular pattern that some high-rated people put it on top of their bare minimum templates as well, for instance, here.
The one drawback for this template is that sometimes the compiler is not able to reason through all the abstraction, and the code generated might be slightly slower. This is fortunately not the case for most cases, but there is a visible overhead difference in a few cases I have seen.
Interfacing library code
Library code should ideally be hidden away in a header file, but since most online judges don't have header file support, we are forced to write library code before any of the actual code begins.
It is also important to ensure that after copypasting library code into your submission, there is absolutely no change that you need to do in the library code unless it is a fundamental difference from the logic of the data structure/algorithm, and you just happen to have all the code at hand. Otherwise, you would be editing a large piece of code that you might have forgotten the details/quirks of, and it is easy to end up with bugs.
To do this, it is quite important to implement your library in a way that is as generic as possible. And there are few things more generic than allowing your data structure to execute arbitrary code.
Hence, it makes for a really good choice to use a lambda as a customization point. In fact, the C++ standard calls certain types of function objects "customization points" which goes on to show that interfacing into library code with functions/function objects is a well-understood/well-adopted design practice that is also very convenient for library usage.
As an example of such a thing, my implementation that modifies and generalizes the AtCoder library code for lazy segment tree can be found here, and it uses lambdas as possible customization points. It not only implements lazy segment trees (with some opt-in optimizations), but it also has functionality for normal segment tree, with barely any overhead compared to a usual segment tree implementation.
Algorithms with custom predicate/aggregation function
This is in fact one of the most common applications. There are countless lines of code among codeforces submissions that essentially sorts an array according to a given predicate: for instance, this code.
There are also a very large number of binary search submissions that follow the template "define a predicate, do binary search on it" — for instance, this code. Note that the manually written binary search could have been avoided by using std::partition_point as well, but it is not very popular for some reason.
Prefix and suffix sums (usual addition or multiplication or xor) can be implemented using std::partial_sum using lambdas as well.
Please let me know if there is anything I missed out, and constructive comments on the content in general are welcome!
