[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__

这样我们的顺序表和链表就可以实现任意类型的程序了。