星期六, 9月 16, 2006

測試編譯器功力的九九乘法表原始碼

最近迷上 template meta-programming,所以百無聊之中(相對於百忙之中...)寫了個入門等級的小程式。類似功能的程式應該很多程式設計師還沒出茅廬的時候就都寫過了吧!

為什麼說是測試「編譯器」的功力呢?因為這個程式用到了一些高階的 template 功能,並不是所有 compiler 都支援。如果您手上的編譯器是 VC6 的話,請去 Program Files 底下把它拖曳進資源桶,然後改用 dev-c++(它使用 GCC 3.4.2)。使用 GCC 4.1.1(我是用這個編譯、測試的)是完全沒有問題的 :)

本來想稍微講解,可是想想又覺得沒什麼好說的,畢竟只是無聊的小作業 = = 如果有什麼問題,歡迎留言、MSN、Email、電話討論。以下附上程式碼!


/*
 * Meta-programming Infrastructure
 */

struct NullType { };

template <typename Head, typename Tail>
struct Typelist { };

/**
 * meta-(data structure) to store "X x Y = Z"
 */

template <unsigned int X, unsigned int Y>
struct ChartNode
{
    enum { first = X, second = Y, product = X * Y };
};

/**
 * Chart Maker...
 *
 * @param X, Y: current X and Y
 * @param XN, YN: max X and Y
 */

template <unsigned int X, unsigned int Y, unsigned int XN, unsigned int YN>
struct makeChart
{
    typedef Typelist< ChartNode<X, Y>, typename makeChart<X+1, Y, XN, YN>::Result > Result;
};

template <unsigned int Y, unsigned int XN, unsigned int YN>
struct makeChart<XN, Y, XN, YN>
{
    typedef Typelist< ChartNode<XN, Y>,
        Typelist< NullType, typename makeChart<1, Y+1, XN, YN>::Result > > Result;
};

template <unsigned int XN, unsigned int YN>
struct makeChart<XN, YN, XN, YN>
{
    typedef Typelist< ChartNode<XN, YN>, NullType > Result;
};

/**
 * Algorithm to write a ChartNodeList to an Ostream
 */
template <typename TList>
struct toOstream;

template <typename X, typename XS>
struct toOstream< Typelist<X, XS> > : toOstream< XS >
{
    template <typename OST, typename DELIM>
    OST & operator() (OST & dest, DELIM delim1, DELIM delim2)
    {
        dest << X::first << "x" << X::second << "=" << X::product << delim1;
        return toOstream<XS>::operator()(dest, delim1, delim2);
    }
};

template <typename XS>
struct toOstream< Typelist<NullType, XS> > : toOstream< XS >
{
    template <typename OST, typename DELIM>
    OST & operator() (OST & dest, DELIM delim1, DELIM delim2)
    {
        dest << delim2;
        return toOstream<XS>::operator()(dest, delim1, delim2);
    }
};

template <>
struct toOstream<NullType>
{
    template <typename OST, typename DELIM>
    OST & operator() (OST & dest, DELIM, DELIM delim2)
    {
        dest << delim2;
        return dest;
    }
};

/*
 * Main Program...
 */
#include <iostream>
#include <iterator>
using namespace std;

int main()
{
    enum { x = 9, y = 9 };
    cout << "make a Chart from [(1x1=1) .. (" << x << "x" << y << "=" << x*y << ")]:" << endl;

    typedef makeChart<1, 1, x, y>::Result ChartList;
    toOstream<ChartList> generator;
    generator(cout, ", ", "\n");

    return 0;
}

整個演算法包裝成一系列的 template objects,最後再丟給 toOstream<> 這個唯一有被具現化的 template object,其他程式碼全部都在編譯時期被展開了!帶入 x = 9, y = 9 的結果:

$ ./ninenine
make a Chart from [(1x1=1) .. (9x9=81)]:
1x1=1, 2x1=2, 3x1=3, 4x1=4, 5x1=5, 6x1=6, 7x1=7, 8x1=8, 9x1=9,
1x2=2, 2x2=4, 3x2=6, 4x2=8, 5x2=10, 6x2=12, 7x2=14, 8x2=16, 9x2=18,
1x3=3, 2x3=6, 3x3=9, 4x3=12, 5x3=15, 6x3=18, 7x3=21, 8x3=24, 9x3=27,
1x4=4, 2x4=8, 3x4=12, 4x4=16, 5x4=20, 6x4=24, 7x4=28, 8x4=32, 9x4=36,
1x5=5, 2x5=10, 3x5=15, 4x5=20, 5x5=25, 6x5=30, 7x5=35, 8x5=40, 9x5=45,
1x6=6, 2x6=12, 3x6=18, 4x6=24, 5x6=30, 6x6=36, 7x6=42, 8x6=48, 9x6=54,
1x7=7, 2x7=14, 3x7=21, 4x7=28, 5x7=35, 6x7=42, 7x7=49, 8x7=56, 9x7=63,
1x8=8, 2x8=16, 3x8=24, 4x8=32, 5x8=40, 6x8=48, 7x8=56, 8x8=64, 9x8=72,
1x9=9, 2x9=18, 3x9=27, 4x9=36, 5x9=45, 6x9=54, 7x9=63, 8x9=72, 9x9=81,

令人驚豔的囉唆... @@

1 則留言:

ffaannccyy 提到...

可以請教一下 template 的 two stages name lookup 嗎?