# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3741 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3443 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | atcoder_official | 162 |
3 | maomao90 | 162 |
5 | adamant | 158 |
5 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
8 | djm03178 | 154 |
10 | Dominater069 | 153 |
Name |
---|
Epic blog as usual ! It is very clear and the discussed patterns are very cool and useful :)
I'm curious if anyone will scroll down far enough to read this comment.
Jokes aside, this is a fantastic blog. The hours I spent reading it were definitely well spent. I learned many things that I didn't know before. If you haven't read it already, I suggest you do.
Is stuff like this even useful for CP? you can always use regular methods which will even be much faster. Fwiw, I also use lambdas occasionally while writing code for CP problems, but I think this blog is more for C++ developers than people who just use C++ for CP.
It's up to you whether you should learn it or not. The first point in the "why you should use lambdas" is very relevant to your concern about it not being seemingly useful for CP.
False, there are instances where lambdas are faster.
What's the difference anyway? :) Anyway, it is not purely a C++ blog. It introduces a model of computation in the beginning that can make it much easier to think of things. Similarly, in some of the latter sections, I talk about some language-agnostic ways of doing programming, so it's not just about C++ developers.
Also, it is worth noting that every time there is a "new" feature, there is a non-trivial amount of pushback from the competitive programming community, saying "oh, this is not relevant for competitive programming, let's just stick to our global array pointer based adjacency list and manual for loops" and as a result they limit their own thinking process.
Rather than thinking in terms of abstract objects (which is what a lot of IMOers do, for instance, but not so many IOIers), programmers limit the way they think to the way they write their code. I've seen an interesting phenomenon happen with a lot of competitive programmers — if they don't have a decent amount of math experience, they are usually completely unable to reason about infinite sets, let alone real numbers. One reason is that they don't think about infinite sets of objects as much as the math people do, but the question is why do they avoid thinking of infinite sets? Surely you could just think of the indices of an array as being a half-infinite line, or circular arrays as being equivalence classes under the modulo operation (the latter had started gaining some momentum after circular array problems became common). But programmers don't do so, and this is mainly because they limit their thought process by their tools.
There are quite a lot of top competitive programmer who have been programming for a long time, but also have been flexible to change (some of their codes have been linked in the article). Not saying that this is the only way to grow as a competitive programmer, but it does not hurt to augment your knowledge graph from time to time, because unexpected connections pop up everywhere (for instance, IMO 2015 P6 was inspired from juggling, who could have guessed).
One thing to note is that you can only capture local variables in lambda (sorry if it's mentioned, as I didn't see it in the "The capture list" section). So if you defaulted capture by value
[=]
, and you are referring to a global variable name inside the lambda, it is accessing the global variable instead of it being captured, and have to be careful.Ah yes, I somehow forgot to mention that, since I don't use global variables in the first place. I'll edit that in, thanks!
I use
function<void(int, int)> dfs = [&](int v, int pr)
, and I didn't know that it is slower thanauto dfs = [&](auto self, int v, int pr)
. Though, writingdfs(dfs)
is SOOO ugly that I don't think I will switch anyway :)I think it's a matter of personal preference, but std::function has betrayed me multiple times in the past. I think you would really like the C++23 feature which would allow you to get rid of passing the lambda to itself (though the current state of things should remind you of Python member functions a bit). The y_combinator solution is a feasible solution for the meantime but it is definitely not the best solution either.
y_combinator also can allow you to write something like:
Another reason I moved to pure C++ lambda recursion is that std::function requires you to write the function signature twice, which is a bit weird in my opinion. (Unrelated, but the fact that we need to pass a lambda to itself (which can't be done in simply typed lambda calculus) for implementing recursion is because untyped lambda calculus is not Turing complete).
Thankfully signatures in c++ allow named arguments, so you can use this define
#define ff(T, name, args...) function<T(args)> name = [&](args)->T
and write signature once
Oh, that's a reasonable solution (though not the best looking one either). The main reason I avoid std::function is still performance though.
Here's a benchmark to show how bad
std::function
can be, compared to a usual function. Also, here's an even more absurd benchmark, which shows that the compiler can optimize away all code in lambdas and standard functions, but not std::function.From left to right: traditional function, recursive lambda, and std::function.
Normally, I have zero/one/two recursive lambdas in my code, and most of the time they are classical, and sometimes I have snippets for them, so it's not that big of a deal for me to write the parameters twice. Though, it is indeed a bit annoying that it doesn't compile if I quickly decide to add another parameter, and I need to remember to add it to the signature too.
Your templates are amazing! I have learned a lot about C++ by trying to replicate similar templates.
I believe y-combinator can be simplified with class template deduction guide instead of using a function? I have a similar struct, but i don't know if this will apply to the more complex one in the post. (or maybe this is worse than function method)
Also,
dfs(dfs)
may seem very ugly, but i got used to it, and only useycom
for recursion heavy DPs :)Thanks for the kind words! I'm glad that my templates had educational value as well.
I think the deduction guide should be fine, unless you run into any forwarding related issues. Though it would be better to replace your deduction guide with
ycom(Func) -> ycom<std::decay_t<Func>>
instead.In the above code, you need to ensure that rather than
*this
, you passstd::ref(*this)
. This is because when you callycom(f)(inputs)
it copiesycom(f)
by value whenever you're using*this
, so any captures that you might have inf
will seem to be "reset" just because you're using a new copy off
each time.An example is in this code:
But you'll run into this issue —
auto& f
doesn't work instead ofauto f
if you use thestd::ref
version. This is because we are not making a copy, so the temporaryycom_ref(f)
is trying to be passed as an lvalue, which should not work. This issue plagues the original version too, though, but you don't really needauto& f
sincestd::ref
makes a wrapper type emulating a reference.Also, if you're returning a reference from a lambda, you will end up making a copy with
auto
— this is one of the very few places wheredecltype(auto)
is required.All in all, it is a wise decision to leave the y-combinator code untouched unless you want to really learn how stuff works under the hood.
Excelent blog! My favorite lambda trick is to sort a collection of indices acording to the value of some other array
What is the best way to pass an anonymous, in-place written, comparator to
std::set
? You could do likeBut it requires
std::function
usage. Is there anything better?you need to pass the type of lambda to
std::set
type parameter, but the only way to do this is to assign lambda to some variable first.After the edit: i don't actually know lol if it's possible, why not just assign it to variable first and pass in?
That's annoying and doesn't adhere to "anonymous and in-place" concept :(
this also works. I inserted 1million elements and removed them at random order:
Either of the options will incur penalty, as they can't be inlined, but function pointer seems to be faster.
Edit: forgot to mention this will only work for lambdas without captures, which means code inside lambda can only access global variables.
This works:
Deduction guide can't be added it seems (it needs to be defined right next to set definition), but function works.
In c++20, this seems to work, but only for lambdas without captures:
I think this is because of this change and that C++ 20 lambda without closure does have a default constructor.
Nice solution! It's interesting to note that this is similar to the v4 idiom in the blog, since we are essentially storing this lambda inside the set. Maybe functional declaration is the way to go with C++ lambdas.
In C++20, you can do it with:
Or with an anonymous lambda:
However, the above do not work if you have a capture, you'll have to do this:
This is because according to the C++ standard, the lambda's type doesn't have a default constructor if it has captures, and since the first one is basically
set<int, decltype(cmp)> s(decltype(cmp){})
, it only works with non-capturing lambdas.Added to my list of favourites.
nor Once, I've seen you using lambda function using cache wrapper, similar to y_combinator. Now, I couldn't find it, can you provide link for it.
Hi, I just wrote a blog regarding this here. As a bonus, it also talks about things like generalized hashing and PBDS.
Thank you, it helps allot
Content so good I would like to pay for it.
In the above code I am getting following error
I am unable to resolve it please help me
Please give any suggestions to improve my lambda function
In cases like this, you should give a minimal reproducible example — a small code file where you remove as many things as possible while still keeping the error intact.
I've seen this error when using lambdas with VLAs (which are not legal C++ so you should not be using them either), are you using them by any chance?
Here is the complete submission
sorry what is this VLAs ,can you explain me please
I got the same error previously while solving another problem , but I ignored it at that time
When you declare an array with size that is only known at runtime, it is called a variable length array (VLA). C++ doesn't support them, but they are GCC extensions.
ok thank you , I understood
I get these error can you please help!
error: use of deleted function 'solve()::<lambda(auto:1, long long int, long long int)>::~<lambda>()' auto dfs = [&](auto self, int u, int p = -1) -> int
'solve()::<lambda(auto:1, long long int, long long int)>::~<lambda>()' is implicitly deleted because the default definition would be ill-formed: auto dfs = [&](auto self, int u, int p = -1) -> int { // can also be auto&& if you want to be careful
^auto dfs = [&](auto self, int u, int p = -1) -> int { // can also be auto&& if you want to be careful
return sz[u];
}; dfs(dfs,1,-1);