pushback(back扩容机制为什么不考虑在尾元素后面的空间申请内存)
资讯
2023-11-23
142
1. pushback,back扩容机制为什么不考虑在尾元素后面的空间申请内存?
首先我们看一下官方文档对vector的说明:
再看一下对push_back函数的说明:
总结起来就是初始时刻vector的capacity为0,塞入第一个元素后capacity增加为1,vector内部是通过数组来实现的,它占用的是一块连续空间,当空间不足时它会重新申请空间,并将当前内容一并拷贝到新的空间,下图是vector内存的扩充的示意图。
有一点需要说明,容量扩充并不总是扩充至两倍,具体的倍数取决于编译器,比如在GCC下是两倍,而在VS2017中是1.5倍,下图是在VS中的实验结果。
可见每push_back一个元素,vector的size就增加1,而capacity则以1.5倍的速度增加,3增加到4而不是4.5,是因为取整的原因。
那么为什么要这样处理,主要有两个原因:
1、vector在push_back以成倍增长可以在均摊后达到O(1)的事件复杂度。具体的推理过程涉及到算法分析与一些数学知识,在此不再傲述,感兴趣的话,可留言。
2、考虑可能产生的堆空间浪费,成倍增长倍数不能太大,为了防止申请内存的浪费,现在使用较多的有2倍与1.5倍的增长方式,而1.5倍的增长方式可以更好的实现对内存的重复利用。
至于问题中的为什么不在vector结尾处申请内存,那是因为每次申请的内存由系统决定,程序和编译器并不能控制。
本站涵盖的内容、图片、视频等数据系网络收集,部分未能与原作者取得联系。若涉及版权问题,请联系我们删除!联系邮箱:ynstorm@foxmail.com 谢谢支持!
1. pushback,back扩容机制为什么不考虑在尾元素后面的空间申请内存?
首先我们看一下官方文档对vector的说明:
再看一下对push_back函数的说明:
总结起来就是初始时刻vector的capacity为0,塞入第一个元素后capacity增加为1,vector内部是通过数组来实现的,它占用的是一块连续空间,当空间不足时它会重新申请空间,并将当前内容一并拷贝到新的空间,下图是vector内存的扩充的示意图。
有一点需要说明,容量扩充并不总是扩充至两倍,具体的倍数取决于编译器,比如在GCC下是两倍,而在VS2017中是1.5倍,下图是在VS中的实验结果。
可见每push_back一个元素,vector的size就增加1,而capacity则以1.5倍的速度增加,3增加到4而不是4.5,是因为取整的原因。
那么为什么要这样处理,主要有两个原因:
1、vector在push_back以成倍增长可以在均摊后达到O(1)的事件复杂度。具体的推理过程涉及到算法分析与一些数学知识,在此不再傲述,感兴趣的话,可留言。
2、考虑可能产生的堆空间浪费,成倍增长倍数不能太大,为了防止申请内存的浪费,现在使用较多的有2倍与1.5倍的增长方式,而1.5倍的增长方式可以更好的实现对内存的重复利用。
至于问题中的为什么不在vector结尾处申请内存,那是因为每次申请的内存由系统决定,程序和编译器并不能控制。
本站涵盖的内容、图片、视频等数据系网络收集,部分未能与原作者取得联系。若涉及版权问题,请联系我们删除!联系邮箱:ynstorm@foxmail.com 谢谢支持!