vector 面试点总结

ps：部分内容使用“AI”查询

一、入门

1、什么是`vector`

动态数组容器，支持自动扩容、随机访问和连续内存存储。

2、怎么创建-初始化vector

std::vector<int> v;  // 创建空vectorstd::vector<int> v = {1, 2, 3};  // 直接初始化std::vector<int> v(5, 0); // 指定大小和值（5个0）

3、访问方式

operator[]（无边界检查）： int v = vec[6];
at()（有边界检查）: vec.at(6) = 8;

4、`size()`和`capacity()`的区别？

size()：当前元素数量。—— 实际的（比如下课时间，班里只有10个人）
capacity()：当前分配的内存可容纳的元素数量（capacity >= size）—— resize改变的是capacity（比如下课时间，班里只有10个人，但是班级里座位能容纳50个学生）

5、vector 在堆上

二、进阶

1、扩容机制

当size == capacity时，容器会分配一块更大的连续内存块，新容量通常是当前容量的 1.5~2倍（具体倍数因实现而异，例如 GCC 默认采用 1.5 倍，而 MSVC 常用 2 倍）。

容器将旧内存中的所有元素复制或移动到新内存中。

复制：适用于不支持移动语义的类型（如 std::array）。
移动：适用于支持移动语义的类型（如 std::string、自定义类），可避免深拷贝开销

释放：旧内存被释放，容器内部指针更新为新内存地址

均摊时间复杂度：push_back 的均摊时间复杂度为 O(1)，但每次扩容操作需 O(n)时间（n 为当前元素数量）。若频繁触发扩容（如循环中不断 push_back），总时间复杂度可能退化为 O(n²)，显著影响性能

代价： 时间复杂度O(n)，可能影响性能

2、如何避免频繁扩容

使用reserve(n)预分配内存

3、迭代器失效的场景

vector内存布局：[1, 2, 3, 4, 5]
迭代器it指向元素2
元素2被删除，后续元素3,4,5前移填补空缺。vector内存布局变为：[1, 3, 4, 5]。it迭代器失效（指向原位置2，但该位置已被覆盖）。erase()返回新迭代器new_it，指向原it的下一个元素3

// 正确更新迭代器例子
it = vec.erase(it); // it 现在指向 3

插入/删除元素（尤其是非尾部操作）可能导致迭代器失效。

比如：扩容时，会导致复制或移动内容到新内存中，同时释放原始内存，容器内部指针更新为新内存地址。原有迭代器指向的旧内存空间被释放，导致迭代器失效。

std::vector<int> vec = {1,2,3};
auto it = vec.begin(); // 指向1
vec.insert(it, 0);     // 可能扩容，it失效

删除元素时，后续元素会向前移动填补空位，导致被删除元素及其后的迭代器失效

在中间或开头插入/删除元素时，操作点之后的所有迭代器均失效

解决方法：

a、重新获取迭代器或使用范围for循环
b、insert和erase等函数返回指向新有效位置的迭代器，可直接更新迭代器

it = vec.insert(it, 0); // 插入后返回新迭代器
it = vec.erase(it);     // 删除后返回下一个有效迭代器

c、范围for循环（推荐）

// 此方法仅适用于删除第一个符合条件的元素。若需删除多个元素，必须采用其他方法（如erase-remove惯用法或反向遍历
for (auto& elem : vec) {if (elem % 2 == 0) {vec.erase(std::find(vec.begin(), vec.end(), elem));break; // 循环迭代器未再被使用，避免了后续可能的失效访问。}
}

d、反向遍历：从后向前删除元素，避免影响未遍历的迭代器。

std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto rit = vec.rbegin(); rit != vec.rend(); ) {if (*rit % 2 == 0) {rit = decltype(rit)(vec.erase(std::next(rit).base()));} else {++rit;}
}
// 反向迭代器遍历：通过rbegin()和rend()获取反向迭代器范围，实现从末尾向开头的遍历
// std::next(it).base()将反向迭代器转换为对应的正向迭代器（指向当前元素的前一个元素）
// 调用vec.erase()删除该元素，并返回下一个有效正向迭代器

