【C++ Templates（21）】元编程

• 使用元编程的目的是为了实现更多功能，并使花费开销更小。元编程的最大特点是用户自定义的计算可以在编译期运行，能在性能或接口简单性方面带来好处
• 元编程通常依赖于traits和类型函数的概念，在深入元编程前最好先熟悉他们

---

以下为第一版内容

---

metaprogram的第一个实例

• 下面是在编译期计算3的幂的实例

// meta/pow3.hpp

#ifndef POW3_HPP
#define POW3_HPP

// primary template to compute 3 to the Nth
template<int N>
class Pow3 {
public:
    enum { result=3*Pow3<N-1>::result };
};

// full specialization to end the recursion
template<>
class Pow3<0> {
public:
    enum { result = 1 };
};

#endif // POW3_HPP


// meta/pow3.cpp

#include <iostream>
#include "pow3.hpp"

int main() 
{
    std::cout << "Pow3<7>::result = " << Pow3<7>::result
              << '\n';
}

• 首先编译器实例化Pow3<7>从而获得3 * Pow3<6>::result，接着Pow3<6>递归往下实例化，直到Pow3<>基于0进行实例化结束递归，并以1作为Pow3<0>的结果，这里的Pow3<>模板及其特化就被称为一个template metaprogramming

枚举值和静态常量

• 最初枚举值是声明常量表达式的唯一方法，后来引入的类内部进行静态常量初始化也可以实现

struct TrueConstants {
    enum { Three = 3 };
    static int const Four = 4;
};

• 利用静态成员常量，Pow3的metaprogram就可以更改如下

// meta/pow3b.hpp

#ifndef POW3_HPP
#define POW3_HPP

// primary template to compute 3 to the Nth
template<int N>
class Pow3 {
  public:
    static int const result = 3 * Pow3<N-1>::result;
};

// full specialization to end the recursion
template<>
class Pow3<0> {
  public:
    static int const result = 1;
};

#endif // POW3_HPP

• 但静态成员变量只能是左值，如果有函数void foo(int const&)，把metaprogram结果传进去foo(Pow3<7>::result)，那么编译器必须传递Pow3<7>::result的地址，这会强制编译器实例化静态成员定义，并分配内存，这样计算就不只是编译期效果了。而枚举值不是左值，没有地址，通过引用传递枚举值不会使用静态内存，因此之后的内容都使用枚举值而放弃静态常量

第2个例子：计算平方根

// meta/sqrt1.hpp

#ifndef SQRT_HPP
#define SQRT_HPP

// primary template to compute sqrt(N)
template <int N, int LO=1, int HI=N>
class Sqrt {
  public:
    // compute the midpoint, rounded up
    enum { mid = (LO+HI+1)/2 };

    // search a not too large value in a halved interval
    enum { result = (N<mid*mid) ? Sqrt<N,LO,mid-1>::result
                                : Sqrt<N,mid,HI>::result };
};

// partial specialization for the case when LO equals HI
template<int N, int M>
class Sqrt<N,M,M> {
  public:
    enum { result = M };
};

#endif // SQRT_HPP


// meta/sqrt1.cpp
#include <iostream>
#include "sqrt1.hpp"

int main()
{
    std::cout << "Sqrt<16>::result = " << Sqrt<16>::result
              << '\n';
    std::cout << "Sqrt<25>::result = " << Sqrt<25>::result
              << '\n';
    std::cout << "Sqrt<42>::result = " << Sqrt<42>::result
              << '\n';
    std::cout << "Sqrt<1>::result =  " << Sqrt<1>::result
              << '\n';
}

• Sqrt<16>::result被扩展为Sqrt<16,1,16>::result，计算过程如下

mid = (1+16+1)/2
    = 9
result = (16<9*9) ? Sqrt<16,1,8>::result : Sqrt<16,9,16>::result
    = (16<81) ? Sqrt<16,1,8>::result : Sqrt<16,9,16>::result
    = Sqrt<16,1,8>::result

mid = (1+8+1)/2
    = 5
result = (16<5*5) ? Sqrt<16,1,4>::result : Sqrt<16,5,8>::result
    = (16<25) ? Sqrt<16,1,4>::result : Sqrt<16,5,8>::result
    = Sqrt<16,1,4>::result

