vector底层原理和扩容过程

简要回答

Vector是C++ STL中的动态数组容器，底层使用连续内存存储元素，支持随机访问。

当容量不足时，会进行扩容操作，通常以一定比例(如2倍)分配新内存，拷贝原有元素并释放旧内存。

详细回答

• 底层结构：

Vector使用动态分配的连续数组存储元素，维护三个关键指针：_start(指向首元素)、_finish(指向最后一个元素的下一个位置)、_end_of_storage(指向分配内存的末尾)

• 扩容机制：

当size() == capacity()时插入新元素触发扩容

分配新内存(通常为原容量的2倍，具体实现可能不同)，将原有元素拷贝，释放旧内存，更新内部指针

• 时间复杂度：

随机访问：O(1)

尾部插入/删除：平均O(1)(考虑分摊成本)

中间插入/删除：O(n)

换句话讲就是，三个要点，开头位置，当前用了多少，总共能装多少。

当装满了还要装东西，它会

找个更大的盒子（通常是之前的两倍），原来盒子的东西全部放入新盒子，旧盒子扔掉，记住新盒子的大小和装了多少东西

适用场景

需要频繁随机访问元素

主要在尾部进行插入删除操作

元素数量变化不大或可预估

需要保证数据在内存中的连续性

• 但以下情况下不适用

频繁在头部或中部插入删除

元素数量极大且无法预估

对内存使用非常敏感的场景

代码示例

#include <iostream>
#include <vector>

void printVectorInfo(const std::vector<int>& v) {
    std::cout << "Size: " << v.size()
              << ", Capacity: " << v.capacity()
              << ", Address: " << &v[0] << std::endl;
}

int main() {
    std::vector<int> vec;

    // 观察扩容过程
    for (int i = 0; i < 20; ++i) {
        vec.push_back(i);
        printVectorInfo(vec);
    }

    // 预留空间避免频繁扩容
    std::vector<int> vec2;
    vec2.reserve(100);  // 预先分配100个元素空间
    std::cout << "\nAfter reserve:\n";
    printVectorInfo(vec2);

    return 0;
}

知识拓展

• 知识图解

• 面试官可能追问

  1.为什么选择2倍扩容而不是固定大小扩容？

2倍扩容分摊时间复杂度为O(1)，而固定大小扩容为O(n)，2倍扩容平均下来每次加东西成本更低，固定大小扩容随着东西变多会越来越慢

2.如何避免频繁扩容带来的性能问题？

使用reserve()预先分配足够空间，或使用带大小的构造函数

3.vector和list的主要区别是什么？

专业：vector连续存储，随机访问高效；list节点分散，插入删除高效

4.如何判断vector扩容的具体策略？

可通过capacity()观察增长模式，或查阅特定STL实现的源代码