浅谈动态数组原理及其实现

  stl中的vector是竞赛中常用的容器,原因在于省内存,O(1)在后端插入和删除、随机下标访问,今天就来谈谈它的实现。

最简单的一个动态数组

  动态数组并不是真正意义上的动态的内存,而是一块连续的内存,当添加新的元素时,容量已经等于当前的大小的时候(存不下了),执行下面3步

  1. 重新开辟一块大小为当前容量两倍的数组
  2. 把原数据拷贝过去
  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,取模真的是慢得吓死人啊。。)

最后呢,欢迎提出问题或指出上面的错误。

时间: 06-25

浅谈动态数组原理及其实现的相关文章

浅谈NAT的原理、缺陷及其解决之道

为什么会有NAT 犹如windows统治着绝大部份桌面系统一样,TCP/IP也是网络协议中的实际统治者,而IP正是这个协议统治的基础,作为标识TCP/IP网络中每个结点的IP地址,由于它只有32个bit的空间,随着网络的发展,它变得越来越稀有,再加上IP地址地区分配的极端不平衡,已使一些地区比如亚洲部分国家的IP资源很快就会用完,在IPv6还没有普及开来之时,为了解决IP地址的燃眉之急,我们需要一种手段来尽量减少对公网IP的使用,这种手段就是NAT(Network Address Transla

浅谈网页运行原理

我们知道打开一个网页的时候,浏览器会首先创建一个窗口,这个窗口就是一个window对象,也是javascript运行所依附的全局环境对象和全局作用域对象. 为了加载网页文档,当期的窗口将为要打开的网页创建一个document对象,然后将页面加载到这个document中,网页的内容就是在这这个过程中一边加载一边显示出来,javascript也是伴随着这个过程,一边加载一边执行的. 进行加载和执行的目的,就是建立文档对象模型(DOM)主框架,这个文档框架是由当前文档窗口的主线程来执行,并依照严格的顺

浅谈JVM及原理

1.什么是JVM ? JVM, 中文名是Java虚拟机, 正如它的名字, 是一个虚拟机器,来模拟通用的物理机. JVM是一个标准,一套规范,  规定了.class文件在其内部运行的相关标准和规范. 及其相关的内部构成. 比如:所有的JVM都是基于栈结构的运行方式.那么不符合这种要求的,不算是JVM, 如Android中所使用的Dalvik 虚拟机就不能称作是JAVA 虚拟机, 因为它是基于寄存器(最新的Android系统据说已经放弃了Dalvik VM, 而是使用ART). JVM相关的产品有很

[iOS]浅谈NSRunloop工作原理和相关应用

一. 认识NSRunloop  1.1 NSRunloop与程序运行 那么具体什么是NSRunLoop呢?其实NSRunLoop的本质是一个消息机制的处理模式.让我们首先来看一下程序的入口——main.m文件,一个ios程序启动后,只有短短的十行代码居然能保持整个应用程序一直运行而没有退出,是不是有点意思?程序之所以没有直接退出是因为UIApplicationMain这个函数内部默认启动了一个跟主线程相关的NSRunloop对象,而UIApplicationMain这个函数一直执行没有返回就保存

浅谈next数组

next数组是加速字符串匹配的的一个重要工具 以下是next数组的实现过程 int* getnext(string &T) { int length = T.length(); int *next = new int[length]; next[0] = -1; next[1] = 0; int i = 1; int j = 0; while(i<length) { if(T[i] == T[j]) { next[++i] = ++j; } else if(j>0) { j = nex

从内存层次浅谈动态与静态

转载请注明原文地址:http://www.cnblogs.com/ygj0930/p/5827364.html 静态内容:在内存中有一片特定的区域,不属于某特定的类对象,而是属于所有类对象,每个对象默认有指针指向这片区域,以调用静态的属性.方法 当创建第一个类对象时,类代码由硬盘加载到内存时,静态内容加载一次,开辟区域存放,之后每次创建对象时不再加载.每个对象默认有指针指向这片区域,以调用静态的属性.方法. 所以,静态方法的调用格式为:  类名.静态方法名 .  对象名.方法名  均可 动态内容

浅谈 HashMap 实现原理

1.HashMap概述 HashMap是基于哈希表的Map接口的非同步实现.此实现提供所有可选的映射操作,并允许使用null值和null键.此类不保证映射的顺序,特别是它不保证该顺序恒久不变. 2.HashMap的数据结构 在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外.HashMap实际上是一个"链表散列"的数据结构,即数组和链表的结合体. 从上图中可以看出,HashMap底层就

浅谈集合---动态数组

集合---一个存储数据的"无底洞"\动态数组,集合的作用和数组一样可以存储多个数据.但是集合中能够存储的数据的个数是动态增长的.随着我们往集合中新增元素的增多而自动增大.那么为什么它的长度可以变化呢? 其实集合的本质就是数组,只不过当数组中存储的元素的个数等于数组长度的时候,就会自动new一个新数组,长度是原来的数组的两倍,在将原始的数据拷贝到新数组中,然后把旧数组的引用重新指向刚刚new的新数组,从而实现了动态增长! 浅谈集合---动态数组,布布扣,bubuko.com

浅谈C++容器动态内存管理的优化

在信息学竞赛中,C++的容器的用途非常广泛,但经常因常数过大而超时.怎样才能提高它们的效率呢? 我们知道,容器是存储同一类对象的对象,既然"对象"我们无法改变,那么我们只能从"存储"入手,不难想到,不同容器在实现上的根本区别是它们对应着不同的内存组织方式,内存管理无疑是这种实现的核心,所以优化内存管理是加快容器效率的最好途径之一. 一.内存分配器简介 怎样才能优化内存管理呢?很简单,C++为我们提供了这样的接口,我们可以通过自定义容器模板中的最后一个allocato

浅谈为什么只有指针能够完成多态及动态转型的一个误区

c++多态由一个函数地址数组Vtable和一个指向Vtable的指针vptr实现. 具体来说,类拥有自己的vtable,类的vtable在编译时刻完成. 每个对象有自己的vptr指针,该指针初始化时指向对象所实现的类的vtable. 关于向上转型的误区: 通常对于向上转型的理解是这样的,当子类对象向上转型(允许隐式)成父类对象时,实际上只是将子类对象暂时看做父类对象,内部的数据并未改变. 对于没有虚函数的对象,这句话是正确的,但是,当引入虚函数后,这样的理解是有问题的,实际上,向上转型的过程中,