mid = (1+4+1)/2
    = 3
result = (16<3*3) ? Sqrt<16,1,2>::result : Sqrt<16,3,4>::result
    = (16<9) ? Sqrt<16,1,2>::result : Sqrt<16,3,4>::result
    = Sqrt<16,3,4>::result

mid = (3+4+1)/2
    = 4
result = (16<4*4) ? Sqrt<16,3,3>::result : Sqrt<16,4,4>::result
    = (16<16) ? Sqrt<16,3,3>::result : Sqrt<16,4,4>::result
    = Sqrt<16,4,4>::result

result = 4

• 编译器计算下列表达式时，会实例化所有分支，又因为使用了::运算符访问类成员，所以类中所有成员同时也被实例化，这就导致完全实例化Sqrt<16,9,16>也会导致完全实例化Sqrt<16,9,12>和Sqrt<16,13,16>，最终产生大量实例化体，总数大约是N的两倍

(16<=8*8) ? Sqrt<16,1,8>::result : Sqrt<16,9,16>::result

• 对大多数编译器来说模板实例化开销很大，但存在一些限制实例化数量过于庞大的技术，下面放弃使用?:运算符而使用特化来选择计算结果

// meta/sqrt2.hpp

#include "ifthenelse.hpp"

// primary template for main recursive step
template<int N, int LO=1, int HI=N>
class Sqrt {
public:
    // compute the midpoint, rounded up
    enum { mid = (LO+HI+1)/2 };

    // search a not too large value in a halved interval
    typedef typename IfThenElse<(N<mid*mid),
                                Sqrt<N,LO,mid-1>,
                                Sqrt<N,mid,HI> >::ResultT
            SubT;
    enum { result = SubT::result };
};

// partial specialization for end of recursion criterion
template<int N, int S>
class Sqrt<N, S, S> {
public:
    enum { result = S };
};

• 这里的主要改变在于使用了IfThenElse模板

// meta/ifthenelse.hpp

#ifndef IFTHENELSE_HPP
#define IFTHENELSE_HPP

// primary template: yield second or third argument depending on first argument
template<bool C, typename Ta, typename Tb>
class IfThenElse;

// partial specialization: true yields second argument
template<typename Ta, typename Tb>
class IfThenElse<true, Ta, Tb> {
public:
    typedef Ta ResultT;
};

// partial specialization: false yields third argument
template<typename Ta, typename Tb>
class IfThenElse<false, Ta, Tb> {
public:
    typedef Tb ResultT;
};

#endif // IFTHENELSE_HPP

• IfThenElse根据给定布尔值在两个类型中选择一个，为类模板定义typedef不会导致实例化，最终只有查找Sub::result时才会完全实例化SubT代表的类型，实例化体数量趋向log2(N)

使用归纳变量

• 下面考虑一个更加自然的计算平方根迭代算法，计算N的平方根，I的值从0迭代到N直到I的平方大于等于N

// meta/sqrt3.hpp

#ifndef SQRT_HPP
#define SQRT_HPP

// primary template to compute sqrt(N) via iteration
template <int N, int I=1>
class Sqrt {
  public:
    enum { result = (I*I<N) ? Sqrt<N,I+1>::result
                            : I };
};

// partial specialization to end the iteration
template<int N>
class Sqrt<N,N> {
public:
    enum { result = N };
};

#endif // SQRT_HPP

• 看起来第一个模板就可以找到最终结果，但这里使用了?:运算符，会对两个分支都进行实例化，如编译器计算Sqrt<4>的实例化过程如下，尽管Step2就找到了结果，但实例化仍会进行，直到找到一个结束递归的特化，因此如果没有该特化编译器就会一直实例化，直到实例化个数达到最大值

Step 1:
result = (1*1<4) ? Sqrt<4,2>::result
    : 1
Step 2:
result = (1*1<4) ? (2*2<4) ? Sqrt<4,3>::result
        : 2
    : 1
Step 3:
result = (1*1<4) ? (2*2<4) ? (3*3<4) ? Sqrt<4,4>::result
            : 3
        : 2
    : 1
Step 4:
result = (1*1<4) ? (2*2<4) ? (3*3<4) ? 4
            : 3
        : 2
    : 1

