Optimize RecursionArray interface

Question

I created a class a while ago that I named a "Recursion Array". It is a way to create dynamically memoized sequences such as the Fibonacci sequence or the factorial numbers sequences. The concept is to create mathematic sequences defined by recursion by only providing the first values and the recursive formula; all the computed results are internally stored into a vector. That allows to create mathematic formula in a recursive way, without having to care about the access time; each result is only computed once. Here is the base class:

#include <initializer_list>
#include <vector>

template<typename T>
types_t;

template<typename Derived>
class RecursionArray
{
    public:

        using value_type = typename types_t<Derived>::value_type;

        // A RecursionArray is not copyable
        RecursionArray(const RecursionArray&) = delete;
        RecursionArray& operator=(const RecursionArray&) = delete;

        /**
         * @brief Calls "function" and applies memoization
         * @see value_type self(size_t n)
         */
        inline auto operator()(std::size_t n)
            -> value_type
        {
            return self(n);
        }

    protected:

        RecursionArray() = default;

        /**
         * @brief Initializer-list constructor
         *
         * This should be the one and only way to instance a
         * RecursionArray.
         *
         * @param vals Results of "function" for the first values
         */
        RecursionArray(std::initializer_list<value_type> vals):
            _values(vals.begin(), vals.end())
        {}

        /**
         * @brief Calls "function" and applies memoization
         *
         * @param n Index of the value to [compute, memoize and] return
         * @return Value of "function" for n
         */
        auto self(std::size_t n)
            -> value_type
        {
            while (size() <= n)
            {
                // Compute and add the values to the vector
                _values.emplace_back(function(size()));
            }
            return _values[n];
        }

        /**
         * @brief Returns the number of computed elements
         * @return Number of computed elements in the vector
         */
        constexpr auto size() const
            -> std::size_t
        {
            return _values.size();
        }

        /**
         * @brief User-defined function whose results are stored
         *
         * This is the core of the class. A RecursionArray is just
         * meant to store the results of "function" are reuse them
         * instead of computing them another time. That is why a
         * RecursionArray function can only accept unsigned integers
         * as parameters.
         *
         * @param n Index of the element
         * @return See user-defined function
         */
        auto function(std::size_t n)
            -> value_type
        {
            return static_cast<Derived&>(*this).function(n);
        }

    private:

        // Member data
        std::vector<value_type> _values;  /**< Computed results of "function" */
};

It is a base class that uses static polymorphism. Here is an example of a user-defined derived class:

class MemoizedFibonacci;
/*
 * We need to tell to the RecursionArray which
 * kind of data it has to store.
 */
template<>
struct types_t<MemoizedFibonacci>
{
    using value_type = unsigned int;
};

/**
 * @brief Fibonacci function class
 *
 * A way to implement the Fibonacci function and to force it
 * to store its results in order to gain some speed with the
 * following calls to the function.
 */
struct MemoizedFibonacci:
    RecursionArray<MemoizedFibonacci>
{
    using super = RecursionArray<MemoizedFibonacci>;
    using typename super::value_type;

    /**
     * @brief Default constructor
     *
     * To use a Fibonacci function, we need to know at least
     * its first two values (for 0 and 1) which are 0 and 1.
     * We pass those values to the RecursionArray constructor.
     */
    MemoizedFibonacci():
        super( { 0, 1 } )
    {}

    /**
     * @brief Fibonacci function
     *
     * Fibonacci function considering that the first values are
     * already known. Also, "self" will call "function" and
     * memoize its results.
     *
     * @param n Wanted Fibonacci number
     * @return nth Fibonacci number
     */
    auto function(std::size_t n)
        -> value_type
    {
        return self(n-1) + self(n-2);
    }
};

And finally, here is how we can use the user-defined class:

int main()
{
    MemoizedFibonacci fibonacci;

    // The Fibonacci numbers up to the nth are computed
    // and stored into the RecursionArray
    std::cout << fibonacci(12) << std::endl;    // 144
    std::cout << fibonacci(0) << std::endl;     // 0
    std::cout << fibonacci(1) << std::endl;     // 1
    std::cout << fibonacci(25) << std::endl;    // 75025
}

The problem is that I want to keep the user side simple, but also to avoid virtual (hence the static polymorphism). There are three main functions in the class: * function: the recursive formula. * operator(): so that the end user can use the final instances as functions. * self: helper function (same as operator()) so that the recursive formula is easier to write.

It would be great if the user did not have to specialize types_t and could just give MemoizedFibonacci, but I can't seem to find a way to do so. Do you whether there would be some way to ease the functor writer work?

Answer 1

There's a (slight) typo in what you've posted - the forward declaration of types_t:

   template<typename T>
   types_t;
// ^^^^^^^^
// Should be struct types_t;

Similarly, you've forward defined class MemoizedFibonacci and then defined it as struct MemoizedFibonacci (this isn't really a problem, but clang will complain about it with warnings enabled).

It'd be nice to not have to specialise a struct with a value_type. Often, decltype can help you get around this, however, in this case, since you're using CRTP and static polymorphism, it's unfortunately not going to work. I actually agree that using another template parameter is potentially a better solution here than to force specialisation of a template.

To me, the largest shortcoming here is that this only works with functions that take a single std::size_t parameter. Perhaps this is fine for your uses (calculating mathematical sequences that depend only on 1 variable). Using variadic templates, you can lift this restriction (at the expense of imposing another). Something like the following (incomplete, but hopefully gives you the idea):

#include <tuple>
#include <unordered_map>

template<typename Derived, typename... Args>
class RecursionArray
{

public:
    using argument_type = std::tuple<Args...>;

    inline auto operator()(Args&&... args)
        -> value_type
    {
        return self(std::forward<Args>(args)...);
    }

    auto self(Args&&... args)
        -> value_type
    {
        auto tup = argument_type(args...);
        auto it = values_.find(tup);
        if(it != values_.end()) {
            return it->second;
        }
        auto p = values_.emplace(std::make_pair(std::move(tup), function(std::forward<Args>(args)...));
        return p.first->second;
    }

private:
    std::unordered_map<argument_type, value_type> values_;

};

This lifts the restriction that you need to have a single std::size_t parameter, at the expense of extra complexity, and the ability to easily enforce computation up to a given size. Whether the trade-off is worth it is up to you, but it is something to think about.