vector 面试点总结
ps：部分内容使用“AI”查询
一、入门
1、什么是vector
动态数组容器，支持自动扩容、随机访问和连续内存存储。
2、怎么创建-初始化vector
std::vector<int> v; // 创建空vector
std::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,44、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 虽支持高效随机访问，但其内存布局为分段连续（通过多个独立块实现）