C++模板的实现（模板函数和模板类，附带模板实现顺序表和链表代码）

 当我们实现一个交换函数时，我们可以写成如下。

void Swap(int& x, int& y)
{
    int tmp = x;
    x = y;
    y = tmp;
}

 这里只能交换两个整数，当我们一会需要实现两个字符交换时用模板实现链表，我们有需要重新写个函数，然而两份代码有很多相同的部分，这样是不是很麻烦。假如我们只需要写一份代码便可以实现不同类型的交换，是不是很棒。是的用模板实现链表，这个编译器已经帮我们设计好了，这就是所谓的泛型编程。

 模板是泛型编程的基础，所谓泛型编程就是编写与类型无关的逻辑代码，是一种复用的方式。模板分为模板函数和模板类。

template<class 形参名1, class 形参名2, class 形参名n>

返回类型 函数名(参数列表)

{…}

模板形参的定义既可以使用class，也可以使用typename，含义是相同的。

刚刚的Swap函数就可以用模板函数搞定了。

template<class T>
void Swap(T& x, T& y)
{
    T tmp = x;
    x = y;
    y = tmp;
}

看看是不是可以进行多种类型交换，测试结果：

这就是模板函数的实现，当然我们很好奇为什么一个函数就可以搞定。其实在底层实现了函数重载，我们转到汇编代码便可得知。

int main()
{
00394D30  push        ebp  
00394D31  mov         ebp,esp  
00394D33  sub         esp,114h  
00394D39  push        ebx  
00394D3A  push        esi  
00394D3B  push        edi  
00394D3C  lea         edi,[ebp-114h]  
00394D42  mov         ecx,45h  
00394D47  mov         eax,0CCCCCCCCh  
00394D4C  rep stos    dword ptr es:[edi]  
00394D4E  mov         eax,dword ptr [__security_cookie (039A000h)]  
00394D53  xor         eax,ebp  
00394D55  mov         dword ptr [ebp-4],eax  
    int a1 = 1, a2 = 2;
00394D58  mov         dword ptr [a1],1  
00394D5F  mov         dword ptr [a2],2  
    Swap(a1, a2);
00394D66  lea         eax,[a2]  
00394D69  push        eax  
00394D6A  lea         ecx,[a1]  
00394D6D  push        ecx  
00394D6E  call        Swap<int> (039137Ah)  
00394D73  add         esp,8  
    char c1 = 5, c2 = 6;
00394D76  mov         byte ptr [c1],5  
00394D7A  mov         byte ptr [c2],6  
    Swap(c1, c2);
00394D7E  lea         eax,[c2]  
00394D81  push        eax  
00394D82  lea         ecx,[c1]  
00394D85  push        ecx  
00394D86  call        Swap<char> (0391375h)  
00394D8B  add         esp,8  
    double d1 = 1.222, d2 = 2.011111111111;
00394D8E  movsd       xmm0,mmword ptr [__real@3ff38d4fdf3b645a (0397BD0h)]  
00394D96  movsd       mmword ptr [d1],xmm0  
00394D9B  movsd       xmm0,mmword ptr [__real@400016c16c16c072 (0397BD8h)]  
00394DA3  movsd       mmword ptr [d2],xmm0  
    Swap(d1, d2);
00394DA8  lea         eax,[d2]  
00394DAB  push        eax  
00394DAC  lea         ecx,[d1]  
00394DAF  push        ecx  
00394DB0  call        Swap<double> (039137Fh)  
00394DB5  add         esp,8  
    return 0;
00394DB8  xor         eax,eax  
}

 可以看到在底层，每一次调用Swap函数都会建立一个栈帧，而每次栈帧建立，形参的类型是不同的，建立栈帧也是不同的。当我们使用模板时编译器会进行一个推演的过程，这个过程在编译之前进行。推演时，编译器会根据传递参数的类型实例化（编译器隐式实例化）

出相应的函数，在进行编译。例如：

 但是当我们遇到这样Swap(1,1.2302102);,此时编译器如何判断到底实例化成那种类型？

其实我们如果把模板声明为这样既可以解决了。模板函数重载（与上面的函数构成重载）

template<typename T1 ,class T2> //使用class 和 typename一样的效果
void Swap(T1& x,T2& y)
{
    T1 tmp = x;
    x = y;
    y = tmp;
}

有时候我们可能会要到这样的奇葩问题。

template< class T>
const T Add(T& x,T& y)
{
    return x+y;
}

