网站建设虚拟,qq空间网址是什么,免费科技,网站制作多少钱一个到需要扩容的时候#xff0c;Vector会根据需要的大小#xff0c;创建一个新数组#xff0c;然后把旧数组的元素复制进新数组。
我们可以看到#xff0c;扩容后#xff0c;其实是一个新数组#xff0c;内部元素的地址已经改变了。所以扩容之后#xff0c;原先的迭代器会…到需要扩容的时候Vector会根据需要的大小创建一个新数组然后把旧数组的元素复制进新数组。
我们可以看到扩容后其实是一个新数组内部元素的地址已经改变了。所以扩容之后原先的迭代器会失效 插一嘴为什么要用迭代器而不用指针。 Iterator迭代器用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。 所以原因1更安全。 第二迭代器不是指针它是类模板。它只是通过重载了指针的一些操作符如“”、“-”、“ * ”等来模拟了指针的功能。也因此它的功能比指针更加智能他可以根据不同的数据类型实现不同的“”等操作。 所以原因2更智能。 int main() {std::vectorint 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::vectorint 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::vectordouble 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倍扩容在一定程度上可以实现内存的复用。当然每次扩容的大小更小也意味着时间效率的降低看取舍了。
