Memoize.cpp

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
struct memoized_function;

template
class memoized_function : public boost::function
{
   private:
   mutable std::map<a> m;
   typedef boost::function super;

   public:
   template
   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
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
}
Advertisements


%d bloggers like this: