Writing Universal memoization function in C++11

Looking for a way to implement a universal generic memoization function which will take a function and return the memoized version of the same?

Looking for something like @memo (from Norving's site)decorator in python.

def memo(f):
    table = {}
    def fmemo(*args):
        if args not in table:
            table[args] = f(*args)
        return table[args]
    fmemo.memo = table
    return fmemo

Going more general, is there a way to express generic and reusable decorators in C++, possibly using the new features of C++11?

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.

The right way to do memoization in C++ is to mix the Y-combinator in.

Your base function needs a modification. Instead of calling itself directly, it takes a templateized reference to itself as its first argument (or, a std::function<Same_Signature> recursion as its first argument).

We start with a Y-combinator. Then we add in a cache on the operator() and rename it to memoizer, and give it a fixed signature (for the table).

The only thing left is to write a tuple_hash<template<class...>class Hash> that does a hash on a tuple.

The type of the function that can be memoized is (((Args...)->R), Args...) -> R, which makes the memoizer of type ( (((Args...) -> R), Args...) -> R ) -> ((Args...) -> R). Having a Y-combinator around to produce a 'traditional' recursive implementation can also be useful.

Note that if the function memoized modifies its args during a call, the memoizer will cache the results in the wrong spot.

struct wrap {};

template<class Sig, class F, template<class...>class Hash=std::hash>
struct memoizer;
template<class R, class...Args, class F, template<class...>class Hash>
struct memoizer<R(Args...), F, Hash> {
  using base_type = F;
private:
  F base;
  mutable std::unordered_map< std::tuple<std::decay_t<Args>...>, R, tuple_hash<Hash> > cache;
public:
  
  template<class... Ts>
  R operator()(Ts&&... ts) const
  {
    auto args = std::make_tuple(ts...);
    auto it = cache.find( args );
    if (it != cache.end())
      return it->second;

    auto&& retval = base(*this, std::forward<Ts>(ts)...);

    cache.emplace( std::move(args), retval );

    return decltype(retval)(retval);
  }
  template<class... Ts>
  R operator()(Ts&&... ts)
  {
    auto args = std::tie(ts...);
    auto it = cache.find( args );
    if (it != cache.end())
      return it->second;

    auto&& retval = base(*this, std::forward<Ts>(ts)...);

    cache.emplace( std::move(args), retval );

    return decltype(retval)(retval);
  }

  memoizer(memoizer const&)=default;
  memoizer(memoizer&&)=default;
  memoizer& operator=(memoizer const&)=default;
  memoizer& operator=(memoizer&&)=default;
  memoizer() = delete;
  template<typename L>
  memoizer( wrap, L&& f ):
    base( std::forward<L>(f) )
  {}
};

template<class Sig, class F>
memoizer<Sig, std::decay_t<F>> memoize( F&& f ) { return {wrap{}, std::forward<F>(f)}; }

live example with a hard-coded hash function based off this SO post.

auto fib = memoize<size_t(size_t)>(
  [](auto&& fib, size_t i)->size_t{
    if (i<=1) return 1;
    return fib(i-1)+fib(i-2);
  }
);

Although @KerrekSB posted a link to another answer, I though I'd throw my answer in the ring as well (it's probably slightly less complicated than the linked answer, although in essence it's very similar):

#include <functional>
#include <map>
#include <tuple>
#include <utility>

/*! \brief A template functor class that can be utilized to memoize any 
*          given function taking any number of arguments. 
*/
template <typename R, typename... Args>
struct memoize_wrapper
{
private:

    std::map<std::tuple<Args...>, R> memo_;
    std::function<R(Args...)> func_;
    
public:

    /*! \brief Auto memoization constructor.
     *  
     *  \param func an the std::function to be memoized.
    */
    memoize_wrapper(std::function<R(Args...)> func)
      : func_(func)
    { }

    /*! \brief Memoization functor implementation.
     *  
     *  \param a Argument values that match the argument types for the 
     *           (previously) supplied function. 
     *  \return A value of return type R equivalent to calling func(a...).
     *          If this function has been called with these parameters
     *          previously, this will take O(log n) time.
    */
    R operator()(Args&&... a)
    {
        auto tup = std::make_tuple(std::forward<Args>(a)...);
        auto it = memo_.find(tup);
        if(it != memo_.end()) {
            return it->second;
        }
        R val = func_(a...);
        memo_.insert(std::make_pair(std::move(tup), val));
        return val;
    }
    
}; //end struct memoize_wrapper

Edit: Example usage:

Edit2: As pointed out, this doesn't work with recursive functions.

#include "utility/memoize_wrapper.hpp"
#include <memory>
#include <vector>
#include <algorithm>
#include <iostream>

long factorial(long i)
{
    long result = 1;
    long current = 2;
	while(current <= i) {
        result *= current;
        ++current;
    }
    return result;
}

int main()
{
	std::vector<int> arg {10, 9, 8, 7, 6, 10, 9, 8, 7, 6};
	std::transform(arg.begin(), arg.end(), arg.begin(), memoize_wrapper<long, long>(factorial));
	for(long i : arg) {
		std::cout << i << "\n";
	}
}

I struggled with the same problem. I created macro that also support (with small modification in recursive code) recursion. Here it is:

#include <map>
#include <tuple>
#define MEMOIZATOR(N, R, ...)                               \
R _ ## N (__VA_ARGS__);                                     \
std::map<std::tuple<__VA_ARGS__>, R> _memo_ ## N;           \
template <typename ... Args>                                \
R N (Args ... args) {                                       \
    auto& _memo = _memo_ ## N;                              \
    auto result = _memo.find(std::make_tuple(args...));     \
    if (result != _memo.end()) {                            \
        return result->second;                              \
    }                                                       \
    else {                                                  \
        auto result = _ ## N  (args...);                    \
        _memo[std::make_tuple(args...)] = result;           \
        return result;                                      \
    }                                                       \
}                                                           

The usage is really simple:

MEMOIZATOR(fibonacci, long int, int);

long int _fibonacci(int n) { // note the leading underscore 
                             // this makes recursive function to go through wrapper
    if (n == 1 or n == 2) {
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

fibonacci(40) // uses memoizator so it works in linear time 
              // (try it with and without memoizator)

See it in action: http://ideone.com/C3JEUT :)

Below is a (thread safe) C++17 function template that acts like std::invoke but memoizes the result:

/**
 * @brief      Drop-in replacement for std::invoke which memoizes the return
 *             result.
 *
 * @param[in]  function  The function whose result needs to be cached
 * @param[in]  args      The function arguments
 *
 * @tparam     Function  The function type
 * @tparam     Args      The argument types
 *
 * @return     A value obtained either by evaluating the function, or by
 *             recalling it from a cache.
 *
 * @note       The function provided must not be a type-erase function object
 *             like a raw function pointer or std::function, because this
 *             function depends on the uniqueness of the Function template
 *             parameter. If you were to call invoke_memoized(f, a) and
 *             invoke_memoized(g, b) in the same translation unit, where f and g
 *             were function pointers of the same type, and a and b were
 *             arguments of the same type, you'd end up using the same cache for
 *             both functions f and g. A reasonable attempt is made to detect
 *             these misuse cases via static_assert.
 */
template<typename Function, typename... Args>
auto invoke_memoized(Function function, Args... args)
{
    using key_type   = std::tuple<Args...>;
    using value_type = std::invoke_result_t<Function, Args...>;

    static_assert(! std::is_same_v<Function, std::function<value_type(Args...)>>,
        "cannot memoize on std::function (use a lambda instead)");

    static_assert(! std::is_same_v<Function, value_type(*)(Args...)>,
        "cannot memoize on function pointer (use a lambda instead)");

    static std::mutex mutex;
    static std::map<key_type, value_type> cache;

    auto key  = std::tuple(args...);
    auto lock = std::lock_guard<std::mutex>(mutex);

    if (cache.count(key))
    {
        return cache[key];
    }
    return cache[key] = std::apply(function, key);
}

You can use it like this:

auto c = invoke_memoized(std::plus<>(), 1, 2.3);

A static cache is maintained for each combination of the function object and argument types. As noted std::function and raw function pointers are rejected, as type-erased functions would get their caches mixed up. You can easily modify this function to impose limits on the cache size.