模板

在我们编写代码时，我们会遇见这种情况：
比如交换函数，当我们要交换的类型是int（传的参数为int型）时，我们要编写的swap函数的形参就应该是int，但当我们要交换的是double型时，我们还要再写一个swap函数来满足要求。每换一种类型就要再重载一个swap函数来满足条件。
虽然通过这方法重载实现所有类型的交换函数，但是这种方法有几个不好的地方，一是重载函数仅仅类型不同，导致代码的复用率很低，只要有新类型出现，就要增加对应的函数；再者代码的可维护性比较低，一个出错可能所有的重载都出错，要一个一个改。

通过上面的例子，我们想能不能告诉编译器一个模子，编译器可以通过不同的类型利用这样的模子自动生成适合各种类型的函数。答案是当然可以
即泛型编程：编写与类型无关的通用代码，而模板是泛型编程的基础。

下面我们来郑重的引入模板

模板分为函数模板和类模板

函数模板：

• 什么是函数模板？
  函数模板是一个与类型无关，并且对所有类型都适用的函数，在使用时函数可被参数化，根据实参类型结合模板产生函数的特定类型版本实现函数功能。

• 如何使用？
  template <typename T1,typename T2...>
  返回值 函数名（参数列表）{ }
  typename是用来定义模板参数关键字的，也可以用class
  例如：

  template<typename T>   
  void Swap(T &x, T &y)      
  //之前不同的类型，对应不同的形参列表，所以要写多个重载函数，但现在只写一个模板函数，编译器就可以根据这个模板结合传入的参数就可完成所有类型的生成对应类型的函数以供调用
  
  T tmp = x;
  x = y;
  y = tmp;
  }
  //在这个函数中，T只能被替换为一样的类型，若传入参数不同，则编译器其则生成不了匹配的函数，而编译器又不会进行类型转换，因而会报错
  //若想要不同类型，可定义两个T
  template<class T1, class T2>       //typename可用class代替
  void Swap(T1 &x, T2 &y)     
  {
  T1 tmp = x;
  x = y;
  y = tmp;
  }
  int main()
  {
  int x1=0, y1=1;
  double x2 = 1.0, y2 = 2.0;
  Swap(x1, y1);
  Swap(x2, y2);
  Swap(x1, y2);
  }

• 函数模板原理
  其实模板本身并不是函数，而是编译器用使用方式产生特定具体类型函数的模具。所以其实模板就是将本来应该我们做的重复的事情交给了编译器。在编译器编译阶段，编译器会根据传入的实参类型来推演生成对应类型的函数以供调用。比如：当用double类型使用函数模板时，编译器通过对实参类型的推演，将T确定为double类型，然后产生一份专门处理double类型的代码，对于字符类型也是如此。

• 函数模板实例化
  编译器根据不同的参数用模板推演不同的函数称为函数模板的实例化，模板参数实例化分为：隐式实例化和显示实例化。
  通过下面例子介绍隐式实例化和显示实例化

  template<typename T>
  T Add(const T &x, const T &y)
  {
  return x + y;
  }
  int main()
  {
  int x1=0, y1=1;
  double x2 = 1.0, y2 = 2.0;
  //隐式实例化，让编译器根据实参推演模板参数的实际类型
  Add(x1, y1);     //隐式实例化
  
  //当无法确定T是什么，由该推演成什么的时候，会报错，因而要不然进行强转使传入参数类型相同，要不然进行显式实例化
  Add(x1, (int)y2); //强转
  
  //显式实例化，直接告诉编译器，由模板该推演成什么，在函数名后的<>中指定模板参数的实际类型
  Add<int>(x1, (int)y2);   
  }

• 模板参数匹配原则

1.一个非模板函数可以和一个同名的函数模板同时存在，而且该函数模板还可以被实例化为这个非模板函数。
2.模板函数不允许自动类型转换，但普通函数可以进行自动类型转换。
3.对于非模板函数和同名函数模板，如果其他条件都相同，在调动时会优先调用非模板函数而不会从该模板产生出一个实例。如果模板可以产生一个具有更好匹配的函数，那么将选择模板。

int Add(int x, int y)
{
    return x + y;
}
template<typename T>
T Add(const T &x, const T &y)
{
    return x + y;
}
template<typename T1, typename T2>
T1 Add(const T1 &x, const T2 &y)
{
    return x + y;
}

