Writing Universal memoization function in C++11

by

A compact one returning a lambda:

template <typename R, typename... Args>
std::function<R (Args...)> memo(R (*fn)(Args...)) {
    std::map<std::tuple<Args...>, R> table;
    return [fn, table](Args... args) mutable -> R {
        auto argt = std::make_tuple(args...);
        auto memoized = table.find(argt);
        if(memoized == table.end()) {
            auto result = fn(args...);
            table[argt] = result;
            return result;
        } else {
            return memoized->second;
        }
    };
}

In C++14, one can use generalized return type deduction to avoid the extra indirection imposed by returning std::function.

Making this fully general, permitting passing arbitrary function objects without wrapping them in std::function first is left as an exercise for the reader.

More Related Contents:

  1. Difference in make_shared and normal shared_ptr in C++
  2. What are the advantages of list initialization (using curly braces)?
  3. std::thread pass by reference calls copy constructor
  4. Static Data Member Initialization
  5. Difference between std::regex_match & std::regex_search?
  6. What does the standard library guarantee about self move assignment?
  7. What is a raw string?
  8. Why should I avoid std::enable_if in function signatures
  9. declare template friend function of template class
  10. Is std::string ref-counted in GCC 4.x / C++11?
  11. How std::function works
  12. How do I use unique_ptr for pimpl?
  13. Why do we copy then move?
  14. Mesh class called with default constructor not working OpenGL C++
  15. Are notes and examples in the core language specification of the C++ Standard non-normative?
  16. What is std::decay and when it should be used?
  17. GNU C++ how to check when -std=c++0x is in effect?
  18. Clang doesn’t see basic headers
  19. Do these members have unspecified ordering?
  20. Check traits for all variadic template arguments
  21. Convert between string, u16string & u32string
  22. Is there any case where a return of a RValue Reference (&&) is useful?
  23. Has the new C++11 member initialization feature at declaration made initialization lists obsolete?
  24. What is different between join() and detach() for multi threading in C++?
  25. std::thread error (thread not member of std)
  26. Advantage of using trailing return type in C++11 functions
  27. Dependent name resolution & namespace std / Standard Library
  28. Implementation of Permutation, Combinations and PowerSet in C++ [duplicate]
  29. std::this_thread::sleep_for() and GCC
  30. Why isn’t std::array::size static?

Leave a Comment