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