在编译时解决河内的塔楼

Question

我试图在编译时解决河内塔,但我发现了一个问题:

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;

不幸的是,上面的元程序只打印了6个而不是7个:

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失踪.这是为什么？问题可以解决吗？

Answer 1

我认为这是因为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