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

比眉伴天荒 2023-01-16 03:24 145阅读 0赞

# 模板元编程：计算平凡根 #

// 用于计算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`的过程如下：  
![在这里插入图片描述][20210423200045700.png]  
接下来要计算`Sqrt<16, 1, 8>::result`，过程如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]  
接下来要计算`Sqrt<16, 1, 4>::result`，过程如下：  
![在这里插入图片描述][20210423200137753.png]  
接下来要计算`Sqrt<16, 3, 4>::result`，过程如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]  
于是`Sqrt<16, 3, 4>::result`结束了整个递归过程，因为它的上界等于下界，能够与显式特化进行匹配。因此，最终的结果如下：`result = 4`

# 追踪所有的实例化 #

在上面的例子中，我们给出了计算16的平方根的一系列重要的过程。然而，当编译器试图计算下面表达式时：  
![在这里插入图片描述][20210423200549619.png]  
编译器会实例化`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};
    };

# 总结 #

一个模板元编程可以包含下面几个部分：

*  状态变量：也就是模板参数
 *  迭代构造：通过递归
 *  路径选择：通过使用条件表达式或者特化
 *  整型（即枚举里面的值应该为整形）算法

[20210423200045700.png]: /images/20221022/a9ea9ddaa9dd4dbcb03ed7049f03e013.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: /images/20221022/53f13261166049dd8b20bcc61b343b03.png
[20210423200137753.png]: /images/20221022/d7e599bb0adc42c1acdb30807f398abd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: /images/20221022/81c88119ef834d35aa3d483f8a8623b2.png
[20210423200549619.png]: /images/20221022/c770e7e499f64561bdafab85e8827e4c.png