Блог пользователя nor

[C++] Write recursive DP without thinking about memoization
Автор nor, 5 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • +86
  • Проголосовать: не нравится

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

→ Ответить
  • »
    »
    5 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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.

      → Ответить
»
5 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.

    → Ответить