优化RecursionArray接口

Question

不久前，我创建了一个类，命名为“递归数组”。它是一种动态创建回忆录序列的方法，例如Fibonacci序列或阶乘数列。其概念是通过只提供第一个值和递归公式来创建由递归定义的数学序列；所有计算结果都内部存储在一个向量中。这允许以递归的方式创建数学公式，而不必考虑访问时间；每个结果只计算一次。下面是基类：

#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" */
};

它是一个使用静态多态性的基类。下面是一个用户定义的派生类的示例：

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

最后，下面是如何使用用户定义的类：

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
}

问题是，我想保持用户端的简单性，但也要避免virtual (因此是静态多态)。类中有三个主要函数：* function：递归公式。* operator()：以便最终用户可以使用最终实例作为函数。* self：助手函数(与操作符()相同)，这样递归公式就更容易编写了。

如果用户不需要专门化types_t并只给MemoizedFibonacci，那就太好了，但我似乎无法找到这样做的方法。你是否有办法减轻函数式作家的工作？

Answer 1

在您发布的内容中有一个(轻微)错误--types_t的前向声明：

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

类似地，您已经转发了定义的class MemoizedFibonacci，然后将其定义为struct MemoizedFibonacci (这并不是一个真正的问题，但是clang会在启用警告的情况下抱怨)。

最好不用专攻struct和value_type。通常，decltype可以帮助您绕过这一问题，但是，在本例中，由于您使用的是CRTP和静态多态性，不幸的是它无法工作。实际上，我同意使用另一个模板参数可能是一个比强制template专业化更好的解决方案。

对我来说，这里最大的缺点是，这只适用于接受单个std::size_t参数的函数。对于您的使用来说，这可能是很好的(计算仅依赖于一个变量的数学序列)。使用各种模板，您可以取消这个限制(以牺牲另一个限制为代价)。如下所示(不完整，但希望给您一个想法)：

#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_;

};

这消除了这样的限制，即您需要一个std::size_t参数，而代价是额外的复杂性，并且可以轻松地强制执行到给定大小的计算。交易是否值得取决于你，但这是值得考虑的事情。