current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 2 down vote favorite

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 <iostream>
#include <map>
using namespace std;

template <class T, class R, R (*Func)(T)>
R memoized(T in) {
    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 = Func(in);
    memo[in] = res;
    return res;
}

double test(double x){return x*x;}
double test2(double x){return x;}

int main() {
    std::cout << memoized<double,double,test>(1) << std::endl;
    std::cout << memoized<double,double,test>(1) << std::endl;
    std::cout << memoized<double,double,test>(1) << std::endl;
    std::cout << std::endl;
    std::cout << memoized<double,double,test2>(1) << std::endl;
    std::cout << memoized<double,double,test2>(1) << std::endl;
    std::cout << memoized<double,double,test2>(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

share|improve this question
up vote 2 down vote

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>
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; }
};

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

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;
}
share|improve this answer
    
hm.. the functions I want to use it for are partly legacy code. I think its a trade off whether it is worth wrapping them in a functor. However, I couldnt find out how to reduce the number of tempalte arguments on my own. Maybe some tempalte specialisation may help to accept both... – tobi303 Sep 20 '16 at 20:12
    
@tobi303. I think wrapping legacy code with a function is worth it. It obviates the need to repeat the type of T and R every time you call the function. – R Sahu Sep 20 '16 at 20:15
    
I was wondering if this also works across compilation units, ie if I can be sure that there will always be a single template instantiation for each function – tobi303 Sep 20 '16 at 20:20
    
@tobi303, are you worried about size of DLLs/EXEs? – R Sahu Sep 20 '16 at 20:22
    
no, I am worried about getting two instantiations with seperate static maps when it actually should be the same – tobi303 Sep 20 '16 at 20:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.