• 同样也可以用IfThenElse模板解决这个问题，不用提供结束递归的局部特化，只要使用一个Value<>模板返回模板实参值作为所求的result，这样实例化数会趋近于Sqrt(N)

// meta/sqrt4.hpp

#ifndef SQRT_HPP
#define SQRT_HPP

#include "ifthenelse.hpp"

// template to yield template argument as result
template<int N>
class Value {
public:
    enum { result = N };
};

// template to compute sqrt(N) via iteration
template <int N, int I=1>
class Sqrt {
public:
    // instantiate next step or result type as branch
    typedef typename IfThenElse<(I*I<N),
                                Sqrt<N,I+1>,
                                Value<I>
                               >::ResultT
            SubT;

    // use the result of branch type
    enum { result = SubT::result };
};

#endif // SQRT_HPP

计算完整性

• 上述例子说明一个template metaprogram可以包含以下部分
  • 状态变量：即模板参数
  • 迭代构造：通过递归
  • 路径选择：通过条件表达式或特化
  • 整型算法
• 如果对递归实例化体和状态变量的数量没有限制，metaprogram就可以在编译器对任何可计算对象进行高效计算，实际上标准建议最多进行17层递归实例化，因此实际开发中很少使用template metaprogram，但某些情况下metaprogram是实现高效模板的一个重要工具，特别是实现一些对性能要求严格的算法

递归实例化和递归模板实参

template<typename T, typename U>
struct Doublify {};

template<int N>
struct Trouble {
    typedef Doublify<typename Trouble<N-1>::LongType,
        typename Trouble<N-1>::LongType> LongType;
};

template<>
struct Trouble<0> {
    typedef double LongType;
};

Trouble<10>::LongType ouch;

• Trouble<10>::LongType引发了Trouble<9>，Trouble<8>...等递归实例化，还基于一些非常复杂的类型实例化了Doublify。从下表可以看出，对于表达式Trouble<N>::LongType的类型描述，复杂度与2^N成正比。这种使用递归模板实参的情况会强制编译器生成更多的实例化体，编译器要为每个类型保存一个mangled name，这个mangled name需要根据模板特化进行组织，早期编译器mangled name的长度一般等于template-id的长度，于是Trouble<10>::LongType可能产生一个长度大于10000个字符的managled name。现在的编译器使用了智能压缩技术来减少增长趋势，Trouble<10>::LongType可能被压缩到只有几百个字符，但在组织递归实例化时，仍然趋向于避免在模板实参中使用递归嵌套的实例化

Typedef Name	Underlying Type
Trouble<0>::LongType	double
Trouble<1>::LongType	Doublify<double,double>
Trouble<2>::LongType	Doublify<Doublify<double,double>, Doublify<double,double> >
Trouble<3>::LongType	Doublify<Doublify<Doublify<double,double>, Doublify<double,double> >, Doublify<Doublify<double,double>, Doublify<double,double> > >

使用metaprogram来展开循环

• 接下来介绍首个实用的metaprogram应用，用于展开数值计算的循环，一个典型应用就是计算两个vector的点乘，下面是一个直接实现

// meta/loop1.cpp

#ifndef LOOP1_HPP
#define LOOP1_HPP

template <typename T>
inline T dot_product (int dim, T* a, T* b)
{
    T result = T();
    for (int i=0; i<dim; ++i) { 
        result += a[i]*b[i];
    }
    return result;
}

#endif // LOOP1_HPP


// meta/loop1.cpp

#include <iostream>
#include "loop1.hpp"

int main()
{
    int a[3] = { 1, 2, 3};
    int b[3] = { 5, 6, 7};

    std::cout << "dot_product(3,a,b) = " << dot_product(3,a,b)
              << '\n';
    std::cout << "dot_product(3,a,a) = " << dot_product(3,a,a)
              << '\n';
}

// output
dot_product(3,a,b) = 38
dot_product(3,a,a) = 14

• 这样的实现是正确的，但太耗时，原因是编译器会优化迭代，这种优化反而带来反面效果，直接展开循环如下可能更好

a[0]*b[0] + a[1]*b[1] + a[2]*b[2]

• template metaprogram可以编写展开循环的程序

// meta/loop2.hpp

#ifndef LOOP2_HPP
#define LOOP2_HPP

