HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Memoization via template

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
templateviamemoization

Problem

This is kind of follow up of this question on stack overflow...

I wrote the following to utilize memoization for functions that take a single parameter and return a value:

#include 
#include 
using namespace std;

template 
R memoized(T in) {
    static std::map memo;
    typename std::map::iterator found = memo.find(in);
    if (found != memo.end()) { return found->second; }  
    std::cout (1) (1) (1) (1) (1) (1) << std::endl;

    return 0;
}


output:

not found
1
1
1

not found
1
1
1


It is a rather strong restriction that it works only for functions taking a single parameter, but thats ok for now. Is there anything else wrong with this approach?

PS: on purpose this is using only pre C++11

Solution

I would change memoized to work with a functor type and use a traits approach to deduce the return type and the argument type.

template 
typename Functor::R memoized(typename Functor::T in) {
   using T = typename Functor::T;
   using R = typename Functor::R;

   static std::map memo;
   typename std::map::iterator found = memo.find(in);
   if (found != memo.end()) { return found->second; }  
   std::cout << "not found" << std::endl; // only for demo
   R res = Functor()(in);
   memo[in] = res;
   return res;
}

struct Test1
{
   using T = double;
   using R = double;
   R operator()(T x) { return x*x; }
};

struct Test2
{
   using T = double;
   using R = double;
   R operator()(T x) { return x; }
};


My rationale for using a functor is that it simplifies user code.

int main() {
    std::cout (1) (1) (1) (1) (1) (1) << std::endl;

    return 0;
}

Code Snippets

template <typename Functor>
typename Functor::R memoized(typename Functor::T in) {
   using T = typename Functor::T;
   using R = typename Functor::R;

   static std::map<T,R> memo;
   typename std::map<T,R>::iterator found = memo.find(in);
   if (found != memo.end()) { return found->second; }  
   std::cout << "not found" << std::endl; // only for demo
   R res = Functor()(in);
   memo[in] = res;
   return res;
}

struct Test1
{
   using T = double;
   using R = double;
   R operator()(T x) { return x*x; }
};

struct Test2
{
   using T = double;
   using R = double;
   R operator()(T x) { return x; }
};
int main() {
    std::cout << memoized<Test1>(1) << std::endl;
    std::cout << memoized<Test1>(1) << std::endl;
    std::cout << memoized<Test1>(1) << std::endl;
    std::cout << std::endl;
    std::cout << memoized<Test2>(1) << std::endl;
    std::cout << memoized<Test2>(1) << std::endl;
    std::cout << memoized<Test2>(1) << std::endl;

    return 0;
}

Context

StackExchange Code Review Q#141961, answer score: 2

Revisions (0)

No revisions yet.