c++ - 在编译时解决汉诺塔

我正在尝试在编译时解决汉诺塔楼，但是我发现了一个问题:

template<int src, int dst>
struct move_disc
{
    // member access will print src and dst
};

template<int n, int src, int tmp, int dst>
struct hanoi
{
    hanoi<n-1, src, dst, tmp> before;
    typename move_disc<src, dst>::lol disc;
    hanoi<n-1, tmp, src, dst> after;
};

template<int src, int tmp, int dst>
struct hanoi<0, src, tmp, dst>
{
    // recursive base case
};

hanoi<3, 1, 2, 3> go;

不幸的是，the above meta program只打印六个 Action ，而不是七个:

prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<1, 3>’
prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<1, 2>’
prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<3, 2>’
prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<1, 3>’
prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<2, 1>’
prog.cpp:11:39: error: no type named ‘lol’ in ‘struct move_disc<2, 3>’

从1到3的最后一步丢失了。这是为什么？问题可以解决吗？

最佳答案

我认为这是因为hanoi<1, 1, 2, 3>已经被实例化(产生第一个错误)，并且在以后在模板实例化过程中“遇到”时没有被再次实例化。

[编辑:为了更清楚一点，这是递归模板实例化(有错误)的“图形”:

hanoi<3, 1, 2, 3>:

1:hanoi<2, 1, 3, 2>:

1.1:hanoi<1, 1, 2, 3>:

1.1.1:hanoi<0, 1, 3, 2>。

(move_disc<1, 3>)

1.1.2:hanoi<0, 2, 1, 3>。

(move_disc<1, 2>)

1.2:hanoi<1, 3, 1, 2>:

1.2.1:hanoi<0, 3, 2, 1>。

(move_disc<3, 2>)

1.2.2:hanoi<0, 1, 3, 2>。

(move_disc<1, 3>)

2:hanoi<2, 2, 1, 3>:

2.1:hanoi<1, 2, 3, 1>:

2.1.1:hanoi<0, 2, 1, 3>。

(move_disc<2, 1>)

2.1.2:hanoi<0, 3, 2, 1>。

(move_disc<2, 3>)

2.2:hanoi<1, 1, 2, 3>:已在1.1实例化(不再重复move_disc<1, 3>错误)。

-结束编辑。]

我能想到的一个“解决方案”是使每个专业都独一无二，例如通过添加“id”模板参数(并在递归实例化期间生成唯一的新值):

template<int n, int src, int tmp, int dst, int id>
struct hanoi
{
    hanoi<n-1, src, dst, tmp, id*2> before;
    typename move_disc<src, dst>::lol disc;
    hanoi<n-1, tmp, src, dst, id*2+1> after;
};

template<int src, int tmp, int dst, int id>
struct hanoi<0, src, tmp, dst, id>
{
    // recursive base case
};

hanoi<3, 1, 2, 3, 1> go;

现场直播:http://ideone.com/0lQaXs