2.1、vector扩容原理

vector扩容核心原理

当vector当前容量（capacity）不足以容纳新增元素时，会执行以下操作：

1. 1. 申请一块更大的连续内存空间；
2. 2. 将已有元素复制到新空间；
3. 3. 释放旧内存空间；
4. 4. 最后插入新元素。

扩容的增长策略及其影响

成倍增长（倍增因子m）

vector通常采用成倍增长策略，比如以1.5倍或2倍扩容。这样做的目的是减少扩容次数，使得n次push_back操作的均摊时间复杂度达到O(1)，相比每次增加固定大小容量导致的均摊时间复杂度为O(n)有明显优势。

为什么不是固定大小增长？

如果每次扩容只增加固定大小k，随着元素增多，扩容次数会线性增加，且每次都需要复制所有元素，导致整体push_back操作的时间复杂度为O(n²)，效率极低。

为什么增长因子取1.5或2？

• • 取2倍增长：每次新容量必然超过之前所有分配容量的总和，导致之前释放的内存空间无法被重用，造成较大空间浪费，对缓存友好性不佳。
• • 取1.5倍增长：经过多次扩容后，新容量可以重用之前释放的内存空间，减少空间浪费，更加节省内存。
• • 取大于2的倍数：不合理，因为空间浪费更严重，且扩容过快可能导致内存占用激增。

不同编译器实现差异

例如，VS2015采用1.5倍扩容，GCC采用2倍扩容，都是在时间效率和空间利用之间的权衡。

扩容过程简述

1. 1. 当执行push_back操作时，如果size == capacity，触发扩容；
2. 2. 申请一个更大的连续内存块（容量为旧容量的1.5倍或2倍）；
3. 3. 将旧内存中的元素复制到新内存；
4. 4. 释放旧内存；
5. 5. 插入新元素。

注意：扩容会使所有指向旧vector的迭代器失效。

总结

1. 1. vector通过成倍扩容保证了push_back操作的均摊时间复杂度为O(1)，大幅提升性能；
2. 2. 选择增长因子时，1.5倍和2倍是常见且合理的折中方案，1.5倍更节省空间且能重用内存，2倍则扩容次数更少但空间浪费较大；
3. 3. 固定大小增长方式因扩容频繁且复制成本高，时间复杂度为O(n)，效率低下，不被推荐；
4. 4. 这体现了vector设计中对时间效率和空间利用的平衡考量，理解这一点对于深入掌握C++容器性能优化非常关键。
   本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
   （加入我的知识星球，免费获取账号，解锁所有文章。）