C/C++编程：模板元编程中的迭代

模板元编程：计算平凡根

// 用于计算sqrt(N)的基本模板
template <int N, int LO=0, int HI=N>
class Sqrt{
public:
    // 计算中点
    enum {
     mid = (LO + HI + 1) / 2};
    //借助二分查找一个较小的result
    enum {
     result = (N < mid*mid) ? Sqrt<N, LO, mid - 1> ::result : Sqrt<N, mid, HI>::result};
};
// 局部特化：适用于L0等于HI
template <int N, int M>
class Sqrt<N, M, M>{
public:
    enum {
    result = M};
};

第一个模板是一个普通的递归计算：运用模板参数N(用于计算平方根的值)和两个（其他的）可选参数进行调用：其中可选参数表示结果可能的最大值和最小值。于是，如果只使用一个实参N来调用模板参数的话，那么我们知道所求的平方根的值域必定在0和N之间

用于结束递归的特化的适用条件是：LO和HI具有相同的值，其中M就是我们的最终结果。

#include <iostream>
int main(){
    printf("%d", Sqrt<16>::result);
}

Sqrt<16>::result被扩展为Sqrt<16, 1, 16>::result。
在模板的内部，该模板元计算Sqrt<16, 1, 16>::result的过程如下：
在这里插入图片描述
接下来要计算Sqrt<16, 1, 8>::result，过程如下：

接下来要计算Sqrt<16, 1, 4>::result，过程如下：

接下来要计算Sqrt<16, 3, 4>::result，过程如下：

于是Sqrt<16, 3, 4>::result结束了整个递归过程，因为它的上界等于下界，能够与显式特化进行匹配。因此，最终的结果如下：result = 4

追踪所有的实例化

在上面的例子中，我们给出了计算16的平方根的一系列重要的过程。然而，当编译器试图计算下面表达式时：
在这里插入图片描述
编译器会实例化Sqrt<16, 1, 8>和Sqrt<16, 9, 16>。而且，由于代码试图使用::运算符访问结果类的成员(即result)，所以类中的所有成员同时也会被实例化。这就意味着，实例化Sqrt<16, 9, 16>将会使得Sqrt<16, 9, 12>和Sqrt<16, 16, 16>完全实例化。

这并不是我们所期望的，因为对于大多数编译器而言，模板实例化通常都是代价高昂的(事实上，C++标准建议最多只进行17层递归特化)。幸运的是，存在一些限制实例化数量过于庞大的技术。比如同使用特化来选择计算的结果而非使用?:

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;
};
template<int N, int LO=1, int HI=N>
class Sqrt {
  public:
    // compute the midpoint, rounded up
    enum {
     mid = (LO+HI+1)/2 };
    // 使用二分法查找一个较小的值
    typedef typename IfThenElse<(N<mid*mid),
                                Sqrt<N,LO,mid-1>,
                                Sqrt<N,mid,HI> >::ResultT
            SubT;
    enum {
     result = SubT::result };
};
// 用于结束递归的局部特化
template<int N, int S>
class Sqrt<N, S, S> {
  public:
    enum {
     result = S };
};

使用归纳变量

上面实现可能关于复杂。如果我们用普通的C++程序计算平方根一般会这样写：

ing I; 
for(I = 0; I*I < N; ++I){
    ;
}

然而，作为一个元编程，我们需要以递归的方式来组织这个迭代，而且我们需要一个终止条件来结束该递归：

// 借助于迭代计算sqrt(N)的基本模板
template<int N, int I=0>
class Sqrt{
public:
    enum{
    result = (I*I<N) ? Sqrt<N, I+1>::result : I};
};
//用于结束迭代的局部特化
template<int N>
class Sqrt<N, N>{
public:
    enum{
    result = N};
};

同样，我们可以使用特化来限制实例化个数：

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;
};
template <int N>
class Value{
public:
    enum {
    result = N};
};
template <int N, int I = 0>
class Sqrt{
public:
    //以实例化下一步 Sqrt<N,I+1>或者结果类型Value<I>作为两个分支
    typedef typename IfThenElse<(I*I<N),
            Sqrt<N,I+1>,
            Value<I>
    >::ResultT
            SubT;
    //使用分支类型的结果
    enum {
    result = SubT ::result};
};