memoize

memoize.cpp

#include <iostream>
#include <functional>
#include <unordered_map>
#include <utility>

template <typename IN_TYPE, typename OUT_TYPE>
std::function<OUT_TYPE(IN_TYPE)> memoize(OUT_TYPE(*f)(IN_TYPE))
{
  std::unordered_map<IN_TYPE, OUT_TYPE> storage;
  return [f, storage](IN_TYPE x) mutable -> OUT_TYPE
  {
    const auto it = storage.find(x);

    if (it == storage.end())
      return storage.insert(
        std::make_pair(x, f(x))).first->second;
    else
      return it->second;
  };
}

int costly_function(int x)
{
  // imagine a very costly function
  return x * x;
}

const auto costly_function_memoized = memoize(costly_function);

int main()
{
  std::cout << costly_function_memoized(10) << std::endl;
  std::cout << costly_function_memoized(10) << std::endl;
}