c++ - 循环中的模板元编程？

Question

几分钟前，我正在练习复杂的算法问题。下面代码(算法题的具体逻辑不重要，我们只需要知道main函数上面的代码就是TMP):

#include <array>
#include <algorithm>
#include <iterator>
#include <iostream>

constexpr int digit_in_ones[10] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };
constexpr int createOneD(int index);

template<int ...>
struct seq
{

};

template<int A, int ...B>
struct gens : gens<A - 1, A - 1, B...>
{

};

template<int ...S>
struct gens<0, S ...>
{
    typedef seq<S...> type;
};

template<int N>
class oneDArrayMaker
{
private:
    typedef typename gens<N>::type sequence;
    template<int ...S>
    static constexpr std::array<int, N> make(seq<S ...>)
    {
        return std::array<int, N>{ {createOneD(S)...}};
    }
public:
    static constexpr std::array<int, N> oneDArr = make(sequence());
};
template<int N>
constexpr std::array<int, N> oneDArrayMaker<N>::oneDArr;

constexpr int createOneD(int index)
{
    return index < 10 ? 
        digit_in_ones[index] : 
        digit_in_ones[(index % 100) / 10] + digit_in_ones[index % 10] + 
        (index >= 100 ? digit_in_ones[index / 100] : 0);
}
int main()
{
    int n{}, ans{};
    scanf("%d", &n);
    for (int i = 0; i < 800; i++)
    {
        for (int j = 0; j < 800; j++)
        {
            auto temp = oneDArrayMaker<800>::oneDArr[i] + oneDArrayMaker<800>::oneDArr[j] + (i+j < 800 ? oneDArrayMaker<800>::oneDArr[i+j] : 100) + 4;
            if (temp == n)
            {
                ans++;
            }
        }
    }
    printf("%d", ans);
}

我知道loop和 if (不包括 constexpr function 和 if constexpr )是运行时的，不是编译时的。所以像template specialization这样的技巧是 if 的变电站和 loop .我吸取了关于 if 愚蠢用法的教训在模板编程中来自 this article-Compile Time Loops with C++11 - Creating a Generalized static_for Implementation ，这里的代码:

#include <iostream>
template<int index> void do_stuff()
{
    std::cout << index << std::endl;
}
template<int max_index, int index = 0> void stuff_helper()
{
    if (index <= max_index)
    {
        do_stuff<index>();
        stuff_helper<max_index, index + 1>();
    }
}
int main()
{
    stuff_helper<100>();
    return 0;
}

作者的解释:

On the surface, it could look like the if statement would be responsible for terminating the recursion, like how this would work with a "normal" run-time based recursion algorithm. But that's the problem. What works at runtime doesn't work at compile time.

This is an infinite loop, and only stops because compilers limit themselves to a certain recursion depth. In clang, I get an error fatal error: recursive template instantiation exceeded maximum depth of 256. You can expect a similar error with your compiler of choice.

哎呀...，我只是说说我所知道的...

最后说到我的问题:

现在模板的实例化(具体来说，两次解析)是在编译时。所以最上面代码中的所有模板实例化都应该在编译时:

    for (int i = 0; i < 800; i++)
    {
        for (int j = 0; j < 800; j++)
        {
            auto temp = oneDArrayMaker<800>::oneDArr[i] + ... // 800 * 800 instantiations should be deternimated at compile time
            ...
        }
        ...
    }

众所周知1.两个for loop这里是运行时啊，虽然它不在模板函数/类的定义中，只是在主函数中。2. 每个auto temp = oneDArrayMaker<800>::oneDArr[i] + ...应该在编译时初始化，所以 800 * 800 个实例化应该在编译时确定。

Q1:main函数中的运行时循环是否与799*799编译时模板初始化冲突？

我的假设:在编译时，编译器知道循环的深度，所以只需展开循环，在运行时没有循环。但我认为这两个循环(i 和 j)也不能在运行时确定，我将 main 函数更改为:

int main()
{
    int n{}, ans{}, i{}, j{};
    scanf("%d", &n);
    scanf("%d %d", &i, &j);
    std::cout << n << " " << i << " " << j << std::endl;
    for (; i < 800; i++)
    {
        for (; j < 800; j++)
        {
            auto temp = oneDArrayMaker<800>::oneDArr[i] + oneDArrayMaker<800>::oneDArr[j] + (i+j < 800 ? oneDArrayMaker<800>::oneDArr[i+j] : 100) + 4;
            if (temp == n)
            {
                ans++;
            }
        }
    }
    printf("%d", ans);
}

现在i和 j由于 scanf，必须在运行时确定.我刚刚通过额外的两个0到标准输入。

这里是 live example修改主函数后，输出为 12 (正确答案是 128)

它编译成功并且没有生成警告。令我困惑的是输出与原始代码不同( live code ，其输出为 128 (等于正确答案)。

调试后，我发现关键是修改代码后，for (; i < 800; i++)只执行一次 i = 0 , 而它应该已经 excauted 1~799 ，这就是 12 的原因, 不是 128 .

Q2:如果for循环的深度在运行时无法确定，TMP代码在循环中，会发生什么？

Q3:如何解释输出12

更新:

Q3 已经被@Scott Brown 解决了，我太粗心了。

Q1 和 Q2 还是让我很困惑

Answer 1

您忘记在 ' for (; j < 800; j++) 之前重置 j '.

int main()
{
    int n{}, ans{}, i{}, j{};
    scanf("%d", &n);
    scanf("%d %d", &i, &j);
    std::cout << n << " " << i << " " << j << std::endl;

    int j_orig = j;// here

    for (; i < 800; i++)
    {

        j = j_orig;// and here

        for (; j < 800; j++)
        {
            auto temp = oneDArrayMaker<800>::oneDArr[i] + oneDArrayMaker<800>::oneDArr[j] + (i+j < 800 ? oneDArrayMaker<800>::oneDArr[i+j] : 100) + 4;
            if (temp == n)
            {
                ans++;
            }
        }
    }
    printf("%d", ans);
}