Vector

1.模板参数T指定向量元素类型
2.向量结构在内部维护一个元素类型为T的私有数组_elem[]，容量由_capacity指示，有效元素数量由变量_size指示。
3.构造方法：默认构造方法、基于复制的构造方法
4.析构方法：释放数组_elem[]
5.静态空间管理：_size/_capacity装填因子不超过1也不太接近0
6.扩容、缩容算法：insert函数调用expand函数，若当前数据区满，将原数组替换成更大的数组，remove 函数调用shrink函数，若当前数据量*2<容量，将容量减半。
7.对向量元素访问沿用数组方式，重载操作符[]。
8.置乱算法：使元素等概率出现在各位置
9.查找算法：无序查找、有序查找
10.去重算法：无需向量去重、有序向量去重
11.排序算法：归并排序、选择排序、起泡排序

#pragma onceusing Rank = int; //秩
#define DEFAULT_CAPACITY  3 //默认的初始容量（实际应用中可设置为更大）template <typename T> class Vector { //向量模板类
protected:Rank _size; Rank _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 maxItem ( Rank lo, Rank hi ); //选取最大元素void selectionSort ( Rank lo, Rank hi ); //选择排序算法void merge ( Rank lo, Rank mi, Rank hi ); //归并算法void mergeSort ( Rank lo, Rank hi ); //归并排序算法void heapSort ( Rank lo, Rank hi ); //堆排序（稍后结合完全堆讲解）Rank partition ( Rank lo, Rank hi ); //轴点构造算法void quickSort ( Rank lo, Rank hi ); //快速排序算法void shellSort ( Rank lo, Rank hi ); //希尔排序算法
public:
// 构造函数//默认构造方法Vector ( int c = DEFAULT_CAPACITY, Rank s = 0, T v = 0 ) //容量为c、规模为s、所有元素初始为v{ _elem = new T[_capacity = c]; for ( _size = 0; _size < s; _elem[_size++] = v ); } //s<=cVector ( 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; } //判空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 T& operator[] ( Rank r ) const; //仅限于做右值的重载版本Vector<T> & operator= ( Vector<T> const& ); //重载赋值操作符，以便直接克隆向量T remove ( Rank r ); //删除秩为r的元素int remove ( Rank lo, Rank hi ); //删除秩在区间[lo, hi)之内的元素Rank insert ( Rank r, T const& e ); //插入元素Rank insert ( T const& e ) { return insert ( _size, e ); } //默认作为末元素插入void sort ( Rank lo, Rank hi ); //对[lo, hi)排序void sort() { sort ( 0, _size ); } //整体排序void unsort ( Rank lo, Rank hi ); //对[lo, hi)置乱void unsort() { unsort ( 0, _size ); } //整体置乱Rank deduplicate(); //无序去重Rank uniquify(); //有序去重
// 遍历void traverse ( void (* ) ( T& ) ); //遍历（使用函数指针，只读或局部性修改）template <typename VST> void traverse ( VST& ); //遍历（使用函数对象，可全局性修改）
}; //Vectortemplate <typename T> //T为基本类型，或已重载赋值操作符'='
void Vector<T>::copyFrom ( T const* A, Rank lo, Rank hi ) { //以数组区间A[lo, hi)为蓝本复制向量_elem = new T[ _capacity = 2 * ( hi - lo ) ]; //分配空间，双倍容量for (_size = 0; lo < hi; _size++, lo++ ) //A[lo, hi)内的元素逐一_elem[ _size ] = A[ lo ]; //复制至_elem[0, hi - lo)
} //用const修饰，保证A中的元素不致被篡改；运行时间 = O(hi-lo)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> void Vector<T>::expand() { //向量空间不足时扩容if ( _size < _capacity ) return; //尚未满员时，不必扩容if ( _capacity < DEFAULT_CAPACITY ) _capacity = DEFAULT_CAPACITY; //不低于最小容量T* oldElem = _elem;  _elem = new T[_capacity <<= 1]; //容量加倍for ( Rank i = 0; i < _size; i++ )_elem[i] = oldElem[i]; //复制原向量内容（T为基本类型，或已重载赋值操作符'='）delete [] oldElem; //释放原空间
}template <typename T> //将e作为秩为r元素插入
Rank Vector<T>::insert ( Rank r, T const& e ) { //assert: 0 <= r <= sizeexpand(); //若有必要，扩容for ( Rank i = _size; r < i; i-- ) //自后向前，后继元素_elem[i] = _elem[i-1]; //顺次后移一个单元_elem[r] = e; _size++; //置入新元素并更新容量return r; //返回秩
}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 ( Rank i = 0; i < _size; i++ ) _elem[i] = oldElem[i]; //复制原向量内容delete [] oldElem; //释放原空间
}template <typename T> int Vector<T>::remove ( Rank lo, Rank hi ) { //删除区间[lo, hi)if ( lo == hi ) return 0; //出于效率考虑，单独处理退化情况，比如remove(0, 0)while ( hi < _size ) //区间[hi, _size)_elem[lo++] = _elem[hi++]; //顺次前移hi - lo个单元_size = lo; //更新规模，直接丢弃尾部[lo, _size = hi)区间shrink(); //若有必要，则缩容return hi - lo; //返回被删除元素的数目
}template <typename T> T & Vector<T>::operator[] ( Rank r ) //重载下标操作符
{ return _elem[r]; } // assert: 0 <= r < _sizetemplate <typename T> void Vector<T>::unsort ( Rank lo, Rank hi ) { //等概率随机置乱区间[lo, hi)T* V = _elem + lo; //将子向量_elem[lo, hi)视作另一向量V[0, hi - lo)for ( Rank i = hi - lo; i > 0; i-- ) //自后向前swap ( V[i - 1], V[rand() % i] ); //将V[i - 1]与V[0, i)中某一元素随机交换
}
template <typename T> //无序向量的顺序查找：返回最后一个元素e的位置；失败时，返回lo - 1
Rank Vector<T>::find ( T const& e, Rank lo, Rank hi ) const { //assert: 0 <= lo < hi <= _sizewhile ( ( lo < hi-- ) && ( e != _elem[hi] ) ); //从后向前，顺序查找return hi; //若hi < lo，则意味着失败；否则hi即命中元素的秩
}
template <typename T> //在有序向量的区间[lo, hi)内，确定不大于e的最后一个节点的秩
Rank Vector<T>::search ( T const& e, Rank lo, Rank hi ) const { //assert: 0 <= lo < hi <= _sizereturn ( rand() % 2 ) ? //按各50%的概率随机使用二分查找或Fibonacci查找binSearch ( _elem, e, lo, hi ) : fibSearch ( _elem, e, lo, hi );
}
template <typename T> Rank Vector<T>::deduplicate() { //删除无序向量中重复元素Rank oldSize = _size; //记录原规模for ( Rank i = 1; i < _size; ) //自前向后逐个考查_elem[1,_size)if ( find(_elem[i], 0, i) < 0 ) //在前缀[0,i)中寻找与之雷同者（至多一个）i++; //若无雷同则继续考查其后继elseremove(i); //否则删除当前元素return oldSize - _size; //被删除元素总数
}
template <typename T> Rank 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> void Vector<T>::traverse ( void ( *visit ) ( T& ) ) //借助函数指针机制
{ for ( Rank i = 0; i < _size; i++ ) visit ( _elem[i] ); } //遍历向量template <typename T> template <typename VST> //元素类型、操作器
void Vector<T>::traverse ( VST& visit ) //借助函数对象机制
{ for ( Rank i = 0; i < _size; i++ ) visit ( _elem[i] ); } //遍历向量// 二分查找算法 ：在有序向量的区间[lo, hi)内查找元素e，0 <= lo <= hi <= _size
template <typename T> static Rank binSearch ( T* S, T const& e, Rank lo, Rank hi ) {while ( lo < hi ) { //每步迭代仅需做一次比较判断，有两个分支Rank mi = ( lo + hi ) >> 1; //以中点为轴点（区间宽度的折半，等效于宽度之数值表示的右移）( e < S[mi] ) ? hi = mi : lo = mi + 1; //经比较后确定深入[lo, mi)或(mi, hi)} //成功查找不能提前终止return lo - 1; //循环结束时，lo为大于e的元素的最小秩，故lo - 1即不大于e的元素的最大秩
} //有多个命中元素时，返回秩最大者；查找失败时，能够返回失败的位置template <typename T> void Vector<T>::sort ( Rank lo, Rank hi ) { //向量区间[lo, hi)排序switch ( rand() % 6 ) {case 1:  bubbleSort ( lo, hi ); break; //起泡排序case 2:  selectionSort ( lo, hi ); break; //选择排序case 3:  mergeSort ( lo, hi ); break; //归并排序case 4:  heapSort ( lo, hi ); break; //堆排序case 5:  quickSort ( lo, hi ); break; //快速排序default: shellSort ( lo, hi ); break; //希尔排序} //随机选择算法以充分测试。实用时可视具体问题的特点灵活确定或扩充
}
template <typename T> //向量的起泡排序（跳跃版）
void Vector<T>::bubbleSort( Rank lo, Rank hi ) { //assert: 0 <= lo < hi <= sizefor( Rank last = --hi; lo < hi; hi = last )for( Rank i = last = lo; i < hi; i++ )if( _elem[i] > _elem[i + 1] ) //若逆序，则swap( _elem[ last = i ], _elem[ i + 1 ] ); //经交换使局部有序
}
template <typename T> //向量选择排序
void Vector<T>::selectionSort ( Rank lo, Rank hi ) { //0 <= lo < hi <= sizewhile ( lo < --hi )swap ( _elem[ maxItem ( lo, hi ) ], _elem[ hi ] ); //将[hi]与[lo, hi]中的最大者交换
}template <typename T>
Rank Vector<T>::maxItem ( 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>::mergeSort ( Rank lo, Rank hi ) { //0 <= lo < hi <= sizeif ( hi - lo < 2 ) return; //单元素区间自然有序，否则...Rank mi = ( lo + hi ) / 2; //以中点为界mergeSort ( lo, mi ); mergeSort ( mi, hi ); //分别排序merge ( lo, mi, hi ); //归并
}