11

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

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;

不幸的是，上面的元程序只打印了六步而不是七步：

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 的最后一步不见了。这是为什么？问题能解决吗？

4

3 回答 3

7

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

于 2013-11-08T18:25:21.863 回答
1

我没有直接回答你的问题，但是，这将是我的版本：

#include <type_traits>

using namespace std;

template <typename T> class TD;

struct NullType {};

template <int N, typename S>
struct Stack {
    static const int Head = N;
    typedef S Tail;
};

#define STACK_0() NullType
#define STACK_1(D1) Stack<D1, NullType>
#define STACK_2(D1, D2) Stack<D1, STACK_1(D2)>
#define STACK_3(D1, D2, D3) Stack<D1, STACK_2(D2, D3)>
#define STACK_4(D1, D2, D3, D4) Stack<D1, STACK_3(D2, D3, D4)>

template <typename S>
struct Pop;

template <int N, typename R>
struct Pop<Stack<N, R>> {
    typedef Stack<N, typename Pop<R>::result> result;
};

template<int N>
struct Pop<Stack<N, NullType>> {
    typedef NullType result;
};

template <typename S>
struct Top;

template <int N, typename R>
struct Top<Stack<N, R>> {
    static const int result = Top<R>::result;
};

template <int N>
struct Top<Stack<N, NullType>> {
    static const int result = N;
};

template <typename S, int D>
struct Push;

template <int N, typename S, int D>
struct Push<Stack<N, S>, D> {
    typedef Stack<N, typename Push<S, D>::result> result;
};

template <int M>
struct Push<NullType, M> {
    typedef Stack<M, NullType> result;
};

template <typename S>
struct SizeOf;

template <int N, typename R>
struct SizeOf<Stack<N, R>> {
    static const int value = SizeOf<R>::value + 1;
};

template <>
struct SizeOf<NullType> {
    static const int value = 0;
};

template <typename S1, typename S2, typename S3>
struct Hanoi {
    typedef S1 Stack1;
    typedef S2 Stack2;
    typedef S3 Stack3;

    template <int I, int J, int unused=0>
    struct MoveDisc;

    template <int unused>
    struct MoveDisc<1, 2, unused> {
        typedef Hanoi<
            typename Pop<Stack1>::result,
            typename Push<Stack2, Top<Stack1>::result>::result,
            Stack3
        > result;
    };

    template <int unused>
    struct MoveDisc<2, 1, unused> {
        typedef Hanoi<
            typename Push<Stack1, Top<Stack2>::result>::result,
            typename Pop<Stack2>::result,
            Stack3
        > result;
    };

    template <int unused>
    struct MoveDisc<1, 3, unused> {
        typedef Hanoi<
            typename Pop<Stack1>::result,
            Stack2,
            typename Push<Stack3, Top<Stack1>::result>::result
        > result;
    };

    template <int unused>
    struct MoveDisc<3, 1, unused> {
        typedef Hanoi<
            typename Push<Stack1, Top<Stack3>::result>::result,
            Stack2,
            typename Pop<Stack3>::result
        > result;
    };

    template <int unused>
    struct MoveDisc<2, 3, unused> {
        typedef Hanoi<
            Stack1,
            typename Pop<Stack2>::result,
            typename Push<Stack3, Top<Stack2>::result>::result
        > result;
    };

    template <int unused>
    struct MoveDisc<3, 2, unused> {
        typedef Hanoi<
            Stack1,
            typename Push<Stack2, Top<Stack3>::result>::result,
            typename Pop<Stack3>::result
        > result;
    };
};

static_assert(
    is_same<
        Pop<STACK_1(1)>::result,
        NullType
    >::value, "Pop<> not working."
);

static_assert(Top<STACK_2(2, 1)>::result == 1, "Top<> not working.");

static_assert(
    is_same<
        Push<STACK_1(2), 1>::result,
        STACK_2(2, 1)
    >::value, "Push<> not working."
);

static_assert(
    SizeOf<STACK_4(4, 3, 2, 1)>::value == 4, "SizeOf<> not working."
);

static_assert(
    is_same<
        typename Hanoi<
            STACK_4(4, 3, 2, 1),
            STACK_0(),
            STACK_0()>::MoveDisc<1,2>::result,
        Hanoi<
            STACK_3(4, 3, 2),
            STACK_1(1),
            STACK_0()>
    >::value, "MoveDisc<1,2> not working."
);

static_assert(
    is_same<
        typename Hanoi<
            STACK_3(4, 3, 2),
            STACK_1(1),
            STACK_0()>::MoveDisc<2,1>::result,
        Hanoi<
            STACK_4(4, 3, 2, 1),
            STACK_0(),
            STACK_0()>
    >::value, "MoveDisc<2,1> not working."
);

static_assert(
    is_same<
        typename Hanoi<
            STACK_1(4),
            STACK_0(),
            STACK_0()>::MoveDisc<1,3>::result,
        Hanoi<
            STACK_0(),
            STACK_0(),
            STACK_1(4)>
    >::value, "MoveDisc<1,3> not working."
);

static_assert(
    is_same<
        typename Hanoi<
            STACK_2(3, 2),
            STACK_0(),
            STACK_2(4, 1)>::MoveDisc<3,1>::result,
        Hanoi<
            STACK_3(3, 2, 1),
            STACK_0(),
            STACK_1(4)>
    >::value, "MoveDisc<3,1> not working."
);

static_assert(
    is_same<
        typename Hanoi<
            STACK_1(1),
            STACK_2(3, 2),
            STACK_1(4)>::MoveDisc<2,3>::result,
        Hanoi<
            STACK_1(1),
            STACK_1(3),
            STACK_2(4, 2)>
    >::value, "MoveDisc<2,3> not working."
);

template <typename H, int D, int F, int T, int V>
struct Solve {
    typedef typename Solve<
        typename Solve<H, D-1, F, V, T>::result::template MoveDisc<F, T>::result, D-1, V, T, F
    >::result result;
};

template <typename H, int F, int T, int V>
struct Solve<H, 1, F, T, V> {
    typedef typename H::template MoveDisc<F, T>::result result;
};

template <typename H>
struct Solution {
    typedef typename Solve<H, SizeOf<typename H::Stack1>::value, 1, 3, 2>::result result;
};

static_assert(
    is_same<
        Solution<
            Hanoi<
                STACK_4(4, 3, 2, 1),
                STACK_0(),
                STACK_0()
            >
        >::result,
        Hanoi<
            STACK_0(),
            STACK_0(),
            STACK_4(4, 3, 2, 1)
        >
    >::value, "Solution<> is not working."
);

int main() {

}

Stack 类模板实际上是来自 Andrei Alexandrescu 的 Modern C++ Design 书中的 TypeList

于 2014-12-01T10:06:45.603 回答
0

您的程序是正确的，但您依赖于编译器错误消息（这是实现定义的），在您的情况下它不会再次打印错误。但在实际代码中，TMP 必须做一些导致运行时行为的事情。如果您只输出 (with std::cout)src并dst在move_discconstrcutor 中创建move_disc一个成员hanoi而不是强制编译时错误，一切都可以。

于 2013-11-08T19:39:40.510 回答