int main()
{
//1
    Add(1, 2);    //调用非模板函数，无需模板实例化
    Add<int>(1, 2);//调用编译器特化的模板函数版本   --如果指定类型就必须用模板来生成相应类型
    //2.
    Add(1, 2.0);      //此处会调用非模板函数，发生隐式类型转换   （说明:此处还未加Add(const T1 &x, const T2 &y)函数模板）
    //3.
    Add(1, 2.0);        //选择函数模板若选择非模板函数，则会发生隐式类型转化，
                        //不如调用Add(const T1 &x, const T2 &y)这个实例化的函数形参列表更匹配

}

类模板

• 使用格式：
  template <class T1,class T2....>
  class A( /A为类模板名,A不是具体的类，是编译器根据被实例化的类型生成具体类的模具)
  {
  ...
  }；

• 类模板实例化

类模板实例化需要在类模板名字后跟<>，然后将实例化的类型放在<>中即可，类模板名字不是真正的类，而实例化的结果才是真正的类。
例如容器vector的实现：

template <class T>
class vector{
    typedef T* iterator;
    public:
        //构造析构
        vector()
            : _start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
        }
        vector(int n, const T &value = 0)
            :_start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            _start = new T[n+1];
            int i = n;
            while (i--)
            {
                _start[i] = value;
            }
            _start[n] = '\0';
            _finish = _start + n;
            _endOfStorage = _finish;
        }
        template <class InputIterator>
        vector(InputIterator first, InputIterator last)    
            :_start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            int n=0;
            auto tmp = first;
            while (tmp != last)                
            {
                n++;
                tmp++;
            }
            _start = new T[n + 1];
            _finish = _start + n;
            _endOfStorage = _finish;

            last--;
            while (n--)
            {
                _start[n] = *last;
                last--;
            }
        }
        vector(const vector<T>& v)
            :_start(nullptr)
            , _finish (nullptr)
            ,_endOfStorage(nullptr)
        {
            reserve(v.capacity());
            //memcpy(_start, v._start,v.size());
            for (int i = 0; i < v.size(); i++)
            {
                _start[i] = v._start[i];
            }
            _finish = _start + v.size();
            _endOfStorage = _start + v.capacity();
        }
        ~vector()
        {
            delete[] _start;
            _start = nullptr;
            _finish = nullptr;
            _endOfStorage = nullptr;
        }
        iterator begin()
        {
            return _start;
        }
        iterator end()
        {
            return _finish;
        }

        int size()const
        {   
            return _finish - _start;
        }
        int capacity()const
        {
            return  _endOfStorage - _start;
        }

friend iterator find(iterator begin, iterator end, const T &value);
    private:
        T *_start;
        T *_finish;
        T *_endOfStorage;

    };
// 注意：类模板中函数放在类外进行定义时，需要加模板参数列表
    template <class T>
    T* find(T* begin, T* end, const T &value)
    {
        auto it = begin;
        while (it != end)
        {
            if (*it == value)
            {
                return it;
            }
            it++;
        }
        return nullptr;
    }
int main(){
vector<int> v1;   //实例化
}

模板的其他知识说明：

模板参数

模板参数分为类型形参与非类型形参
类型形参：出现在模板参数列表中，跟在class或者typename之类的参数类型名称。
非类型形参，就是用一个常量作为类(函数)模板的一个参数，在类(函数)模板中可将该参数当成常量来使用。

例如：
namespace Eg
{
    template <class T,size_t N=10>     //N在下面类中，作为常数使用
    class array{
    public:
        size_t size()const
        {
            //N = 20;      //会报错：错误 1   error C2106: “=”: 左操作数必须为左值,可证明N是常数
            return _size;
        }
    private:
        T _array[N];
        size_t _size;
    };
}
void Test1(){
    Eg::array<int> x;     
    x.size();
}

• 注：
  1.浮点数、类对象以及字符串是不允许作为非类型模板参数
  Eg::array<int, 2.0> x3; //这样创建对象会报错
  2.非类型模板参数要在编译期就能确认结果，比如1+2可以在编译时确认，而变量a+变量b不可以确认因而会报错
  Eg::array<int, 2+1> x2; //√
  //int a = 1, b = 2;
  //Eg::array<int, a+b> x3; //×

模板特化

对于一些特殊的类型（比如指针类型），使用已写的模板可能达不到我们想要的结果，得出错误的结果。
例如：

