在面试时vector的扩容问题会经常被问到,比如:
一系列问题下来,是否有种被吊打的感觉呢?本节我们再来深究vector扩容背后所包含的细节问题,让你的面试不再尴尬。
当向vector中插入元素时,如果元素有效个数size与空间容量capacity相等时,vector内部会触发扩容机制:
开辟新空间
注意:每次扩容新空间不能太大,也不能太小,太大容易造成空间浪费,太小则会导致频繁扩容而影响程序效率。
如果要避免扩容而导致程序效率过低问题,其实非常简单:**如果在插入之前,可以预估vector存储元素的个数,提前将底层容量开辟好即可。**如果插入之前进行reserve,只要空间给足,则插入时不会扩容,如果没有reserve,则会边插入边扩容,效率极其低下。
#include <iostream>
#include <vector>
int main ()
{
size_t sz;
std::vector<int> foo;
// foo.reserve(100); // 先将vector底层空间扩增到100个,然后插入
sz = foo.capacity();
std::cout << "making foo grow:\n";
for (int i=0; i<100; ++i)
{
foo.push_back(i);
if (sz!=foo.capacity())
{
sz = foo.capacity();
std::cout << "capacity changed: " << sz << '\n';
}
}
}
vs:运行结果:
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 3
capacity changed: 4
capacity changed: 6
capacity changed: 9
capacity changed: 13
capacity changed: 19
capacity changed: 28
capacity changed: 42
capacity changed: 63
capacity changed: 94
capacity changed: 141
g++运行结果:
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128
等长个数方式扩容,**新空间大小就是将原空间大小扩增到capacity+K个空间(capacity为旧空间大小)。假设需要向vector中插入100个元素,K为10,那么就需要扩容10次;**每次扩容都需要将旧空间元素搬移到新空间,第i次扩容拷贝的元素数量为:ki(第1次扩容,新空间大小为20,旧空间中有10个元素,需要搬移到新空间中;第2次扩容,新空间大小为30,旧空间中有20个元素,需要全部搬移到新空间中),假设元素插入与元素搬移为1个单位操作,则n个元素push_back()的总操作次数为:
**假设有n个元素需要像vector插入,倍增因子为m,则完成n个元素像vector的push_back操作需要扩容log以m为低n的次方。**比如:以二倍方式扩容,当向vector插入1000个元素,需要扩容log以2为底1000次方,就是扩容10次,第i次增容会把m的i次方个元素搬移到新空间,n次push_back的总操作次数为:
可以看到以倍数的方式扩容比以等长个数的扩容方式效率高。
扩容原理为:申请新空间,拷贝元素,释放旧空间,**理想的分配方案是在第N次扩容时如果能复用之前N-1次释放的空间就太好了,**如果按照2倍方式扩容,第i次扩容空间大小如下:
可以看到,**每次扩容时,前面释放的空间都不能使用。**比如:第4次扩容时,前2次空间已经释放,第3次空间还没有释放(开辟新空间、拷贝元素、释放旧空间),即前面释放的空间只有1 + 2 = 3,假设第3次空间已经释放才只有1+2+4=7,而第四次需要8个空间,因此无法使用之前已释放的空间,但是按照小于2倍方式扩容,多次扩容之后就可以复用之前释放的空间了。如果倍数超过2倍(包含2倍)方式扩容会存在:
空间浪费可能会比较高,比如:扩容后申请了64个空间,但只存了33个元素,有接近一半的空间没有使用。
*
无法使用到前面已释放的内存。
使用2倍(k=2)扩容机制扩容时,每次扩容后的新内存大小必定大于前面的总和。
而使用1.5倍(k=1.5)扩容时,在几次扩展以后,可以重用之前的内存空间了。
因为STL标准并没有严格说明需要按何种方式进行扩容,因此不同的实现厂商都是按照自己的方式扩容的,即:linux下是按照2倍的方式扩容的,而vs下是按照1.5倍的方式扩容的。
Windows中堆管理系统会对释放的堆块进行合并,因此:vs下的vector扩容机制选择使用1.5倍的方式扩容,这样多次扩容之后,就可以使用之前已经释放的空间。
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/qq_44918090/article/details/120583540
内容来源于网络,如有侵权,请联系作者删除!