0001 constexpr Rank DEFAULT_SIZE = 5; //默认规模（小数值利于充分测试；实际应用中可设为更大）
0002 template <typename T> class Vector { //向量模板类
0003 private:
0004    T* _elem; Rank _capa, _size; //数据区、容量、规模：始终保证_size < _capa，末尾预留一个哨兵
0005    friend struct ComplHeap<T>; //作为向量的友元类，完全二叉堆在第12章的实现将可以简化
0006 protected:
0007    void copy(Rank r, const T* A, Rank lo, Rank hi); //复制区间A[lo,hi)到_elem[r,r-lo+hi)
0008    void expand(Rank d = 1); //若不足以新增d个元素，则扩容
0009    void shrink(); //若装填因子过小，则缩容
0010    void bubbleSort(Rank lo, Rank hi); //起泡排序
0011    Rank getMax(Rank lo, Rank hi); //选取最大元素
0012    void selectionSort(Rank lo, Rank hi); //选择排序
0013    void merge(Rank lo, Rank mi, Rank hi); //二路归并
0014    void mergeSort(Rank lo, Rank hi); //归并排序
0015    void heapSort(Rank lo, Rank hi); //堆排序
0016    Rank partition(Rank lo, Rank hi); //快速划分
0017    void quickSort(Rank lo, Rank hi); //快速排序
0018    void shellSort(Rank lo, Rank hi); //希尔排序
0019 public:
0020    Vector(Rank s = DEFAULT_SIZE) //按预估的规模开出足够大的空间，可减少甚至避免扩容
0021       { _elem = new T[_capa = s+1];  _size = 0; } //末尾预留一个哨兵
0022    Vector(const Vector<T>& V) : Vector(V._elem, 0, V._size) {} //向量整体复制
0023    Vector(const Vector<T>& V, Rank lo, Rank hi) : Vector(V._elem, lo, hi) {} //向量区间复制
0024    Vector(const T* A, Rank lo, Rank hi) : Vector() { insert(0, A, lo, hi); } //数组区间复制
0025    ~Vector() { delete[] _elem; } //析构
0026 //静态操作
0027    Rank size() const { return _size; } //查询规模
0028    bool empty() const { return !_size; } //判空
0029    Rank find(const T& e) const { return find(e, 0, _size); } //无序向量整体查找
0030    Rank find(const T& e, Rank lo, Rank hi) const; //无序向量区间查找
0031    Rank search(const T& e) const { return search(e, 0, _size); } //有序向量整体查找
0032    Rank search(const T& e, Rank lo, Rank hi) const; //有序向量区间查找
0033    Rank select(const Rank k) const { return quickSelect(_elem, _size, k); } //选取第k大元
0034    const T& operator[](Rank r) const { return _elem[r]; } //仅限于右值引用
0035 //动态操作
0036    T& operator[](Rank r) { return _elem[r]; } //模仿数组元素的引用方式
0037    void operator=(const Vector<T>&); //深复制
0038    template <typename VST> void traverse(VST&); //遍历
0039    void insert(Rank r, const T& e); //将e插至[r]
0040    void insert(const T& e) { return insert(_size, e); } //默认作为末元素插入
0041    void insert(Rank r, const T* A, Rank lo, Rank hi); //将A[lo,hi)插至[r]
0042    void insert(Rank r, Vector<T>& S, Rank lo, Rank hi) { insert(r, S._elem, lo, hi); }
0043    void insert(Rank r, Vector<T>& S) { insert(r, S, 0, S._size); } //将S插至[r]
0044    void insert(Vector<T>& S) { insert(_size, S); } //将S续接至末尾
0045    void remove(Rank lo, Rank hi);  T remove(Rank r); //区间删除及单元素删除
0046    T remove() { return remove(_size-1); } //默认删除末元素
0047    void sort(Rank lo, Rank hi);  void sort() { sort(0, _size); } //区间排序及整体排序
0048    void dedup();  void uniquify(); //无序向量、有序向量的去重
0049 }; //Vector