template <class T>
T& MAX_T(T& left, T& right)
{
    return left>right?left:right;
}
void Test(){
    int x = 2,y=3;
    cout << MAX_T(x, y) << endl;  
    char *p1 = "wello";
    char *p2 = "hello";
    cout << MAX_T(p1, p2) << endl;   //应该输出wello  但因为比较的是地址却输出hello不符合逻辑，因此我们要为char*来特化一个模板提供给这种类型
}

通过上述列子我们可以通过对模板进行特化，在原来模板函数（或类）的基础上，针对特殊类型进行特殊化的实现。比如上述例子中为char*特化一个函数，按照我们的想法针对这种类型进行特殊化处理，得到正确的结果。

模板特化又分为函数模板特化与类模板特化

函数模板特化

函数模板的特化方式：
1.要先有一个基础函数模板
2.关键字template后面接一堆空的尖括号<>
3.函数名后跟一对尖括号里面放需要特化的类型
4.函数形参表必须要和模板函数的基础参数类型完全相同，不同的话编译器可能会报一些错误

//比如针对上述char*类型特化：
template <class T>
T& MAX_T(T& left, T& right)
{
    return left>right?left:right;
}
template <>
char*& MAX_T<char*>(char*& left, char*& right)
{
    if (strcmp(left, right) == 1)
    {
        return left;
    }
    else{
        return right;
    }
}
void Test(){
    char *p1 = "wello";      
    char *p2 = "hello";
    cout << MAX_T(p1, p2) << endl;   
    //会调用char*& MAX_T<char*>(char*& left, char*& right)特化模板函数
}

但是！！
对于特例化的函数模板，一般都是将该函数直接给出，一是实现简单，二是因为函数模板可能会遇到不能处理或者处理有误的类型

类模板特化

类模板特化又分为全特化和偏特化

1. 全特化：即将模板参数列表中所有的参数都确定了

template<class T1, class T2>
class Data1
{
public:
    Data1() { cout << "Data<T1, T2>" << endl; }
private:
    T1 _d1;
    T2 _d2;
};

template<>
class Data1<int, int>
{
public:
    Data1()
    {
        cout << "Data1<int, int>" << endl;
    }
private:
    int _d1;
    int _d2;
};

void Test(){
    Data1<int, int> d1;      //用特化模板参数类
    Data1<int, double> d2;
}

2.偏特化：有两种表现：部分特化和参数更进一步的限制

template<class T1, class T2>
class Data2
{
public:
    Data2() { cout << "Data2<T1, T2>" << endl; }
private:
    T1 _d1;
    T2 _d2;
};

• 部分特化：将模板参数列表中部分参数类型化

template<class T1>
class Data2<T1, int>    //特化一半
{
public:
    Data2()
    {
        cout << "Data2<T1, int>" << endl;
    }

private:
    T1 _d1;
    int _d2;
};
void Test(){                     
    Data2<int, int> d1;      //用部分特化模板参数类
    Data2<double, int> d2;   //用部分特化模板参数类     因为后面的都是int，都符合这个部分特化模板
    Data2<int, double> d3;
    Data2<double, double> d4;
    }

• 参数更进一步的限制：让模板参数列表中的类型限制更加严格

template<class T1, class T2>
class Data2<T1*, T2*>
{
public:
    Data2()
    {
        cout << "Data2<T1*, T2*>" << endl;
    }
private:
    T1* _d1;
    T2* _d2;
};
void Test(){                     
    Data2<int*, int> d5;    //使用class Data2<T1, int>
    Data2<int, int*> d6;    //使用template<class T1, class T2> class Data2{}
    Data2<int*, int*> d7;  //使用class Data2<T1*, T2*>
    Data2<int*, double*> d8; //使用class Data2<T1*, T2*>
}

类型萃取

通过以下题目来感受类型萃取

// 写一个通用的拷贝函数，要求：效率尽可能高

/*Way1：
//String：用该函数会报错拷贝的是地址，析构会对同一块空间释放两次，会报错
template<class T>
void Copy(T* dst, T* src, size_t size)
{
memcpy(dst, src, sizeof(T)*size);
}
*/

//因而要区分自定义和内置类型，来调用使用不同的方法进行拷贝
/*
//Way2：增加函数判定 区分自定义和内置类型
bool IsPodType(const char* strType){
    const char* arrType[] = { "char", "short", "int", "long", "long long", "float","double", "long double" };
    for (size_t i = 0; i < sizeof(arrType) / sizeof(arrType[0]); ++i)      //每次都要遍历，效率太低！
    {
        if (0 == strcmp(strType, arrType[i]))
            return true;
    }
    return false;
}

template<class T>
void Copy(T* dst, T* src, size_t size)
{
    if (IsPodType(typeid(T).name()))
    {
        memcpy(dst, src, sizeof(T)*size);
    }
    else{
        for (int i = 0; i < size; i++)
        {
            dst[i] = src[i];
        }
    }
}
*/