// primary template
template <int DIM, typename T>
class DotProduct {
public:
    static T result (T* a, T* b) {
        return *a * *b  +  DotProduct<DIM-1,T>::result(a+1,b+1);
    }
};

// partial specialization as end criteria
template <typename T>
class DotProduct<1,T> {
public:
    static T result (T* a, T* b) {
        return *a * *b;
    }
};

// convenience function
template <int DIM, typename T>
inline T dot_product (T* a, T* b)
{
    return DotProduct<DIM,T>::result(a,b);
}

#endif // LOOP2_HPP


// meta/loop2.cpp

#include <iostream>
#include "loop2.hpp"

int main()
{
    int a[3] = { 1, 2, 3};
    int b[3] = { 5, 6, 7};

    std::cout << "dot_product<3>(a,b) = " << dot_product<3>(a,b)
              << '\n';
    std::cout << "dot_product<3>(a,a) = " << dot_product<3>(a,a)
              << '\n';
}

• 这里把前面的dot_product(3,a,b)改成了dot_product<3>(a,b)，这会实例化一个辅助函数模板，在函数模板内部会直接调用DotProduct<3,int>::result(a,b)，这就是metaprogram的起点。在这个metaprogram内部，result等于第一个元素a和b的乘积加上两个新vector的点乘，两个新vector由a和b后面的元素组成

template <int DIM, typename T>
class DotProduct {
public:
    static T result (T* a, T* b) {
        return *a * *b + DotProduct<DIM-1,T>::result(a+1,b+1);
    }
};

• 结束条件是一元vector，另外要注意，使用这种metaprogram要求vector元数在编译期已知

template <typename T>
class DotProduct<1,T> {
public:
    static T result (T* a, T* b) {
        return *a * *b;
    }
};

• dot_product<3>(a,b)实例化过程的计算如下

DotProduct<3,int>::result(a,b)
= *a * *b + DotProduct<2,int>::result(a+1,b+1)
= *a * *b + *(a+1) * *(b+1) + DotProduct<1,int>::result(a+2,b+2)
= *a * *b + *(a+1) * *(b+1) + *(a+2) * *(b+2)

---

以下为第二版内容

---

现代C++元编程的情况

值元编程（Value Metaprogramming）

• 第一版中限制于传统C++标准，编译期计算是一个小的挑战，这里将花大量内容来实现。C++11开始，特别是C++14引入的constexpr函数，移除了大部分挑战。一个例子就是在编译期使用递归计算平方根，C++14中可以简单地写为

// meta/sqrtconstexpr.hpp

template<typename T>
constexpr T sqrt(T x)
{
    if (x <= 1) {
        return x;
    }

    // 反复确定平方根位于[lo, hi]哪一半，直到区间减为一个值
    T lo = 0, hi = x;
    for (;;) {
        auto mid = (hi+lo)/2, midSquared = mid*mid;
        if (lo+1 >= hi || midSquared == x) {
            // mid一定是平方根
            return mid;
        }
        if (midSquared < x) {
            lo = mid;
        }
        else {
            hi = mid;
        }
    }
}

// 这个算法能在编译期或运行期计算
// 虽然在运行期不是最高效的算法，但这不是最重要的
static_assert(sqrt(25) == 5, ""); // OK (evaluated at compile time)
static_assert(sqrt(40) == 6, ""); // OK (evaluated at compile time)
std::array<int, sqrt(40)+1> arr; // 声明7个元素的数组 (compile time)
long long l = 53478;
std::cout << sqrt(l) << '\n'; // prints 231 (evaluated at run time)

类型元编程（Type Metaprogramming）

• 以前讨论过的trait可以将类型作为输入并产生一个新类型，如RemoveReferenceT类模板，然而只能计算初等类型操作。依赖于递归模板实例化，可以进行更复杂的类型计算

// meta/removeallextents.hpp

// primary template: in general we yield the given type:
template<typename T>
struct RemoveAllExtentsT {
    using Type = T;
};

// partial specializations for array types (with and without bounds):
template<typename T, std::size_t SZ>
struct RemoveAllExtentsT<T[SZ]> {
    using Type = typename RemoveAllExtentsT<T>::Type;
};
template<typename T>
struct RemoveAllExtentsT<T[]> {
    using Type = typename RemoveAllExtentsT<T>::Type;
};

