模板類：

typedef int Rank; //秩
#define DEFAULT_CAPACITY  3 //默認(rèn)的初始容量（實(shí)際應(yīng)用中可設(shè)置為更大）

template <typename T> class Vector { //向量模板類
protected:
   Rank _size; int _capacity;  T* _elem; //規(guī)模、容量、數(shù)據(jù)區(qū)
   void copyFrom ( T const* A, Rank lo, Rank hi ); //復(fù)制數(shù)組區(qū)間A[lo, hi)
   void expand(); //空間不足時(shí)擴(kuò)容
   void shrink(); //裝填因子過(guò)小時(shí)壓縮
   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:
// 構(gòu)造函數(shù)
   Vector ( int c = DEFAULT_CAPACITY, int s = 0, T v = 0 ) {
   //容量為c、規(guī)模為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 ); } //數(shù)組整體復(fù)制
   Vector ( T const* A, Rank lo, Rank hi ) { copyFrom ( A, lo, hi ); } //區(qū)間
   Vector ( Vector<T> const& V ) { copyFrom ( V._elem, 0, V._size ); } //向量整體復(fù)制
   Vector ( Vector<T> const& V, Rank lo, Rank hi ) { copyFrom ( V._elem, lo, hi ); } //區(qū)間
// 析構(gòu)函數(shù)
   ~Vector() { delete [] _elem; } //釋放內(nèi)部空間
// 只讀訪問(wèn)接口
   Rank size() const { return _size; } //規(guī)模
   bool empty() const { return !_size; } //判空
   int disordered() const; //判斷向量是否已排序
   Rank find ( T const& e ) const { return find ( e, 0, _size ); } //無(wú)序向量整體查找
   Rank find ( T const& e, Rank lo, Rank hi ) const; //無(wú)序向量區(qū)間查找
   Rank search ( T const& e ) const //有序向量整體查找
   { return ( 0 >= _size ) ? -1 : search ( e, 0, _size ); }
   Rank search ( T const& e, Rank lo, Rank hi ) const; //有序向量區(qū)間查找
// 可寫訪問(wèn)接口
   T& operator [] ( Rank r ) const; //重載下標(biāo)操作符，可以類似于數(shù)組形式引用各元素
   Vector<T>& operator = ( Vector<T> const& ); //重載賦值操作符，以便直接克隆向量
   T remove ( Rank r ); //刪除秩為r的元素
   int remove ( Rank lo, Rank hi ); //刪除秩在區(qū)間[lo, hi)之內(nèi)的元素
   Rank insert ( Rank r, T const& e ); //插入元素
   Rank insert ( T const& e ) { return insert ( _size, e ); } //默認(rèn)作為末元素插入
   void unsort ( Rank lo, Rank hi ); //對(duì)[lo, hi)置亂
   void unsort() { unsort ( 0, _size ); } //整體置亂
   int deduplicate(); //無(wú)序去重
   int uniquify(); //有序去重
// 遍歷
//void traverse ( void (* ) ( T& ) ); //遍歷（使用函數(shù)指針，只讀或局部性修改）
template <typename VST> void traverse ( VST& ); //遍歷（使用函數(shù)對(duì)象，可全局性修改）
}; //Vector

操作符重載：

template <typename T> Vector<T>& Vector<T>::operator = (Vector<T> const &v){
    //重載操作符
    if(_elem) delete []_elem; //如果非空，釋放原有內(nèi)容
    copyFrom(v._elem , 0 , v._size); // 整體復(fù)制
    return *this; //返回當(dāng)前對(duì)象的引用
}

template <typename T>T& Vector<T>::operator [](Rank r)const{
    //重載中括號(hào)
    return _elem[r];
}

方法實(shí)現(xiàn)：

template <typename T> //元素類型
void Vector<T>::copyFrom(T const* A , Rank lo , Rank hi){
    //以數(shù)組區(qū)間A[lo , hi]為藍(lán)本復(fù)制向量
    _elem = new T[_capacity = 2*(hi - lo)]; //分配空間(留有空閑空間)
    _size=0; //規(guī)模為0
    while(lo < hi) //A[lo,hi]中的元素逐一遍歷
        _elem[_size++] = A[lo++]; //復(fù)制至_elem[0,hi-lo] 
}

template <typename T> void Vector<T>::expand(){//向量空間不足時(shí)擴(kuò)容
    if(_size < _capacity) return; //尚未滿，不用擴(kuò)容
    if(_capacity < DEFAULT_CAPACITY) _capacity = DEFAULT_CAPACITY;//不低于最小容量，擴(kuò)容時(shí)好像不需要
    T* oldELem = _elem; _elem = new T[_capacity <<= 1];//容量加倍
    for(int i = 0 ; i < _size ; i++)
        _elem[i] = oldELem[i]; //賦值原向量?jī)?nèi)容（需要重載操作符'='）
    delete []oldELem;  
}

template <typename T> void Vector<T>::shrink(){
    //壓縮向量空間
    if(_capacity < DEFAULT_CAPACITY << 1) return; //不會(huì)收縮至最低以下
    if(_size << 2 > _capacity) return; //內(nèi)容大于25% 不縮容
    T* oldELem = _elem; _elem = new T[_capacity >>= 1]; //容量減半
    for(int i = 0 ; i < _size ; i++)
        _elem[i] =  oldELem[i]; //復(fù)制原向量?jī)?nèi)容
    delete []oldELem; //釋放空間
}


template <typename T>//無(wú)序向量的順序查找，返回最后一個(gè)元素e的位置，失敗時(shí)返回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(); //判斷向量是否滿了，滿了就擴(kuò)容
    for(int i = _size ; i > r ; i--)
        //自后向前，一直移動(dòng)到r這個(gè)位置
        _elem[i] = _elem[i-1];
    _elem[r] = e; _size++; //更新向量當(dāng)前容量
    return r ; //返回秩 
}

