vector.h:
#ifndef __Vector__H__ #define __Vector__H__ typedef int Rank; #define DEFAULT_CAPACITY 3 template<typename T> class Vector{ protected: Rank _size; int _capacity; T*_elem; void copyFrom(T const *A, Rank lo, Rank hi); void expand(); void shrink(); void bubbleSort(Rank lo,Rank hi); bool bubble(Rank lo,Rank hi); void mergeSort(Rank lo,Rank hi); void merge(Rank lo,Rank mi,Rank hi); public: Vector(int c = DEFAULT_CAPACITY,int s = 0, T v = 0) { _elem = new T[_capacity = s]; for (_size = 0; _size < s; _elem[_size++] = v); } Vector(T const *A, Rank n) { copyFrom(A, 0, n); } Vector(T const *A, Rank lo, Rank hi) { copyFrom(A, lo, hi); } Vector(Vector<T> const &V) { copyFrom(V._elem,0,V._size); } Vector(Vector<T> const &V, Rank lo, Rank hi) { copyFrom(V._elem, lo, hi);} ~Vector(){delete[]_elem;} Rank size() const { return _size;} bool empty() const { return !_size;} Vector<T>& operator=(Vector<T> const&); T&operator[](Rank r) const; void unsort(Rank lo,Rank hi); Rank find(T const& e,Rank lo,Rank hi) const; Rank insert(Rank r,T const& e); int remove(Rank lo,Rank hi); T remove(Rank r); int deduplicate(); int disordered() const; int uniquify(); void traverse(void(*)(T&)); template<typename VST> void traverse(VST&); static Rank binSearch(T* A,T const& e,Rank lo,Rank hi); static Rank binSearch2(T* A, T const& e, Rank lo, Rank hi); static Rank binSearch3(T* A, T const& e, Rank lo, Rank hi); }; #endif
vector.cpp:
#include"Vector.h" template<typename T> void Vector<T>::copyFrom(T const * A, Rank lo, Rank hi) { _elem = new T[_capacity=2*(hi-lo)]; _size = 0; while (lo < hi) { _elem[_size++] = A[lo++]; } } template<typename T> void Vector<T>::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]; } delete[]oldElem; } template<typename T> void Vector<T>::shrink() { if (_capacity < DEFAULT_CAPACITY << 1)return; if (_size << 2 > _capacity)return; T *oldElem = _elem; _elem = new T[_capacity>>=1]; for(int i = 0; i < _size; i++) { _elem[i] = oldElem[i]; } delete[]oldElem; } template<typename T> void Vector<T>::bubbleSort(Rank lo, Rank hi) { while (!bubble(lo,hi--)); } template<typename T> bool Vector<T>::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<typename T> void Vector<T>::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<typename T> void Vector<T>::merge(Rank lo, Rank mi,Rank hi) { T *A = _elem + lo; int lb = mi - lo; T* B = new T[lb]; for (int i = 0; i < lb; i++) B[i] = A[i]; int rb = hi - mi; T *C = _elem + mi; for (Rank i=0,int j = 0, int k = 0; (j < lb) || (k < rb);) { if ((j<lb)&&(k>rb||(B[j] < C[k]))) { A[i++] = B[j++]; } if ((k<rb)&&(j>lb||(C[k]<=B[j]))) ｛ A[i++] = C[k++]; ｝ } delete[] B; } template<typename T> Vector<T>& Vector<T>::operator=(Vector<T> const & V) { if (_elem) delete[]_elem; copyFrom(V._elem,0,V._size); return *this; } template<typename T> T & Vector<T>::operator[](Rank r) const { return _elem[r]; } template<typename T> void Vector<T>::unsort(Rank lo, Rank hi) { T* V = _elem + lo; for(Rank i = hi - lo; i >= 0; i--) { swap(V[i-1] = V[rand()%i]); } } template<typename T> Rank Vector<T>::find(T const & e, Rank lo, Rank hi) const { while((lo < hi--)&&(e!=_elem[hi])); return hi; } template<typename T> Rank Vector<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; } template<typename T> int Vector<T>::remove(Rank lo, Rank hi) { if (lo == hi)return 0; while (hi < _size) { _elem[lo++] = _elem[hi++]; } _size = lo; shrink(); return hi - lo; } template<typename T> T Vector<T>::remove(Rank r) { T e = _elem[r]; remove(r,r+1); return e; } template<typename T> int Vector<T>::deduplicate() { int oldsize = _size; Rank i = 1; while (i < _size) { (find(_elem[i], 0, _size) < 0) ? i++ : remove(i); } return oldsize-_size; } template<typename T> int Vector<T>::disordered() const { int n = 0; for (int i = 1; i < _size; i++) { if(_elem[i - 1] > _elem[i]) { n++; } } return n; } template<typename T> int Vector<T>::uniquify() { Rank i = 0, j = 0; while (++j < _size) { if (_elem[i] != _elem[j]) { _elem[++i] = _elem[j]; } } _size = ++i; shrink(); return j - i; } template<typename T> Rank Vector<T>::binSearch(T * A, T const & e, Rank lo, Rank hi) { while (lo < hi) { Rank mi = (lo + hi) >> 1; if (e > A[mi]) { lo = mi+1; } else if (e < A[mi]) { hi = mi; } else { return mi; } } return -1; } template<typename T> Rank Vector<T>::binSearch2(T * A, T const & e, Rank lo, Rank hi) { while (1 < (hi - lo)) { Rank mi = (lo + hi) >> 1; (e < A[mi]) ? hi = mi : lo = mi; } return (e == A[lo]) ? lo : -1; } template<typename T> Rank Vector<T>::binSearch3(T * A, T const & e, Rank lo, Rank hi) { while (lo < hi) { Rank mi = (lo + hi) >> 1; (e < A[mi]) ? hi = mi : lo = mi + 1; } return --lo; } template<typename T> void Vector<T>::traverse(void(*visit)(T &)) { for (int i = 0; i < _size; i++) { visit(_elem[i]); } } template<typename T> template<typename VST> void Vector<T>::traverse(VST &visit) { for (int i = 0; i < _size; i++) { visit(_elem[i]); } }