back扩容机制为什么不考虑在尾元素后面的空间申请内存_java

资料来源：网络整理时间：2023/3/8 17:45:29 共计：3596 浏览

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结尾处申请内存，那是因为每次申请的内存由系统决定，程序和编译器并不能控制。

版权说明：
本网站凡注明“广州京杭原创”的皆为本站原创文章，如需转载请注明出处！
本网转载皆注明出处，遵循行业规范，如发现作品内容版权或其它问题的，请与我们联系处理！
欢迎扫描右侧微信二维码与我们联系。