1.Vector模板实现
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class T>
class Vector
{
public:
Vector()
:_start(NULL)
,_finish(NULL)
,_endofstorage(NULL)
{}
Vector(const Vector<T>& v)
{
if(v.Size()>0)
{
_start=new T[v.Size()];
memcpy(_start,v._start,sizeof(T)*v.Size());
_finish=_start+v.Size();
_endofstorage=_start+v.Capacity();
}
else
{
_start=_finish=_endofstorage=NULL;
}
}
Vector<T>& operator=(const Vector<T>& v)
{
size_t size=v.Size();
delete [] _start;
T* tmp=new T[size];
for(size_t i=0; i<size; ++i)
{
tmp[i]=v._start[i];
}
_start=tmp;
_finish=_start+size;
_endofstorage=_start+v.Capacity();
return *this;
}
~Vector()
{
delete[] _start;
_start=_finish=_endofstorage=NULL;
}
void Insert(size_t pos,const T& x)
{
assert(pos<=Size());
if(_finish==_endofstorage)
{
Expand(Capacity()*2);
}
T* end=_finish;
while(end>=_start+pos)
{
*(end+1)=*end;
--end;
}
_start[pos]=x;
++_finish;
}
void Expand(size_t n)
{
if(Empty())
{
_start=new T[3];
_finish=_start;
_endofstorage=_start+3;
}
else if(n>Capacity())
{
size_t size=Size();
T* tmp=new T[n];
//类型萃取
for(size_t i=0; i<size; ++i)
{
tmp[i]=_start[i];//调用string的赋值运算符
}
_start=tmp;
_finish=_start+size;
_endofstorage=_start+n;
}
}
void PushBack(const T& x)
{
Insert(Size(),x);
}
void Erase(size_t pos)
{
assert(pos<Size());
T* cur=_start+pos+1;
while(cur!=_finish)
{
*(cur-1)=*cur;
++cur;
}
--_finish;
}
void PopBack()
{
Erase(Size()-1);
}
void PopFront()
{
Erase(0);
}
bool Empty()
{
return _start==_finish;
}
size_t Capacity()const
{
return _endofstorage-_start;
}
size_t Size()const
{
return _finish-_start;
}
size_t Find(const T& x)
{
size_t size=Size();
for(size_t i=0; i<size; ++i)
{
if(_start[i]=x)
{
return i;
}
}
return -1;
}
void Print()
{
for(size_t i=0; i<Size(); ++i)
{
cout<<_start[i]<<" ";
}
cout<<endl;
}
T& Back()
{
return *(_finish-1);
}
T& Front()
{
return *_start;
}
size_t operator[](size_t index)
{
return _start[index];
}
private:
T* _start;
T* _finish;
T* _endofstorage;
};
void TestVector()
{
Vector<int> v1;
v1.PushBack(1);
v1.PushBack(2);
v1.PushBack(3);
v1.PushBack(4);
Vector<int> v2(v1);
//Vector<int> v2;
//v2=v1;
v1.Print();
v2.Print();
}
2.List模板实现
#pragma once
#include<iostream>
#include<assert.h>
#include<string>
#include<stddef.h>
using namespace std;
template<class T>
struct ListNode{
ListNode<T>* _next;
ListNode<T>*_prev;
T _data;
ListNode(const T& x)
:_data(x)
,_next(NULL)
,_prev(NULL)
{}
};
template<class T>
class List{
typedef ListNode<T> Node;
public:
List()
:_head(new Node(T()))
{
_head->_next=_head;
_head->_prev=_head;
}
List(const List<T>&l)
{
_head=new Node(T());
_head->_next=_head;
_head->_prev=_head;
Node* cur=l._head->_next;
while(cur!=l._head)
{
PushBack(cur->_data);
cur=cur->_next;
}
}
List<T>& operator=( List<T>& l)
{
swap(l._head,_head);
return *this;
}
~List()
{
Clear();
delete _head;
_head=NULL;
}
void Clear()
{
Node* cur=_head->_next;
while(cur!=_head)
{
Node* next=cur->_next;
delete cur;
cur=next;
}
}
void PushBack(const T& x)
{
Insert(_head,x);
}
void PopBack()
{
Erase(_head->_prev);
}
void PushFront(const T& x)
{
Insert(_head->_next,x);
}
void PopFront()
{
Erase(_head->_next);
}
void Insert(Node* pos,const T& x)
{
assert(pos);
Node* prev=pos->_prev;
Node* new_node=new Node(x);
new_node->_next=pos;
pos->_prev=new_node;
prev->_next=new_node;
new_node->_prev=prev;
}
void Erase(Node* pos)
{
assert(pos);
Node* prev=pos->_prev;
Node* next=pos->_next;
delete pos;
prev->_next=next;
next->_prev=prev;
}
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()
{
Node* cur=_head->_next;
size_t count=0;
while(cur!=_head)
{
cur=cur->_next;
++count;
}
return count;
}
void Print()
{
Node* cur=_head->_next;
while(cur!=_head)
{
cout<<cur->_data<<" ";
cur=cur->_next;
}
cout<<endl;
}
void Swap(List<T>& l)
{
swap(_head,l._head);
}
T& Back()
{
return _head->_prev->_data;
}
T& Front()
{
return _head->_next->_data;
}
bool Empty()
{
return _head->_next==_head;
}
protected:
Node* _head;
};
void TestList()
{
List<int> L1;
L1.PushBack(1);
L1.PushBack(2);
L1.PushBack(3);
L1.PushBack(4);
L1.PushBack(5);
//L1.PopBack();
//List<int> L2(L1);
List<int> L2;
L2=L1;
//L2=L1;
/*List<string> L2;
L2.PushBack("hello");
L2.PushBack("world");
L2.PushBack("hello");
L2.PushBack("linux");*/
L1.Print();
L2.Print();
}
3.基于Vector和List实现的Stack(适配器)
//适配器模式
//模板的模板参数
#pragma once
#include "Vector.h"
#include "List.h"
template<class T,class Container>
class stack
{
public:
void Push(const T& x)
{
_con.PushBack(x);
}
void Pop()
{
_con.PopBack();
}
const T& Top()
{
return _con.Back();
}
bool Empty()
{
return _con.Empty();
}
size_t size()
{
return _con.Size();
}
private:
Container _con;
};
void TestStack()
{
//stack<int,Vector<int> > s1;
stack<int,List<int> > s1;
s1.Push(1);
s1.Push(2);
s1.Push(3);
s1.Push(4);
while(!s1.Empty())
{
cout<<s1.Top()<<" ";
s1.Pop();
}
cout<<endl;
}
4.基于Vector和List实现的Queue
#pragma once
#include "List.h"
#include "Vector.h"
template<class T,class container>
//template<class T,template<class>class container>//防止参数类型不一致
class Queue
{
public:
void Push(const T& x)
{
_con.PushBack(x);
}
void Pop()
{
_con.PopFront();
}
T& Front()
{
return _con.Front();
}
size_t Size()
{
return _con.Size();
}
bool Empty()
{
return _con.Empty();
}
protected:
container _con;
//container<T> _con;
};
void TestQueue()
{
Queue<int,List<int> > q1;
//Queue<int,Vector<int> > q1;
q1.Push(1);
q1.Push(2);
q1.Push(3);
q1.Push(4);
while(!q1.Empty())
{
cout<<q1.Front()<<" ";
q1.Pop();
}
cout<<endl;
}
//main.c
#include "List.h"
#include "Vector.h"
#include "stack.h"
#include "Queue.h"
int main()
{
//TestVector();
//TestList();
TestStack();
//TestQueue();
system("pause");
return 0;
}