模板特化

前言:

C++提供了一种特例机制，对于某个已有模板,可以为某个或者某组模板参数类型另外指定一种变体,以应付原模板无法处理的问题，或者提供更高效的实现方案.这种机制就称为模板特例.

模板特例一个典型的例子就是C++标准库中的容器类模板vector<T>。与数组相似,vector是一种将数据连续存放的容器.但与数组不同的是,vector容量可随所存数据增加而自动增加.vecotr<bool>则是vector<T>的一个特例,专门为存储布尔型值设计.布尔型只有两个值,真或者假,只需要1比特即可表示.1字节完全可以用来存储8个布尔型变量.如果采用基于sizeof(T)的算法,则1个布尔值占用1字节,显得太浪费.

我们将vector<bool>设计成用一系列整数值来保存压缩后的布尔值.

具体见代码:

#include <cstdio>
#include <iostream>
#include <stdexcept>

template<typename T>
class my_vector{
private:
     T * array;
     unsigned size;
     unsigned block_size;
public:
    my_vector(unsigned bsz):array((T*)malloc(sizeof(T)*block_size),size(0),
                              block_size(size){
                              }
    ~my_vector(){
         if(array){
               free(array);
         }
    }
    
    void push_back(const T& v) throw (std::runtime_error){
           if(size==block_size){
                  block_size*=2;
                  T *new_array=realloc(array,block_size*sizeof(T));
                  if(new_array!=NULL){
                        array=new_array;
                  }
                  
                  else{
                         free(array);
                         array=NULL;
                         throw std::runtime_error("Out of memory.");
                  }
           }
           array[size++]=elem;
    }
    
    T& operator[] (unsigned i) {return array[i];}
    const T& operator[] (unsigned i) const{return array[i];}
    
    //告诉我们占了多少内存
    unsigned get_mem_size() const{return block_size*sizeof(T);}
};


template<>
class my_vector<bool>{
private:
       int *array;
       unsigned size;
       unsigned block_size;
       //一个段(segment)即一个整数值,段大小为一个整数值所能容纳的最多布尔值
       const static unsigned seg_size;
public:
       my_vector(unsigned bsz):array((int*)malloc(sizeof(int)*bsz),size(0),
                                                       block_size(bsz){
                                                       }
       
       ~my_vector(){
              if(array){
                    free(array);
              }
       }
       
       void push_back(bool elem) throw (std::runtime_error){
               if(size==block_size){
                     block_size*=2;
                     int *new_array=(int*)realloc(array,sizeof(int)*block_size);
                     if(new_array){
                           array=new_array;
                     }
                     
                     else{
                          free(array);
                          array=NULL;
                          throw std::runtime_error("Out of memory.");
                     }       
               }
               
              set(size++,elem);
      }
      
      void set(unsigned i,bool elem){
             if(elem){
                   array[i/seq_size] |=(0x1 << (i%seq_size));
             }
             
             else{
                   array[i/seq_size] &=~(0x1 << (i%seq_size));
             }
      }
      
      bool operator[] (unsigned i) const{
             return array[i/seq_size] & (0x1 << (i%seq_size))!=0;
      }
      
      unsigned get_mem_size() const{
            return block_size* sizeof(int);
      }
};

const unsigned my_vector<bool>::seq_size =sizeof(int)*8;

面试题：

在软件公司的招聘考试中,经常出现的C/C++题目是:不使用循环及条件判断语句,打印1-100的数字.

思路如下:

这个问题可以通过采用编译器的递归调用来轻松解决问题.

首先,既然不能采用循环的方式来打印,就只能采用"分而治之"的策略.那么"打印1~100的数"可以分解为"打印1~99的数"及"打印100的数"两个问题.依次类推, 则该问题显然可以通过递归来实现。
模板特例实际上也是实现了一种条件判断逻辑-当模板参数满足某一匹配条件时所匹配的特例实现,否则用通例来实现.并且由于模板通例及特例是分别写在多个模板实现代码中,并不需要增加任何判断语句。

注意:

不过模板特例所实现的判断逻辑是在编译器来执行，而不是在程序运行时基于输入值来判断,这就要求判断式的值在编译器已知.

解题思路还是按照递归方式,只是将递归函数改写成函数模板,将打印范围由函数参数变为模板参数.

代码:

#include <iostream>

template<int i>
void print(){
     print<i-1>();
     std::cout<<i<<std::endl;
}

//递归,终止递归
template<>
void print<1>(){
    std::cout<<1<<std::endl;
}

int main(){
    print<100>();
}