mark++

Here’s my attempt at writing a higher-order-function in C++ which allows one to memoize a function. It’s not complete. It doesn’t work for functions with signatures much more complicated than int fib(int).

Perhaps most disappointing is that there appears to be no way to generically memoize the recursive calls, the way Memoize.pm can.

#include <boost/function.hpp>
#include <map>
#include <iostream>

using namespace std;

template< typename T >
struct memoized_function;

template< typename R, typename A >
class memoized_function : public boost::function
{
   private:
   mutable std::map m;
   typedef boost::function super;

   public:
   template< typename T >
   memoized_function( const T& x ) : super(x) {}

   R operator()(A& a) const
   {
      if( m.find(a) != m.end() )
         return m[a];

      m[a] = super::operator()(a);
      return m[a];
   }
};

template< typename T >
memoized_function memoize( const T& f )
{
   return memoized_function(f);
}

int fib( int n )
{
   cout << "called fib(" << n << ")\\n";

   if( n < 2 )
      return n;

   return fib(n-1) + fib(n-2);
}

int main()
{
   cout << fib(5) << endl << endl;

   typedef boost::function func;
   func fastfib = memoize( fib );
   cout << fastfib(5) << endl;
   cout << fastfib(5) << endl;  // just a look up
}