1.8 模板元编程

stl

模板元编程

  • 编译期数值计算: 求阶乘
  • 类型计算: if/else, is_same_type
  • 代码计算

注意元编程的位置。

编程形式

从编程范型（programming paradigm）上来说，C++模板是函数式编程（functional programming），它的主要特点是：函数调用不产生任何副作用（没有可变的存储），用递归形式实现循环结构的功能。C++模板的特例化提供了条件判断能力，而模板递归嵌套提供了循环的能力，这两点使得其具有和普通语言一样通用的能力（图灵完备性）。

总结一下就是：

  • 不能访问存储变量
  • 偏特化来支持递归
  • 偏特化实现if/else结构

从编程形式来看，模板的<>中的模板参数相当于函数调用的输入参数，模板中的typedef或static const或enum定义函数返回值（类型或数值，数值仅支持整型，如果需要可以通过编码计算浮点数），代码计算是通过类型计算进而选择类型的函数实现的（C++ 属于静态类型语言，编译器对类型的操控能力很强）。

这里需要解释一下：

  • templnate<.输入类型.>是函数的输入
  • typedef ….或者static constexpr 整型是函数的返回值
  • 代码计算是通过不同的类型跳转到不同的函数来运行。

这里有个非常简单的例子来说明这三点。

#include <iostream>
template<typename T, int i=1>
class someComputing {
public:
    typedef volatile T* retType; // 类型计算
    enum { retValume = i + someComputing<T, i-1>::retValume }; // 数值计算，递归
    static void f() { std::cout << "someComputing: i=" << i << '\n'; }
};
template<typename T> // 模板特例，递归终止条件
class someComputing<T, 0> {
public:
    enum { retValume = 0 };
};
template<typename T>
class codeComputing {
public:
    static void f() { T::f(); } // 根据类型调用函数，代码计算
};
int main(){
    someComputing<int>::retType a=0;
    std::cout << sizeof(a) << '\n'; // 64-bit 程序指针
    // VS2013 默认最大递归深度500，GCC4.8 默认最大递归深度900（-ftemplate-depth=n）
    std::cout << someComputing<int, 500>::retValume << '\n'; // 1+2+...+500
    codeComputing<someComputing<int, 99>>::f();
    std::cin.get(); return 0;
}

模板元编程的组织形式

数值计算

前面已经介绍了连续求和的模板。这里写一个编译时计算一个数值是否是质数。

#include <iostream>
template<int N>
struct is_prime {
    template<int p, int i>
    struct check_prime {
        static constexpr bool value = (p%i) && check_prime<p, i-1>::value;
    };
    template<int p>
    struct check_prime<p, 2> {
        static constexpr bool value = p == 2 || (p > 2 && (p&0x01));
    };
    template<int p>
    struct check_prime<p, 1> {
        static constexpr bool value = true;
    };
    static constexpr bool value = N == 2 || check_prime<N, N-1>::value;
};
int main(void) {
    std::cout << is_prime<5>::value << std::endl;
    std::cout << is_prime<7>::value << std::endl;
    std::cout << is_prime<2>::value << std::endl;
    return 0;
}

如果是再写一个类，用来连续打印<=N的所有的质数。写法如下：

template<int N>
struct print_prime {
    static constexpr bool value = (N < 2) ? false : is_prime<N>::value;
    static void print() {
        if (value) {
            std::cout << N << ":" << "true" << std::endl;
        }
        print_prime<N-1>::print();
    }
};
template<>
struct print_prime<2> {
    static constexpr bool value = true;
    static void print() {
        std::cout << 2 << ":" << "true" << std::endl;
    }
};