企业官网建设流程全解析

一、vector底层到底是什么

vector可以简单理解成：

一块动态申请的连续内存。

例如：

std::vector<int> nums; nums.push_back(10); nums.push_back(20); nums.push_back(30);

底层大致可以理解成：

连续内存： ┌────┬────┬────┐ │ 10 │ 20 │ 30 │ └────┴────┴────┘

因为元素在内存中连续排列，所以可以直接：

nums[0]; nums[1]; nums[2];

访问。

假设第一个元素地址是：

0x1000

一个int占 4 字节，那么：

nums[0] → 0x1000 nums[1] → 0x1004 nums[2] → 0x1008

所以访问某个位置只需要计算：

首地址 + 下标 × 元素大小

因此：

nums[i];

的时间复杂度可以做到：

O(1)

这也是 vector 和list一个很大的区别。

list的元素不是连续存储：

Node1 → Node2 → Node3 → Node4

想访问第 100 个元素，需要从前面不断往后找。

而 vector：

连续内存 ↓ 直接计算地址

所以支持：

随机访问

为了管理这块动态内存，可以把 vector 的底层简化理解成维护三个位置：

start ↓ ┌────┬────┬────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ │ │ │ └────┴────┴────┴────┴────┴────┘ ↑ ↑ finish end_of_storage

也就是：

start ↓ 第一个元素的位置 finish ↓ 当前最后一个有效元素的下一个位置 end_of_storage ↓ 整块内存空间的末尾

因此：

size = finish - start capacity = end_of_storage - start

例如：

std::vector<int> nums; nums.reserve(10); nums.push_back(1); nums.push_back(2); nums.push_back(3);

此时可能是：

size = 3 capacity = 10

也就是：

真正存了3个元素 但是已经准备好了10个元素的空间

所以一定要区分：

size

和：

capacity

它们不是一个概念。

二、vector为什么需要扩容

假设当前 vector：

size = 4 capacity = 4

内存：

┌────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ 40 │ └────┴────┴────┴────┘ 空间已经全部使用

这时候再：

nums.push_back(50);

原来的空间已经放不下了。

但是 vector 的数据必须：

连续存储

它不能简单地在旁边随便找一块空间：

旧内存： ┌────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ 40 │ └────┴────┴────┴────┘ 另一处： ┌────┐ │ 50 │ └────┘

如果这样存，数据就不连续了。

所以 vector 必须进行：

扩容

整个扩容过程可以理解成：

原空间不足 ↓ 申请一块更大的连续内存 ↓ 把原来的元素搬过去 ↓ 构造新元素 ↓ 销毁旧元素 ↓ 释放旧内存

例如原来：

capacity = 4

旧区域：

┌────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ 40 │ └────┴────┴────┴────┘

现在申请一块更大的空间：

┌────┬────┬────┬────┬────┬────┬────┬────┐ │ │ │ │ │ │ │ │ │ └────┴────┴────┴────┴────┴────┴────┴────┘

然后搬过去：

┌────┬────┬────┬────┬────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ 40 │ 50 │ │ │ │ └────┴────┴────┴────┴────┴────┴────┴────┘

最后原来的内存：

释放

这就是 vector 扩容的基本过程。

很多时候会听到：

vector按1.5倍扩容

或者：

vector按2倍扩容

这里需要注意：

C++ 标准并没有规定 vector 必须按照固定的 1.5 倍或者 2 倍扩容。

具体增长策略由：

STL实现 编译器 标准库版本

决定。

不同实现可能采用不同策略。

因此面试时更严谨的说法是：

vector 容量不足时一般会按照某种增长因子申请更大的连续内存，不同标准库的具体扩容倍数可能不同，常见实现可能采用约 1.5 倍或 2 倍增长。

为什么不每次只增加一个元素？

假设每次：

capacity + 1

那么连续插入 10000 个元素，就可能发生大量：

申请新内存 复制旧数据 释放旧内存

开销非常大。

采用成倍增长以后：

1 ↓ 2 ↓ 4 ↓ 8 ↓ 16 ↓ 32 ...

扩容次数会大幅减少。

这也是为什么：

push_back();

虽然偶尔一次扩容需要：

O(N)

但连续很多次push_back()的平均复杂度，也就是：

均摊复杂度

通常可以认为是：

O(1)

三、扩容时到底是拷贝还是移动

这里是 vector 面试中很容易继续被问到的一点。

假设：

class Student { public: Student() { std::cout << "构造" << std::endl; } Student(const Student &) { std::cout << "拷贝构造" << std::endl; } Student(Student &&) noexcept { std::cout << "移动构造" << std::endl; } };

然后：

std::vector<Student> students; students.push_back(Student()); students.push_back(Student()); students.push_back(Student());

当 vector 需要扩容时，旧内存中的对象必须被搬到：

新的内存区域

这时候有两种方案。

第一种：

拷贝构造

相当于：

Student newObject(oldObject);

第二种：

移动构造

相当于：

Student newObject(std::move(oldObject));

对于一个内部拥有大量资源的对象来说，移动通常比深拷贝成本更低。

例如：

class Buffer { private: char *data_; };

拷贝可能需要：

重新申请内存 ↓ 复制全部数据

而移动可以：

直接接管data_指针 ↓ 原对象置空

所以：

移动

通常会更高效。

但是这里又涉及：

noexcept

例如：

Student(Student &&other) noexcept;

为什么移动构造经常建议加：

noexcept

？

因为 vector 扩容时很重视：

异常安全

假设原来：

A B C D

准备搬到新空间。

已经成功移动：

A B

但是移动：

C

的时候突然抛异常。

如果前面的：

A B

已经被移动走，原对象状态可能已经发生变化。

vector 就比较难保证：

扩容失败以后 原来的vector仍然保持原状

因此标准库实现通常会根据类型特性决定：

优先移动 还是 优先拷贝

常见情况可以理解为：

移动构造是noexcept ↓ 优先使用移动

如果：

移动可能抛异常 但是类型又可以拷贝

为了更好的异常安全保证，实现可能选择：

拷贝构造

这也是：

std::move_if_noexcept

背后的一个重要思路。

所以面试问：

vector扩容时为什么移动构造最好写noexcept？

可以回答：

vector 扩容需要把旧元素搬到新的内存区域。如果类型的移动构造明确标记为noexcept，标准库可以更放心地使用移动来提高效率；如果移动可能抛异常而类型又支持拷贝，实现可能为了保证异常安全而选择拷贝。

所以：

vector扩容 ↓ 重新申请内存 ↓ 搬迁旧元素 ↓ 移动 / 拷贝 ↓ 释放旧内存

而不是简单：

realloc一下

就结束了。

四、resize、reserve和push_back有什么区别

这几个函数也是 vector 面试高频。

先来看：

reserve();

例如：

std::vector<int> nums; nums.reserve(100);

它主要改变：

capacity

但是：

size不变

例如：

size = 0 capacity = 100

可以理解成：

提前准备100个元素的空间 但现在一个元素都没有

所以不能因为：

nums.reserve(100);

就直接认为：

nums[50] = 10;

是合理的。

因为：

size仍然是0

还不存在第 50 个有效元素。

而：

resize();

改变的是：

size

例如：

std::vector<int> nums; nums.resize(5);

此时：

size = 5

真的已经存在 5 个元素：

┌───┬───┬───┬───┬───┐ │ 0 │ 0 │ 0 │ 0 │ 0 │ └───┴───┴───┴───┴───┘

如果新的size超过当前capacity：

resize

也可能触发扩容。

所以可以简单区分：

reserve ↓ 提前准备空间 ↓ 主要改变capacity

resize ↓ 改变真正的元素数量 ↓ 改变size

再看：

push_back();

例如：

nums.push_back(10);

表示：

在vector末尾增加一个元素

如果：

size < capacity

当前空间还有位置：

直接在尾部构造

例如：

size = 3 capacity = 8

执行：

push_back(100);

通常不需要重新申请内存。

但如果：

size == capacity

空间已经满了：

push_back ↓ 触发扩容

因此如果提前知道大概需要存：

100000个元素

可以：

std::vector<int> nums; nums.reserve(100000);

然后再不断：

nums.push_back(...);

这样可以减少中间多次扩容。

三个接口可以简单记成：

五、为什么扩容会导致迭代器失效

这是 vector 面试中非常经典的问题。

例如：

std::vector<int> nums = {1, 2, 3}; auto it = nums.begin();

这时：

it ↓ ┌───┬───┬───┐ │ 1 │ 2 │ 3 │ └───┴───┴───┘

假设继续：

nums.push_back(4);

并且这次恰好触发扩容。

vector 会：

申请新的内存 ↓ 搬迁所有元素 ↓ 释放原来的内存

也就是说：

原地址： 0x1000

可能变成：

新地址： 0x5000

原来的：

it

还保存：

0x1000

但是：

0x1000

那块内存已经被释放了。

因此：

*it

就变成了未定义行为。

这就是：

迭代器失效

实际上不仅是迭代器。

原来指向 vector 元素的：

指针 引用

也可能一起失效。

例如：

std::vector<int> nums = {1, 2, 3}; int *p = &nums[0]; int &ref = nums[1]; nums.push_back(4);

如果：

push_back触发扩容

那么：

p ref

也可能全部失效。

所以可以理解成：

vector扩容 ↓ 底层内存地址改变 ↓ 原来的iterator pointer reference ↓ 全部失效

这里还要区分：

push_back有没有发生扩容。

如果：

size < capacity

没有重新分配底层存储，一般不会因为单纯的尾插导致已有元素的引用、指针和迭代器全部失效；不过原来的end()会失效。

如果：

size == capacity

触发重新分配：

所有指向原元素的迭代器、指针和引用都会失效

另外：

erase();

也会导致部分迭代器失效。

例如：

std::vector<int> nums = {10, 20, 30, 40}; auto it = nums.begin() + 1; nums.erase(it);

删除：

20

以后，后面的元素需要向前移动：

原来： 10 20 30 40 删除20： 10 30 40

因此：

被删除位置 以及它后面的迭代器

都会失效。

所以面试时可以这样总结 vector 的迭代器失效：

如果 vector 发生重新分配，原来指向元素的迭代器、指针和引用都会失效；如果没有重新分配，push_back通常不会使已有元素的引用和指针失效，但原来的end()会变化。erase会使被删除位置以及其后的迭代器失效，因为后面的元素需要向前移动。

把整篇内容串起来，vector 的底层逻辑其实可以概括成：

vector ↓ 连续动态内存 ↓ size记录元素数量 capacity记录容量 ↓ 空间不足 ↓ 申请更大的连续内存 ↓ 移动或拷贝旧元素 ↓ 释放旧内存 ↓ 底层地址发生变化 ↓ 原来的迭代器可能失效

如果面试官问：

vector底层是怎么实现的？

可以直接回答：

vector底层使用一块连续的动态内存存储元素，因此支持 O(1) 随机访问。它内部需要维护当前元素数量和容量，当size达到capacity后继续插入元素，就需要申请一块更大的连续内存，再通过拷贝或移动构造把旧元素搬过去，最后释放旧内存。具体扩容倍数由标准库实现决定，并不是 C++ 标准固定要求的 1.5 倍或 2 倍。由于重新分配后底层地址发生变化，所以原来的迭代器、指针和引用都会失效。

如果继续追问：

为什么push_back平均是O(1)，明明扩容是O(N)？

可以回答：

单次扩容确实需要搬迁 N 个元素，是 O(N)，但 vector 一般采用增长容量而不是每次只增加一个位置，所以扩容不会每次发生。把多次 push_back 的总成本平均下来，其均摊时间复杂度是 O(1)。

如果继续问：

reserve有什么用？

可以回答：

reserve()可以提前申请足够的容量，减少后续连续插入过程中反复扩容和搬迁元素的次数。在能够预估元素数量时，提前 reserve 通常能够降低不必要的内存重新分配开销。

所以 vector 面试真正需要掌握的核心并不是只会：

push_back();

而是理解下面这一条完整链路：

连续内存 ↓ size / capacity ↓ 容量不足 ↓ 扩容 ↓ 拷贝或移动 ↓ noexcept与异常安全 ↓ 旧内存释放 ↓ 迭代器失效

这也是为什么 vector 看起来只是一个简单容器，却能连续考察：

动态内存 移动语义 异常安全 迭代器 时间复杂度

多个 C++ 基础知识点。

0voice · GitHub