2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ 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... \$\endgroup\$ – formerlyknownas_463035818 Sep 20 '16 at 20:12
  • \$\begingroup\$ @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. \$\endgroup\$ – R Sahu Sep 20 '16 at 20:15
  • \$\begingroup\$ 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 \$\endgroup\$ – formerlyknownas_463035818 Sep 20 '16 at 20:20
  • \$\begingroup\$ @tobi303, are you worried about size of DLLs/EXEs? \$\endgroup\$ – R Sahu Sep 20 '16 at 20:22
  • \$\begingroup\$ no, I am worried about getting two instantiations with seperate static maps when it actually should be the same \$\endgroup\$ – formerlyknownas_463035818 Sep 20 '16 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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