After hacking around with some simple dynamic programming, it occurred to me that it should be possible to write a simple class template to handle memoization of functions. With the changes in C++0x that help solve the forwarding problem, writing a generic memoizer should be fairly straightforward. (Or so I thought!) The interface is straightforward, so I'll let the following code snippet speak for itself: memoizer<int (int,int)> memo(my_func); int ret = memo(i,j); As you'd expect, this creates a memoizer that caches results of calls to my_func. Pretty simple, right? Well, not exactly. :) (If you'd rather not read about the implementation, you can skip ahead to the end, where there is a link to download the source.) There are a number of issues that make this a fairly complicated problem, even with the improved generic programming facilities in C++0x. Chief among these is copying. With the naive implementation of the memoizer, I found that calculating the result of an unmemoized value created 3 copies (one for creating a tuple to search a map for, and two to insert the tuple into the map), and returning a memoized value created 1 copy (to create a tuple to search the map). To make a long story short, I set about trying to reduce the number of copies to the expected amount: 1 copy for unmemoized values and 0 for memoized values. I'm happy to say that this was a success! The trick was creating a tuple that holds references to each argument and can be upgraded to hold the arguments by value. In this way, we can compare by reference and store by value. This is simple on the surface, but requires some care when dealing with rvalue references. There are also issues with passing convertible types to the memoizer (e.g. passing floats when the function expects ints). For complicated types, you certainly wouldn't want to copy them more than once, and you'd want to use move constructors where possible. This is resolved with some creative manipulation of template types (lines 52-58 of memoizer.hpp). There are still a number of things missing in this code, such as the ability to use function objects with the memoizer, or the ability to specify the map type, but I believe that the most important issues are resolved: * Minimizes copying of arguments * Supports move constructors wherever possible * Safely converts arguments to the appropriate types The full source code for this is available here (requires gcc 4.3 or a compiler that supports variadic templates and rvalue refs): http://www.teamboxel.com/misc/memoizer.tar.gz Comments and criticisms are welcome. If there's interest, I will - of course - work on a version that supports the current C++ standard. - Jim