4. 序列式容器（vector）深度解析：动态数组的内存管理、push_back与insert的源码

好，咱们今天来聊聊 vector。说实话，vector 是我在项目里用得最多的容器，没有之一。它就像 C++ 里的瑞士军刀——简单、好用，但你真的了解它底层的「肌肉」是怎么长的吗？

很多人用 vector 就是 push_back 往里塞数据，觉得它就是个能自动扩容的数组。嗯，这个理解没错，但太浅了。你想想看，如果每次 push_back 都重新分配内存、拷贝所有元素，那性能得多差？STL 的设计者当然不会这么傻。

4.1 动态数组的内存管理：三个指针的博弈

vector 底层其实就维护了三个指针：

• start：指向已分配内存的起始位置
• finish：指向已构造元素的末尾（即最后一个元素的下一个位置）
• end_of_storage：指向已分配内存的末尾

说白了，size() 就是 finish - start，capacity() 就是 end_of_storage - start。这个设计非常巧妙，我当年第一次看源码时，忍不住拍了一下大腿。

为什么会是 1.5 倍或 2 倍？我简单解释一下：如果每次只增加一个元素的空间，那插入 n 个元素的时间复杂度就是 O(n²)，这谁受得了？而采用倍增策略，均摊下来每次 push_back 的时间复杂度是 O(1)。

4.2 push_back 源码剖析：尾部插入的奥秘

咱们直接看源码（简化版，但核心逻辑不变）：

void push_back(const T& value) {
    if (finish != end_of_storage) {
        // 还有空闲空间，直接构造
        allocator.construct(finish, value);
        ++finish;
    } else {
        // 空间不足，需要扩容
        insert_aux(end(), value);
    }
}

你看，逻辑其实很简单：有空间就直接在 finish 位置构造元素，然后 finish 后移一位。没空间了，就调用 insert_aux 去扩容。

那 insert_aux 又是怎么做的呢？

void insert_aux(iterator position, const T& value) {
    // 计算新容量：如果旧容量为0，新容量为1；否则为旧容量的2倍
    size_type old_size = size();
    size_type new_size = old_size != 0 ? 2 * old_size : 1;

    // 分配新内存
    iterator new_start = allocator.allocate(new_size);
    iterator new_finish = new_start;

    // 拷贝旧元素到新内存
    try {
        // 拷贝插入点之前的元素
        new_finish = uninitialized_copy(start, position, new_start);
        // 构造新元素
        allocator.construct(new_finish, value);
        ++new_finish;
        // 拷贝插入点之后的元素
        new_finish = uninitialized_copy(position, finish, new_finish);
    } catch(...) {
        // 异常处理：销毁已构造的元素，释放新内存
        destroy(new_start, new_finish);
        allocator.deallocate(new_start, new_size);
        throw;
    }

    // 销毁旧元素，释放旧内存
    destroy(start, finish);
    allocator.deallocate(start, end_of_storage - start);

    // 更新指针
    start = new_start;
    finish = new_finish;
    end_of_storage = new_start + new_size;
}

嗯，这里要注意几个细节：

• 异常安全：如果拷贝过程中抛出异常，已经构造的元素会被正确销毁，新分配的内存也会被释放。这就是 STL 的「要么全做，要么不做」原则。
• 元素移动：在 C++11 之后，如果元素类型支持移动语义，uninitialized_copy 会退化为 uninitialized_move，性能会更好。我建议你在自定义类型中实现移动构造函数和移动赋值运算符。

4.3 insert 源码剖析：中间插入的代价

insert 比 push_back 复杂得多，因为它可能需要在任意位置插入元素。咱们看一个简化版本：

iterator insert(iterator position, const T& value) {
    size_type offset = position - start;

    if (finish != end_of_storage && position == end()) {
        // 尾部有空闲空间，且插入位置是末尾
        allocator.construct(finish, value);
        ++finish;
    } else {
        // 需要扩容或插入位置在中间
        insert_aux(position, value);
    }

    return start + offset;
}

如果插入位置在中间，且还有空闲空间，STL 会怎么做？

// 假设还有空闲空间，且插入位置在中间
void insert_aux(iterator position, const T& value) {
    // 在末尾构造一个元素（拷贝最后一个元素）
    allocator.construct(finish, *(finish - 1));
    ++finish;

    // 将插入点之后的元素向后移动一位
    T* p = finish - 1;
    T* q = position.base();
    while (p != q) {
        *p = *(p - 1);
        --p;
    }

    // 在插入点赋值
    *position = value;
}

你看，这个过程其实就是在做「元素搬家」——先把最后一个元素拷贝到末尾的空闲位置，然后把插入点之后的元素依次后移，最后在插入点赋值。这个操作的时间复杂度是 O(n)，所以如果你需要频繁在中间插入，我建议你考虑 list 或 deque。

4.4 知识体系图：vector 的内存管理全貌

下面这张图总结了 vector 的核心机制，我建议你多看几遍：

4.5 总结与避坑指南

好了，咱们来捋一捋今天讲的重点：

• vector 的本质：三个指针管理的动态数组，size 和 capacity 是两个不同的概念
• 扩容策略：倍增（1.5x 或 2x），均摊 O(1) 的插入时间
• push_back：有空间直接构造，无空间扩容
• insert：中间插入需要移动元素，O(n) 时间复杂度
• 迭代器失效：扩容后所有迭代器、指针、引用都失效

vector 虽然简单，但用好它并不容易。理解了它的内存管理机制，你就能在合适的场景下做出正确的选择。嗯，今天就到这里吧。