当我们这样调用时Add(1,5.222222);,编译器又该如何实例化呢？

这就涉及必须显示指定实例化类型 模板参数显示实例化

Add<double> (1.5.2222222); 这样就可以搞定刚刚的问题。

template<class 形参名1, class 形参名2, ...class 形参名n>
class 类名
{ ... };

当我们刚开始用c++写顺序表和链表之前，我们是这样的。

typedef int Datatype;
typedef struct SeqList
{
    struct SeqList* _data;
    size_t _size;
}SeqList;
typedef struct ListNode
{
    struct ListNode* _prev;
    struct ListNode* _next;
    Datatype _data;
}ListNode;

我们这样定义顺序表和链表的，但是会存在很大一个问题，如下。

当我们在一个程序中要使用两个不同数据类型顺序表和链表，这样是无法完成的，除非我们每种类型定义一个类型

```
typedef int Datatype; //存int类型
typedef struct SeqList
{
    struct SeqList* _data;
    size_t _size;
}SeqList;
typedef struct ListNode
{
    struct ListNode* _prev;
    struct ListNode* _next;
    Datatype _data;
}ListNode;

```
typedef char Datatype; //存char类型
typedef struct SeqList
{
    struct SeqList* _data;
    size_t _size;
}SeqList;
typedef struct ListNode
{
    struct ListNode* _prev;
    struct ListNode* _next;
    Datatype _data;
}ListNode;

这样就会很麻烦，在我们学了模板之后，我们可以这样。

模板实现顺序表

template<class T>
class Vector
{
public:
    Vector():_first(NULL),_finish(NULL),_endofstorge(NULL)//构造函数
    {}
    ~Vector()//析构函数
    {
        delete[]_first;
        _first = _finish = _endofstorge = NULL;
    }
    Vector(const Vector<T>& v)//拷贝构造
        :_first(NULL)
        ,_finish(NULL)
        ,_endofstorge(NULL)
    {
        int len = v._finish - v._first;
        _first = _finish = new T[len];
        T* start = v._first;
        while(start != v._finish)
        {
            *(_finish) = *start;
            ++_finish;
            ++start;
        }
        _endofstorge = _first+len;
    }
    Vector<T>& operator=(Vector<T>& v) //赋值运算符重载
    {
        delete[]_first;
        Vector<T> v1(v);
        swap(_first ,v1._first);
        swap(_finish , v1._finish);
        swap(_endofstorge , v1._endofstorge);
        return *this;
    }
    void PushBack(const T& x) //尾插
    {
        if(_finish == _endofstorge)
            Expand(Capacity()*2+1);
        _first[Size()] = x;
        ++_finish;
    }
    void PopBack()//尾删
    {
        Erase(Size()-1);
    }
    void Expand(size_t n) //扩容
    {
        int size = Size();
        if(n>Capacity())
        {
            T* tmp = new T[n];
            for (int i = 0;i<size;i++)
            {
                *(tmp+i) = *(_first+i);
            }
            delete[]_first;
            _first = tmp;
            _finish = _first + size;
            _endofstorge = _first + n;
        }
    }
    void Insert(size_t pos,const T& x)//随机插入
    {
        assert(_first+pos <= _finish);
        if(_finish == _endofstorge)
            Expand(2*Capacity());
        T* end = _finish;
        while(end != _first + pos)
        {
            *(end) = *(end-1);
            --end;
        }
        _first[pos] = x;
        ++_finish;
    }
    void Erase(size_t pos)//删除任意位置的数据
    {
        assert(_first+pos < _finish);
        int size = Size();
        T* start = _first + pos + 1;
        while(start != _finish)
        {
            *(start - 1) = *(start);
            ++start;
        }
        --_finish;
    }
    size_t Find(const T& x)//查找
    {
        int size = Size();
        for(int i = 0;i<size;i++)
        {
            if (_first[i] == x)
                return i;
        }
        return -1;
    }
    T& operator[](size_t pos)//获取任意位置的数据
    {
        assert(pos<Size());
        return _first[pos];
    }
    const T& operator[](size_t pos) const
    {
        assert(_first+pos < _finish);
        return _first[pos];
    }
    size_t Size() //求取顺序表的有效容量
    {
        return _finish - _first;
    }
    size_t Capacity()//求取顺序表的容量
    {
        return _endofstorge - _first;
    }
    bool Empty() //判断是否为空顺序表
    {
         return Size()==0;
    }
protected:
    T* _first;
    T* _finish;
    T* _endofstorge;
};

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-112103-1.html