為什麼使用data_array:
1. data_array是用於物件為資料型態，不需建構與解構式。
2. data_array資料移動使用記憶體複製，比標準函式庫的個別物件複製快。
3. 檔案相依性與複雜性比標準函式庫少，有特殊需求，容易修改。
4. 直接改變陣列大小：set_size
5. 指定物件的記憶體位址：set_memory
6. 當非排序陣列，刪除元素，將最後一個移到要刪除的位置，可以減少物件移動數量:move_last_and_erase
7. 加入物件不需要複製；加入空物件，針對目標記憶體內容修改，減少複製物件動作：add_one
8. 將物件移動到特定位置，減少物件總移動數量：move_position
#ifndef _data_array_h_
#define _data_array_h_
#include <crtdbg.h>
template <class T>
class data_array
{
public:
data_array(const data_array&,int max_item_count=0);
data_array(const T*,int count,int max_item_count=0);
explicit data_array(int max_item_count=0);//explicit: 數字不要自動轉成data_array!
~data_array();
//有多少物件
int size()const;
//改變物件數量
void set_size(int new_size,int max_item_count=0);
//存取物件
T* ptr();
T* begin();
T* end();
T& operator[](int index);
T& at(int index);
T& front();
T& back();
//const 物件
const T* ptr()const;
const T* begin()const;
const T* end()const;
const T& operator[](int index) const;
const T& at(int index) const;
const T& front()const;
const T& back()const;
//指定
void set_memory(T* item_ptr,int item_size);
void assign(const T*,int count,int max_item_count=0);
void assign(const data_array&,int max_item_count=0);
void assign(int count,const T&x)
{
_size=0;
reserve(count);
_size=count;
T*from=_ptr;
T*end=_ptr+_size;
while(from&operator =(const data_array&);
bool operator ==(const data_array&)const;
bool operator !=(const data_array&x)const
{
return !(x==*this);
}
//加入物件
void push_back(const T&);
void push_back(const T*,int count);
void push_back(const T*pfrom,const T* pend)
{
push_back(pfrom,pend-pfrom);
}
void insert(int index,const T&);
void insert(int index,const T*,int count);
void insert(T*pat,const T*pfrom, const T* pend)
{
//pat 是array的指標
_ASSERT(pat>=_ptr && pat<=_ptr+_size); insert(pat-_ptr,pfrom,pend-pfrom); } void insert(T*pat,const T&x) { //pat 是array的指標 _ASSERT(pat>=_ptr && pat<=_ptr+_size); insert(pat-_ptr,x); } //加入未初始化的項目，傳回新加入的指標 //如果要加入的物件已經存在，使用push_back, //如果要加入的物件不存在，用add_one再去改變內部的資料，這樣少1次複製動作。 T&add_one(); //移動位置 //動作等同:但可能必較快 //T tmp=vec[from_index]; //vec.insert(to_index,tmp); //vec.erase(from_index); void move_position(int from_index,int to_index); //刪除物件 void erase(int index,int count=1); void erase(T*pat,T*pend) { //pat 是array的指標 _ASSERT(pat>=_ptr && pat<=_ptr+_size); erase(pat-_ptr,pend-pat); } void erase(T*pat) { //pat 是array的指標 _ASSERT(pat>=_ptr && pat<=_ptr+_size);
erase(pat-_ptr);
}
void move_last_and_erase(int index);//將最後一個移到index位置，刪除最後一個
void pop_back();
void clear();//物件數量設為0
void swap(data_array&);
void swap_item(int index1,int index2);
//配置記憶體大小
int capacity()const;
void reserve(int);
static int granule_size(int t)
{
//allocate_granule, 當使用push_back或insert已配置的記憶體不足，記憶體以allocate_granule的整數增加
const int allocate_granule=128;
int scale=t/allocate_granule;
int value=scale*allocate_granule;
int extra=t-value;
if(extra)
return value+allocate_granule;
return value;
}
//刪除配置的記憶體
void reset();
protected:
int _size;
T* _ptr;
int _memory_item_size;
BOOL _need_free;
//記憶體已配置完成，複製到後面
void memory_copy_to_back(const T*ptr,int item_count);
//記憶體已配置完成，將ptr往後gap_count複製item_count個
void memory_copy_items_back(int gap_count,T*ptr,int item_count);
//記憶體已配置完成，將ptr往前gap_count複製item_count個
void memory_copy_items_front(int gap_count,T*ptr,int item_count);
};
#include <malloc.h>
//note memcpy:編譯器最佳化會使用rep movs錯誤！
//使用MoveMemory，拒絕編譯器最佳化
template <class T>
inline bool data_array<T>::operator ==(const data_array<T>&x)const
{
if(&x==this)
return true;
if(x._size!=_size)
return false;
if(_size<=0)
return true;
//當物件有內部有空間，不能用memcmp
//例如如下xx, 內部記憶體可能有未用到的空間，使用memcmp會比較未初始化的空間！
// struct xx
// {
// int x;
// BYTE t;
// int g;
// };
const T*e=end();
const T*at=begin();
const T*c=x.begin();
while(at<e)
{
if(*c!=*at)
return false;
c++;
at++;
}
return true;
}
template <class T>
inline void data_array<T>::swap_item(int index1,int index2)
{
_ASSERT(index1>=0 && index1<_size && index2>=0 && index2<_size);
T tmp=_ptr[index1];
_ptr[index1]=_ptr[index2];
_ptr[index2]=tmp;
}
//記憶體已配置完成，複製到後面
template <class T>
inline void data_array<T>::memory_copy_to_back(const T*ptr,int item_count)
{
_ASSERT(_memory_item_size>=item_count+_size);
int len=sizeof(T)*item_count;
MoveMemory(_ptr+_size,ptr,len);
}
//記憶體已配置完成，將ptr往後gap_count複製item_count個
template <class T>
inline void data_array<T>::memory_copy_items_back(int gap_count,T*ptr,int item_count)
{
_ASSERT(ptr>=_ptr && ptr<=_ptr+_memory_item_size);
int len=sizeof(T)*item_count;
T* dst=ptr+gap_count;
//end position in memory range.
_ASSERT((dst+gap_count)<=_ptr+_memory_item_size);
MoveMemory(dst,ptr,len);
}
//記憶體已配置完成，將ptr往前gap_count複製item_count個
template <class T>
inline void data_array<T>::memory_copy_items_front(int gap_count,T*ptr,int item_count)
{
_ASSERT(ptr>=_ptr && (ptr+item_count)<=_ptr+_memory_item_size);
int len=sizeof(T)*item_count;
T* dst=ptr-gap_count;
//dst in memory range.
_ASSERT(dst>=_ptr);
MoveMemory(dst,ptr,len);
}
template <class T>
inline void data_array<T>::move_position(int from_index,int to_index)
{
_ASSERT(from_index>=0 && from_index<_size);
_ASSERT(to_index>=0 && to_index<_size);
if(from_index==to_index)
return;
T tmp=_ptr[from_index];
if(from_index<to_index)
{
//copy from front
MoveMemory(_ptr+from_index,_ptr+from_index+1,(to_index-from_index)*sizeof(T));
}else
{
//copy from back
MoveMemory(_ptr+to_index+1,_ptr+to_index,(from_index-to_index)*sizeof(T));
}
_ptr[to_index]=tmp;
}
template <class T>
inline T& data_array<T>::at(int index)
{
_ASSERT(index>=0 && index<_size);
return _ptr[index];
}
template <class T>
inline const T& data_array<T>::at(int index)const
{
_ASSERT(index>=0 && index<_size);
return _ptr[index];
}
template <class T>
inline T& data_array<T>::front()
{
_ASSERT(_size);
return _ptr[0];
}
template <class T>
inline const T& data_array<T>::front()const
{
_ASSERT(_size);
return _ptr[0];
}
template <class T>
inline T& data_array<T>::back()
{
_ASSERT(_size);
return _ptr[_size-1];
}
template <class T>
inline const T& data_array<T>::back()const
{
_ASSERT(_size);
return _ptr[_size-1];
}
template <class T>
inline void data_array<T>::pop_back()
{
_ASSERT(_size>0);
_size--;
}
template <class T>
inline const T* data_array<T>::begin()const
{
return _ptr;
}
template <class T>
inline T* data_array<T>::begin()
{
return _ptr;
}
template <class T>
inline const T* data_array<T>::end()const
{
return _ptr+_size;
}
template <class T>
inline T* data_array<T>::end()
{
return _ptr+_size;
}
template <class T>
inline const T* data_array<T>::ptr()const
{
return _ptr;
}
template <class T>
inline T* data_array<T>::ptr()
{
return _ptr;
}
template <class T>
inline const T& data_array<T>::operator[](int index) const
{
_ASSERT(index>=0 && index<_size);
return _ptr[index];
}
template <class T>
inline T& data_array<T>::operator[](int index)
{
_ASSERT(index>=0 && index<_size);
return _ptr[index];
}
template <class T>
inline void data_array<T>::clear()
{
_size=0;
}
template <class T>
inline void data_array<T>::reset()
{
if(_memory_item_size)
{
if(_need_free)
{
free(_ptr);
_need_free=0;
}
_ptr=0;
_size=0;
_memory_item_size=0;
}
}
template <class T>
inline int data_array<T>::capacity()const
{
return _memory_item_size;
}
template <class T>
inline void data_array<T>::reserve(int t)
{
_ASSERT(t>=_size);
//只配置更多
if(_memory_item_size<t)
{
data_array<T> tmp(*this,t);
tmp.swap(*this);
return;
}
}
template <class T>
inline void data_array<T>::move_last_and_erase(int index)//將最後一個移到index位置，刪除最後一個
{
//請保證index正確
_ASSERT(index>=0 && index<_size);
int last=_size-1;
if(index!=last)
_ptr[index]=_ptr[last];
_size--;
}
template <class T>
inline void data_array<T>::erase(int index,int count)
{
//請保證index正確
_ASSERT(index>=0 && index<_size);
_ASSERT(count>=1);
//刪過頭了, count太多！
_ASSERT(index+count<=_size);
int back_count=_size-(index+count);
_size=index+back_count;
if(back_count<=0)//刪到尾巴
{
return;
}
_ASSERT(_size>0);//當為0, 在上一個if判斷裡面處理了
memory_copy_items_front(count,_ptr+index+count,back_count);
}
template <class T>
inline T& data_array<T>::add_one()
{
if(_size+1>_memory_item_size)
{
int new_size=granule_size(_size+1);
reserve(new_size);
}
_size++;
_ASSERT(_memory_item_size>=_size);
return _ptr[_size-1];
}
template <class T>
inline void data_array<T>::push_back(const T&x)
{
if(_size+1>_memory_item_size)
{
int new_size=granule_size(_size+1);
reserve(new_size);
}
_ptr[_size]=x;
_size++;
_ASSERT(_memory_item_size>=_size);
}
template <class T>
inline void data_array<T>::push_back(const T*p,int count)
{
if(count<=0)
return;
if(_size+count>_memory_item_size)
{
int new_size=granule_size(_size+count);
data_array<T> tmp(*this,new_size);
tmp.memory_copy_to_back(p,count);
tmp._size+=count;
tmp.swap(*this);
}else
{
memory_copy_to_back(p,count);
_size+=count;
}
_ASSERT(_memory_item_size>=_size);
}
template <class T>
void data_array<T>::insert(int index,const T&x)
{
if(_size+1>_memory_item_size)
{
int new_size=granule_size(_size+1);
if(index>=_size)
{//add back.
data_array<T> tmp(*this,new_size);
tmp.swap(*this);
_ptr[_size]=x;
_size++;
_ASSERT(_memory_item_size>=_size);
return;
}
data_array<T> tmp(new_size);
if(index>0)//copy datas before index
{
tmp.memory_copy_to_back(_ptr,index);
tmp._size=index;
}
tmp._ptr[tmp._size]=x;
tmp._size++;
int remain_count=_size-index;
tmp.memory_copy_to_back(_ptr+index,remain_count);
tmp._size+=remain_count;
tmp.swap(*this);
_ASSERT(_memory_item_size>=_size);
return;
}
int remain_count=_size-index;
if(remain_count<=0)
{//add back.
_ptr[_size]=x;
_size++;
return;
}
//move back 1 items.
memory_copy_items_back(1,_ptr+index,remain_count);
_ptr[index]=x;
_size++;
_ASSERT(_memory_item_size>=_size);
}
template <class T>
void data_array<T>::insert(int index,const T*p,int count)
{
if(count<=0)
return;
//加入的不應該是data_array的內容
_ASSERT(!(p>=_ptr && p<(_ptr+_size)));
if(_size+count>_memory_item_size)
{
int new_size=granule_size(_size+count);
if(index>=_size)
{//add back.
data_array<T> tmp(*this,new_size);
tmp.swap(*this);
memory_copy_to_back(p,count);
_size+=count;
_ASSERT(_memory_item_size>=_size);
return;
}
data_array<T> tmp(new_size);
if(index>0)//copy datas before index
{
tmp.memory_copy_to_back(_ptr,index);
tmp._size=index;
}
//copy data
tmp.memory_copy_to_back(p,count);
tmp._size+=count;
//copy data at and after index.
int remain_count=_size-index;
tmp.memory_copy_to_back(_ptr+index,remain_count);
tmp._size+=remain_count;
tmp.swap(*this);
_ASSERT(_memory_item_size>=_size);
return;
}
int remain_count=_size-index;
if(remain_count<=0)
{//add back.
memory_copy_to_back(p,count);
_size+=count;
return;
}
//move back.
memory_copy_items_back(count,_ptr+index,remain_count);
//add data to index.
int len=sizeof(T)*count;
MoveMemory(_ptr+index,p,len);
_size+=count;
_ASSERT(_memory_item_size>=_size);
}
template <class T>
inline void data_array<T>::assign(const T*p,int count,int max_item_count)
{
//不應該是data_array的內容
_ASSERT(!(p>=_ptr && p<(_ptr+_size)));
if(max_item_count<count)
max_item_count=count;
if(_memory_item_size<max_item_count)
{
data_array<T> tmp(p,count,max_item_count);
tmp.swap(*this);
return;
}
if(count>0)
{
int len=count*sizeof(T);
MoveMemory(_ptr,p,len);
_size=count;
return;
}
_size=0;
}
template <class T>
inline void data_array<T>::assign(const data_array&x,int max_item_count)
{
if(this==&x)
return;
assign(x._ptr,x._size,max_item_count);
}
template <class T>
inline data_array<T>& data_array<T>::operator =(const data_array<T>&x)
{
if(this==&x)
return *this;
assign(x._ptr,x._size,x._memory_item_size);
return *this;
}
template <class T>
inline int data_array<T>::size()const
{
return _size;
}
template <class T>
inline void data_array<T>::set_size(int new_size,int max_item_count)
{
if(max_item_count<new_size)
max_item_count=new_size;
if(max_item_count<=_memory_item_size)
{
_size=new_size;
return;
}
if(new_size<_size)//比較小的值複製數量較少
_size=new_size;
data_array<T> tmp(*this,max_item_count);
tmp.swap(*this);
_size=new_size;
}
template <class T>
inline void data_array<T>::set_memory(T* item_ptr,int item_size)
{
_ASSERT(item_size>0);
//memory ptr can read?
_ASSERT(_CrtIsValidPointer( item_ptr, item_size*sizeof(T), TRUE ) );
reset();
//reset will set _need_free, _size to zero
_ASSERT(_need_free==0);
_ASSERT(_size==0);
_ptr=item_ptr;
_memory_item_size=item_size;
}
template <class T>
data_array<T>::data_array(const data_array<T>&x,int max_item_count)
{
if(max_item_count<x._size)
max_item_count=x._size;
if(max_item_count==0)
{
_need_free=0;
_ptr=0;
_size=0;
_memory_item_size=0;
return;
}
int len=max_item_count*sizeof(T);
_ptr=(T*)malloc(len);
_need_free=1;
_memory_item_size=max_item_count;
len=x._size*sizeof(T);
if(len)
MoveMemory(_ptr,x._ptr,len);
_size=x._size;
}
template <class T>
data_array<T>::data_array(const T*p,int count,int max_item_count)
{
if(max_item_count<count)
max_item_count=count;
if(max_item_count==0)
{
_need_free=0;
_ptr=0;
_size=0;
_memory_item_size=0;
return;
}
int len=max_item_count*sizeof(T);
_ptr=(T*)malloc(len);
_need_free=1;
_memory_item_size=max_item_count;
len=count*sizeof(T);
if(len)
MoveMemory(_ptr,p,len);
_size=count;
}
template <class T>
inline data_array<T>::data_array(int max_item_count)
{
if(max_item_count==0)
{
_need_free=0;
_ptr=0;
_size=0;
_memory_item_size=0;
return;
}
int len=max_item_count*sizeof(T);
_ptr=(T*)malloc(len);
_need_free=1;
_size=0;
_memory_item_size=max_item_count;
}
template <class T>
inline void data_array<T>::swap(data_array<T>&x)
{
int tmp;
tmp=_need_free;
_need_free=x._need_free;
x._need_free=tmp;
tmp=_size;
_size=x._size;
x._size=tmp;
tmp=_memory_item_size;
_memory_item_size=x._memory_item_size;
x._memory_item_size=tmp;
T* t;
t=_ptr;
_ptr=x._ptr;
x._ptr=t;
}
template <class T>
inline data_array<T>::~data_array()
{
reset();
}
#endif
