Re: Perl's memoize function in C++

lookup table for an argument(s) after the function has been called once
with a particular set of arguments.

[...]


code or including additional dependencies in the original code?

In order for a recursive function to properly memoize, you either have
to modify the function to call itself through a memoizing decorator
(like Nicola suggests), or "intrusively" memoize by inserting the cache
code into the body of the function. Following the idea of
"MEMOIZE_BEGIN(int, int)" from your other post, you could implement it
like this:

// define additional structs for different function arities
// use boost::tuple as the key
template<typename Ret, typename Arg1>
struct Memoizer1
{
        typedef std::map<Arg1, Ret> CacheMap;

        Ret* m_pRet;
        Arg1* m_pArg1;
        CacheMap* m_pMap;

        Memoizer1(CacheMap* pMap, Ret* pRet, Arg1* pArg1) :
m_pRet(pRet),
m_pArg1(pArg1), m_pMap(pMap)
        {}

        ~Memoizer1()
        {
                (*m_pMap)[*m_pArg1] = *m_pRet;
        }
};

#define MEMOIZE1(RetType, RetVar, ArgType, ArgVar) \
static std::map<ArgType, RetType> cacheMap;
                         \
{
                     \
        std::map<ArgType, RetType>::iterator iter =
cacheMap.find(ArgVar);\
        if (iter != cacheMap.end())
                                        \
                return iter->second;
                                        \
}
                                 \
Memoizer1<ArgType, RetType> memoizer(&cacheMap, &RetVar, &ArgVar);

use like this:

int fib(int n)
{
        int ret;

MEMOIZE1(int, ret, int, n) // return type, return variable, argument 1
type, name of argument 1

        if (n < 2)
                ret = n;
        else
                ret = fib(n-1) + fib(n-2); // or return (ret = fib(n-1)
+ fib(n-2));

        return ret;
}

The code can handle early function returns, as long as the correct
return value is assigned to the return variable (as in the comment).
It would probably be a good idea to have the function arguments be
const-qualified.
If I were going to use this in production code, I would include some
sort of mechanism to prevent the cache from getting too big, or a way
to clear it out.
It may be possible get rid of the type arguments to the macro or to
avoid creating a different class for each argument count.

Hope it helps.

Brian

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]