反向迭代器rit初始化为vec.rbegin()（指向5）

rit指向4（偶数），执行vec.erase(std::next(rit).base())

4被删除，5前移填补空缺

rit更新为vec.rend()（循环结束）

e、 erase-remove

std::remove将待删除元素移到容器末尾，并返回新逻辑末尾的迭代器；erase根据该迭代器真正删除元素。
remove_if标记待删除元素，将不需要删除的元素移到vector前端，返回“新逻辑末尾”迭代器new_end。

通过new_end和vec.end()范围删除剩余元素

std::vector<int> vec = {1, 2, 3, 4, 5};
auto new_end = std::remove_if(vec.begin(), vec.end(), [](int n) {return n % 2 == 0; // 删除偶数
});
vec.erase(new_end, vec.end()); // 删除 2,4

4、push_back与emplace_back的区别

push_back与emplace_back的区别主要体现在对象构造方式和性能效率上

push_back：需要先构造一个完整的对象（临时对象或已有对象），再通过拷贝/移动构造函数将其添加到容器中
emplace_back：直接在容器的内存空间中调用对象的构造函数，无需临时对象，避免拷贝/移动

性能差异

简单类型（如int）：两者性能几乎无差异，因为int的构造/拷贝成本极低

自定义复杂类型：emplace_back通过避免临时对象和拷贝操作，显著提升性能

struct Complex { Complex(int, double); }; // 高成本构造函数
vec.emplace_back(42, 3.14); // 直接构造，效率高
vec.push_back(Complex(42, 3.14)); // 需先构造临时对象再拷贝

5、vector<bool> 使用的是bit，不能取地址

三、高阶

1、如何快速释放`vector`的内存？

shrink_to_fit(); //请求容量等于大小（非强制）std::vector<int>(vec).swap(vec);  // 强制释放多余内存

`shrink_to_fit()` 的实现与效果（内存地址改变，原容器的迭代器、指针、引用可能失效）

目标：释放 vector 未使用的内存（即 capacity > size 的部分），使 capacity 尽可能接近 size。

创建临时容器：生成一个空的临时 vector，使用与原容器相同的分配器。
预分配精确内存：临时容器调用 reserve(size)，使其容量恰好等于原容器的当前元素数量（size）。
复制元素：将原容器的所有元素复制到临时容器中。
内存交换：通过 swap 交换两个容器的内部指针（指向数据内存、size 和 capacity 的指针）。
销毁临时容器：临时容器析构时，释放原容器之前占用的多余内存。

`std::vector<int>(vec).swap(vec)` 的实现与效果

目标：通过构造临时对象并交换内存，强制将 capacity 缩减到 size。

构造临时对象：std::vector<int>(vec) 调用复制构造函数，生成一个临时 vector。**新容器的 capacity 等于原容器的 size**（因为复制构造函数仅复制元素，不保留多余容量）
交换内存：通过 swap(vec) 交换临时容器与原容器的内部指针。
销毁临时对象：临时对象析构时，释放原容器的旧内存（此时临时对象持有原容器的旧内存）。
结果：原容器的 capacity 变为临时对象的 size，即精确匹配当前元素数量。

2、`vector`与`list`的核心差异？

vector支持O(1)随机访问，插入/删除非尾部元素代价高；

list插入/删除任意位置高效，无法随机访问

3、移动语义在`vector`中的应用？

std::vector<std::string> v1 = {"a", "b"};
std::vector<std::string> v2 = std::move(v1);  // v1变为空，v2接管资源

4、自定义分配器如何与`vector`结合？

通过模板参数指定分配器类型

std::vector<int, MyAllocator<int>> v;  // 使用自定义分配器

5、vector里面的内存总是连续的吗？

std::vector 的内存布局始终是连续的。std::deque 虽支持高效随机访问，但其内存布局为分段连续（通过多个独立块实现）