0

I am fairly new to dynamic programming, i have seen people, memoize in javascript using objects. But i would like to know what will be the most efficient way to memoize in c++. Which data structure should i use, is map good? orr is there something better, please let me know.

Tushar Bhatt
  • 1
  • In JS more or less everything is a kind of object. As for what data structure to use, it depends on what you need to memoize, and how you need to access the memoized data. You could use a single `static int` variable if all you want is a single `int` value "memoized". – Some programmer dude Jul 25 '21 at 18:30
  • 1
    This is hard to answer without a more concrete problem. Probably a `std::unordered_map` is the most generic solution, but depending on the problem a `std::vector` might be more suitable. – G. Sliepen Jul 25 '21 at 18:30
  • Does this answer your question? [Writing Universal memoization function in C++11](https://stackoverflow.com/questions/17805969/writing-universal-memoization-function-in-c11) – Caleb Jul 25 '21 at 18:37

1 Answers1

2

I think you should use unordered_map instead of map.

The reason is that the time complexity for the search operation are as follow:

  • unordered_map = O(1)
  • map = O(log(N))

The reason is that unordered_map works as a hash table while map works as a binary tree.

Similarly, you can also use unordered_set instead of set for the same reason:

The time complexity for the search operation are as follow:

  • unordered_set = O(1)
  • set = O(log(N))
Job_September_2020
  • 858
  • 2
  • 10
  • 25
  • 1
    One should bear in mind that `unordered_map` has O(1) **amortized** time complexity, but `map` guarantees `O(log N)` on **each** search operation. This is a general note, for DP problems most likely is doesn't matter. – Evg Jul 25 '21 at 19:37