Cpp Template Meta Programming MergeSort

|

C++ 模板元编程之编译时归并排序，源自水木社区 ilovecpp

Cpp Template Meta Programming MergeSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <boost/mpl/vector.hpp>
#include <boost/mpl/vector_c.hpp>
#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/identity.hpp>
#include <boost/mpl/empty.hpp>
#include <boost/mpl/less.hpp>
#include <boost/mpl/front.hpp>
#include <boost/mpl/pop_front.hpp>
#include <boost/mpl/push_front.hpp>
#include <boost/mpl/size.hpp>
#include <boost/mpl/iterator_range.hpp>
#include <boost/mpl/int.hpp>
#include <boost/mpl/for_each.hpp>
#include <iostream>

using namespace boost::mpl;

template<typename V1, typename V2>
struct Merge {
    template<typename T1, typename T2>
    struct F {
        typedef typename push_front<
            typename Merge<typename pop_front<T1>::type, T2>::type,
            typename front<T1>::type
            >::type type;
    };
        
    typedef typename eval_if<
        empty<V1>,
        identity<V2>,
        eval_if<
            empty<V2>,
            identity<V1>,
            eval_if<
                less<typename front<V1>::type, typename front<V2>::type>,
                F<V1, V2>,
                F<V2, V1>
                >
            >
        >::type type;
};

template<typename V>
struct MergeSort {
    template<typename T>
    struct F {
        typedef typename begin<T>::type t0;
        typedef typename advance<t0, int_<size<T>::value/2>>::type t1;
        typedef typename end<T>::type t2;
        typedef typename Merge<
            typename MergeSort<iterator_range<t0, t1>>::type,
            typename MergeSort<iterator_range<t1, t2>>::type
            >::type type;
    };
    
    typedef typename eval_if<
        empty<V>,
        identity<vector<>>,
        eval_if<
            less<size<V>, int_<2>>,
            identity<vector<typename front<V>::type>>,
            F<V>
            >
        >::type type;
};

typedef vector_c<int, 0,2,1,3,4> t1;
typedef MergeSort<t1>::type t10;

struct print {
    template <typename T>
    void operator()( T t ) const {
       std::cout << T::value << " ";
    }
};

int main() {
    for_each<t10>(print());
    return 0;
}

顺便说一下怎么读这类代码。困难主要来自不熟悉编译时的这套完全不同的语法，而概念和运行其实没多大差别。

  • 所有的typename关键字都是C++的语法限制，没有意义，先删掉。

  • 形如

    1
    2
    3
    4
    template<typename T1, typename T2>
    struct F {
        typedef ... type;
    };

的是编译时函数，相当于运行时的

1
2
3
F(T1, T2) {
    return ...;
}

  • 形如F<T1, T2>::type 的是编译时的函数调用，相当于运行时的 F(T1, T2)

如果没有::type，形如F<T1, T2>则是lazy的函数，相当于运行时的 function object，例如bind(F, T1, T2)。

  • eval_if<C, T1, T2>相当于运行时的if，根据C的真值决定对T1或T2 lazy求值。由于C++对模板实参是eager求值的，我们递归的话就不能用T1::type这种函数调用的形式，而只能把T1传进去让eval_if做lazy求值，否则会无穷递归。

  • typedef foo bar相当于运行时的bar=foo

  • 类型相当于运行时的值。所以像2这样的常数需要用int_<2>包装成类型。

好，我按照上述几条规则翻译一下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Merge(V1, V2) {
    F(T1, T2) {
        return push_front(Merge(pop_front(T1), T2), front(T1));
    };

    if (empty(V1))
        return V2;
    else if (empty(V2))
        return V1;
    else if (front(V1)<front(V2))
        return F(V1, V2);
    else
        return F(V2, V1);
}

MergeSort(V) {
    F(T) {
        t0 = begin(T);
        t1 = advance(t0, size(T)/2);
        t2 = end(T);
        return Merge(MergeSort(iterator_range(t0, t1)),
                     MergeSort(iterator_range(t1, t2)));
    }

    if (empty(V))
        return vector();
    else if (size(V)<2)
        return vector(front(V));
    else
        return F<V>;
}