0

所以，假设我有一个模板 structure-function fib<i>::value。我想在运行时获得第 n 个斐波那契数。为此，我创建了数组fibs[] = { fib<0>::value, ... , fib<maxN>::value }。不幸的是，对于某些功能maxN可能非常大，我不能只用手填充它。所以我写了一些预处理指令来简化任务。

#define fib(x) (fib<(x)>::value)
#define fibLine_level_0(x) fib(5*(x) + 0), fib(5*(x) + 1), fib(5*(x) + 2), fib(5*(x) + 3), fib(5*(x) + 4)
#define fibLine_level_1(x) fibLine_level_0(2*(x) + 0), fibLine_level_0(2*(x) + 1)
#define fibLine_level_2(x) fibLine_level_1(2*(x) + 0), fibLine_level_1(2*(x) + 1)
#define fibLine_level_3(x) fibLine_level_2(2*(x) + 0), fibLine_level_2(2*(x) + 1)

#define cAarrSize(x) (sizeof(x) / sizeof(x[0]))

我这样使用它：

int fibs[] = { fibLine_level_3(0) };

for (int i = 0; i < cAarrSize(fibs); i++)
    cout << "fib(" << i << ") = " << fibs[i] << endl;

您可能需要的代码：

template<int i>
struct fibPair{
    static const int fst = fibPair<i-1>::snd;
    static const int snd = fibPair<i-1>::fst + fibPair<i-1>::snd;
};

template<>
struct fibPair<0> {
    static const int fst = 0;
    static const int snd = 1;
};

template<int i>
struct fib {
    static const int value = fibPair<i>::fst;
};

但是这段代码真的很丑。怎么做才能让它更漂亮？

约束：此代码必须在体育节目中使用。这意味着 - 没有第三方库，有时也没有 C++11（但它可以）

4

2 回答 2

3

Fib结构可以改写如下：

template <size_t i>
struct fib
{
    static const size_t value = fib<i - 1>::value + fib<i - 2>::value;
};

template <>
struct fib<0>
{
    static const size_t value = 0;
};

template <>
struct fib<1>
{
    static const size_t value = 1;
};

斐波那契数列的编译时数组可以使用 C++11 计算。

编辑 1（更改了fib值的类型）。

编辑 2：

斐波那契数列的编译时生成（基于此答案）。

template<unsigned... args> struct ArrayHolder
{
    static const unsigned data[sizeof...(args)];
};

template<unsigned... args>
const unsigned ArrayHolder<args...>::data[sizeof...(args)] = { args... };

template<size_t N, template<size_t> class F, unsigned... args>
struct generate_array_impl
{
    typedef typename generate_array_impl<N-1, F, F<N>::value, args...>::result result;
};

template<template<size_t> class F, unsigned... args>
struct generate_array_impl<0, F, args...>
{
    typedef ArrayHolder<F<0>::value, args...> result;
};

template<size_t N, template<size_t> class F>
struct generate_array
{
    typedef typename generate_array_impl<N-1, F>::result result;
};

int main()
{
    const size_t count = 10;
    typedef generate_array<count, fib>::result fibs;

    for(size_t i = 0; i < count; ++i)
        std::cout << fibs::data[i] << std::endl;
}

您所需要的只是提供generate_array生成«function»（我们的fib结构）。

于 2013-01-26T23:30:17.320 回答
0

感谢@nameless，提供了问题的链接，在那里我找到了@MichaelAnderson 对简单c++（没有新功能）的回答。我使用它并根据自己的需要进行扩展。

所以，概念很简单，但有点奇怪。我们必须生成递归模板化结构，其中第一个字段是与其他参数相同的模板化结构。

template<size_t N>
struct FibList {
    FibList<N-1> previous;
    size_t value;
    FibList<N>() : value(fib<N>::value) {}
};

让我们尝试扩展一下（只是看看，编译器会产生什么）：

template<size_t N>
struct FibList {
    FibList<N-3> previous;
    size_t value_N_minus_2;
    size_t value_N_minus_1;
    size_t value_N;
};

所以我们可以认为 FibList 是数组并且只是转换它（这是我的解决方案的弱点 - 我现在无法证明这一点）

static const size_t maxN = 2000;
FibList<maxN> fibList;
size_t *fibArray = &fibList.value - maxN;

或者以另一种方式：

size_t *fibArray = reinterpret_cast<size_t*>(&fibList);

重要提示：数组的大小为 maxN+1，但获取数组大小（sizeof(array) / sizeof(array[0]）的标准方法将失败。对此非常准确。

现在我们必须停止递归：

// start point
template<>
struct FibList<0> {
    size_t value;
    FibList<0>() : value(0) {}
};

// start point
template<>
struct FibList<1> {
    FibList<0> previous;
    size_t value;
    FibList<1>() : value(1) {}
};

请注意，交换位置FibList<1>和FibList<0>将在编译器中产生堆栈溢出。

我们必须解决另一个问题——模板递归的深度有限（取决于编译器和/或选项）。但是，幸运的是，编译器只有深度限制，没有模板的内存限制（嗯，是的，内存限制大于深度限制）。所以我们有明显丑陋的解决方案 -fib<N>以等于深度限制的步长串联调用 - 我们永远不会捕获模板深度限制fib<N>。但是我们不能只fib<500>::value在运行时写 not。所以我们得到了解决方案 - 编写将专门FibList<N>使用的宏fib<N>::value：

#define SetOptimizePointForFib(N) template<>\
struct FibList<N> {\
    FibList<(N)-1> previous;\
    size_t value;\
    FibList<N>() : value(fib<N>::value) {}\
};

我们必须这样写：

SetOptimizePointForFib(500);
SetOptimizePointForFib(1000);
SetOptimizePointForFib(1500);
SetOptimizePointForFib(2300);

所以我们得到了真正的编译时间预计算并填充了惊人长度的静态数组。

于 2013-01-27T02:36:47.883 回答