编译时递归和条件

Question

我正在阅读对 “在没有循环或条件的情况下打印 1 到 1000”的回复 我想知道为什么必须有 NumberGeneration<1> 的特殊情况在最上面的答案中。

如果我删除它并在模板中添加对 N == 1 的检查（下面的代码），则代码编译失败，并显示“模板实例化深度超出最大值”，但我不确定为什么。条件语句在编译时的处理方式是否不同？

#include <iostream>

template<int N>
struct NumberGeneration
{
    static void out(std::ostream& os)
    {
        if (N == 1)
        {
            os << 1 << std::endl;
        }
        else
        {
            NumberGeneration<N-1>::out(os);
            os << N << std::endl;
        }
    }
};

int main()
{
    NumberGeneration<1000>::out(std::cout);
}

Answer 1

代码生成和编译不会根据条件进行分支！考虑一下：

// don't declare bar()!

void foo()
{
     if (false) { bar(); }
}

如果您从未声明 bar()，即使永远无法到达内部作用域，这也是一个编译错误。出于同样的原因，无论是否可以到达该分支，NumberGeneration 始终会被实例化，并且您具有无限递归。

事实上，条件语句的静态模拟正是模板特化：

template <> struct NumberGeneration<0> { /* no more recursion here */ };

Answer 2

条件 if 不会在编译时处理。它将在运行时处理。

因此，即使对于 N=1，编译器也会生成 NumberGenerator<0>，然后生成 NumberGenerator<-1> 。 ...无休止地，直到达到模板实例化深度。

Answer 3

模板在编译时实例化，模板特殊情况可防止编译器在编译时递归到 1 以下。

if 子句是在运行时评估的，因此编译器在编译您的代码时已经失败了，因为它会产生任何效果。

Answer 4

我想知道为什么有必要有特殊情况
NumberGeneration<1>在最上面的答案中。

因为这是递归的结束条件！如果没有这个，递归怎么可能结束呢？

Answer 5

一般来说，代码中的条件 N == 1 是在运行时评估的（尽管编译器可能会对此进行优化），而不是在编译时评估。因此，else 子句中的模板实例化递归永远不会终止。另一方面，NumberGeneration<1> 在编译时进行评估，因此充当此递归模板的终止情况。

Answer 6

我相当确定这是特定于编译器的；一些编译器可能会尝试生成 if/else 的两个分支，无论 N 的值是什么，在这种情况下，编译无论如何都会失败。其他编译器可能会在编译时评估条件，并且仅为所执行的分支生成代码，在这种情况下编译将成功。

更新：或者正如 Luc 在评论中所说，编译器可能必须生成两个分支，这样代码总是会失败。我不太确定是哪种情况，但无论哪种方式，依赖运行时条件来控制编译时代码生成都是一个坏主意。

最好使用专门化：（

template <int N>
struct NumberGeneration
{
    static void out(std::ostream & os)
    {
        NumberGeneration<N-1>::out(os);
        os << N << std::endl;
    }
};

template <>
void NumberGeneration<1>::out(std::ostream & os)
{
    os << 1 << std::endl;
}

或者您可以通过专门化 N=0 来稍微缩短这个时间，并使用一个不执行任何操作的 out 函数）。

另外，请注意某些编译器可能不支持深度递归模板； C++03 建议最小支持深度仅为 17，C++11 增加到 1024。您应该检查编译器的限制。

Answer 7

这是因为整数可以为负数，并且运行时代码（if 检查）不会阻止编译器使用 0、-1、-2 等实例化模板。编译器可能 能够摆脱你的建议，但是如果实例化其他模板（0、-1、...）有你所依赖的副作用怎么办？在这种情况下，编译器不可能无法为您实例化它们。

简而言之，就像所有递归一样，您必须提供自己的基本情况。

Answer 8

这是正确的方法：

template<int N>
struct NumberGeneration
{
    static void out(std::ostream& os);
};

template<int N>
void NumberGeneration<N>::out(std::ostream& os)
{
    NumberGeneration<N-1>::out(os);
    os << N << std::endl;
}

template<>
void NumberGeneration<1>::out(std::ostream& os)
{
    os << 1 << std::endl;
}

int main()
{
    NumberGeneration<20>::out(std::cout);
}

这称为模板专业化：您，程序员，为模板的特定实例化提供替代定义。您可以专门化整个模板，也可以只专门化其中的一部分，就像我在这里所做的那样（我只专门化了函数，而不是整个结构）。