闲来蛋疼，练练手。
参考标准库的vector实现。与STL源码相比大同小异，主要功能都以实现。
#include<iostream>
#include<algorithm>
#include<memory>
using namespace std;
template<class T>
class Vector{
public:
typedef T value_Type;
typedef value_Type* Pointer;
typedef value_Type* iterator;
typedef value_Type& reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
protected:
iterator start;
iterator finish;
iterator end_of_storage;
void insert_aux(iterator position,const T& x);
void fill_initialize(size_type n, const T& value){
start = allocate_and_fill(n,value);
finish = start + n;
end_of_storage = finish;
}
iterator allocate_and_fill(const size_type n, const T& value){
iterator result = new value_Type[n];
uninitialized_fill_n(result,n,value);
return result;
}
iterator uninitialized_fill_n(iterator first,size_t n ,const T& x){
iterator tmp_start = first;
while(n--){
*first++ = x;
}
return tmp_start;
}
public:
iterator begin(){return start;}
iterator end(){return finish;}
size_type size(){return size_type(end()-begin());}
bool empty()const{return begin() == end();}
reference operator[](size_type n){return *(begin()+n);}
Vector():start(0),finish(0),end_of_storage(0){}
Vector(size_type n, const T& value){fill_initialize(n,value);}
Vector(int n, const T& value){fill_initialize(n,value);}
Vector(long n, const T& value){fill_initialize(n,value);}
explicit Vector(size_type n){fill_initialize(n,T());}
~Vector(){
destory(start,finish);
deallocate(start);
}
void deallocate(iterator iter){
delete []iter;
}
void destory(iterator iter){
iter->~T();
}
void destory(iterator start, iterator finish){
int i=0;
while ((start+i) != finish)
{
(start+i)->~T();
i++;
}
}
reference front(){return *begin();}
reference back(){return *(end()-1);}
void push_back(const T& x){
if(finish!=end_of_storage)
*finish = x;
else{
insert(end(),1,x);
}
++finish;
}
void pop_back(){
--finish;
destory(finish);
}
iterator erase(iterator position){
if(position+1 != end())
copy(position+1,finish,position);
--finish;
destory(finish);
return position;
}
iterator erase(iterator first,iterator last){
iterator tmp = copy(last,finish,first);
destory(tmp,finish);
finish = finish - (last-first);
return first;
}
void resize(size_type new_size,const T& x){
if(new_size< size())
erase(begin()+new_size,end());
else
insert(end(),new_size-size(),x);
}
void resize(size_type new_size){resize(new_szie,T());}
void clear(){erase(begin(),end());}
void insert(iterator position,size_type n,const T& x){
if(n!=0){
//备用空间大于新增元素个数
if(size_type(end_of_storage-finish)>=n){
T x_copy;
const size_type elems_after = finish -position;
iterator old_finish = finish;
if(elems_after > n){
uninitialized_copy(finish-n,finish,finish);
finish += n;
copy_backward(position,old_finish-n,old_finish);
fill(position,position+n,x_copy);
}
else{
uninitialized_fill_n(finish,n-elems_after,x_copy);
finish += n - elems_after;
uninitialized_copy(position,old_finish,finish);
finish += elems_after;
fill(position,old_finish,x_copy);
}
}
else{ //备用空间不足
const size_type old_size = size();
const size_type len = old_size + max(old_size,n);
iterator new_start = reallocate(old_size+2*(max(old_size,n)));//新增元素个数为不足空间个数的2倍
iterator new_finish = new_start;
try{
// 将vector插入点之前的元素复制到新空间
new_finish = uninitialized_copy(start,position,new_start);
new_finish = uninitialized_fill_n_my(new_finish,n,x);
new_finish = uninitialized_copy(position,finish,new_finish);
}
//#ifdef _STL_USE_EXCEPTIONS
catch(...){
//若发生异常，回滚保持原有向量
destory(new_start,new_finish);
deallocate(new_start);
throw;
}
//#endif
destory(start,finish);
deallocate(start);
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
}
iterator uninitialized_copy(iterator first,iterator last,iterator res){
while(first!=last){
*(res++) = *(first++);
}
return res;
}
iterator copy_backward(iterator first,iterator last,iterator res){
while(last!=first){
*(--res) = *(--last);
}
return res;
}
iterator reallocate(const size_t len){
iterator iter;
iter = new T[len];
return iter;
}
iterator uninitialized_fill_n_my(iterator start,size_t n, const T& x){
while(n--){
*(start++) = x;
}
return start;
}
iterator find(iterator first,iterator last,const T& value){
while(first!=last){
if(*first == value)return first;
++first;
}
return first;
}
};
void test1(){//测试各种类型数据存储
Vector<int> Vint(10,2);
for(Vector<int>::iterator iter =Vint.begin();iter!= Vint.end();++iter)
cout<<*iter<<" ";
cout<<endl;
Vector<float>Vflt(10,2.1);
for(Vector<float>::iterator iter =Vflt.begin();iter!= Vflt.end();++iter)
cout<<*iter<<" ";
cout<<endl;
Vector<double>Vdoub(10,2.13);
for(Vector<double>::iterator iter =Vdoub.begin();iter!= Vdoub.end();++iter)
cout<<*iter<<" ";
cout<<endl;
class TT{
int tmp;
public:
TT(int a=0):tmp(a){}
operator int(){
return tmp;
}
};
Vector<TT>Vtt(10,TT(3));
for(Vector<TT>::iterator iter =Vtt.begin();iter!= Vtt.end();++iter)
cout<<*iter<<" ";
cout<<endl;
}
void test2(){//测试插入
Vector<int> Vint(10,2);
Vector<int>::iterator iter =Vint.end();
Vint.insert(----iter,2,3);
Vint.push_back(4);
for(iter=Vint.begin();iter!= Vint.end();++iter)
cout<<*iter<<" ";
cout<<endl;
}
void test3(){//测试删除
Vector<int> Vint(10,2);
Vector<int>::iterator iter =Vint.end();
Vint.insert(----iter,2,3);
Vint.push_back(4);
for(iter=Vint.begin();iter!= Vint.end();++iter)
cout<<*iter<<" ";
cout<<endl;
Vector<int>::iterator iter1 = Vint.find(Vint.begin(),Vint.end(),3);
Vint.erase(iter1,Vint.end());
for(iter=Vint.begin();iter!= Vint.end();++iter)
cout<<*iter<<" ";
cout<<endl;
iter = Vint.end();
Vint.erase(--iter);
for(iter=Vint.begin();iter!= Vint.end();++iter)
cout<<*iter<<" ";
cout<<endl;
}
int main(){
cout<<"----------test1---------"<<endl;
test1();
cout<<"----------test2---------"<<endl;
test2();
cout<<"----------test3---------"<<endl;
test3();
}