Abstract Memoizer

Question

I was inspired by this answer to make this.

ex[0] = 1;
ex[n_] := ex[n] = ex[n - 1] + 0.5^n/n!;

The double assignment in the second line is very important. This causes all function calls to be evaluated only once. Once it has been initially evaluated, it will be saved in ex[n].

After a little research, it looks like I just reinvented a memoizer.

#include <unordered_map>
#include <functional>

template < auto callback,
           typename data_t,
           typename key_t = std::size_t >
class static_memoizer_t
{
public:
    using map_t = std::unordered_map< key_t,
                                      data_t >;
    using callback_t = decltype( callback );

    static_memoizer_t( ) = default;
    static_memoizer_t( static_memoizer_t const & ) = default;
    static_memoizer_t( static_memoizer_t && ) = default;
    static_memoizer_t & operator =( static_memoizer_t const & ) = default;
    static_memoizer_t & operator =( static_memoizer_t && ) = default;
    ~static_memoizer_t( ) = default;

    data_t operator[ ]( key_t const & key )
    {
        if( map.end( ) == map.find( key ) )
            return map[ key ] = callback( key );
        return map[ key ];
    }

    data_t operator[ ]( key_t const & key ) const
    {
        return map.at( key );
    }

private:
    map_t map;
};

template < typename data_t,
           typename key_t = std::size_t >
class dynamic_memoizer_t
{
public:
    using map_t = std::unordered_map< key_t,
                                      data_t >;
    using callback_t = std::function< data_t( key_t const & ) >;

    dynamic_memoizer_t( callback_t callback ):
        callback( std::move( callback ) )
    { }
    dynamic_memoizer_t( dynamic_memoizer_t const & ) = default;
    dynamic_memoizer_t( dynamic_memoizer_t && ) = default;
    dynamic_memoizer_t & operator =( dynamic_memoizer_t const & ) = default;
    dynamic_memoizer_t & operator =( dynamic_memoizer_t && ) = default;
    ~dynamic_memoizer_t( ) = default;

    data_t operator[ ]( key_t const & key )
    {
        if( map.end( ) == map.find( key ) )
            return map[ key ] = callback( key );
        return map[ key ];
    }

    data_t operator[ ]( key_t const & key ) const
    {
        return map.at( key );
    }

private:
    map_t map;
    callback_t callback;
};

The basic gist is that it stores the results of expensive functions. I wanted to add support for expensive recursive functions for my initial inspiration, not sure how to approach that though.

Usage:

int square_of( int i ) noexcept
{
    return i * i;
}

// static usage
using memoizer_t = static_memoizer_t< square_of, int, int >;
memoizer_t memoizer;
memoizer[ 2 ]; // calculates 2*2, returns 4
memoizer[ 2 ]; // pulls 2*2 from map

// dynamic usage
using memoizer_t = dynamic_memoizer_t< int, int >;
memoizer_t memoizer( square_of );
memoizer[ 2 ]; // calculates 2*2, returns 4
memoizer[ 2 ]; // pulls 2*2 from map

Answer 1

Unfortunately, a major weakness of your class is that it only allows functions with a single argument. Now, this can be alleviated by using std::tuple and std::apply, but it's an ugly solution because it forces the user of the class to specify the tuple type, and every invocation of the object requires a std::make_tuple.

Fortunately, this can be solved using variadic templates.

To start, here's a basic definition of our class.

#include<tuple>
template<typename ReturnType, typename ... Args>
class Memoizer
{
};

Now, we need a way to store variadic number and types of arguments. std::tuple is perfect for this.

using tuple_type = std::tuple<Args...>;
using return_type = ReturnType;
using callback_type = std::function<return_type(Args...)>;
using map_type = std::unordered_map<tuple_type, return_type>;

Now, std::tuple doesn't come with an overloaded std::hash. Fortunately, this SO answer provides a good implementation.

Your data members would then become

map_type map;
callback_type callback;

The meat of the implementation lies in operator().

return_type operator()(Args&& ... args)
{
    auto arguments_tuple = std::make_tuple<Args...>(std::forward<Args>(args)...);
    if(map.find(arguments_tuple) == map.end())
    {
       std::cout << "Invoking function\n"; // for debugging
       map.insert({arguments_tuple, std::apply(callback, arguments_tuple)});
    }
    return map[arguments_tuple]; 
}

The method takes the arguments, create a tuple of them and then checks if the map already contains the tuple. If it doesn't, it inserts an entry into the map, using std::apply (C++17 feature).

Usage might look like this:

int func(int x, int y)
{
    return x * y;
}

int main()
{
   Memoizer<int, int, int> mem{func};
   auto t1 = mem(2, 3);
   auto t2 = mem(2, 3);
   std::cout << t1 << '\n';
   std::cout << t2 << '\n';
}

The output is:

Invoking function
6
6

The full implementation is here:

https://godbolt.org/z/Eczq93

You can also use custom types as arguments, provided std::hash and operator== are overloaded for those types.

Answer 2

Some nitpicks:

• Rule of zero — don't explicitly default the special member functions unless necessary.

• This method always traverses the map twice, and sometimes unnecessarily default-constructs a value:

    data_t operator[ ]( key_t const & key )
    {
        if( map.end( ) == map.find( key ) )
            return map[ key ] = callback( key );
        return map[ key ];
    }
  

  The following version avoids most of the problems above, but still traverses the map twice when there is no cached value:

    data_t operator[](const key_t& key) {
        if (auto it = map.find(key); it != map.end()) {
            return it->second;
        } else {
            return map.emplace(key, callback(key))->first->second;
        }
    }
  

  An optimal version might involve using try_emplace and a wrapper around the callback that converts to the value type.