C++ 模板类 vector

//export #include "vector.h" #include "Fib.h" #include "stdlib.h" #include "time.h" using namespace std; template <typename T> ///元素类型 void Vector<T>::copyFrom(T const* A, Rank lo, Rank hi) { ///以数组区间A[lo, hi)为蓝本复制向量 _elem = new T[_capacity = 2 * (hi - lo)]; _size = 0; ///分配空间，规模清零 while (lo < hi) ///A[lo, hi)内的元素逐一 _elem[_size++] = A[lo++]; ///复制至_elem[0, hi - 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]; ///复制原向量内容（T为基本类型，或已重载赋值操作符'='）; delete [] oldElem; ///释放原空间 } template <typename T> void Vector<T>::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 <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>::bubbleSort(Rank lo, Rank hi) ///assert: 0 <= lo < hi <= size { while (!bubble(lo, hi--)); } ///逐趟做扫描交换，直至全序 template <typename T> Rank Vector<T>::max(Rank lo, Rank hi) { ///在[lo, hi]内找出最大者 Rank mx = hi; while (lo < hi--) ///逆向扫描 if (_elem[hi] > _elem[mx]) ///且严格比较 mx = hi; ///故能在max有多个时保证后者优先，进而保证selectionSort稳定 return mx; } template <typename T> //向量选择排序 void Vector<T>::selectionSort(Rank lo, Rank hi) { //assert: 0 < lo <= hi <= size /// /*DSA*/printf("\tSELECTIONsort [%3d, %3d)\n", lo, hi); while (lo < --hi) swap(_elem[max(lo, hi)], _elem[hi]); ///将[hi]与[lo, hi]中的最大者交换 } template<typename T> void Vector<T>::insertionSort(Rank lo,Rank hi){ /// Rank start=lo; while(lo++<hi) swap(_elem[find(_elem[lo],start,lo-1)],_elem[lo]); } template <typename T> ///有序向量的归并 void Vector<T>::merge(Rank lo, Rank mi, Rank hi) { ///以mi为界、各自有序的子向量[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 } ///归并后得到完整的有序向量[lo, hi) template <typename T> ///向量归并排序 void Vector<T>::mergeSort(Rank lo, Rank hi) { ///0 <= lo < hi <= size //// /*DSA*/printf("\tMERGEsort [%3d, %3d)\n", lo ,hi); if (hi - lo < 2) return; ///单元素区间自然有序，否则... int mi = (lo + hi) >> 1; ///以中点为界 mergeSort(lo, mi); mergeSort(mi, hi); merge(lo, mi, hi); ///分别对前、后半段排序，然后归并 } template <typename T> ///轴点构造算法：通过调整元素位置构造区间[lo, hi]的轴点，并返回其秩 Rank Vector<T>::partition(Rank lo, Rank hi) { ///版本B：可优化处理多个关键码雷同的退化情况 srand((unsigned)time(NULL));///以时间作为一个种子产生一个随机数 swap(_elem[lo], _elem[lo + rand() % (hi - lo + 1)]); ///rand()函数任意产生一个元素与首元素交换 T pivot = _elem[lo]; ///以首元素为候选轴点——经以上交换，等效于随机选取 while (lo < hi) { ///从向量的两端交替地向中间扫描 while (lo < hi) if (pivot < _elem[hi]) ///在大于pivot的前提下 hi--; ///向左拓展右端子向量 else ///直至遇到不大于pivot者 { _elem[lo++] = _elem[hi]; break; } ///将其归入左端子向量 while (lo < hi) if (_elem[lo] < pivot) ///在小于pivot的前提下 lo++; ///向右拓展左端子向量 else ///直至遇到不小于pivot者 { _elem[hi--] = _elem[lo]; break; } ///将其归入右端子向量 } ///assert: lo == hi _elem[lo] = pivot; ///将备份的轴点记录置于前、后子向量之间 return lo; ///返回轴点的秩 } template <typename T> ///向量快速排序 void Vector<T>::quickSort(Rank lo, Rank hi) { //0 <= lo < hi <= size ///*DSA*/printf("\tQUICKsort [%3d, %3d)\n", lo, hi); if (hi - lo < 2) return; ///单元素区间自然有序，否则... Rank mi = partition(lo, hi - 1); ///在[lo, hi - 1]内构造轴点 quickSort(lo, mi); ///对前缀递归排序 quickSort(mi + 1, hi); ///对后缀递归排序 } template <typename T> int Vector<T>::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 } template <typename T> ///无序向量的顺序查找：返回最后一个元素e的位置；失败时，返回lo - 1 Rank Vector<T>::find(T const & e, Rank lo, Rank hi) const { ///assert: 0 <= lo < hi <= _size while ((lo < hi--) && (e != _elem[hi])); ///从后向前，顺序查找 return hi; ///若hi < lo，则意味着失败；否则hi即命中元素的秩 } template <typename T> T Vector<T>::remove(Rank r) { ///删除向量中秩为r的元素，0 <= r < size T e = _elem[r]; ///备份被删除元素 remove(r, r + 1); ///调用区间删除算法，等效于对区间[r, r + 1)的删除 return e; ///返回被删除元素 } template <typename T> int Vector<T>::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; ///返回被删除元素的数目 } template <typename T> ///将e作为秩为r元素插入 Rank Vector<T>::insert(Rank r, T const& e) { ///assert: 0 <= r <= size 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>::deduplicate() { ///删除无序向量中重复元素（高效版） int oldSize = _size; ///记录原规模 Rank i = 1; ///从_elem[1]开始 while (i < _size) ///自前向后逐一考查各元素_elem[i] (find(_elem[i], 0, i) < 0) ? ///在其前缀中寻找与之雷同者（至多一个） i++ : remove(i); ///若无雷同则继续考查其后继，否则删除雷同者 return oldSize - _size; ///向量规模变化量，即被删除元素总数 }/// 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; ///向量规模变化量，即被删除元素总数 } /** @brief 二分查找 * 对有序向量进行二分查找 * */ template<typename T> Rank Vector<T>::binSearch(T const& e,Rank lo,Rank hi)const{ while(lo<hi){///每步迭代仅需做一次判断，有 两个分支 Rank mi=(lo+hi)>>1;///取中间点作为判断条件 (e<_elem[mi])?hi=mi:lo=mi+1;///经过比较后，确定深入[lo,mi)或者[mi+1,hi)中搜索 } return --lo; } template<typenam