template<typename T>
using RemoveAllExtents = typename RemoveAllExtentsT<T>::Type;

• 这里RemoveAllExtents是一个类型元函数（即一个产生结果类型的计算设备），它将移除任意数量的顶层“数组层”，即移除所有数组维度的数组类型T的元素类型，如果T不是数组类型，则此实例包含T

RemoveAllExtents<int[]> // yields int
RemoveAllExtents<int[5][10]> // yields int
RemoveAllExtents<int[][10]> // yields int
RemoveAllExtents<int(*)[5]> // yields int(*)[5]，pointer to int[5]

混合元编程（Hybrid Metaprogramming）

• 使用值元编程和类型元编程可以在编译期计算值和类型，然而最终我们对运行期效率感兴趣，所以在运行期使用这些元程序替代期望的类型和常量。然而元编程能做的更多：可以在编译期以编程的方式汇编小片带运行期效率的代码。这被称为混合元编程
• 从一个简单的例子开始：计算两个std::array值的点积，std::array是固定长度容器模板

template<typename T, std::size_t N>
auto dotProduct(std::array<T, N> const& x, std::array<T, N> const& y)
{
    T result{};
    for (std::size_t k = 0; k<N; ++k) {
        result += x[k]*y[k];
    }
    return result;
}

• 在一些机器上，for循环的汇编将产生分支指令，可能比直接写出循环造成更大的开销

result += x[0]*y[0];
result += x[1]*y[1];
result += x[2]*y[2];
result += x[3]*y[3];
...

• 幸运的是，现代编译器将优化循环为目标平台最高效形式。出于讨论的原因，重写一个避免循环的实现

template<typename T, std::size_t N>
struct DotProductT {
    static inline T result(T* a, T* b) {
        return *a * *b + DotProduct<T, N-1>::result(a+1,b+1);
    }
};

// partial specialization as end criteria
template<typename T>
struct DotProductT<T, 0> {
    static inline T result(T*, T*) {
        return T{};
    }
};

template<typename T, std::size_t N>
auto dotProduct(std::array<T, N> const& x, std::array<T, N> const& y)
{
    return DotProductT<T, N>::result(x.begin(), y.begin());
}

• 定长数组在混合元编程中是有用的，尽管如此，混合元编程真正的hero容器是tuple，一个tuple是一个值序列，每个值类型可选，标准库提供了std::tuple类模板

std::tuple<int, std::string, bool> tVal{42, "Answer", true};

对单元类型（Unit Type）的混合元编程

• 另一个展现混合计算能力的例子是计算不同单元类型值的结果的库，值计算在运行期执行，但决定的结果单元在编译期计算
• 为了解释这点，先提出一个高度简化的例子，将单元和他们的比值相联系，比如如果时间的主要单元是秒，一毫秒代表1/1000的比值，一分钟代表60/1的比值

// meta/ratio.hpp
// 定义分数类型
template<unsigned N, unsigned D = 1>
struct Ratio {
    static constexpr unsigned num = N; // 分子
    static constexpr unsigned den = D; // 分母
    using Type = Ratio<num, den>;
};

// 随后可以定义一个编译期计算，比如相加两个单元

// meta/ratioadd.hpp
// 实现两个分数的相加
template<typename R1, typename R2>
struct RatioAddImpl
{
private:
    static constexpr unsigned den = R1::den * R2::den;
    static constexpr unsigned num = R1::num * R2::den + R2::num * R1::den;
public:
    typedef Ratio<num, den> Type;
};

// 方便起见使用using声明
template<typename R1, typename R2>
using RatioAdd = typename RatioAddImpl<R1, R2>::Type;

// 这允许在编译期计算两个分数的和
using R1 = Ratio<1,1000>;
using R2 = Ratio<2,3>;
using RS = RatioAdd<R1,R2>; // RS has type Ratio<2003,2000>
std::cout << RS::num << '/' << RS::den << '\n'; // 打印2003/3000
using RA = RatioAdd<Ratio<2,3>,Ratio<5,7>>; // RA has type Ratio<29,21>
std::cout << RA::num << '/' << RA::den << '\n'; // 打印29/21

