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

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

似乎效果很好。我看到的唯一两个问题是：

潜在的大调用堆栈，因为计算斐波那契<2>要求我们一直将TableMax一直遍历到2，并且：:
如果值在表之外，则返回零，而不是计算它。

所以我缺少什么？似乎应该有一种更好的方法在运行时选择这些值。

也许是switch语句的模板元编程版本，它最多可以生成一定数量的switch语句？

提前感谢。

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

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

作为旁注，重要的是不要在Fibonacci<1>上方定义Fibonacci<0>，否则您的编译器在解析对Fibonacci<0>::add_values的调用时会感到困惑[[very，因为Fibonacci<0>的模板专业化具有未指定。

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

Answer 2

我知道这个问题很旧，但是这引起了我的兴趣，我不得不在运行时不填充动态容器的情况下进行尝试：

#ifndef _FIBONACCI_HPP #define _FIBONACCI_HPP template <unsigned long N> struct Fibonacci { static const unsigned long long value = Fibonacci<N-1>::value + Fibonacci<N-2>::value; static unsigned long long get_value(unsigned long n) { switch (n) { case N: return value; default: return n < N ? Fibonacci<N-1>::get_value(n) : get_value(n-2) + get_value(n-1); } } }; template <> struct Fibonacci<0> { static const unsigned long long value = 0; static unsigned long long get_value(unsigned long n) { return value; } }; template <> struct Fibonacci<1> { static const unsigned long long value = 1; static unsigned long get_value(unsigned long n) { return value; } }; #endif

这似乎可行，并且当使用优化进行编译时（不确定是否要允许这样做），调用堆栈不会变得很深-当然，在堆栈上对于值（参数）的正常运行时递归n> N，其中N是模板实例化中使用的TableSize。但是，一旦达到TableSize以下，生成的代码将替换在编译时计算的常量，或者最坏的情况是替换掉通过跳转表（在-c -g -Wa，-adhlns = main中编译的gcc）中的“计算”值。并检查了清单），就像我认为您的显式switch语句将导致的一样。当这样使用时：
int main()
{
    std::cout << "F" << 39 << " is " << Fibonacci<40>::get_value(39) << '\n';
    std::cout << "F" << 45 << " is " << Fibonacci<40>::get_value(45) << '\n';
}

在第一种情况下根本没有对计算的调用（在编译时计算了值，在第二种情况下，调用堆栈的深度最差：fibtest.exe!Fibonacci<40>::get_value(unsigned long n=41)  Line 18 + 0xe bytes    C++
fibtest.exe!Fibonacci<40>::get_value(unsigned long n=42)  Line 18 + 0x2c bytes    C++
fibtest.exe!Fibonacci<40>::get_value(unsigned long n=43)  Line 18 + 0x2c bytes    C++
fibtest.exe!Fibonacci<40>::get_value(unsigned long n=45)  Line 18 + 0xe bytes    C++
fibtest.exe!main()  Line 9 + 0x7 bytes    C++
fibtest.exe!__tmainCRTStartup()  Line 597 + 0x17 bytes    C

即它重复进行，直到在“表”中找到一个值。 （通过逐行调试器中的反汇编来进行验证，也可以用随机数<= 45代替测试整数）]递归部分也可以用线性迭代解决方案代替：
static unsigned long long get_value(unsigned long n)
{
    switch (n) {
        case N:
            return value;    
        default:
            if (n < N) {
                return Fibonacci<N-1>::get_value(n);
            } else {
                // n > N
                unsigned long long i = Fibonacci<N-1>::value, j = value, t;
                for (unsigned long k = N; k < n; k++) {
                    t = i + j;
                    i = j;
                    j = t;
                }
                return j;
            }
    }
}

Answer 3

如果您有支持可变参数模板（C ++ 0x standard）的C ++编译器，则可以在编译时将fibonacii序列保存在元组中。在运行时，您可以通过索引访问该元组中的任何元素。

#include <tuple> #include <iostream> template<int N> struct Fib { enum { value = Fib<N-1>::value + Fib<N-2>::value }; }; template<> struct Fib<1> { enum { value = 1 }; }; template<> struct Fib<0> { enum { value = 0 }; }; // ---------------------- template<int N, typename Tuple, typename ... Types> struct make_fibtuple_impl; template<int N, typename ... Types> struct make_fibtuple_impl<N, std::tuple<Types...> > { typedef typename make_fibtuple_impl<N-1, std::tuple<Fib<N>, Types... > >::type type; }; template<typename ... Types> struct make_fibtuple_impl<0, std::tuple<Types...> > { typedef std::tuple<Fib<0>, Types... > type; }; template<int N> struct make_fibtuple : make_fibtuple_impl<N, std::tuple<> > {}; int main() { auto tup = typename make_fibtuple<25>::type(); std::cout << std::get<20>(tup).value; std::cout << std::endl; return 0; }

Answer 4

使用C ++ 11：您可以创建std::array和简单的getter：https://ideone.com/F0b4D3

namespace detail { template <std::size_t N> struct Fibo : std::integral_constant<size_t, Fibo<N - 1>::value + Fibo<N - 2>::value> { static_assert(Fibo<N - 1>::value + Fibo<N - 2>::value >= Fibo<N - 1>::value, "overflow"); }; template <> struct Fibo<0u> : std::integral_constant<size_t, 0u> {}; template <> struct Fibo<1u> : std::integral_constant<size_t, 1u> {}; template <std::size_t ... Is> constexpr std::size_t fibo(std::size_t n, index_sequence<Is...>) { return const_cast<const std::array<std::size_t, sizeof...(Is)>&&>( std::array<std::size_t, sizeof...(Is)>{{Fibo<Is>::value...}})[n]; } template <std::size_t N> constexpr std::size_t fibo(std::size_t n) { return n < N ? fibo(n, make_index_sequence<N>()) : throw std::runtime_error("out of bound"); } } // namespace detail constexpr std::size_t fibo(std::size_t n) { // 48u is the highest return detail::fibo<48u>(n); }

在C ++ 14中，您可以简化一些功能：template <std::size_t ... Is>
constexpr std::size_t fibo(std::size_t n, index_sequence<Is...>)
{
    constexpr std::array<std::size_t, sizeof...(Is)> fibos{{Fibo<Is>::value...}};
    return fibos[n];
}

Answer 5

C（大多数情况下为C ++）的基本租户之一是，您不用为不需要的东西付钱。

查找表的自动生成只是编译器不需要为您执行的操作。即使您需要该功能，也并非所有人都需要。

如果要查找表，请编写一个程序。然后在程序中使用该数据。

如果要在运行时计算值，请不要使用模板元程序，只需使用常规程序来计算值。

Answer 6

您可以使用预处理程序元编程技术来生成开关或静态数组。如果复杂度不超过该方法的局限性，则是一个很好的决定，并且您宁愿不使用生成代码或数据的额外步骤来扩展工具链。

Answer 7

这应该可以解决问题...

template <int N> class EXPAND { public: static const string value; }; template <> class EXPAND<0> { public: static const string value; }; template <int N> const string EXPAND<N>::value = EXPAND<N-1>::value+"t"; const string EXPAND<0>::value = "t"; int main() { cout << EXPAND<5>::value << endl; }

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

问题描述投票：43回答：7

背景

问题

7个回答

最新问题

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

问题描述 投票：43回答：7

背景

问题

7个回答

最新问题

问题描述投票：43回答：7