nor's blog

[C++] Write recursive DP without thinking about memoization
By nor, 4 months ago, In English

https://nor-blog.codeberg.page/posts/2024-01-14-easy-recursive-dp-template/

  • Vote: I like it
  • +86
  • Vote: I do not like it

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

It's nice to see something like @lru_cache implemented in C++. Thanks very much, the blog is great!

Btw, what is the version of C++ that you used?

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

    I'm glad to know that you liked it! I used C++20 when I submitted a few years back, but it works in C++17 too (relevant submission).

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

    In C++ 23, you could use 'deducing this' for lambda recursion.

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      By the way, the way in which we implement recursive lambdas in C++17-20 is just the continuation passing style, which is also how the design of the cache is done in the blog.

      C++23 makes it a language feature (in the form of syntactic sugar) but it still remains a special case. It will definitely help and encourage more people to write recursive lambdas, though.

      → Reply
»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

most important types that we will ever need to hash: ...sets, maps ...

it is worth noting that for equals unordered_sets this hasher can return different values

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

    Thanks for pointing this out. I used the phrase "sequence types" (and not container types) for this precise reason. The (unqualified) default set and map in C++ are ordered and will always give the same hash.

    The implementation, however, doesn't prevent you from using unordered versions of these, so you should indeed take care that you're not plugging them in anywhere.

    → Reply