• 现在可以定义一个时间的类模板，它用任意的值类型和一个Ratio<>实例的单元类型参数化

// meta/duration.hpp

// duration type for values of type T with unit type U:
template<typename T, typename U = Ratio<1>>
class Duration {
public:
    using ValueType = T;
    using UnitType = typename U::Type;
private:
    ValueType val;
public:
    constexpr Duration(ValueType v = 0)
    : val(v) {
    }
    constexpr ValueType value() const {
        return val;
    }
};

• 有趣的部分是定义operator+

// meta/durationadd.hpp

// adding two durations where unit type might differ:
template<typename T1, typename U1, typename T2, typename U2>
auto constexpr operator+(Duration<T1, U1> const& lhs,
Duration<T2, U2> const& rhs)
{
    // resulting type is a unit with 1 a nominator and
    // the resulting denominator of adding both unit type fractions
    using VT = Ratio<1,RatioAdd<U1,U2>::den>;
    // resulting value is the sum of both values
    // converted to the resulting unit type:
    auto val = lhs.value() * VT::den / U1::den * U1::num +
        rhs.value() * VT::den / U2::den * U2::num;
    return Duration<decltype(val), VT>(val);
}

• 这里允许实参有不同的单元类型U1和U2，使用这些单元类型计算有对应unit fraction（分子是1的分数）类型的结果，使用这些可以编译如下代码

int x = 42;
int y = 77;
auto a = Duration<int, Ratio<1,1000>>(x); // x milliseconds
auto b = Duration<int, Ratio<2,3>>(y); // y 2/3 seconds
auto c = a + b; // computes resulting unit type 1/3000 seconds
// and generates run-time code for c = a*3 + b*2000

• hybrid在这里的体现是，c在编译期决定结果的单元类型Ratio<1, 3000>，并产生在运行期计算结果值的代码
• 由于值类型是一个模板参数，可以让类Duration带除了int的值类型甚至各种混杂的值类型（只要这些类型值的相加是定义的）

auto d = Duration<double, Ratio<1,3>>(7.5); // 7.5 1/3 seconds
auto e = Duration<int, Ratio<1>>(4); // 4 seconds
auto f = d + e; // computes resulting unit type 1/3 seconds
// and generates code for f = d + e*3

• 此外，如果值在编译期已知，值计算甚至能在编译期进行，因为Duration的operator+是constexpr
• 标准库类模板std::chrono略带改进地使用这个方法，比如使用预定义单元（如std::chrono::milliseconds）支持时间字面量（如10ms）和溢出处理

反射元编程的维度（The Dimensions of Reflective Metaprogramming）

• 值元编程也能用递归模板实例化完成，这也是C++11前的实现机制

// meta/sqrt1.hpp

// primary template to compute sqrt(N)
template<int N, int LO=1, int HI=N>
struct Sqrt {
    // compute the midpoint, rounded up
    static constexpr auto mid = (LO+HI+1)/2;

    // search a not too large value in a halved interval
    static constexpr auto value = (N<mid*mid) ?
        Sqrt<N,LO,mid-1>::value : Sqrt<N,mid,HI>::value;
};

// partial specialization for the case when LO equals HI
template<int N, int M>
struct Sqrt<N,M,M> {
    static constexpr auto value = M;
};

• 然而，这个元函数的输入是一个非类型模板实参，而不是函数实参，且跟踪绑定区间的“局部变量”也被重铸为非类型模板实参。比起constexpr函数，这明显是一个很不友好的方法，稍后将分析此代码，以检查它如何消耗编译器资源
• 在任何情况下，可以看到元编程的计算引擎可能有很多选择。然而，这不是考虑这些选项的唯一维度。相反，C++的综合元编程解决方案必须沿着三个维度进行选择：
  • Computation（计算）
  • Reflection（反射）：以编程方式检查程序特征的能力
  • Generation（生成）：为程序生成附加代码的能力。
