面试题：C++中vector动态扩容策略的基本原理

Question

请简述C++ STL中vector动态扩容的基本原理，包括扩容的触发条件和扩容时内存重新分配与数据迁移的大致过程。

Answer 1

1. 扩容触发条件：
   • 当vector的元素数量（size()）达到容量（capacity()）时，若再执行插入操作（如push_back等），就会触发扩容。这是因为当前分配的内存空间已不足以容纳新元素。
2. 内存重新分配与数据迁移过程：
   • 内存重新分配：
     • vector会重新分配一块更大的内存空间。通常，新的容量是原容量的2倍（不同编译器实现可能略有差异，但一般是倍数增长，这样可以减少重新分配内存的频率，降低时间复杂度）。例如，原容量为4，当触发扩容时，新容量可能变为8。
     • 使用operator new等机制在堆上分配这块新的更大的内存。
   • 数据迁移：
     • 通过memcpy或逐个元素拷贝（对于有复杂构造析构函数的对象，采用逐个元素拷贝构造）的方式，将原vector中的数据从旧内存空间迁移到新分配的内存空间。
     • 迁移完成后，释放原有的旧内存空间（通过operator delete）。
   • 更新相关信息：
     • vector会更新其内部记录的容量（capacity）和大小（size）信息，使其反映新的内存状况和元素数量。