[セットトップ]データ構造――ベクトルテンプレートのソースコード
自分で一つのベクトルテンプレートを書きました.テンプレート関数の定義と実現本は同じファイルに書くべきです.探しやすいように別れました.ヘッダファイルに書くことを定義して、ソースファイルに書くことができます.
本ページの内容:
a.ヘッダファイル(「myVector.h」)
b.ソースファイル(「myVector.cpp」)
c.テンプレートテストファイル(「manVTest.cpp」)
ベクトルテンプレートのソースコード:
a.ヘッダファイル(「myVector.h」):
本ページの内容:
a.ヘッダファイル(「myVector.h」)
b.ソースファイル(「myVector.cpp」)
c.テンプレートテストファイル(「manVTest.cpp」)
ベクトルテンプレートのソースコード:
a.ヘッダファイル(「myVector.h」):
#ifndef _MYVECTOR_H__
#define _MYVECTOR_H__
typedef int Rank;//
#define DEFAULT_CAPACITY 3 // （ ）
template <typename T> class myVector { //
protected:
Rank _size; int _capacity; T* _elem; // 、 、
void copyFrom ( T const* A, Rank lo, Rank hi ); // A[lo, hi)
void expand(); //
void shrink(); //
bool bubble ( Rank lo, Rank hi ); //
void bubbleSort ( Rank lo, Rank hi ); //
Rank max ( Rank lo, Rank hi ); // [lo,hi)
int maxoftwo(int one,int two){ if(one>two) return one; else return two; }//
Rank binSearch(T*A,T const&e,Rank lo,Rank hi) const;//
public:
//
myVector ( int c = DEFAULT_CAPACITY, int s = 0, T v = 0 ) // c、 s、 v
{ _elem = new T[_capacity = c]; for ( _size = 0; _size < s; _elem[_size++] = v ); } //s<=c
myVector ( T const* A, Rank n ) { copyFrom ( A, 0, n ); } //
myVector ( T const* A, Rank lo, Rank hi ) { copyFrom ( A, lo, hi ); } //
myVector ( myVector<T> const& V ) { copyFrom ( V._elem, 0, V._size ); } //
myVector ( myVector<T> const& V, Rank lo, Rank hi ) { copyFrom ( V._elem, lo, hi ); } //
//
~myVector() { delete [] _elem; } //
//
Rank size() const { return _size; } //
T get(Rank r) const;// r
void put(Rank r,T e);// e r
Rank insert ( Rank r, T const& e ); //
Rank insert ( T const& e ) { return insert ( _size, e ); } //
int remove ( Rank lo, Rank hi ); // [lo, hi)
T remove ( Rank r ){ T e=_elem[r];remove(r,r+1); return e;} // r
int disordered() const; //
void sort ( Rank lo, Rank hi ); // [lo, hi)
void sort() { sort ( 0, _size ); } //
Rank find ( T const& e ) const { return find ( e, 0, _size ); } //
Rank find ( T const& e, Rank lo, Rank hi ) const; //
Rank search ( T const& e ) const //
{ return ( 0 >= _size ) ? -1 : search ( e, 0, _size ); }
Rank search ( T const& e, Rank lo, Rank hi ) const; //
int deduplicate(); //
int uniquify(); //
bool empty() const { return !_size; } //
//
T& operator[] ( Rank r ) const{return _elem[r];}; // ，
myVector<T> & operator= ( myVector<T> const& ); // ，
//
void traverse ( void (*visit ) ( T& ) ); // （ ， ）
template <typename VST> void traverse ( VST& ); // （ ， ）
}; //Vector
#include"myVector.cpp"
#endif
/***************protected ****************/
// A[lo, hi)--"copyFrom"
template<typename T>
void myVector<T>::copyFrom(T const*A,Rank lo,Rank hi)
{
_size=hi-lo;//
_capacity=hi-lo;//
_elem=new T[_capacity];// ( ）
for(int i=lo;i<hi;i++)
{
_elem[i]=A[i];
}
}
// --"expand"
template<typename T>
void myVector<T>::expand()
{
if(_size<_capacity)
{
return; // ，
}
_capacity=maxoftwo(_capacity,DEFAULT_CAPACITY);//
T*oldElem=_elem;//
_elem=new T[_capacity<<=1];//
for(int i=0;i<_size;i++)//
{
_elem[i]=oldElem[i];//T ， "="
}
delete [] oldElem;//
}
// --"shrink"
template<typename T>
void myVector<T>::shrink()
{
if(_size<_capacity/2)
{
T*oldElem=_elem;//
_elem=new T[_capacity>>=1];//
for(int i=0;i<_size;i++)//
{
_elem[i]=oldElem[i];//T ， "="
}
}
}
// --"bubble"
template<typename T>
bool myVector<T>::bubble(Rank lo,Rank hi)
{
bool sorted=true;//
while(++lo<hi)
{
if(_elem[lo-1]>_elem[lo])// ，
{
sorted=false; //
T temp;//
temp=_elem[lo-1];
_elem[lo-1]=_elem[lo];
_elem[lo]=temp;
}
}
return sorted;
}
//
template<typename T>
void myVector<T>::bubbleSort(Rank lo,Rank hi)
{
while(!bubble(lo,hi--));// ，
}
// [lo,hi)
template<typename T>
Rank myVector<T>::max(Rank lo,Rank hi)
{
T maxT;
Rank rank;
maxT=_elem[lo];
for(int i=lo;i<hi;i++)
{
if(maxT<_elem[i])
{
rank=i;
maxT=_elem[i];
}
}
return rank;
}
/****************public ******************/
// r
template<typename T>
T myVector<T>::get(Rank r) const
{
return _elem[r];
}
// --"put"
template<typename T>
void myVector<T>::put(Rank r,T e)
{
_elem[r]=e;// e r
}
// --"insert"
template<typename T>
Rank myVector<T>::insert(Rank r,T const& e)
{
expand();// ，
for(int i=_size;i>r;i--)//
{
_elem[i]=_elem[i-1];//
}
_elem[r]=e;//
_size++;//
return r;//
}
// [lo, hi) --"remove"
template<typename T>
int myVector<T>::remove(Rank lo,Rank hi)
{
if(lo==hi)
{
return 0;
}
while(hi<_size)
{
_elem[lo++]=_elem[hi++];//[hi,_size) hi-lo
}
_size=lo;//
shrink();// ，
return hi-lo;//
}
// --"disordered"
template<typename T>
int myVector<T>::disordered() const
{
int n=0;//
for(int i=1;i<_size;i++)//
{
n+=(_elem[i-1]>_elem[i]);//
}
return n;// n=0
}
// [lo,hi) ( ）--"sort"
template<typename T>
void myVector<T>::sort(Rank lo,Rank hi)
{
bubbleSort(lo,hi);
}
// [lo,hi) --"find"
template<typename T>
Rank myVector<T>::find( T const& e, Rank lo, Rank hi ) const// ，
{
while((lo<hi--)&&e!=_elem[hi]) ;//
return hi;//hi<lo ； hi
}
// [lo,hi) --"search"
template<typename T>
Rank myVector<T>::search(T const &e,Rank lo,Rank hi) const
{
return binSearch(_elem,e,lo,hi);//
}
// --"deduplicate"
template<typename T>
int myVector<T>::deduplicate()
{
int oldSize=_size;//
Rank i=1;// _elem[1]
while(i<_size)// _elem[i]
{
if(find(_elem[i],0,i)<0)//
{
i++;//
}
else
{
remove(i);//
}
}
return oldSize-_size;// 。
}
// --"uniquify"
template<typename T>
int myVector<T>::uniquify()
{
int oldSize=_size;//
int i=0;//
while(i<_size-1)//
{
(_elem[i]==_elem[i+1])?remove(i+1):i++;// ， ；
}
return oldSize-_size;// 。
}
// --"traverse"
// 1--
template<typename T>
void myVector<T>::traverse(void (*visit ) ( T& ))
{
for(int i=0;i<_size;i++)
{
visit(_elem[i]);
}
}
// 2--
template<typename T>
template<typename VST>
void myVector<T>::traverse(VST &visit)
{
for(int i=0;i<_size;i++)
{
visit(_elem[i]);
}
}
/************ **************/
// ( ）
template<typename T>
Rank myVector<T>::binSearch(T*A,T const&e,Rank lo,Rank hi) const
{
Rank mi;
while(lo<hi)// ， 3
{
mi=(lo+hi)>>1;//
if(e<A[mi]) hi=mi;// [lo,mi)
else if(A[mi]<e) lo=mi+1;// (mi,hi)
else return mi;// mi
}
if(e<A[mi])
{
return mi-1;//
}
else
{
return mi;//
}
<pre>}c.模板测试文件("mainVTest.cpp"):
#include<iostream> #include"myVector.h" #include<cstdlib> using namespace std; myVector<int> VTest; void CoutVTest(); void DisturbVTest(); template <typename T> void visit(T e) { e++; } int main() { for(int i=0;i<20;i++) { VTest.insert(i); } cout<<" (insert ,get ）:"<<endl; CoutVTest(); // cout<<" :"<<endl; //size() cout<<"size()="<<VTest.size()<<endl; //put(int r,T e) VTest.put(0,20);// 0 20 cout<<"put(0,20)="; CoutVTest(); //insert(2,100) VTest.insert(2,100); cout<<"insert(2,100)="; CoutVTest(); //remove(4) VTest.remove(4); cout<<"remove(4)="; CoutVTest(); VTest.remove(0,10); cout<<"remove(0,10)="; CoutVTest(); //disordered() cout<<"disordered()="<<VTest.disordered()<<endl; VTest.put(0,100); cout<<"After put(0,100)="; CoutVTest(); cout<<"Then disordered()="<<VTest.disordered()<<endl; //sort() VTest.sort(); cout<<"sort()="; CoutVTest(); cout<<"After New VTest="; DisturbVTest(); CoutVTest(); VTest.sort(0,5); cout<<"sort(0,5)="; CoutVTest(); //find(41) cout<<"find(41)="<<VTest.find(41)<<endl; cout<<"find(1000)="<<VTest.find(1000)<<endl; cout<<"find(41,0,5)="<<VTest.find(41,0,5)<<endl; cout<<"find(41,5,10)="<<VTest.find(41,5,10)<<endl; // search(4) VTest.sort(); cout<<"After sort()="; CoutVTest(); cout<<"search(41)="<<VTest.search(41)<<endl; cout<<"search(50)="<<VTest.search(50)<<endl; //deduplicate() VTest.put(2,58); VTest.put(9,58); cout<<"After New VTest="; CoutVTest(); cout<<"deduplicate()="<<VTest.deduplicate()<<endl; CoutVTest(); //uniquify() VTest.sort(); VTest.insert(3,58); VTest.insert(3,58); cout<<"After New VTest="; CoutVTest(); cout<<"uniquify()="<<VTest.uniquify()<<endl; CoutVTest(); //traverse() VTest.traverse(visit); cout<<"traverse()="; CoutVTest(); cout<<" ！"; return 0; } void CoutVTest() { for(int i=0;i<VTest.size();i++) { cout<<VTest.get(i)<<" "; } cout<<endl; } void DisturbVTest() { for(int i=0;i<VTest.size();i++) { VTest.put(i,rand()%100); } }