到需要扩容的时候,Vector会根据需要的大小,创建一个新数组,然后把旧数组的元素复制进新数组。
我们可以看到,扩容后,其实是一个新数组,内部元素的地址已经改变了。所以扩容之后,原先的迭代器会失效:
插一嘴,为什么要用迭代器而不用指针。
Iterator(迭代器)用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。
所以原因1:更安全。
第二,迭代器不是指针,它是类模板。它只是通过重载了指针的一些操作符(如“++”、“->”、“ * ”等)来模拟了指针的功能。也因此,它的功能比指针更加智能,他可以根据不同的数据类型实现不同的“++”等操作。
所以原因2:更智能。
int main() {
std::vector<int> arr;
arr.emplace_back(1);
auto it = arr.begin();
auto it2 = arr.end();
std::cout << *it << "\t" << *(--it2) << std::endl;
arr.emplace_back(2);
std::cout << *it << "\t" << *(--it2) << std::endl;
return 0;
}
执行后,只有第一个cout输出了结果,第二个cout没有输出,直接程序结束。
因为一开始没有声明大小,所以默认cap为0(这里cap指的是vector.capacity(),是可以调用的函数,返回当前vector的实际容量,超过了就要扩容);插入1之后,cap变为1;再插入2,因为size超过了cap,所以要扩容。
如前文所叙,扩容之后,元素的位置都变了,所以原先的迭代器失效了。
问题:元素的位置都变了?那头元素的位置变了吗?
答案是:变了。
有的人在这个时候会有疑问:那我还怎么找到原来的vector?
实际上,vector的头元素地址,与vector的地址并不相同。我们日常将vector叫做数组,但至少在这一点上,它不同于真正的数组。
以下是我做的实验出来的结果:
声明: std::vector<int> vector1 = { 1 };
&vector1: 00EFF824
&vector1[0]: 011B04D0
声明: int* p1 = &vector1[0];
*p1: 1
指针p1的值(指向的地址): 011B04D0
扩容后*p1: -572662307
扩容后,指针p1的值(指向的地址): 011B04D0
扩容后,&vector1: 00EFF824
扩容后,&vector1[0]: 011C0C40
声明: int array2[] = { 1 };
&array2: 00EFF7D4
&array2[0]: 00EFF7D4
从第三部分可以看到,对于一个数组array2,它的地址就是它的头元素的地址。而第一部分中,vector1的地址,与它的头元素地址并不相同。
扩容之后,&vector1 地址还是不变,但是头元素的地址已经变了。
如果你在扩容前,使用一个指针指向头元素,扩容后,指针指向的地址不变,但是这个地方已经变成了野值。
最后,扩容有两种机制,2倍扩容和1.5倍扩容。这个机制随编译器的不同而不同。
VS2017使用的是1.5倍扩容,g++编译器用的是2倍扩容。
在大部分情况下,1.5倍扩容要好一些。因为随着内存的增长,可以实现一定程度上的内存复用。
下面展示两种编译器具体的扩容情况。
以下内容来源于链接。
测试代码:
#include <stdio.h>
#include <vector>
int main() {
std::vector<double> v;
printf("size:%d capacity:%d max_size:%llu\n",v.size(),v.capacity(),v.max_size());
int last_capacity = -1;
for (int i = 0; i < v.max_size(); ++i) {
v.push_back(1.0*i);
if (last_capacity!=v.capacity()) {
printf("size:%10d capacity:%10d c/l:%d max_size:%llu\n",
v.size(),v.capacity(),v.capacity()/last_capacity,v.max_size());
}
last_capacity = v.capacity();
}
return 0;
}
上面是vs2017的1.5倍扩容,下面是g++的2倍扩容:
vector的capacity,是指当前状态下(未重新向操作系统申请内存前)的最大容量。
这个值如果不指定,则开始是0,加入第一个值时,由于capacity不够,向操作系统申请了长度为1的内存。在这之后每次capacity不足时,都会重新向操作系统申请长度为原来两倍的内存。
回到刚才的话题:为什么1.5倍扩容要好一些?
以下内容来源于链接。
- 两倍扩容
假设我们一开始申请了 16Byte 的空间。
当需要更多空间的时候,将首先申请 32Byte,然后释放掉之前的 16Byte。这释放掉的16Byte 的空间就闲置在了内存中。
当还需要更多空间的时候,你将首先申请 64Byte,然后释放掉之前的 32Byte。这将在内存中留下一个48Byte 的闲置空间(假定之前的 16Byte 和此时释放的32Byte 合并)
当还需要更多空间的时候,你将首先申请128Byte,然后释放掉之前的 64 Byte。这将在内存中留下一个112Byte 的闲置空间(假定所有之前释放的空间都合并成了一个块)
扩容因子为2时,上述例子表明:每次扩容,我们释放掉的内存连接起来的大小,都小于即将要分配的内存大小。
- 1.5倍扩容
假设我们一开始申请了 16Byte 的空间。
当需要更多空间的时候,将申请 24 Byte ,然后释放掉 16 ,在内存中留下 16Byte 的空闲空间。
当需要更多空间的时候,将申请 36 Byte,然后释放掉 24,在内存中留下 40Byte (16 + 24)的空闲空间。
当需要更多空间的时候,将申请 54 Byte,然后释放 36,在内存中留下 76Byte。
当需要更多空间的时候,将申请 81 Byte,然后释放 54, 在内存中留下 130Byte。
当需要更多空间的时候,将申请 122 Byte 的空间(复用内存中闲置的 130Byte)
由此可见,1.5倍扩容在一定程度上可以实现内存的复用。当然,每次扩容的大小更小,也意味着时间效率的降低,看取舍了。