template <typename T> void Vector<T>::unsort(Rank lo , Rank hi){
    //隨機(jī)置亂向量區(qū)間lo 到 hi 之間的_elem
    T* v = _elem  + lo ;  //指針從 lo 開始, v[0]是原來(lái)的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>//刪除區(qū)間[lo ,hi) ,返回被刪掉的元素?cái)?shù)
int Vector<T>::remove(Rank lo , Rank hi){
    if(lo == hi) return 0; //沒(méi)有刪掉任何元素
    while(hi < _size)
        _elem[lo++] = _elem[hi++]; //把后面的不刪的元素往刪元素的區(qū)間挪
    _size = lo ;//更新現(xiàn)在的向量容量
    shrink();//如有必要縮容
    return hi-lo; //返回刪了多少個(gè)
}

template <typename T>//刪除秩為r的那個(gè)向量 ,返回被刪掉的元素?cái)?shù)
T Vector<T>::remove(Rank r){
    T e = _elem[r]; //備份被刪的元素
    remove(r,r+1); //調(diào)用區(qū)間刪除方法
    return e; //返回被刪除元素
}


template <typename T>//刪除無(wú)序向量中的重復(fù)元素
int Vector<T>::deduplicate(){
    int oldside = _size; // 保存原始容量值
    Rank i = 1; //從_elem[1]開始
    while(i < _size) //自前向后逐一考察各個(gè)元素
        (find(_elem[i],0,i) < 0)? // 保證前i個(gè)元素沒(méi)有重復(fù)的
        i++ : remove(i); //無(wú)雷同則繼續(xù)遍歷，有則刪除后再遍歷
    return oldside - _size; //返回向量規(guī)模
}

template <typename T> void Vector<T>::traverse(void (*visit)(T&))
{   //利用函數(shù)指針機(jī)制的遍歷
    for(int i = 0 ; i <_size ;i++) visit(_elem[i]);
}

template <typename T> template <typename VST> //元素類型 ，操作器
void Vector<T>::traverse(VST& visit)
{//利用函數(shù)對(duì)象機(jī)制的遍歷
    for(int i = 0 ; i < _size ; i++ )
        visit(_elem[i]);
}


template <typename T> int Vector<T>::disordered() const{
    //返回向量中逆序相鄰元素對(duì)的總數(shù)
    int n = 0; //計(jì)數(shù)器
    for(int i = 1 ; i < _size-1 ; i++) //逐一檢查_size-1對(duì)相鄰元素
        if(_elem[i-1] > _elem[i]) n++; //逆序則計(jì)數(shù)
    return n; // 向量有序當(dāng)且僅當(dāng)n = 0
}

template <typename T> int Vector<T>::uniquify(){
    //有序向量重復(fù)元素剔除算法（高效版）
    Rank i = 0 ; Rank j = 0; // 各對(duì)互異相鄰的元素秩
    while(++j < _size){
        if(_elem[i] != _elem[j]) //跳過(guò)雷同的
            _elem[++i] = _elem[j]; //發(fā)現(xiàn)不同元素時(shí)，將此時(shí)j下標(biāo)的元素移動(dòng)到i+1的位置上
}
        _size = ++i; shrink(); //最后i要加1，然后縮向量
        return j-i; //返回被刪去的元素?cái)?shù)
}

//**********************************************************************


// //二分查找算法版本A，在有序向量[lo,hi)內(nèi)查找元素e
// template <typename T> static Rank binSearch(T* A , T const& e, Rank lo , Rank hi){
//  while(lo < hi){ //每步迭代可能要做兩次比較判斷，有三個(gè)分支
//      Rank mi = (lo + hi)>>1; // 以中點(diǎn)為軸點(diǎn)
//      if (e < A[mi]) hi = mi;//深入前半段[lo , mi) 繼續(xù)查找
//      else if(e > A[mi]) lo = mi ; // 深入后半段[mi , hi) 繼續(xù)查找
//      else return mi; //返回該元素的秩
//   }
//   return -1 ; // 表示未找到
// }
// //缺點(diǎn)： 有多個(gè)命中時(shí)，不能保證返回秩最大者，查找失敗時(shí)，簡(jiǎn)單的返回-1，而不能指示失敗的位置

// //二分查找版本B 
// template <typename T> static Rank binSearch(T* A , T const& e, Rank lo , Rank hi){
//  while (1 < hi - lo){  // 每一步迭代僅需做一次計(jì)較判斷，有兩個(gè)分支，成功查找不能提前停止
//      Rank mi = (lo + hi)>>1 //中點(diǎn)為軸點(diǎn)
//      (e < A[mi]) ? hi = mi : lo = mi ; //比較確定下一次查找范圍
//  }//出口時(shí)hi = lo+1 查找區(qū)間僅剩下A[lo]
//  return (0 == A[lo]) ? lo : -1;
// }//有多個(gè)命中時(shí)，不能保證返回秩最大者，查找失敗時(shí)，簡(jiǎn)單的返回-1，而不能指示失敗的位置

//二分查找版本c 
template <typename T> static Rank binSearch(T* A , T const& e, Rank lo , Rank hi){
    while(lo < hi){ // 每一步迭代僅需做一次計(jì)較判斷，有兩個(gè)分支
        Rank mi = (lo + hi)>>1 //中點(diǎn)為軸點(diǎn)
        (e < A[mi]) ? hi = mi : lo = mi + 1 ; //經(jīng)比較后確定深入[lo,mi)和(mi,hi) 
    }//成功查找不能提前停止
return --lo;
}
 //循環(huán)結(jié)束，lo為大于e的元素最小的秩，不管是有還是沒(méi)有
     //有多個(gè)命中時(shí)，能保證返回秩最大者，查找失敗時(shí)，能指示比e小一點(diǎn)點(diǎn)的元素位置


//*************************************************************************


template <typename T> //在有序向量[lo,hi)中，確定不大于e 的最后一個(gè)結(jié)點(diǎn)的秩
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; //整體有序的標(biāo)志
    while( ++lo < hi){ //自左向右逐一檢查相鄰元素
        if ( _elem[lo-1] > _elem[lo]){ //若存在逆序
            sorted = false; //表示此時(shí)尚未排好序
            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++]);//復(fù)制前子向量,只有前面的有必要復(fù)制，有被覆蓋的風(fēng)險(xiǎn)
    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]中的小者續(xù)至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; //釋放臨時(shí)空間B
} // 歸并后得到完整的有序向量 lo,hi



//分治策略
template <typename T> //有序向量的歸并排序
void Vector<T>::mergeSort(Rank lo , Rank hi){
    if (hi - lo < 2) return; //一直分治到單元素區(qū)間，此時(shí)自然順序
    int mi = (lo + hi) >>1; // 找到中軸點(diǎn)
    mergeSort(lo,mi); mergeSort(mi,hi); merge(lo,mi,hi); //分治，然后歸并
}