1、何为动态
这里我们来解决一下，我们到现在为止所实现的数组这个类的一个非常重要的局限性。那么也是我们在做数组这个类一开始我就一直说的一个问题，就是现在我们的这个数组它内部实际还是使用的一个静态数组。那个对于data的这个静态数组来说，它的容量是有限的，可是很多时候我们使用我们的这个数组，可能无法实现预估我们要往这个数组中放入多少个元素。那么在这种情况下，如果我们的容量开的太大的话，很有可能浪费了好多空间。但是如果容量开的太小的话，又有可能最后这个空间不够用，在这种情况下我们需要一种解决方案，使得我们的这个数组的容量是个伸缩的，也就是所谓的动态数组。
数组类-扩容展示
2、分析怎样动态
那么具体我们怎样实现这样的一个需求呢？其实它的原理非常简单，想像一下假设我们这个数组在现在只有四个元素这么多的容量，并且现在我们这个数组中四个元素已经装满了，那么此时，如果我们向这个数组中再添加1个元素的话，显然是做不到的。那么根据我们现在的代码的逻辑会抛出一个异常，我们可以在这种情况下进行一个其它的操作，来打破这的限制。那么这个其它的操作其实思路特别的简单。它方法是这样的，我们首先再开创一个新的数组，那么比如说我把这个新的数组叫做newdata，对于这个newdata我开的空间比原来的空间要大一些。原来的这个静态数组他的空间只有四个现在不够用了，那么对于这个newdata开8个空间，在开8个空间之后。我将data中的所有的元素全都放进我的newdata中。注意这步实现实际上我们是要进行一次循环的，循环来遍历原来data数组中的所有的元素。把它们依次的复制到newdata中。
数组类-扩容
那么做完这件事之后，对我们整个数组来说，我们其实就是想让newdata来取代我的这个data，换句话说对于我们现在的这个数组来说，capacity也就是容量已经变成了8，与此同时size也就数组中装了多少个元素这个值是不变的，依然是有四个元素。只不过现在在newdata中，在这四个元素的后面有了新的空间，可以装下更多的元素了。之后都有我们整个数组的这个data，在这里注意它在我们程序实现中本身是一个引用，引用以前装的是这个有四个空间的数组，现在呢，我把它指向新的这个有八个空间的数组。那么此时很显然可以看到，类中的这个data这个成员变量和我们新开的这个newdata这个变量，其实指向的是同样的空间，我们整个这个过程是封装在一个函数中。所以对于newdata这个变量，在我们这个函数执行完成之后就失效了，而我们的这个data呢，由于它是我们整个类的成员变量，所以它和我们的这个整个类生存周期是一致的。只要我们这个类还在使用，那么这个data就是有效的。它指向了我们这个新的含有八个空间的这样的一个数组data，对于原来的这个只有四个空间的数组，由于也没有人指着它，所以在这个方法执行完后将它释放。最后我们整个这个类经过这样的变化，相当于就进行了扩容。那么可能会觉得这个过程我需要把原来的数组中的所有的元素都复制给我们的这个新的数组，那么是不是在性能上时间消耗上太大，关于这个问题我们在后面会做具体的讨论。这里首先看到的是，我们使用这种方法确实让我们的这个数组类有了容量的动态伸缩的能力，我们先加上这样的一种方式之后，就再也不用担心用户一开始开的这个数组它的容量不够这样的问题了，我们马上实践的时候，也会看到其实我在对数组删除元素的时候，也可以同样使用类似的技术，只不过此时是缩减整个空间，这样一来呢争取做到整个数组空间也不会有太多的浪费。
3、重点为扩容
下面那我们就具体的来编程实践一下这个思路。看一下我们这个程序让他在之前的实现中可以看，对于插入这个操作来说，如果当前的数组空间已经满了或者用户给定的这个index它是非法的情况下抛出异常。如果当前我的这个类里面data这个静态数组的空间已经满了，不抛出异常了，而是使用我之前ppt里所讲的策略，和进行一个我们整个数据空间的扩容，把这个过程叫做resize。那么扩容多少呢？在这里我让这个扩容的量等于现在数组空间容量的二倍，那么我为什么这么设计呢？在这里主要是我不希望我扩容的空间是比原来的capacity这个大小再加1个常数，因为对于这个常数到底取多少，其实很难判断。可能我们每次就扩容十个空间吧。但是如果这样做的话，想象一下，假设我们当前现在数组里已经有1万个元素了，那么我们扩容才扩容成1万零十个元素。那么很有可能我们的这个扩容相对来说是比较低效的，因为现在这个数组里装一万个元素已经装满了。现在又有新的元素来了，很有可能还要来一大波元素，还要来1000个元素。那么每次我们只新增加10个空间的话，我们就要扩100次容，这个性能消耗那就太大了。如果我干脆每次都只1000个容量就好了，但是这样做也有问题，那如果我现在整个数组这个容量只有十个的话，一下括1000的那么有很大的概率大部分容量了会被浪费掉。我用二乘以当前的这个数据容量，相当于是我要扩容多少和我们当前数组有多少元素是相关的。我扩容的量其实是和我当前数组中已经有的元素个数是在同样一个数量级的，那么我当前数组有100个元素，我就给它扩容充200；有1万个元素，我就给他扩容成2万，是这样的一个思路。我们后续很快也会看到，使用这样的一个思路在整体性能上是有优势的，那么这个性能优势的具体分析，我会在后面再进行介绍。
可以不可以不扩容两倍，比如扩容1.5倍可不可以，或者扩容三倍可不可以，其实都是可以的，这里面其实就是一个参数选择的问题了。
数组类-扩容实现
4、扩容的实现
那么下面我们来具体的实现一下resize这个函数，它是一个私有的方法，用户是不能自己来调动这个resize给我们的这个数组进行扩容的，这个扩容由我们数组的内部逻辑来决定什么时候进行。
// 扩容
void AMGArray::resize(int newCapacity) {
if ( 0 >= newCapacity ) {
cout << "newCapacity 不合法" << endl;
return;
}
// 开辟新的空间
int *newData = new int[newCapacity];
// 将元素逐个赋值到新的空间
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
// 是否旧的空间
// delete data;
// 将旧的指向新空间
data = newData;
// 维护容量
capacity = newCapacity;
}
在insert方法中，当静态数组满时，就进行一次resize操作。现在我们整个数组已经拥有了动态数组的能力，用户再也不用操心这个数组中空间不够用的问题。
// 在指定位置添加元素
void AMGArray::insert(int index, int e) {
if ( index < 0 || index > size ) {
cout << "Index 不合法" << endl;
return;
}
// 是否容量已满/扩容
if ( size == capacity ) {
resize(capacity * 2);
}
// 从后往前赋值
for (int i = size; i >= index; i--) {
data[i + 1] = data[i];
}
// 腾出来的位置放入e元素
data[index] = e;
size++;
}
5、同理的缩容
相当于扩容来说，同理在我们从数组中删除元素的时候，为了减少空间我们也可以设置删除到一定程度的时候，我们整个数组的容量进行一下缩小。现在我们已经有了resize这个方法来做这个逻辑呢就非常的简单了。我们可以看一下我们的remove这个函数，现在对于我们的remove这个函数在我们完成了删除逻辑之后什么都不做，在这里呢我可以添加1段逻辑。如果我看到我当前的元素个数已经小到一定程度了，那么小到什么程度呢，在这里呢我们先这样写，小到我们整个这个数组容积的二分之一的时候，也就是我们现在整个数组只有一半的空间被利用了，另外的一半空间呢都是被浪费的，那么在这种情况下我也调用一下resize。只不过这次resize我是把我们数组中的容量比size乘当前容量的一半，也就是将的数组容量进行缩小。
那么可以想象一下，这样一来当我们减小元素的时候减少到一定程度，我们数组的空间也会动态的进行减小。就使用这样的一个resize这个逻辑，让我们整个数组拥有了动态的容量变化这样的一个能力，此时我们实现了一个真正意义上的动态数组。这个动态内存分配的过程对于使用而为的用户来说是不可见的，根本不需要了解这其中是怎样的机制。
// 删除某个位置上的元素
int AMGArray::remove(int index) {
if ( index < 0 || index >= size ) {
cout << "remove Index 不合法 " << index << endl;
return -1;
}
// 从index位置开始往后赋值
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
int res = data[index];
data[size - 1] = 0; // 游荡元素
size--;
// 缩容
if ( size == capacity / 2 && 0 != capacity / 2 ) {
resize(capacity / 2);
}
return res;
}
6、总结
接下来讲一下我们这个数组操作，它的性能是如何的，怎么用一个专业点的术语来说？就是我们进行一下时间的复杂度分析。
数组类-静态数组改造
网友评论