C++模板的知識實現順序表
模板：是泛型編程的基礎
泛型編程：編寫與類型無關的邏輯代碼
說白了模板其實就是一個模具，它是在使用傳類型時才存在一個推演的過程，簡單的一個模板類的推演過程如下：
用模板的方式實現順序表：
#pragma once
#include
#include
using namespace std;
template
class SeqList
{
template
friend ostream& operator<<(ostream& os,SeqList& d);
public:
SeqList();
SeqList(const SeqList& seq);
SeqList &operator=(SeqList seq);
T& operator[](const T& index);
~SeqList();
public:
void PushBack(const T& t);
void PopBack();
void PushFront(const T& t);
void PopFront();
int FindNum(const T& x);
void Insert(int pos,const T& x);
void Remove(const T& x);
void RemoveAll(const T& x);
void Sort();
void Display();
public:
void Reserve(size_t len);
size_t Size()
{
return _size;
}
T *_data;
private:
void CheckCapacity(int count);
void Copy(T *dest,T *src,int sz);
size_t GetCapacity()
{
return _capacity;
}
private:
int _size;
int _capacity;
};
template
ostream& operator<<(ostream& os,SeqList& d)
{
for(int i=0;i
SeqList::SeqList()
:_size(0)
,_capacity(3)
,_data(0)
{
_data=new T[_capacity];
}
template
SeqList::SeqList(const SeqList& seq)
{
T *tmp=new T[seq._capacity];
for(int i=0;i
SeqList &SeqList::operator=(SeqList seq)
{
std::swap(seq._data,_data);
std::swap(seq._size,_size);
std::swap(seq._capacity,_capacity);
return *this;
}
template
T& SeqList::operator[](const T& index)
{
return _data[index];
}
template
SeqList::~SeqList()
{
if(_data != NULL)
{
delete[]_data;
_data=0;
_size=0;
_capacity=0;
}
}
template
void SeqList::Display()
{
for(int i=0;i<_size;i++)
{
cout<<_data[i]<<" ";
}
cout<
void SeqList::Reserve(size_t len)
{
if(GetCapacity() <= len)
{
CheckCapacity(len);
}
else
{
return ;
}
}
template
void SeqList::Copy(T *dest,T *src,int sz)
{
if(TypeTraits::_IsPodType().Get())
{
for(int i=0;i
void SeqList::CheckCapacity(int count)
{
//cout<(_capacity+count)?(2*_capacity):(_capacity+count);
T *tmp=new T[NewCapacity];
Copy(tmp,_data,_size);
delete[]_data;
_data=tmp;
_capacity=NewCapacity;
}
}
template
void SeqList::PushBack(const T& t)
{
CheckCapacity(1);
_data[_size]=t;
_size++;
}
template
void SeqList::PopBack()
{
if(_data != 0)
{
_size--;
}
}
template
void SeqList::PushFront(const T& t)
{
CheckCapacity(1);
for(int i=_size-1;i>=0;i--)
{
_data[i+1]=_data[i];
}
_data[0]=t;
_size++;
}
template
void SeqList::PopFront()
{
for(int i=0;i<_size;i++)
{
_data[i]=_data[i+1];
}
_size--;
}
template
int SeqList::FindNum(const T& x)
{
for(int i=0;i<_size;i++)
{
if(_data[i] == x)
return i;
}
return -1;
}
template
void SeqList::Insert(int pos,const T& x) //在指定位置的前面插入元素
{
CheckCapacity(1);
for(int i=_size-1;i>=pos;i--)
{
_data[i+1]=_data[i];
}
_data[pos]=x;
_size++;
}
template
void SeqList::Remove(const T& x) //刪除指定元素
{
int ret=FindNum(x);
if(ret != -1)
{
for(int i=ret;i<_size-1;i++)
{
_data[i]=_data[i+1];
}
_size--;
}
else
{
return ;
}
}
template
void SeqList::RemoveAll(const T& x) //刪除所有指定元素
{
while(_size != 0)
{
int ret=FindNum(x);
if(ret != -1)
{
for(int i=ret;i<_size-1;i++)
{
_data[i]=_data[i+1];
}
_size--;
}
else
{
break;
}
}
}
template
void SeqList::Sort()
{
int flag=1;
int m=0;
int k=0;
for(int i=0;i<_size-1;i++)
{
for(int j=0;j<=k;j++)
{
if(_data[i] > _data[i+1])
{
T tmp=_data[i];
_data[i]=_data[i+1];
_data[i+1]=tmp;
flag=0;
m=j; //m用來記錄上一次交換完成的位置
}
k=m;
}
if(flag == 1)
break;
}
}
模板的模板參數-容器適配器
我們知道棧是先進後出的一種數據結構，而如果我們要模擬實現棧的這種數據結構我們發現順序表是最好的選擇，因為效率高，棧的插入和刪除正好對應的是順序表的尾插和尾刪
//模板參數
//template
//模板的模板參數
templateclass Container=SeqList>
class Stack
{
public:
void Push(const T& d)
{
_con.PushBack(d);
}
void Pop()
{
_con.PopBack();
}
bool Empty()
{
return _con.Size() == 0;
}
T& Top()
{
int sz=_con.Size();
return _con._data[--sz];
}
void Display()
{
while(!Empty())
{
cout<
測試代碼：
void test5()
{
Stack s;
s.Push(1);
s.Push(2);
s.Push(3);
s.Push(4);
s.Push(5);
s.Display();
}
類型萃取的實例應用一：SeqList
類型萃取其實就是區分內置類型和自定義類型
#define _CRT_SECURE_NO_WARNINGS 1
struct _TrueType
{
int Get()
{
return 1;
}
};
struct _FalseType
{
int Get()
{
return -1;
}
};
template //自定義類型
struct TypeTraits
{
typedef _FalseType _IsPodType;
};
template<> //內置類型
struct TypeTraits
{
typedef _TrueType _IsPodType;
};
template<>
struct TypeTraits
{
typedef _TrueType _IsPodType;
};
template<>
struct TypeTraits
{
typedef _TrueType _IsPodType;
};
template
void Copy(T *dest,T *src,int sz,_TrueType)
{
memcpy(dest,src,sz*sizeof(T));
}
template
void Copy(T *dest,T *src,int sz,_FalseType)
{
for(int i=0;i
void Copy(T *dest,T *src,int sz)
{
if(TypeTraits::_IsPodType().Get())
{
for(int i=0;i
測試代碼：
void testTypeTraits()
{
string s1[10]={"abcd","bcde","defg","bbbxxxxxxxxxxxxxxxxxxxxx"};
string s2[10]={"12","23","34","45"};
Copy(s1,s2,10,TypeTraits ::_IsPodType());
Copy(s1,s2,10);
int a1[10]={1,2,3};
int a2[10]={0};
Copy(a1,a2,10,TypeTraits ::_IsPodType());
Copy(a1,a2,10);
}
C++模板的知識實現鏈表：
C++實現鏈表：
http://blog.csdn.net/qq_34328833/article/details/52290441
#pragma once
#include
#include
using namespace std;
template
struct Node
{
template
friend ostream& operator<<(ostream& os,Node& n)
{
os<* _next;
Node* _front;
};
template
class LinkList
{
template
friend ostream& operator<<(ostream& os,LinkList& list);
public:
LinkList()
:_head(0)
,_tail(0)
{}
LinkList(const LinkList& list);
LinkList& operator=(LinkList list);
~LinkList();
public:
void PushBack(const T& d);
void PopBack();
void PushFront(const T& d);
void PopFront();
Node *FindNum(const T& x);
void Insert(Node *pos,const T& x);
void Insert(int,Node *pos,const T& x);
void Remove(const T& x);
void RemoveAll(const T& x);
void Sort();
void Display()
{
Node* cur=_head;
while(cur)
{
cout<_data<<" ";
cur=cur->_next;
}
cout<* GetFront()
{
return _head;
}
Node* GetTail()
{
return _tail;
}
size_t Size();
private:
Node *_head;
Node *_tail;
};
template
ostream& operator<<(ostream &os,LinkList &list)
{
Node *cur=list._head;
while(cur)
{
os<<(*cur)<<" ";
cur=cur->_next;
}
return os;
}
template
LinkList::LinkList(const LinkList& list)
:_head(0)
,_tail(0)
{
Node* cur=list._head;
while(cur)
{
PushBack(cur->_data);
cur=cur->_next;
}
}
template
LinkList& LinkList::operator=(LinkList list)
{
std::swap(list._head,_head);
std::swap(list._tail,_tail);
return *this;
}
template
LinkList::~LinkList()
{
Node* cur=_head;
while(cur != 0)
{
Node* del=cur;
cur=cur->_next;
delete del;
del=NULL;
}
_head=NULL;
_tail=NULL;
}
template
void LinkList::PushBack(const T& d)
{
Node *NewNode=new Node(d);
if(_head == NULL)
{
_head=NewNode;
_tail=NewNode;
}
else
{
_tail->_next=NewNode;
NewNode->_front=_tail;
_tail=NewNode;
}
}
template
void LinkList::PopBack()
{
if(!_head) //空鏈表
{
return ;
}
else if(!_head->_next) //只有一個節點
{
delete _tail;
_head=NULL;
_tail=NULL;
}
else //至少存在兩個節點
{
_tail=_tail->_front;
delete _tail->_next;
_tail->_next=0;
}
}
template
void LinkList::PushFront(const T& d)
{
Node *NewNode=new Node(d);
if(_head)
{
Node *tmp=_head;
NewNode->_next=tmp;
tmp->_front=NewNode;
}
else //空鏈表
{
_tail=NewNode;
}
_head=NewNode; //更新頭
}
template
void LinkList::PopFront()
{
if(!_head) //空鏈表
{
return ;
}
else if(!_head->_next) //只有一個結點
{
delete _head;
_head=NULL;
_tail=NULL;
}
else //至少存在兩個結點
{
_head=_head->_next;
delete _head->_front;
_head->_front=NULL;
}
}
template
Node *LinkList::FindNum(const T& x)
{
Node *cur=_head;
while(cur)
{
if(cur->_data == x)
return cur;
cur=cur->_next;
}
return NULL;
}
template
void LinkList::Insert(Node *pos,const T& x) //在指定位置後插
{
Node *NewNode=new Node(x);
if(pos->_next)
{
NewNode->_front=pos;
NewNode->_next=pos->_next;
pos->_next->_front=NewNode;
pos->_next=NewNode;
}
else //在最後一個結點後插，類似PushBack
{
pos->_next=NewNode;
NewNode->_front=pos;
_tail=NewNode; //更新尾
}
}
template
void LinkList::Insert(int,Node *pos,const T& x) //在指定位置前插
{
Node *NewNode=new Node(x);
if(pos->_front)
{
NewNode->_next=pos;
pos->_front->_next=NewNode;
NewNode->_front=pos->_front;
pos->_front=NewNode;
}
else //在第一個結點的前插，類似PushFront
{
NewNode->_next=pos;
pos->_front=NewNode;
_head=NewNode; //更新頭
}
}
template
void LinkList::Remove(const T& x)
{
Node *pos=this->FindNum(x);
if(pos != 0)
{
if((!(pos->_front)) && pos->_next) //刪除第一個結點
{
Node *tmp=pos->_next;
tmp->_front=NULL;
_head=tmp;
}
else if(pos->_front && (!(pos->_next))) //刪除最後一個結點
{
Node *tmp=pos->_front;
tmp->_next=NULL;
_tail=tmp;
}
else //刪除中間節點
{
Node *front=pos->_front;
Node *next=pos->_next;
next->_front=front;
front->_next=next;
}
delete pos;
pos=0;
}
}
template
void LinkList::RemoveAll(const T& x)
{
Node *cur=_head;
Node *ret=this->FindNum(x);
if(ret != _head) //可刪除第一個結點不是要刪除的元素
{
while(cur)
{
Remove(x);
cur=cur->_next;
}
}
}
template
void LinkList::Sort()
{
int flag=1;
Node *cur=_head;
Node *tail=NULL;
while(cur != tail)
{
while(cur->_next != tail)
{
if(cur->_data > cur->_next->_data)
{
T tmp=cur->_data;
cur->_data=cur->_next->_data;
cur->_next->_data=tmp;
flag=0;
}
cur=cur->_next;
}
if(flag == 1)
break;
tail=cur;
cur=_head;
}
}
template
size_t LinkList::Size()
{
Node* cur=_head;
size_t count=0;
while(cur)
{
count++;
cur=cur->_next;
}
return count;
}
模板參數-容器適配器
借用鏈表的某些函數實現隊列這種數據結構，隊列：先進先出，之所以使用鏈表的方式而不使用順序表，因為順序表在插入一個元素時需要大量移動元素而鏈表則不需要，我們發現針對隊列的這種數據結構，它的插入和刪除則正好對應鏈表的尾插和頭刪
//模板參數
template
class Queue
{
public:
void Push(const T& d)
{
_con.PushBack(d);
}
void Pop()
{
_con.PopFront();
}
Node& Front()
{
return *_con.GetFront();
}
Node& Back()
{
return *_con.GetTail();
}
bool Empty()
{
return _con.GetFront() == 0;
}
size_t Size()
{
return _con.Size();
}
void Display()
{
while(!Empty())
{
cout<