//Way3:萃取类型
//代表内置类型
struct TrueType{
    static bool Get(){     //只有静态才能用 ::  访问
        return true;
    }
};
//代表自定义类型
struct FlaseType{
    static bool Get(){
        return false;
    }
};

template<class T>
struct TypeTraits{
    typedef FlaseType IsPodeType;
};

//对上述模板进行实例化，将内置类型都特化
template<>
struct TypeTraits<int>{
    typedef TrueType IsPodeType;
};
template<>
struct TypeTraits<double>{
    typedef TrueType IsPodeType;
};
/*
T为int：TypeTraits<int>已经特化过，程序运行时就会使用已经特化过的TypeTraits<int>, 该类中的IsPODType刚好为类TrueType，而TrueType中Get函数返回true，内置类型使用memcpy方式拷贝
T为string：TypeTraits<string>没有特化过，程序运行时使用TypeTraits类模板, 该类模板中的IsPODType刚好为类FalseType，而FalseType中Get函数返回true，自定义类型使用赋值方式拷贝
*/

template<class T>
void Copy(T* dst, T* src, size_t size)
{
    if (TypeTraits<T>::IsPodeType::Get())
    {
        memcpy(dst, src, sizeof(T)*size);
    }
    else{
        for (int i = 0; i < size; i++)
        {
            dst[i] = src[i];
        }
    }
}

void TestCopy()
{
    int array1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    int array2[10];
    Copy(array2, array1, 10);

    String s1[3] = { "1111", "2222", "3333" };
    String s2[3];            
    Copy(s2, s1, 3);
}

模板分离编译

要说模板分离编译我们就要先来谈谈什么是分离编译

分离编译

一个工程中有很多文件，但他们分为两大类：头文件和源文件
程序的运行有以下五个步骤：
预处理-->编译-->汇编-->链接
头文件会在预处理阶段展开，在预处理期间程序会将头文件中的内容复制一份到源文件。参与编译的只有源文件，而且每个源文件都单独进行编译生成目标文件，最后将所有目标文件链接形成单一的可执行文件。如下图：

目标文件链接的时候，是通过找函数地址（入口）进行调用的。

注意：强调：每个源文件都单独进行编译

模板的分离编译

对于模板：
实例化之前编译器只会做一些简单的语法测验，不会生成处理具体类型的代码
实例化期间编译器用过推演形参类型来确保模板参数，通过列表中T的实际类型在生成处理具体类型的代码

//头文件 CompilingTest.h
template <class T>
T Add(T left,T right);

//源文件 CompilingTest.c
#include "CompilingTest.h"
template <class T>
T Add(T left, T right)
{
    return left + right;
}

//源文件 main.c
#include "CompilingTest.h"
int main()
{
    Add(1.0, 1.0);   //会发生报错，因为没有实例化Add（int，int），找不到匹配的函数入口地址，因而在链接时会报错
    }

//头文件 CompilingTest.h
template <class T>
T Add(T left,T right);

//源文件 CompilingTest.c
#include "CompilingTest.h"
template <class T>
T Add(T left, T right)
{
    return left + right;
}
void tmp(){
    Add(1, 2);         //在此编译器推演出了T->int的函数，在链接时找到了适合Add(1, 1);该函数的入口地址，因而才不会报错
}

//源文件 main.c
#include "CompilingTest.h"
int main()
{
    Add(1, 1);   //这样就不会发生错误了
    //Add(1.0, 1.0);  //无匹配的Add(double,,double)
}

通过上述例子可得模板不支持分离编译

解决方法：

1. 将声明和定义放到一个文件 "xxx.hpp" 里面或者xxx.h其实也是可以的。推荐。
2. 模板定义的位置显式实例化。这种方法不实用，不推荐使用。

分离编译详细讲解： http://blog.csdn.net/pongba/article/details/19130

模板优缺点

优点：

1. 模板复用了代码，节省资源，更快的迭代开发，C++的标准模板库(STL)因此而产生
2. 增强了代码的灵活性
   缺点
3. 模板会导致代码膨胀问题，也会导致编译时间变长
4. 出现模板编译错误时，错误信息非常凌乱，不易定位错误