//动态空间管理

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 = oldElem[i]
    }
    delete [] oldElem;
}



//容量递增策略
T* oldElem = _elem;
_elem = new T[_capacity += INCREMENT]

//加倍式扩容
T* oldElem = _elem;
_elem = new T[_capacity <<= 1]

 //分摊分析 amortized complexity

  //深复制和浅复制？



//无序向量

Template <typename T> Vector{};
Vector < int > myVector;
Vector < float > myVector;
Vector < char > myVector;
Vector < BinTree > forest;

//循秩访问
V.get(r);
V.put(r,e);

T & Vector<T>::operator[](Rank r) const {return _elem[r];}

//右值
T x = ...
//左值
V[r] = (T)...

//插入
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>
Rank Vector<T>::find(T const & e, Rank lo, Rank hi) const{
    while ((lo<hi--) && (e!=_elem[hi]));
    return hi;
}

//相邻逆序对
template <typename T>
int Vector<T>::disorder() const{
    int n = 0;
    for (int i = 1; i<_ size; i++)
        n += (_elem[i-1] > _elem[i]);
    return n;
}

//唯一化-低效版
template <typename T> int Vector<T>::uniquify(){
    int oldSize = _size; int i=0;
    while(i < _size-1)
        (_elem[i] == _elem[i+1])? remove(i+1) : 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;
}

//二分查找

template <typename T> //查找算法统一接口
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>
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;
        else if (A[mi]<e) lo=mi+1;
        else return mi;
    }
    return -1;
}

//Fibonacci Search

template <typename T>
static Rank