编译时递归和条件语句

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

- baris.m

Answer 1

代码生成和编译不会根据条件分支！考虑以下情况：

// don't declare bar()!

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

如果您从未声明bar()，即使内部范围永远无法到达，这也是一个编译错误。出于同样的原因，NumberGeneration<N-1>总是被实例化，无论该分支是否可达，从而导致无限递归。

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

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

- Kerrek SB

---

谢谢，这很合理，我没有考虑到编译时实例化，并期望它只在代码被执行时完成。 - baris.m

@baris.m：但是你所说的“代码被触及”的关键微妙之处在于：编译器会在编译期间始终触及一次，然后在程序执行期间再次有条件地触及。 - Kerrek SB

在我的评论中，我谈到了在运行时被调用的问题。你的回答非常有道理。 - baris.m

Answer 2

if条件语句不会在编译时处理，而是在运行时处理。

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

- Didier Trosset

Answer 3

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

if语句在运行时评估，所以当它产生任何影响时，编译器已经在编译您的代码时失败了。

- Joachim Isaksson

Answer 4

我在想为什么在顶部答案中需要特殊情况处理 NumberGeneration<1>。

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

- RoundPi

---

我在模板中添加了一个条件语句 if N == 1，这个怎么处理呢？在这种情况下，我们不会使用 N-1 实例化一个新的对象，所以我期望递归会在这里停止。 - baris.m

@baris.m：您不应该删除条件1的模板特化，因为那是编译结束计算/编译的终止条件。 - RoundPi

@baris.m：您添加的条件并没有帮助，因为编译器不会关心它，并且在编译期间结束编译。您添加的检查仅在运行时有用，而不是在编译时。 - RoundPi

@baris.m：如果你还有任何疑问，请阅读这篇文章：http://en.wikipedia.org/wiki/Template_metaprogramming - RoundPi

Answer 5

通常情况下，您代码中的条件N == 1是在运行时评估的（尽管编译器可能会优化掉它），而不是在编译时评估。因此，在else子句中的模板实例化递归永远不会终止。NumberGeneration<1>则在编译时评估，因此充当了此递归模板的终止情况。

- vitaut

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。您应该检查您的编译器限制是多少。

- Mike Seymour

---

嗯，我认为编译器必须实例化模板，即使它可以检测到代码在运行时永远不会被执行，所以无论你使用什么编译器，我都不认为这段代码能够完成编译。 - Luc Touraille

你不需要为整个结构体进行专门化，只需为函数进行即可。 - Paul Manta

@PaulManta：确实可以。谢谢。 - Mike Seymour

Answer 7

这是因为整数可以为负，而运行时代码（if检查）不会阻止编译器使用0、-1、-2等实例化模板。编译器可能能够逃避你提出的问题，但如果实例化其他模板（0、-1等）具有你所依赖的副作用呢？在这种情况下，编译器不能不为你实例化它们。

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

- Mark B

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

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

- Paul Manta