1 #ifndef  VECTOR_H  2 #define  VECTOR_H  3   4 #include <algorithm>  5   6 template<typename Object>  7 class  Vector  8 {  9 private: 10     int theSize;                         //实际数据大小 11     int theCapacity;                     //实际容器容量大小 12     Object *objects;                     //基本数组 13 public: 14     enum { SPACE_CAPACITY = 16 };        //默认容量大小 15      16     explicit Vector(int initSize = 0)    //单参数构造函数要用explicit()避免类型在后台转换 17         : theSize(initSize), theCapacity(initSize + SPACE_CAPACITY) { 18         objects = new Object[theCapacity]; 19     } 20     Vector(const Vector& rhs) : objects(NULL) {    //复制构造函数--调用operator=对已有的Vector进行复制 21         operator = (rhs); 22     } 23     ~Vector() { 24         delete[] objects; 25     } 26  27     const Vector& operator = (const Vector& rhs) //重载赋值运算符 28     { 29         if (this != &rhs)                        //避免复制自身--混淆检验 30         { 31             delete []objects;                    //删除旧的内存空间 32             theSize = rhs.size();                //生成同样的样本大小 33             theCapacity = rhs.theCapacity;       //生成同样的容量大小 34  35             objects = new Object[capacity()];    //生成与所复制的Vector同样容量的新数组 36             for (int k = 0; k < size(); k++) 37                 objects[k] = rhs.objects[k];  38         } 39         return *this; 40     } 41      42     void resize(int newSize) 43     { 44         if (newSize > theCapacity)        //重置大小 45             reserve(newSize * 2 + 1);     //新大小 46         theSize = newSize; 47     } 48  49     //扩容 50     void reserve(int newCapacity) 51     { 52         if (newCapacity < theSize)        //至少和（样本大小）一样大 53             return; 54  55         Object *oldArray = objects;       //oldArray--用于复制旧数组内容 56         objects = new Object[newCapacity]; 57         for (int k = 0; k < theSize; k++) 58             objects[k] = oldArray[k]; 59                      60         theCapacity = newCapacity; 61         delete []oldArray; 62     } 63  64     Object& operator[] (int index) 65     { 66         return objects[index]; 67     } 68     const Object& operator[] (int index) const 69     { 70         return objects[index]; 71     } 72  73     bool empty() const { 74         return size() == 0; 75     } 76      77     int size() const { 78         return theSize; 79     } 80     int capacity() const { 81         return theCapacity; 82     } 83     //在数据尾端插入元素 84     void push_back(const Object& x) { 85         if (theSize == theCapacity) 86             reserve(2 * theCapacity + 1); 87         objects[theSize++] = x; 88     } 89  90     //在index位置前端插入数据data 91     void insert(int index, const Object& data) { 92         if (theSize == theCapacity) 93             reserve(2 * theCapacity + 1); 94         for (int i = theSize; i >= index; i--) { 95             objects[i] = objects[i - 1]; 96         } 97         objects[index] = data; 98         theSize++; 99     }100 101     void pop_back() {102         theSize--;103     }104 105     //区间删除 [lo, hi)  --- 左闭右开！！ --- 删除索引从 1,2..k106     int remove(int lo, int hi) {107         if (lo == hi) return 0;108         while (hi < theSize) {109             objects[lo++] = objects[hi++];      //[hi,theSize)顺次前移 hi-lo 位110         }111         theSize = lo;112         return hi - lo;                         //返回被删除元素数目113     }114     //重载删除一个指定位置元素--删除r位置元素，[r,r+1). 如果先写删除单个元素函数，删除区间时会低效.115     Object remove(int r) {116         Object oldElem = objects[r];117         remove(r, r + 1);                   118         return oldElem;                         //返回删除的元素119     }120 121     //order the vector122     //二分查找--有序向量123     int Search(Object &elem, int lo, int hi) {124         while (lo < hi) {        //不变性: A[0,lo) <= e < A[hi,n)125             int mid = (lo + hi) >> 1;                 // 以中点为轴126             (elem < objects[mid]) ? hi = mid : lo = mid + 1; // [lo,mi) 或 (mi,hi)127         }                                             // 出口时,A[lo = hi]为大于elem的最小元素128         return --lo;                                  // lo-1即为不大于elem的元素的最大秩129     }130 131     /*mergesort()归并排序132     /*无序向量的递归分解，两个有序的子序列合成大的子序列*/133     void mergeSort(int lo, int hi) {134         if (hi - lo < 2) return;135         int mid = (lo + hi) >> 1;136         mergeSort(lo, mid);                           //对前半段排序137         mergeSort(mid, hi);                           //对后半段排序138         merge(lo, mid, hi);                            //归并139     }140      141     //归并---O(nlogn), T(n) = 2T(n/2) + O(n)142     void merge(int lo, int mid, int hi) {143         //A用来存放合并后的向量，B，C进行比较(前后子向量比较)144         Object *A = objects + lo;          //合并后的向量A[0,hi-lo) = objects[lo,hi)145         int lb = mid - lo;146         Object *B = new Object[lb];        //前子向量 B[0,lb) = objects[lo,mi)147         for (int i = 0; i < lb; B[i] = A[i++]);   //复制前子向量148         int lc = hi - mid;149         Object *C = objects + mid;         //后子向量150         for (int i = 0, j = 0, k = 0; (j < lb || k < lc);) {151             //B[i], C[k]中小者转至A的末尾.        152             //因为C本来就占据A中，不需要考虑提前耗尽情况153             if ((j < lb) && (k >= lc || C[k] >= B[j]))      //C[k]已无或不小154                 A[i++] = B[j++];155             if ((k < lc) && (j >= lb || B[j] >= C[k]))      //B[k]已无或不小156                 A[i++] = C[k++];157         }158         delete []B;159     }160 161     //有序向量的去重, 重复的元素必定紧邻,每个区间只保留单个---每次常数，累计O(n)162     int uniquify() {163         int i = 0, j = 0;            //各对互异,"相邻"元素的秩,逐一扫描,直至末元素164         while (++j < theSize) {165             //跳过雷同者,发现不同元素时，向前移至紧邻元素166             if (objects[i] != objects[j]) objects[++i] = objects[j];167         }168         theSize = ++i; 169         return j - i;                //返回被删除元素总数170     }171 172 173     //得到尾元素174     const Object& back() const {175         return objects[theSize - 1];176     }177     178     typedef Object * iterator;179     typedef const Object * const_iterator;180 181     iterator begin() {182         return &objects[0];183     }184     const_iterator begin() const {185         return &objects[0];186     }187     iterator end() {               //尾后的不存在的指针188         return &objects[size()];     189     }190     const_iterator end() const {191         return &objects[size()];192     }193 194 };195 196 197 198 #endif // VECTOR_H

  1 /************************************************************************/  2 /* Vs2013, c++11标准编写      测试vector.h                                */  3 /************************************************************************/  4 #include <iostream>  5 #include <cstring>  6 #include "Vector.h"  7 using namespace std;  8   9 int test[100] = { 0 }; 10  11 void Merge(int *test, int lo, int mid, int hi); 12 void MergeSort(int *test, int lo, int hi) { 13     if (hi - lo < 2) return; 14     int mid = (lo + hi) >> 1; 15     MergeSort(test, lo, mid);                           //对前半段排序 16     MergeSort(test, mid, hi);                           //对后半段排序 17     Merge(test, lo, mid, hi);                            //归并 18 } 19  20 //归并---O(nlogn), T(n) = 2T(n/2) + O(n) 21 void Merge(int *test, int lo, int mid, int hi) { 22     //A用来存放合并后的向量，B，C进行比较(前后子向量比较) 23     int  *A = test + lo;          //合并后的向量A[0,hi-lo) = int s[lo,hi) 24     int lb = mid - lo; 25     int  *B = new int [lb];        //前子向量 B[0,lb) = int s[lo,mi) 26     for (int i = 0; i < lb; B[i] = A[i++]);   //复制前子向量 27     int lc = hi - mid; 28     int  *C = test + mid;         //后子向量 29     for (int i = 0, j = 0, k = 0; (j < lb || k < lc);) { 30         //B[i], C[k]中小者转至A的末尾.         31         //因为C本来就占据A中，不需要考虑提前耗尽情况 32         if ((j < lb) && (k >= lc || C[k] >= B[j]))      //C[k]已无或不小 33             A[i++] = B[j++]; 34         if ((k < lc) && (j >= lb || B[j] >= C[k]))      //B[k]已无或不小 35             A[i++] = C[k++]; 36     } 37     delete[]B; 38 } 39  40  41 int main() 42 { 43     //用来测试 非模板写的 归并排序 算法 44     /*int Test[13] = { 1, 5, 2, 3, 6, 8, 9, 10, 13, 12, 4, 7, 11 }; 45     MergeSort(Test, 0, 13); 46     for (int i = 0; i < 13; i++) 47     cout << Test[i] << " "; 48     cout << endl;*/ 49  50     Vector<int> testOne; 51     int testData, cnt, index; 52     cout << "输入数字数目: "; 53     cin >> cnt; 54     cout << "输入 " << cnt << "个数: "; 55     while (cnt-- && cin >> testData) 56     { 57         testOne.push_back(testData); 58     } 59  60     cout << "显示所有元素: "; 61     for (int i = 0; i < testOne.size(); i++) { 62         cout << testOne[i] << " "; 63     } 64     cout << endl; 65      66     cout << "\n输入插入元素位置(0...k)和插入的数值: "; 67     cin >> index >> testData; 68     testOne.insert(index, testData); 69     cout << "显示所有元素: "; 70     for (int i = 0; i < testOne.size(); i++) { 71         cout << testOne[i] << " "; 72     } 73     cout << endl; 74  75     cout << "\n输入删除元素位置(0...k): "; 76     cin >> index; 77     testOne.remove(index); 78     cout << "显示所有元素: "; 79     for (int i = 0; i < testOne.size(); i++) { 80         cout << testOne[i] << " "; 81     } 82     cout << endl; 83      84     cout << "\n归并排序向量元素: \n"; testOne.mergeSort(0, testOne.size()); 85     cout << "显示所有元素: "; 86     for (int i = 0; i < testOne.size(); i++) { 87         cout << testOne[i] << " "; 88     } 89     cout << endl; 90  91     cout << "\n(有序向量)(二分查找:)输入查找元素: "; 92     cin >> testData; 93     cout << "查找位置返回(不大于查找元素的最大的秩): " 94         << testOne.Search(testData, 0, testOne.size()) << endl; 95  96     cout << "\n(有序向量)去除重复元素: \n"; testOne.uniquify(); 97     cout << "显示所有元素: "; 98     for (int i = 0; i < testOne.size(); i++) { 99         cout << testOne[i] << " ";100     }101     cout << endl;102 103     return 0;104 105 }