模板类：
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 ); //复制数组区间A[lo, hi)
void expand(); //空间不足时扩容
void shrink(); //装填因子过小时压缩
bool bubble ( Rank lo, Rank hi ); //扫描交换
void bubbleSort ( Rank lo, Rank hi ); //起泡排序算法
void merge ( Rank lo, Rank mi, Rank hi ); //归并算法
void mergeSort ( 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<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; } //判空
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<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 unsort ( Rank lo, Rank hi ); //对[lo, hi)置乱
void unsort() { unsort ( 0, _size ); } //整体置乱
int deduplicate(); //无序去重
int uniquify(); //有序去重
// 遍历
//void traverse ( void (* ) ( T& ) ); //遍历（使用函数指针，只读或局部性修改）
template <typename VST> void traverse ( VST& ); //遍历（使用函数对象，可全局性修改）
}; //Vector
操作符重载：
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>::copyFrom(T const* A , Rank lo , Rank hi){
//以数组区间A[lo , hi]为蓝本复制向量
_elem = new T[_capacity = 2*(hi - lo)]; //分配空间(留有空闲空间)
_size=0; //规模为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]; //赋值原向量内容（需要重载操作符'='）
delete []oldELem;
}
template <typename T> void Vector<T>::shrink(){
//压缩向量空间
if(_capacity < DEFAULT_CAPACITY << 1) return; //不会收缩至最低以下
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>//无序向量的顺序查找，返回最后一个元素e的位置，失败时返回lo-1
Rank Vector<T>::find(T const& e, Rank lo , Rank hi)const{
while((lo < hi--) && (e != _elem[hi])); //从后向前顺序查找
return hi; //若hi < lo,意味着未查找到，否则hi即命中元素的秩
}
template <typename T>//将元素e 作为秩为r的元素插入
Rank Vector<T>::insert(Rank r , T const& e){
expand(); //判断向量是否满了，满了就扩容
for(int i = _size ; i > r ; i--)
//自后向前，一直移动到r这个位置
_elem[i] = _elem[i-1];
_elem[r] = e; _size++; //更新向量当前容量
return r ; //返回秩
}
template <typename T> void Vector<T>::unsort(Rank lo , Rank hi){
//随机置乱向量区间lo 到 hi 之间的_elem
T* v = _elem + lo ; //指针从 lo 开始, v[0]是原来的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>//删除区间[lo ,hi) ,返回被删掉的元素数
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>//删除秩为r的那个向量 ,返回被删掉的元素数
T Vector<T>::remove(Rank r){
T e = _elem[r]; //备份被删的元素
remove(r,r+1); //调用区间删除方法
return e; //返回被删除元素
}
template <typename T>//删除无序向量中的重复元素
int Vector<T>::deduplicate(){
int oldside = _size; // 保存原始容量值
Rank i = 1; //从_elem[1]开始
while(i < _size) //自前向后逐一考察各个元素
(find(_elem[i],0,i) < 0)? // 保证前i个元素没有重复的
i++ : remove(i); //无雷同则继续遍历，有则删除后再遍历
return oldside - _size; //返回向量规模
}
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]);
}
template <typename T> int Vector<T>::disordered() const{
//返回向量中逆序相邻元素对的总数
int n = 0; //计数器
for(int i = 1 ; i < _size-1 ; i++) //逐一检查_size-1对相邻元素
if(_elem[i-1] > _elem[i]) n++; //逆序则计数
return n; // 向量有序当且仅当n = 0
}
template <typename T> int Vector<T>::uniquify(){
//有序向量重复元素剔除算法（高效版）
Rank i = 0 ; Rank j = 0; // 各对互异相邻的元素秩
while(++j < _size){
if(_elem[i] != _elem[j]) //跳过雷同的
_elem[++i] = _elem[j]; //发现不同元素时，将此时j下标的元素移动到i+1的位置上
}
_size = ++i; shrink(); //最后i要加1，然后缩向量
return j-i; //返回被删去的元素数
}
//**********************************************************************
// //二分查找算法版本A，在有序向量[lo,hi)内查找元素e
// template <typename T> 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 , mi) 继续查找
// else if(e > A[mi]) lo = mi ; // 深入后半段[mi , hi) 继续查找
// else return mi; //返回该元素的秩
// }
// return -1 ; // 表示未找到
// }
// //缺点： 有多个命中时，不能保证返回秩最大者，查找失败时，简单的返回-1，而不能指示失败的位置
// //二分查找版本B
// template <typename T> static Rank binSearch(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 ; //比较确定下一次查找范围
// }//出口时hi = lo+1 查找区间仅剩下A[lo]
// return (0 == A[lo]) ? lo : -1;
// }//有多个命中时，不能保证返回秩最大者，查找失败时，简单的返回-1，而不能指示失败的位置
//二分查找版本c
template <typename T> static Rank binSearch(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 ; //经比较后确定深入[lo,mi)和(mi,hi)
}//成功查找不能提前停止
return --lo;
}
//循环结束，lo为大于e的元素最小的秩，不管是有还是没有
//有多个命中时，能保证返回秩最大者，查找失败时，能指示比e小一点点的元素位置
//*************************************************************************
template <typename T> //在有序向量[lo,hi)中，确定不大于e 的最后一个结点的秩
Rank Vector<T>::search(T const& e ,Rank lo , Rank hi)const{
return (rand()%2)?
//二分查找或者斐波那契查找
binSearch(_elem ,e,lo,hi) : fibSearch(_elem,e,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>::bubbleSort(Rank lo , Rank hi){
while( !bubble(lo , hi--));
}
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){
if (hi - lo < 2) return; //一直分治到单元素区间，此时自然顺序
int mi = (lo + hi) >>1; // 找到中轴点
mergeSort(lo,mi); mergeSort(mi,hi); merge(lo,mi,hi); //分治，然后归并
}