• 我们已经看到了两种计算方法：递归实例化和constexpr计算。为了进行反射，我们在type trait中找到了部分解决方案。尽管可用的trait启用了许多高级模板技术，但远不能涵盖语言中的反射所需的全部内容。比如给定一个类类型，许多应用程序都希望以编程方式探索该类的成员。当前的trait基于模板实例化，C++可以设想提供额外的语言能力或内在库组件，来产生在编译期包含反射信息的类模板实例，这是基于递归模板实例化的计算的一个好方法。不幸的是，类模板实例消耗大量编译器存储，且直到编译结束时才能释放。另一种选择，与constexpr计算很好地配对，是引入一种新的标准类型来表示反射信息
• 在现有C++语言中创建一个灵活的、通用的和程序员友好的代码生成机制仍然是各方正在研究的挑战。但是，实例化模板也是一种“代码生成”机制。此外，编译器在将扩展内联的小函数的调用过程中已经足够可靠，该机制可以用作代码生成的工具。这些观察正是DotProductT例子的基础，结合更强大的反射能力，现有技术已经能够实现显著的元编程效果

递归实例化的开销

• 模板实例化不廉价：即使是相对温和的类模板也可以为每个实例分配一个千兆字节的存储空间，直到编译完成该存储才被回收。这里检查一个使用Sqrt模板的简单程序的细节

// meta/sqrt1.cpp

#include <iostream>
#include "sqrt1.hpp"
int main()
{
    std::cout << "Sqrt<16>::value = " << Sqrt<16>::value << '\n';
    std::cout << "Sqrt<25>::value = " << Sqrt<25>::value << '\n';
    std::cout << "Sqrt<42>::value = " << Sqrt<42>::value << '\n';
    std::cout << "Sqrt<1>::value = " << Sqrt<1>::value << '\n';
}

Sqrt<16>::value
// 扩展为
Sqrt<16,1,16>::value
// 计算如下
mid = (1+16+1)/2 = 9
value = (16<9*9) ? Sqrt<16,1,8>::value : Sqrt<16,9,16>::value
    = (16<81) ? Sqrt<16,1,8>::value : Sqrt<16,9,16>::value
    = Sqrt<16,1,8>::value
// 计算Sqrt<16,1,8>::value
mid = (1+8+1)/2 = 5
value = (16<5*5) ? Sqrt<16,1,4>::value : Sqrt<16,5,8>::value
    = (16<25) ? Sqrt<16,1,4>::value : Sqrt<16,5,8>::value
    = Sqrt<16,1,4>::value
// 计算Sqrt<16,1,4>::value
mid = (1+4+1)/2 = 3
value = (16<3*3) ? Sqrt<16,1,2>::value : Sqrt<16,3,4>::value
    = (16<9) ? Sqrt<16,1,2>::value : Sqrt<16,3,4>::value
    = Sqrt<16,3,4>::value
// 计算Sqrt<16,3,4>::value
mid = (3+4+1)/2 = 4
value = (16<4*4) ? Sqrt<16,3,3>::value : Sqrt<16,4,4>::value
    = (16<16) ? Sqrt<16,3,3>::value : Sqrt<16,4,4>::value
    = Sqrt<16,4,4>::value
// 结束递归
value = 4

跟踪所有实例化

• 以上分析计算16的平方根，然而编译器计算下列表达式时，将实例化所有分支

(16<=8*8) ? Sqrt<16,1,8>::value : Sqrt<16,9,16>::value

• 此外，由于代码试图使用::运算符访问生成的类类型的成员，所以该类类型中的所有成员也被实例化
• 这意味着，Sqrt<16,9,16>的实例化将造成Sqrt<16,9,12>和Sqrt<16,13,16>的实例化。当检查整个过程，发现生成了大量实例化，整个数量几乎是N的两倍
• 幸运的是，有办法减少实例化数量的膨胀。为了说明这个技术，重写Sqrt如下

// meta/sqrt2.hpp

#include "ifthenelse.hpp"
// primary template for main recursive step
template<int N, int LO=1, int HI=N>
struct Sqrt {
    // compute the midpoint, rounded up
    static constexpr auto mid = (LO+HI+1)/2;
    // search a not too large value in a halved interval
    using SubT = IfThenElse<(N<mid*mid),
        Sqrt<N,LO,mid-1>,
        Sqrt<N,mid,HI>>;
    static constexpr auto value = SubT::value;
};

// partial specialization for end of recursion criterion
template<int N, int S>
struct Sqrt<N, S, S> {
    static constexpr auto value = S;
};

