ベクトル-vector最下位実装
10397 ワード
最も基本的な線形構造はシーケンスと総称され、データ項目の論理順序とその物理記憶アドレスとの対応関係に応じて、シーケンスをベクトル(vector)とリスト(list)にさらに区別することができる.
ベクトルでは、すべてのデータ項目の物理的格納位置が論理順序と完全に一致し、このときの論理順序もランク(rank)と呼ばれる.
リストでは,論理的に隣接するデータ項目は物理的に必ずしも隣接していないが,間接アドレス方式でカプセル化された位置(position)で相互参照される.
Vectorテンプレートクラス
レプリケーションベースの構築方法:
リロードベクトル複素値オペレータ:
ダイナミックスペース管理
1.静的空間管理
内部配列が占める物理空間の容量は、ベクトルのライフタイム内に調整が許可されない場合、静的空間管理ポリシーと呼ばれます.このポリシーの空間効率は保証しにくい.一方、容量が固定され、オーバーフローを招く可能性がある.一方,一部の空間を予約しても,合理的な予約量を明確に定義することは困難である.
上記copyFrom()メソッドでは,容量を初期規模の2倍にしてもオーバーフローするリスクがある.
ベクトルの実際の規模とその内部配列容量との比(_size/_capacity)は、空間利用率を測定する重要な指標である充填因子と呼ばれる.
そのため、ダイナミックスペース管理ポリシーを変更する必要があります.その中で有効な方法は,いわゆる拡張可能容量を用いることである.
2.動的空間管理
拡張アルゴリズムexpand()
コンパクトアルゴリズムshrink()
ベクトルの実際の規模は内部配列の容量よりはるかに小さい可能性があり、充填因子がバルブ値より低い場合、配列にオーバーフローが発生したと呼ばれ、オーバーフローが発生した場合、内部配列の容量を適切に削減し、空間利用率を高めるよりもある.
リロードベクトルオペレータ[]
無秩序ベクトル要素検索インタフェースfind()
ベクトル要素挿入インタフェースinsert()
区間削除:remove(lo,hi)
単一要素削除remove(r)
秩序性の選別
ユニーク化
秩序ベクトルuniquify()インタフェースの効率的な実現
検索
統合インタフェースsearch()
二分検索(バージョンA)
Fibonacci検索
ちょっと...
シーケンサ
ユニファイドエントリ
バブルソート
集計ソート
集計ソートの主体構造は典型的な分治戦略に属し、コードのように再帰的に記述し、実現することができる.
ベクトルでは、すべてのデータ項目の物理的格納位置が論理順序と完全に一致し、このときの論理順序もランク(rank)と呼ばれる.
リストでは,論理的に隣接するデータ項目は物理的に必ずしも隣接していないが,間接アドレス方式でカプセル化された位置(position)で相互参照される.
Vectorテンプレートクラス
/*************************************************************************
> File Name: vector.h
> Author: amoscykl
> Mail: [email protected]
> Created Time: 2018 07 02 20 51 45
************************************************************************/
typedef int Rank; //
#define DEFAULT_CAPACITY 3 //
template class Vector { //
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); //
void selectionSort(Rank lo, Rank hi); //
void merge(Rank lo, Rank mi, Rank hi); //
void mergeSort(Rank lo, Rank hi); //
Rank partition(Rank lo, Rank hi); //
void quickSort(Rank lo, Rank hi); //
void heapSort(Rank lo, Rank hi); //
public:
//
Vector( 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
/* */
Vector( T const* A, Rank n) { copyFrom(A,0,n); } //
Vector( T const* A, Rank lo, Rank hi) { copyFrom(A,lo,hi); } //
Vector( Vector const& V) { copyFrom( V._elem, 0, V._size); } //
Vector( Vector const& V, Rank lo, Rank hi) { copyFrom( V._elem, lo, hi); } //
//
~Vector() { delete [] __elem};
//
Rank size() const { return _size; } //
bool empty() const { return !_size; } //
int disordered() const; //
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; //
//
T& operator[] (Rank r) const; // ，
Vector & operator = (Vector const& ); // ，
T remove ( Rank r ); // r
int remove(Rank lo, Rank hi); //
Rank insert(Rank r, T const& e); //
Rank insert(T const& e ) { return insert (_size,e); } //
void sort(Rank lo, Rank hi); //
void sort() { sort(0,_size); } //
void unsort (Rank lo, Rank hi ); //
void unsort { unsort(0, _size); } //
int deduplicate(); //
int uniquify(); //
//
void traverse( void (* ) (T &) ); // :
template void traverse ( VST& ); // ：
}; //Vector レプリケーションベースの構築方法:
template //
void Vector::copyFrom ( T const* A, Rank lo, Rank hi) { // A[lo,hi]
_elem = new T[_capacity = 2 * (hi - lo) ]; _size = 0; // ，
while ( lo < hi)
_elem[_size++] = A[lo++]; // _elem[0,hi-lo]
} リロードベクトル複素値オペレータ:
template Vector& Vector::operator= (Vector const& V) { //
if (_elem ) delete [] _elem; //
copyFrom(V._elem, 0, V.size() ); //
return *this; // ，
} ダイナミックスペース管理
1.静的空間管理
内部配列が占める物理空間の容量は、ベクトルのライフタイム内に調整が許可されない場合、静的空間管理ポリシーと呼ばれます.このポリシーの空間効率は保証しにくい.一方、容量が固定され、オーバーフローを招く可能性がある.一方,一部の空間を予約しても,合理的な予約量を明確に定義することは困難である.
上記copyFrom()メソッドでは,容量を初期規模の2倍にしてもオーバーフローするリスクがある.
ベクトルの実際の規模とその内部配列容量との比(_size/_capacity)は、空間利用率を測定する重要な指標である充填因子と呼ばれる.
そのため、ダイナミックスペース管理ポリシーを変更する必要があります.その中で有効な方法は,いわゆる拡張可能容量を用いることである.
2.動的空間管理
拡張アルゴリズムexpand()
template void Vector::expand() { //
if (_size < _capacity ) return; // ，
if (_capacity < DEFAULT_CAPACITY ) _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 void Vector::shrink() { //
if (_capacity < DEFAULT_CAPACITY << 1) return; // DEFAULT_CAPACITY
if (_size << 2 > _capacity) return ; // 25%
T* oldElem = _elem; _elem = new T[_capacity >>= 1]; // ，
for (int i = 0; i < _size; i++) _elem[i] = oldElem[i]; //
delete [] oldElem; //
} リロードベクトルオペレータ[]
template T& Vector::operator[] (Rank r) const //
{ return _elem[r]; } 無秩序ベクトル要素検索インタフェースfind()
template // ： e ； ， lo-1
Rank Vector::find(T const& e, Rank lo, Rank hi) const {
while( (lo < hi -- ) && (e != _elem[hi] ) ); // ，
return hi; // hi < lo, ； hi
} ベクトル要素挿入インタフェースinsert()
template // e r
Rank Vector::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; //
} 区間削除:remove(lo,hi)
template int Vector::remove ( Rank lo, Rank hi ) { // [lo,hi]
if (lo == hi) return 0; // ， ， remove(0,0)
while (hi < _size) _elem[lo++] = _elem[hi++]; //[hi,_size] hi-lo
_size = lo; // ， [lo,_size=hi]
shrink(); // ，
return hi - lo; //
} 単一要素削除remove(r)
template int Vector::remove (Rank r) { // r ，0 <= e < size
T e = _elem[r]; //
remove(r,r+1); // ， [r,r+1]
return e; //
} 秩序性の選別
template int Vector::disordered() const { //
int n = 0; //
for (int i = 1; i < _size; i ++) // _size-1
if (_elem[i-1] > _elem[i] ) n++; //
return n; // n=0
} ユニーク化
秩序ベクトルuniquify()インタフェースの効率的な実現
template int Vector::uniquify() { //
Rank i = 0, j = 0; // “ ”
while(++j < _size) // ，
if ( _elem[i] != _elem[j] ) //
_elem[++i] = _elem[j]; // ，
_size = ++i; shrink(); //
return j - i; // ，
} 検索
統合インタフェースsearch()
template // [lo,hi] ， e
Rank Vector::search (T const& e, Rank lo, Rank hi) const {
return ( rand() % 2) ? // 50% Fibonacci
binSearch(_elem, e, lo, hi) : fibSearch (_elem, e, lo, hi);
} 二分検索(バージョンA)
//
template static Rank binSearch(T* A, T const& e, Rank lo, Rank hi) {
while( lo < hi) { // ，
Rank mi = ( lo + hi) >> 1; //
if( e < A[mi] ) hi = mi; // [lo,hi)
else if (A[mi] < e) lo = mi + 1; // (mi,hi)
else return mi; // mi
} //
return -1; //
} // ， 。 Fibonacci検索
ちょっと...
シーケンサ
ユニファイドエントリ
template void Vector::sort (Rank lo, Rank hi) { // [lo,hi]
switch( rand() % 5) { // ，
case 1: bubbleSort ( lo, hi); break; //
case 2: selectionSort (lo, hi); break; //
case 3: mergeSort (lo,hi); break; //
case 4: heapSort (lo,hi); break; //
default: quickSort (lo,hi); break; //
}
} バブルソート
//
template //
void Vector::bubbleSort( Rank lo, Rank hi)
{ while ( !bubble(lo, hi--) ); } // ，
//
template bool Vector::bubble (Rank lo, Rank hi) { //
bool sorted = true; //
while (++lo < hi) // ，
if ( _elem[lo-1] > _elem[lo] ) { // ， ，
sorted = false;
swap( _elem[lo-1],_elem[lo]);
}
return sorted; //
} 集計ソート
集計ソートの主体構造は典型的な分治戦略に属し、コードのように再帰的に記述し、実現することができる.
//
template //
void Vector::mergeSort (Rank lo, Rank hi) {
if (hi - lo < 2) return ; // ， ...
int mi = ( lo + hi ) / 2; //
mergeSort ( lo, mi ); mergeSort ( mi, hi ); //
merge(lo,mi,hi); //
}
template //
void Vector::merge ( Rank lo, Rank mi, Rank hi ) { // [lo,mi) [mi,hi)
T* A = _elem + lo; // A[0,hi-lo) = _elem[lo,hi)
int lb = mi - lo; T* B = new T[lb]; // B[0,lb) = _elem[lo,mi)
for ( Rank i = 0; i < lb; B[i] = A[i++] )
; //
int lc = hi - mi; T* C = _elem + mi; // C[0,lc_ = _elem[mi,hi)
for (Rank i = 0, j = 0, k = 0; ( j < lb ) || ( k < lc) ; ) { //B[j] C[k] A }
if ( ( j < lb ) && ( ! ( k < lc ) || (B[j] <= C[k] ))) A[i++] = B[j++];
if ( ( k < lc ) && ( ! ( j < lb ) || (C[k] < B[j] ))) A[i++] = C[k++];
}
delete [] B; // B
} //