Re: [boost] Interest check: memoization

Subject: Re: [boost] Interest check: memoization
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2009-01-26 07:40:47

James Porter wrote:

> That's the plan, but I was writing for gcc 4.3, and auto is only 
> available in gcc 4.4. :)

Well, bind has an unspecified return type, and that never bothered anyone.
If you don't have auto, just don't make it a named variable.

> 
>> Does your memoize adaptor require knowing the signatures of the 
>> function object?
> 
> arbitrary function
> objects can have many overloads of operator(), and there would need to 
> be a way to specify which overload is associated with the memoizer.

Can't you just do something like

template<typename F>
struct memoizer
{
     memoizer(F f_) : f(f_) {}

     typedef typename boost::result_of<F>::type result_type;

     template<typename T1, typename T2, ..., typename Tn>
     result_type operator()(T1 t1, T2 t2, ..., Tn tn)
     {
        typedef boost::tuple<T1, T2, ..., Tn> tuple_type;

        typedef std::map<
            tuple_type,
            result_type
        > map_type;

        static map_type values;

        tuple_type tuple = boost::make_tuple(t1, t2, ..., tn);
        map_type::iterator it = values.find(tuple);

        if(it == values.end())
           it = values.insert(
                std::make_pair(tuple, f(t1, t2, ..., tn))
            ).first;

        return *it;
     }

private:
     F f;
};

template<typename F>
memoizer<F> memoize(F f)
{
     return memoizer<F>(f);
}

With ... standing for preprocessing magic.