nor's blog

By nor, 12 months ago, In English
  • Vote: I like it
  • +407
  • Vote: I do not like it

| Write comment?
»
12 months ago, # |
  Vote: I like it +35 Vote: I do not like it

Epic blog as usual ! It is very clear and the discussed patterns are very cool and useful :)

»
12 months ago, # |
  Vote: I like it +58 Vote: I do not like it

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.

»
12 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

  • »
    »
    12 months ago, # ^ |
    Rev. 5   Vote: I like it +25 Vote: I do not like it

    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.

    uou can always use regular methods which will even be much faster.

    False, there are instances where lambdas are faster.

    this blog is more for C++ developers than people who just use C++ for CP

    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).

»
12 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

»
12 months ago, # |
  Vote: I like it +14 Vote: I do not like it

I use function<void(int, int)> dfs = [&](int v, int pr), and I didn't know that it is slower than auto dfs = [&](auto self, int v, int pr). Though, writing dfs(dfs) is SOOO ugly that I don't think I will switch anyway :)

  • »
    »
    12 months ago, # ^ |
    Rev. 7   Vote: I like it +1 Vote: I do not like it

    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:

    auto fact = [](auto fact, int n) -> int {
        if (n <= 1) return 1;
        return fact(n - 1); // notice fact and not self - naming hack
    };
    auto ans = y_combinator(fact)(10);
    

    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).

    • »
      »
      »
      12 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      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

      ff(void, dfs, int v, int p) {
          for(int i : g[v]) if(i != p) dfs(i, v);
      };
      
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

template <typename Func>
struct ycom {
  Func f;
  template <typename... T> auto operator()(T &&...args) {
    return f(*this, forward<T>(args)...);
  }
};
template <typename Func> ycom(Func) -> ycom<Func>;

Also, dfs(dfs) may seem very ugly, but i got used to it, and only use ycom for recursion heavy DPs :)

  • »
    »
    12 months ago, # ^ |
    Rev. 4   Vote: I like it +2 Vote: I do not like it

    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 pass std::ref(*this). This is because when you call ycom(f)(inputs) it copies ycom(f) by value whenever you're using *this, so any captures that you might have in f will seem to be "reset" just because you're using a new copy of f each time.

    An example is in this code:

    Spoiler

    But you'll run into this issue — auto& f doesn't work instead of auto f if you use the std::ref version. This is because we are not making a copy, so the temporary ycom_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 need auto& f since std::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 where decltype(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.

»
12 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Excelent blog! My favorite lambda trick is to sort a collection of indices acording to the value of some other array

vector<int> a(n), p(n)
forn(i, n) cin>>a[i], p[i] = i;
sort(begin(p), end(p), [&](int i, int j) {
    return a[i] < a[j];
};
»
12 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

What is the best way to pass an anonymous, in-place written, comparator to std::set? You could do like

std::set<int, std::function<bool(int, int)>> me(
    [&](int a, int b) {return a < b;}
);

But it requires std::function usage. Is there anything better?

  • »
    »
    12 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    const auto comp = [&](int a, int b) {return a > b; };
    set<int, decltype(comp)> st(comp);
    

    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?

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's annoying and doesn't adhere to "anonymous and in-place" concept :(

  • »
    »
    12 months ago, # ^ |
    Rev. 6   Vote: I like it +10 Vote: I do not like it
    std::set<int, bool(*)(int, int)>> me(
        [&](int a, int b) {return a < b;}
    );
    

    this also works. I inserted 1million elements and removed them at random order:

    ~700ms multiset<int>
    ~700ms multiset<int, decltype(comp)> st(comp)
    ~775ms multiset<int, bool(*)(int, int)> st(comp)
    ~800ms multiset<int, function<bool(int, int)>> st(comp)
    

    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.

  • »
    »
    12 months ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    This works:

    template<typename T, typename U>
    multiset<T, U> make_set(U comp) {
        return multiset<T, U>(comp);
    }
    
        auto c = [&](int a, int b) {return a > b; };
        auto st = make_set<int>(c);
    
    

    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:

        multiset<int, decltype([](int a, int b) {
            return a > b;
        })> st;
    
    

    I think this is because of this change and that C++ 20 lambda without closure does have a default constructor.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    In C++20, you can do it with:

    auto cmp = [](int x, int y) { return x < y; };
    set<int, decltype(cmp)> s;
    

    Or with an anonymous lambda:

    set<int, decltype([](int x, int y) { return x < y; })> s;
    

    However, the above do not work if you have a capture, you'll have to do this:

    auto cmp = [&](int x, int y) { return a[x] < a[y]; };
    set<int, decltype(cmp)> s(cmp);
    

    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.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Added to my list of favourites.

»
11 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, I just wrote a blog regarding this here. As a bonus, it also talks about things like generalized hashing and PBDS.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Content so good I would like to pay for it.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it
    auto solve =[&](ll rw,ll cl,ll till,auto&& solve) -> ll {

        if(cl>=m){
            return 0;
        }

        ll &ans=dp[rw][cl]; 
        if(~ans)
            return ans;
        
        ans=1e18;

        if(cl==0)
            ans= solve(rw,cl+1,till,solve)+1;
        else if(cl==m-1){
            ans=solve(rw,cl+1,till,solve)+1;
        }
        else
            fo(i,0,till+1){
                if(cl+i<m)
                    ans=min(ans,solve(rw,cl+i+1,till,solve)+a[rw][cl+i]+1);
            }

        return ans;

    };

In the above code I am getting following error

dp.cpp: In function 'void solve()':
dp.cpp:146:17: error: use of deleted function 'solve()::<lambda(ll, ll, ll, auto:1&&)>::~<lambda>()'
     auto solve =[&](ll rw,ll cl,ll till,auto&& solve)  {
                 ^
dp.cpp:146:19: note: 'solve()::<lambda(ll, ll, ll, auto:1&&)>::~<lambda>()' is implicitly deleted because the default definition would be ill-formed:
     auto solve =[&](ll rw,ll cl,ll till,auto&& solve)  {

I am unable to resolve it please help me

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please give any suggestions to improve my lambda function

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ^

Spoiler