首页 > 代码库 > 浅谈动态数组原理及其实现
浅谈动态数组原理及其实现
<style></style>
stl中的vector是竞赛中常用的容器，原因在于省内存，O(1)在后端插入和删除、随机下标访问，今天就来谈谈它的实现。
最简单的一个动态数组
动态数组并不是真正意义上的动态的内存，而是一块连续的内存，当添加新的元素时，容量已经等于当前的大小的时候(存不下了)，执行下面3步
- 重新开辟一块大小为当前容量两倍的数组
- 把原数据拷贝过去
- 释放掉旧的数组
完事后再把这个元素加在后面。
那么你一定会很好奇，它为什么会是O(1)。这个是均摊下来的结果，我们只需要证明总共拷贝的元素个数是O(n)级别的就好了(因为释放内存和申请内存都比较快，详情自行百度吧)。
总共拷贝的元素个数是
,根据等比数列求和公式那么有
。因为
,所以
,所以有
。因此总共拷贝的元素个数是O(n)级别，均摊下来，每次在尾部插入的时间复杂度就是O(1)。
1 #include<iostream> 2 #include<malloc.h> 3 using namespace std; 4 5 template<typename T> 6 class Vector { 7 protected: 8 int cap; 9 int siz;10 T* l;11 public:12 Vector():l(NULL), cap(0), siz(0) { }13 14 inline void push_back(T x) {15 if(l == NULL) {16 l = new T[4];17 cap = 4, siz = 0;18 }19 if(siz == cap) {20 l = (T*)realloc(l, sizeof(T) * cap * 2); //重新申请内存，并拷贝数组 21 cap = cap << 1; 22 }23 l[siz++] = x;24 }25 26 T& operator [] (int pos) {27 return l[pos];28 }29 30 inline int size() {31 return siz;32 }33 34 inline int capt() {35 return cap;36 }37 };
这里为了省时间，不用new而是用malloc，这样稍微会快一些。
支持在头部插入的动态数组
stl的vector是不支持push_front，但是你可以通过insert在头部插入，但是这样是O(n)的，而不是O(1)的，因为vector中的insert是将它后面的内容往后copy，再把自己弄进vector。但是显然可以用近似的方法实现push_front，只是多需要一些内存罢了。
开一个头部缓冲数组，它的大小是l的一半，凡是push_front，都把加入的元素塞进去。当这个数组满了或者重新申请内存时，就先将它中的内容拷贝进新的数组。其他地方就稍微改一下就好了。因为这样会消耗更多的内存，所以用了一个boolean类型的变量sign区分是否需要使它实现push_front。
1 #include<iostream> 2 #include<algorithm> 3 #include<string.h> 4 #include<malloc.h> 5 using namespace std; 6 typedef bool boolean; 7 8 template<typename T> 9 class Vector {10 protected:11 int cap; //容量 12 int siz; //当前元素个数 13 boolean sign; //是否支持push_front 14 T* l; //数组部分15 T* fronts; //头部缓冲数组(追加在前面的部分)16 int sizf; //前面部分的大小 17 18 inline void extends(int newsize) {19 if(sign) {20 T* newarr = (T*)malloc(sizeof(T) * newsize); //申请新的数组 21 memcpy(newarr, fronts, sizeof(T) * sizf); //将原来添加到前面的数据拷贝进这个数组22 reverse(newarr, newarr + sizf); //翻转这一段，因为往前塞时却是往后存 23 memcpy(newarr + sizf, l, sizeof(T) * siz); //拷贝从l开始的这一段 24 siz += sizf, cap = newsize; //更新数据 25 free(l); //释放指针指向的数组 26 free(fronts);27 sizf = 0; //重新设置大小 28 fronts = (T*)malloc(sizeof(T) * (newsize >> 1)); //重新设置动态数组头部缓冲数组 29 l = newarr;30 } else {31 l = (T*)realloc(l, sizeof(T) * newsize);32 cap = newsize;33 }34 }35 public:36 Vector():l(NULL), cap(0), siz(0), sizf(0), sign(false), fronts(NULL) { }37 Vector(boolean sign):l(NULL), cap(0), siz(0), sizf(0), sign(sign), fronts(NULL) { }38 39 /**40 * 向动态数组尾部追加一个元素。41 * @param x 追加的元素42 * @return 如果成功追加，返回true，否则返回false 43 */44 inline boolean push_back(T x) {45 if(l == NULL) {46 extends(4);47 if(l == NULL) return false;48 }49 if(siz == cap) {50 extends(cap * 2);51 if(l == NULL) return false;52 }53 l[siz++] = x;54 return true;55 }56 57 /**58 * 向动态数组头部追加一个元素。59 * @param x 追加的元素60 * @return 如果成功追加，返回true，否则返回false 61 */62 inline boolean push_front(T x) {63 if(!sign) return false;64 if(fronts == NULL) {65 extends(4);66 if(fronts == NULL) return false;67 }68 if(sizf == (cap >> 1)) {69 extends(cap * 2);70 if(fronts == NULL) return false;71 }72 fronts[sizf++] = x;73 return true;74 }75 76 T& operator [] (int pos) {77 if(pos < sizf)78 return fronts[sizf - pos - 1];79 return l[pos - sizf];80 }81 82 inline int size() {83 return siz + sizf;84 }85 86 inline int capt() {87 if(sign) return cap + (cap >> 1);88 return cap;89 }90 91 inline int size_front() {92 return sizf;93 }94 95 inline int size_middle() {96 return siz;97 }98 };
支持在双端删除的动态数组
如果push_front还用上面的方法实现，那么代码可能会很长，因为在头部删除插入都需要特判。所以考虑将头部缓冲数组和l合并到一起。这样不难想到队列，给一个头指针和一个尾指针也可以实现边界判断(是否需要申请空间了)。
为了不被极端数据卡死，每次重新申请空间时，都将旧的数组拷贝到新的数组的中间。
下面来说一下删除。队列的删除很简单，挪"指针"就好了, 只不过要考虑下面这个问题
要不要释放内存？
至少我觉得应该是，不然我还不如直接开一块静态内存当队列用，还要动态数组干什么？但是不是当当前元素个数少于容量的一半就应该缩小当前数组，而是少于四分之一时才考虑缩小，不然可能有些不良心的题目数据让你删完一个，然后又插入一个，迫使你重新申请内存导致时间复杂度变成了O(n)。
1 #include<iostream> 2 #include<algorithm> 3 #include<string.h> 4 #include<malloc.h> 5 using namespace std; 6 typedef bool boolean; 7 8 template<typename T> 9 class Vector { 10 protected: 11 int cap; //容量 12 boolean sign; //是否支持push_front 13 T* l; //数组部分 14 int front; //头指针 15 int rear; //尾指针 16 17 inline void extends(int newsize) { 18 if(sign) { 19 int realsize = newsize * 3; //实际大小 20 T* newarr = (T*)malloc(sizeof(T) * realsize); //开辟新的数组 21 int s = this->size(); 22 int start_pos = (realsize - s) >> 1; //将原数据拷贝到新数组的中间 23 memcpy(newarr + start_pos, l + front + 1, sizeof(T) * s); 24 free(l); //释放原数组 25 l = newarr; 26 front = start_pos - 1, rear = start_pos + s; //重新计算下标 27 cap = newsize; 28 } else { 29 l = (T*)realloc(l, sizeof(T) * newsize); 30 cap = newsize; 31 } 32 } 33 34 inline void construct(boolean sign) { 35 if(!sign) { 36 l = (T*)malloc(sizeof(T) * 4); 37 front = -1, rear = 0, cap = 4; 38 } else { 39 l = (T*)malloc(sizeof(T) * 6); 40 front = 1, rear = 2, cap = 2; 41 } 42 } 43 public: 44 Vector():l(NULL), front(-1), rear(0), sign(false) { } 45 Vector(boolean sign):l(NULL), front(-1), rear(0), sign(sign) { } 46 47 /** 48 * 向动态数组尾部追加一个元素。 49 * @param x 追加的元素 50 * @return 如果成功追加，返回true，否则返回false 51 */ 52 inline boolean push_back(T x) { 53 if(l == NULL) { 54 construct(sign); 55 if(l == NULL) return false; 56 } 57 if(!sign && rear == cap) { 58 extends(cap * 2); 59 if(l == NULL) return false; 60 } else if(sign && rear == cap * 3) { 61 extends(cap * 2); 62 if(l == NULL) return false; 63 } 64 l[rear++] = x; 65 return true; 66 } 67 68 /** 69 * 向动态数组头部追加一个元素。 70 * @param x 追加的元素 71 * @return 如果成功追加，返回true，否则返回false 72 */ 73 inline boolean push_front(T x) { 74 if(!sign) return false; 75 if(l == NULL) { 76 construct(sign); 77 if(l == NULL) return false; 78 } 79 if(front == -1) { 80 extends(cap * 2); 81 if(l == NULL) return false; 82 } 83 l[front--] = x; 84 return true; 85 } 86 87 /** 88 * 在头部删除动态数组的一个元素。 89 * @return 如果成功删除，返回true，否则返回false 90 */ 91 inline boolean pop_front() { 92 if(!sign) return false; 93 if(front == rear - 1) return false; 94 front++; 95 int s = this->size(); 96 int c = this->capt(); 97 if(s < (c >> 2) && c >= 12) { //当当前容量过大时，缩小一下容量 98 extends(cap >> 1); 99 }100 return true;101 }102 103 /**104 * 在尾部删除动态数组的一个元素105 * @return 如果成功删除，返回true，否则返回false 106 */107 inline boolean pop_back() {108 if(front == rear - 1) return false;109 rear--;110 int s = this->size();111 int c = this->capt();112 if(s < (c >> 2) && c >= 12) { //当当前容量过大时，缩小一下容量 113 extends(cap >> 1);114 }115 return true;116 } 117 118 T& operator [] (int pos) {119 return l[front + pos + 1];120 }121 122 inline int size() {123 return rear - front - 1;124 }125 126 inline int capt() {127 if(sign) return cap * 3;128 return cap;129 }130 131 };
更小内存消耗的动态数组
注意到上面两种动态数组常常有些位置是空的，但是有时还是会重新申请新的内存，这对空间是一个极大的浪费(某些卡内存的题目，这个1.5倍可以决定你是AC还是MLE)。首先存数据是连续的，上面已经用了队列，不难想到用循环队列。这样极大地减少了浪费的空间，唯一的缺点就是循环队列取模很多，会很耗时间，所以还是按需使用吧。下面给出实现。(比较懒，就不写取模优化了)
1 #include<iostream> 2 #include<algorithm> 3 #include<string.h> 4 #include<malloc.h> 5 using namespace std; 6 typedef bool boolean; 7 8 template<typename T> 9 class Vector { 10 protected: 11 int cap; //容量 12 T* l; //数组部分 13 int front; //头指针 14 int rear; //尾指针 15 boolean isempty; //动态数组是否是空 16 17 inline void extends(int newsize) { 18 if(!isempty) { 19 T* newarr = (T*)malloc(sizeof(T) * newsize); //开辟新的数组 20 int s = size(); 21 if(rear <= front) { //拷贝数据 22 memcpy(newarr, l + front, sizeof(T) * (cap - front)); 23 memcpy(newarr + (cap - front), l, sizeof(T) * rear); 24 } else { 25 memcpy(newarr, l + front, sizeof(T) * s); 26 } 27 free(l); //释放原数组 28 l = newarr; 29 front = 0, rear = s; //重新计算数据 30 } else { 31 l = (T*)realloc(l, sizeof(T) * newsize); 32 } 33 cap = newsize; 34 } 35 36 inline void construct() { 37 l = (T*)malloc(sizeof(T) * 4); 38 front = 0, rear = 0, cap = 4, isempty = true; 39 } 40 41 inline int lastPos(int pos) { return (pos + cap - 1) % cap; } 42 inline int nextPos(int pos) { return (pos + 1) % cap; } 43 public: 44 Vector():l(NULL), front(0), rear(0), isempty(true) { } 45 46 /** 47 * 向动态数组尾部追加一个元素。 48 * @param x 追加的元素 49 * @return 如果成功追加，返回true，否则返回false 50 */ 51 inline boolean push_back(T x) { 52 if(l == NULL) { 53 construct(); 54 if(l == NULL) return false; 55 } 56 if(rear == front && !isempty) { 57 extends(cap * 2); 58 if(l == NULL) return false; 59 } 60 l[rear] = x; 61 rear = nextPos(rear); 62 isempty = false; 63 return true; 64 } 65 66 /** 67 * 向动态数组头部追加一个元素。 68 * @param x 追加的元素 69 * @return 如果成功追加，返回true，否则返回false 70 */ 71 inline boolean push_front(T x) { 72 if(l == NULL) { 73 construct(); 74 if(l == NULL) return false; 75 } 76 if(rear == front && !isempty) { 77 extends(cap * 2); 78 if(l == NULL) return false; 79 } 80 front = lastPos(front); 81 l[front] = x; 82 isempty = false; 83 return true; 84 } 85 86 /** 87 * 在头部删除动态数组的一个元素。 88 * @return 如果成功删除，返回true，否则返回false 89 */ 90 inline boolean pop_front() { 91 if(isempty) return false; 92 front = nextPos(front); 93 if(front == rear) isempty = true; 94 int s = this->size(); 95 int c = this->capt(); 96 if(s < (c >> 2) && c >= 8) { //当当前容量过大时，缩小一下容量 97 extends(cap >> 1); 98 } 99 return true;100 }101 102 /**103 * 在尾部删除动态数组的一个元素104 * @return 如果成功删除，返回true，否则返回false 105 */106 inline boolean pop_back() {107 if(isempty) return false;108 rear = lastPos(rear);109 int s = this->size();110 int c = this->capt();111 if(s < (c >> 2) && c >= 8) { //当当前容量过大时，缩小一下容量 112 extends(cap >> 1);113 }114 return true;115 }116 117 inline void clear() {118 free(l);119 l = NULL;120 front = 0, rear = 0, cap = 0;121 isempty = true;122 }123 124 inline boolean empty() {125 return isempty;126 }127 128 T& operator [] (int pos) {129 return l[(front + pos) % cap];130 }131 132 inline int size() {133 if(rear == front && !isempty) return cap;134 return (rear - front + cap) % cap;135 }136 137 inline int capt() {138 return cap;139 }140 141 };
快速实现随机下标插入，随机下标删除的动态数组
这个嘛。。直接用splay好了，反正都是一个log。。当然也可以自行百度搜一下stl中的deque的实现。
性能测试
因为比较懒，就用1e7的数据量测试一下push_back和pop_back
std::vector的测试结果
普通队列实现的Vector的测试结果
不支持push_front的速度
支持push_front的速度
(反正插入都比stl快)
循环队列实现的Vector的测试结果
(插入还是比stl，取模真的是慢得吓死人啊。。)
最后呢，欢迎提出问题或指出上面的错误。
浅谈动态数组原理及其实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。