题目

编写程序，循环向 std::vector<int> 中逐个追加元素，追踪并打印每次容器内部触发扩容（capacity() 突变）时的元素个数、当前容量以及底层数组的实际堆内存地址迁移过程；随后对比使用 reserve() 预分配连续内存时对重新分配（Reallocation）开销与指针失效的消除效果。

输入格式：无需外部输入。

输出格式：输出逐次追加元素触发倍增扩容的扩容倍率日志与预分配对照验证。

数据范围与约定：STL 动态数组内存模型与几何级数扩容。

思路与算法

1. 倍增扩容的均摊复杂度
std::vector 之所以能够保证尾部插入的均摊时间复杂度为 O(1)，关键在于几何级数扩容（GCC 采用 2 倍扩容，MSVC 采用 1.5 倍扩容）。若采用线性增量（如每次固定增加 10），插入 N 个元素的总耗时将恶化为 O(N^2)。

2. 扩容的三步代价
一旦 size() == capacity()：①在堆上开辟 1.5 或 2 倍的新连续内存；②将旧元素按移动（若移动构造带 noexcept）或拷贝复制到新空间；③析构并释放旧空间。此时指向原 vector 的所有迭代器、指针与引用全部失效！

3. reserve 与 resize 的根本区别
reserve(n) 仅改变 capacity，不改变 size，不构造新元素；resize(n) 不仅改变容量，还会改变 size 并就地调用默认构造函数填充元素。

完整程序

#include <iostream>
#include <vector>

void traceVectorGrowth() {
    std::vector<int> vec;
    size_t prevCap = vec.capacity();
    const int* prevData = vec.data();

    std::cout << "--- 1. 逐个 push_back 观察自动扩容迁移 ---\n";
    for (int i = 1; i <= 35; ++i) {
        vec.push_back(i);
        if (vec.capacity() != prevCap) {
            std::cout << "触发扩容 -> 元素数 size: " << vec.size()
                      << ", 旧容量: " << prevCap 
                      << " => 新容量 capacity: " << vec.capacity()
                      << ", 底层缓冲区是否换址: " << (vec.data() != prevData ? "是" : "否") << "\n";
            prevCap = vec.capacity();
            prevData = vec.data();
        }
    }
}

void testPreallocation() {
    std::cout << "\n--- 2. 使用 reserve(50) 预分配内存 ---\n";
    std::vector<int> fastVec;
    fastVec.reserve(50);
    std::cout << "初始 reserve 后 capacity: " << fastVec.capacity() 
              << ", 当前 size: " << fastVec.size() << "\n";

    const int* fixedData = fastVec.data();
    for (int i = 1; i <= 50; ++i) {
        fastVec.push_back(i);
    }
    std::cout << "插入 50 个元素后，内存地址是否发生迁移: " 
              << (fastVec.data() == fixedData ? "【完全未迁移，零重分配】" : "发生迁移") << "\n";
}

int main() {
    traceVectorGrowth();
    testPreallocation();
    return 0;
}

运行示例

输出：

--- 1. 逐个 push_back 观察自动扩容迁移 ---
触发扩容 -> 元素数 size: 1, 旧容量: 0 => 新容量 capacity: 1, 底层缓冲区是否换址: 是
触发扩容 -> 元素数 size: 2, 旧容量: 1 => 新容量 capacity: 2, 底层缓冲区是否换址: 是
触发扩容 -> 元素数 size: 3, 旧容量: 2 => 新容量 capacity: 4, 底层缓冲区是否换址: 是
触发扩容 -> 元素数 size: 5, 旧容量: 4 => 新容量 capacity: 8, 底层缓冲区是否换址: 是
触发扩容 -> 元素数 size: 9, 旧容量: 8 => 新容量 capacity: 16, 底层缓冲区是否换址: 是
触发扩容 -> 元素数 size: 17, 旧容量: 16 => 新容量 capacity: 32, 底层缓冲区是否换址: 是
触发扩容 -> 元素数 size: 33, 旧容量: 32 => 新容量 capacity: 64, 底层缓冲区是否换址: 是

--- 2. 使用 reserve(50) 预分配内存 ---
初始 reserve 后 capacity: 50, 当前 size: 0
插入 50 个元素后，内存地址是否发生迁移: 【完全未迁移，零重分配】