当前位置: 首页 > >

顺序表---模板类实现

发布时间:

第三种书写方式
1. C语言实现
2. C++实现
3. 类模板实现
接下来我们用类模板来实现STL下的六大组件容器Vector


代码如下:


#pragma once

#include
#include
#include
using namespace std;


template
class Vector
{
public:
typedef T ValueType;
typedef ValueType* Iterator;
typedef size_t SizeType;
typedef ValueType& reference;
typedef const ValueType* ConstIterator;

public:
//构造函数
Vector():_start(0),_finish(0),_endofstorage(0){}

//重载构造函数
Vector(SizeType n,const T& value)
:_start(new T[n*sizeof(T)])
{
for(size_t idx = 0;idx < n; ++idx)
_start[idx] = value;
_finish = _start + n;
_endofstorage = _finish;
}

//拷贝构造函数
Vector(const Vector& v)
{
size_t size = (v._finish - v._start);
size_t capacity = v._endofstorage - v._start;

_start = new T[capacity];
for(size_t idx = 0;idx < size; ++idx)
_start[idx] = v._start[idx];

_finish = _start + size;
_endofstorage = _start+capacity;
/*_finish = v._finish;
_endofstorage = v._endofstorage;*/ //错误:浅拷贝
}

//赋值运算符重载
Vector& operator=(const Vector& v)
{
_finish = v._finish;
CheckCapacity();
Iterator pTemp = new T[v.capacity()];
Iterator pre = pTemp;
if(pTemp != NULL)
/*memcpy(pTemp,v._start,v.size());*/
for(size_t idx = 0;idx < v.size(); ++idx)
pre[idx] = v._start[idx];

if(_start != NULL)
delete[] _start;

_start = pTemp;
_finish = _start+(v._finish-v._start);
_endofstorage = _start+capacity();
return *this;
}

//析构函数
~Vector()
{
if(_start != NULL)
{
delete[] _start;
}
_finish = _start = _endofstorage = NULL;
}

////////////////////////////////////////
Iterator Begin()
{
return _start;
}
ConstIterator Begin() const
{
return _start;
}

Iterator End()
{
return _finish;
}
ConstIterator End() const
{
return _finish;
}

SizeType size()
{
return (End()-Begin());
}
SizeType size() const
{
return (End()-Begin());
}

SizeType capacity()
{
return (_endofstorage - _start);
}
SizeType capacity()const
{
return (_endofstorage - _start);
}

bool Empty()
{
if(size()==0)
return true;
return false;
}

ValueType operator[](const size_t index)
{
return _start[index];
}

reference Front()
{
return *Begin();
}

reference Front()const
{
return *Begin();
}

reference Back()
{
return *(End()-1);
}

reference Back()const
{
return *(End()-1);
}



//////////////////////////////////
void PushBack(const T& value)
{
CheckCapacity();
*_finish = value;
++_finish;
}

void PopBack()
{
if(_start == NULL)
return;
--_finish;
}

Iterator Insert(Iterator pos,const T& value)
{
size_t n = pos-_start;
size_t m =_finish-pos;
CheckCapacity();
Iterator pTemp = End();
for(size_t idx = 0;idx < m;++idx)
{
*pTemp = *(pTemp-1);
--pTemp;
}

*pTemp= value;
++_finish;
return _start+n;//不能直接返回pos的值,因为可能存在扩容,pos的值可能改变
}

Iterator Erase(Iterator pos)
{
Iterator pTemp = pos+1;
while(pTemp != End())
{
*(pTemp-1) = *pTemp;
pTemp++;
}
--_finish;
return pos;
}

void Resize(SizeType newsize,const T& value)
{
if(newsize < size())
_finish =_start + newsize;
else
{
size_t size = newsize-(End()-Begin());
CheckCapacity();
while(size--)
{
*_finish = value;
_finish++;
CheckCapacity();//不能只进行一次扩容的判断,在finish++的过程中随时可能超过容量
}
_finish = _start+newsize;
}
}


void Assign(SizeType n, const T& data)
{
if(n<=size())
{
SizeType size = (_finish-_start)-n;
_finish = _finish - size;

T* pTemp =_start;
while(pTemp!=_finish)
{
*pTemp = data;
pTemp++;
}
}
else
{
T* pRe = _start;

while(pRe!=_finish)
{
*pRe = data;
++pRe;
}
CheckCapacity();
while(_finish!=_start+n)
{
*_finish = data;
_finish++;
CheckCapacity();
}
}
}

private:
void CheckCapacity()
{
if(_finish >= _endofstorage)
{
size_t capacity = 3+(_endofstorage-_start)*2;
Iterator pTemp = new T[capacity];

if(pTemp != NULL)
memcpy(pTemp,_start,sizeof(T)*size());
if(NULL != _start)
delete[] _start;

_finish = pTemp+size();
_start = pTemp;
_endofstorage = _start+capacity;
}
}
private:
Iterator _start ;
Iterator _finish;
Iterator _endofstorage;
};



友情链接: