一、vector底层到底是什么vector可以简单理解成一块动态申请的连续内存。例如std::vectorint 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::vectorint 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为什么需要扩容假设当前 vectorsize 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::vectorStudent 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::vectorint nums; nums.reserve(100);它主要改变capacity但是size不变例如size 0 capacity 100可以理解成提前准备100个元素的空间 但现在一个元素都没有所以不能因为nums.reserve(100);就直接认为nums[50] 10;是合理的。因为size仍然是0还不存在第 50 个有效元素。而resize();改变的是size例如std::vectorint nums; nums.resize(5);此时size 5真的已经存在 5 个元素┌───┬───┬───┬───┬───┐ │ 0 │ 0 │ 0 │ 0 │ 0 │ └───┴───┴───┴───┴───┘如果新的size超过当前capacityresize也可能触发扩容。所以可以简单区分reserve ↓ 提前准备空间 ↓ 主要改变capacityresize ↓ 改变真正的元素数量 ↓ 改变size再看push_back();例如nums.push_back(10);表示在vector末尾增加一个元素如果size capacity当前空间还有位置直接在尾部构造例如size 3 capacity 8执行push_back(100);通常不需要重新申请内存。但如果size capacity空间已经满了push_back ↓ 触发扩容因此如果提前知道大概需要存100000个元素可以std::vectorint nums; nums.reserve(100000);然后再不断nums.push_back(...);这样可以减少中间多次扩容。三个接口可以简单记成操作sizecapacity主要作用reserve(n)一般不改变至少准备到 n提前预留空间resize(n)改变必要时扩大改变有效元素数量push_back(x)1空间不足时扩大尾部增加元素五、为什么扩容会导致迭代器失效这是 vector 面试中非常经典的问题。例如std::vectorint 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::vectorint 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::vectorint 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