在运行时获取模板元编程编译时常量

Question

背景

考虑以下：

 template <unsigned N>
struct Fibonacci
{
    enum
    {
        value = Fibonacci<N-1>::value + Fibonacci<N-2>::value
    };
};

template <>
struct Fibonacci<1>
{
    enum
    {
        value = 1
    };
};

template <>
struct Fibonacci<0>
{
    enum
    {
        value = 0
    };
};

这是一个常见的例子，我们可以将斐波那契数的值作为编译时常量：

 int main(void)
{
    std::cout << "Fibonacci(15) = ";
    std::cout << Fibonacci<15>::value;
    std::cout << std::endl;
}

但是您显然无法在运行时获得该值：

 int main(void)
{
    std::srand(static_cast<unsigned>(std::time(0)));

    // ensure the table exists up to a certain size
    // (even though the rest of the code won't work)
    static const unsigned fibbMax = 20;
    Fibonacci<fibbMax>::value;

    // get index into sequence
    unsigned fibb = std::rand() % fibbMax;

    std::cout << "Fibonacci(" << fibb << ") = ";
    std::cout << Fibonacci<fibb>::value;
    std::cout << std::endl;
}

因为 fibb 不是编译时常量。

问题

所以我的问题是：

在运行时查看此表的最佳方法是什么？最明显的解决方案（“解决方案”应该轻描淡写）是有一个大的 switch 语句：

 unsigned fibonacci(unsigned index)
{
    switch (index)
    {
    case 0:
        return Fibonacci<0>::value;
    case 1:
        return Fibonacci<1>::value;
    case 2:
        return Fibonacci<2>::value;
    .
    .
    .
    case 20:
        return Fibonacci<20>::value;
    default:
        return fibonacci(index - 1) + fibonacci(index - 2);
    }
}

int main(void)
{
    std::srand(static_cast<unsigned>(std::time(0)));

    static const unsigned fibbMax = 20;

    // get index into sequence
    unsigned fibb = std::rand() % fibbMax;

    std::cout << "Fibonacci(" << fibb << ") = ";
    std::cout << fibonacci(fibb);
    std::cout << std::endl;
}

但是现在表格的大小是非常硬编码的，将其扩展为 40 并不容易。

我想出的唯一一个具有类似查询方法的方法是：

 template <int TableSize = 40>
class FibonacciTable
{
public:
    enum
    {
        max = TableSize
    };

    static unsigned get(unsigned index)
    {
        if (index == TableSize)
        {
            return Fibonacci<TableSize>::value;
        }
        else
        {
            // too far, pass downwards
            return FibonacciTable<TableSize - 1>::get(index);
        }
    }
};

template <>
class FibonacciTable<0>
{
public:
    enum
    {
        max = 0
    };

    static unsigned get(unsigned)
    {
        // doesn't matter, no where else to go.
        // must be 0, or the original value was
        // not in table
        return 0;
    }
};

int main(void)
{
    std::srand(static_cast<unsigned>(std::time(0)));

    // get index into sequence
    unsigned fibb = std::rand() % FibonacciTable<>::max;

    std::cout << "Fibonacci(" << fibb << ") = ";
    std::cout << FibonacciTable<>::get(fibb);
    std::cout << std::endl;
}

这似乎工作得很好。我看到的唯一两个问题是：

• 调用堆栈可能很大，因为计算 Fibonacci<2> 需要我们通过 TableMax 一直到 2，并且：

• 如果该值在表之外，则返回零而不是计算它。

那么我有什么遗漏吗？似乎应该有更好的方法在运行时挑选出这些值。

一个 switch 语句的模板元编程版本可能会生成一个特定数量的 switch 语句？

提前致谢。

原文由 GManNickG 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

template <unsigned long N>
struct Fibonacci
{
    enum
    {
        value = Fibonacci<N-1>::value + Fibonacci<N-2>::value
    };
    static void add_values(vector<unsigned long>& v)
    {
        Fibonacci<N-1>::add_values(v);
        v.push_back(value);
    }
};

template <>
struct Fibonacci<0>
{
    enum
    {
        value = 0
    };
    static void add_values(vector<unsigned long>& v)
    {
        v.push_back(value);
    }

};

template <>
struct Fibonacci<1>
{
    enum
    {
        value = 1
    };
    static void add_values(vector<unsigned long>& v)
    {
        Fibonacci<0>::add_values(v);
        v.push_back(value);
    }
};

int main()
{
    vector<unsigned long> fibonacci_seq;
    Fibonacci<45>::add_values(fibonacci_seq);
    for (int i = 0; i <= 45; ++i)
        cout << "F" << i << " is " << fibonacci_seq[i] << '\n';
}

经过深思熟虑，我想出了这个解决方案。当然，您仍然必须在运行时将值添加到容器中，但（重要的是）它们不是在运行时 计算 的。

作为旁注，重要的是不要在 Fibonacci<1> Fibonacci<0> Fibonacci<0> 否则编译器在解析对 Fibonacci<0>::add_values 的调用时会感到 非常 困惑 --- 的模板特化尚未指定。

当然，TMP 有其局限性：您需要预先计算的最大值，并且在运行时获取值需要递归（因为模板是递归定义的）。

原文由 rlbond 发布，翻译遵循 CC BY-SA 2.5 许可协议