• 这里的关键是使用了IfThenElse模板，它是一个基于一个给定的布尔常量在两个类型之间选择的设备。如果常量是true选择第一个类型，否则选择第二个。在这点上，重要的是要记住，为类模板实例定义类型别名不会导致C++编译器实例化该实例的函数体

using SubT = IfThenElse<(N<mid*mid),
    Sqrt<N,LO,mid-1>,
    Sqrt<N,mid,HI>>;

• 这里Sqrt<N,LO,mid-1>或Sqrt<N,mid,HI>都不会完全实例化，这里实例化的数量级为log2(N)

计算完整性

• 上述例子说明一个template metaprogram可以包含以下部分
  • 状态变量：即模板参数
  • 迭代构造：通过递归
  • 路径选择：通过条件表达式或特化
  • 整型算法
• 如果对递归实例化体和状态变量的数量没有限制，metaprogram就可以在编译器对任何可计算对象进行高效计算，实际上标准建议最多进行1024层递归实例化，因此实际开发中很少使用template metaprogram，但某些情况下metaprogram是实现高效模板的一个重要工具，特别是实现一些对性能要求严格的算法

递归实例化与递归模板实参

template<typename T, typename U>
struct Doublify {
};

template<int N>
struct Trouble {
    using LongType = Doublify<typename Trouble<N-1>::LongType,
    typename Trouble<N-1>::LongType>;
};
template<>
struct Trouble<0> {
    using LongType = double;
};

Trouble<10>::LongType ouch;

• Trouble<10>::LongType引发了Trouble<9>，Trouble<8>...等递归实例化，还基于一些非常复杂的类型实例化了Doublify。从下表可以看出，对于表达式Trouble<N>::LongType的类型描述，复杂度与2^N成正比。这种使用递归模板实参的情况会强制编译器生成更多的实例化体，编译器要为每个类型保存一个mangled name，这个mangled name需要根据模板特化进行组织，早期编译器mangled name的长度一般等于template-id的长度，于是Trouble<10>::LongType可能产生一个长度大于10000个字符的managled name。现在的编译器使用了智能压缩技术来减少增长趋势，Trouble<10>::LongType可能被压缩到只有几百个字符，但在组织递归实例化时，仍然趋向于避免在模板实参中使用递归嵌套的实例化

Typedef Name	Underlying Type
Trouble<0>::LongType	double
Trouble<1>::LongType	Doublify<double,double>
Trouble<2>::LongType	Doublify<Doublify<double,double>, Doublify<double,double> >
Trouble<3>::LongType	Doublify<Doublify<Doublify<double,double>, Doublify<double,double>>, Doublify<Doublify<double,double>, Doublify<double,double>>>

枚举值与静态常量

• 最初枚举值是声明常量表达式的唯一方法，比如用枚举定义元程序Pow3

// meta/pow3enum.hpp

// primary template to compute 3 to the Nth
template<int N>
struct Pow3 {
    enum { value = 3 * Pow3<N-1>::value };
};
// full specialization to end the recursion
template<>
struct Pow3<0> {
    enum { value = 1 };
};

• C++98引入了类内静态常量初始化的概念，Pow3可以修改如下

// meta/pow3const.hpp

// primary template to compute 3 to the Nth
template<int N>
struct Pow3 {
    static int const value = 3 * Pow3<N-1>::value;
};
// full specialization to end the recursion
template<>
struct Pow3<0> {
    static int const value = 1;
};

• 然而，这个版本有一个确点是，静态常量成员是左值，如果有如下声明

void foo(int const&);

• 并将元程序的结果传递给它

foo(Pow3<7>::value);

• 编译器必须传递Pow3<7>::result的地址，这会强制编译器实例化静态成员定义，并分配内存，这样计算就不只是编译期效果了。而枚举值不是左值，没有地址，通过引用传递枚举值不会使用静态内存，这几乎就像把计算值作为字面值传递，因此第一版中更喜欢使用枚举常量
• C++11中引入了constexpr静态数据成员，且将不限于整型。虽然没有解决上述的地址问题，但现在是一个产生元程序结果的常用方法，这种方法的优点是有一个正确类型，且当静态成员用auto声明时类型能被推断
• C++17中添加的inline静态成员解决了地址问题，并且能与constexpr一起使用