[TOC]
模板
当我们实现一个交换函数时，我们可以写成如下。
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;};
测试代码及结果：
void VectorTest(){Vector<int> v;v.PushBack(1);v.PushBack(2);v.PushBack(3);v.PushBack(4);v.PushBack(5);v.PushBack(6);v.PushBack(7);PrintVocter(v);Vector<string> v1;v1.PushBack("hello");v1.PushBack("world !");v1.PushBack("i");v1.PushBack("love");v1.PushBack("you");PrintVocter(v1);}
模板实现双链表
#ifndef __LIST_H__#define __LIST_H__#include<string>#include<iostream>using namespace std;template <class T>struct ListNode{struct ListNode* _prev;struct ListNode* _next;T _data;};template <class T>class List{typedef ListNode<T> Node;public:List()//构造函数{_head = new Node;_head->_next = _head->_prev = _head;}List(const List<T>& h) //拷贝构造{Node* head = h._head;Node* tmp = head->_next;_head = new Node;_head->_next = _head->_prev = _head;while (tmp != head){PushBack(tmp->_data);tmp = tmp->_next;}}~List() //析构函数{Clear();delete _head;_head = NULL;}void PushBack(const T& x) //尾插{Node *tmp = new Node;tmp->_data = x;Node* tail = _head->_prev;tail->_next = tmp;tmp->_prev = tail;_head->_prev = tmp;tmp->_next = _head;}void PushFront(const T& x) //头插{Node *tmp = new Node;tmp->_data = x;Node* cur = _head->_next;tmp->_prev = _head;_head->_next = tmp;tmp->_next = cur;cur->_prev = tmp;}void PopBack() //尾删{Node* cur = _head->_prev;_head->_prev = cur->_prev;cur->_prev->_next = _head;delete[]cur;cur->_next = cur->_prev = NULL;}void PopFront() //头删{Node* cur = _head->_next;_head->_next = cur->_next;cur->_next->_prev = _head;}void Insert(Node* pos,const T& x) //随机插入{Node* cur = new Node;cur->_data = x;cur->_prev = pos->_prev;pos->_prev->_next = cur;pos->_prev = cur;cur->_next = pos;}void Erase(Node* pos) //删除随机位置{Node* cur = pos->_next;pos->_prev->_next = cur->_next;cur->_next->_prev = pos->_prev;}void Clear() //清除链表数据{Node* cur = _head->_next;while(cur != _head){Node* tmp = cur;cur = cur->_next;delete tmp;}_head->_next = _head;_head->_prev = _head;}Node* Find(const T& x) //查找{Node* cur = _head->_next;while (cur != _head){if(cur->_data==x)return cur;cur = cur->_next;}return NULL;}size_t Size() //求取链表长度{size_t count = 0;Node* cur = _head->_next;while (cur != _head){count++;cur = cur->_next;}return count;}bool Empty(){if (_head->_next = _head->_prev)return 1;return 0;}void PrintList() //打印链表{Node* tmp = _head->_next;while (tmp != _head){std::cout<<tmp->_data<<" ";tmp = tmp->_next;}std::cout<<std::endl;}protected:Node* _head;};#endif//__LIST_H__
这样我们的顺序表和链表就可以实现任意类型的程序了。
