---

一、vector 核心概念速查

1.1 本质

vector 是一个动态数组，底层是连续内存空间，迭代器是原生指针 T*。

1.2 构造函数（重点掌握）

构造函数	说明
vector<T> v;	无参构造
vector<T> v(n, val);	n 个 val 构造并初始化
vector<T> v(first, last);	迭代器区间构造
vector<T> v(const vector& x);	拷贝构造

---

二、核心接口（必须熟练）

2.1 容量相关

接口	作用	注意
size()	有效元素个数
capacity()	当前容量大小
empty()	判空
resize(n, val)	改变 size，可能扩容	会改变 size，新元素用 val 填充
reserve(n)	改变 capacity	只扩容不改变 size，不初始化

2.2 增删查改

接口	作用	注意
push_back(val)	尾插	可能触发扩容
pop_back()	尾删
insert(pos, val)	在 pos 前插入	可能触发扩容
erase(pos)	删除 pos 位置元素	返回删除后的下一个有效迭代器
operator[]	随机访问	不检查越界，高效
swap(v1, v2)	交换两个 vector

注意：find 不是 vector 的成员函数，是 <algorithm> 中的算法。

2.3 迭代器

接口	说明
begin() / end()	正向迭代器（end 是最后一个元素的下一个位置）
rbegin() / rend()	反向迭代器

---

三、扩容机制（面试高频）

3.1 扩容倍数

平台	STL 版本	扩容倍数
VS (Windows)	PJ 版	1.5 倍
g++ (Linux)	SGI 版	2 倍

不要固化地认为 vector 一定是 2 倍扩容，具体取决于实现需求。

3.2 reserve vs resize（高频易混淆）

	reserve(n)	resize(n, val)
改变 capacity	是	可能
改变 size	否	是（变为 n）
初始化新元素	否	是（用 val）
使用场景	提前知道元素个数，避免反复扩容	需要填充默认值

// 最佳实践：提前 reserve 避免反复扩容
vector<int> v;
v.reserve(100);  // 已知要存 100 个元素
for (int i = 0; i < 100; ++i)
    v.push_back(i);  // 不会触发扩容

3.3 扩容带来的代价

• 开辟新空间（1.5倍或2倍）
• 拷贝/移动旧元素到新空间
• 释放旧空间
• 迭代器失效

---

四、迭代器失效（重点中的重点）

4.1 什么是迭代器失效？

迭代器底层是原生指针 T*。当 vector 底层空间发生变化（扩容），旧空间被释放，迭代器仍指向已释放的内存，继续使用会导致程序崩溃或未定义行为。

4.2 导致迭代器失效的操作

操作	失效原因	解决办法
push_back	可能扩容	操作后重新获取迭代器
insert	可能扩容 + 插入位置后元素后移	用返回值：it = v.insert(it, val)
erase	删除位置后元素前移	用返回值：it = v.erase(it)
resize	可能扩容	操作后重新获取迭代器
reserve	改变底层空间	操作后重新获取迭代器
assign	可能改变底层空间	操作后重新获取迭代器

4.3 删除偶数的正确与错误示例

错误写法（程序可能崩溃）：

auto it = v.begin();
while (it != v.end()) {
    if (*it % 2 == 0)
        v.erase(it);   // erase 后 it 失效
    ++it;               // 失效的 it 再 ++ 会崩溃
}

正确写法（用 erase 的返回值更新迭代器）：

auto it = v.begin();
while (it != v.end()) {
    if (*it % 2 == 0)
        it = v.erase(it);  // erase 返回下一个有效迭代器
    else
        ++it;              // 只有不删除时才 ++
}

核心规则：erase(it) 后 it 已失效，必须用返回值更新！

4.4 VS vs Linux 对迭代器失效的态度

平台	检测严格程度	表现
VS (PJ版)	严格	失效后访问直接崩溃
Linux g++ (SGI版)	宽松	可能不崩溃，但结果错误

不要依赖平台宽容！迭代器失效后必须重新赋值。

4.5 string 的迭代器也会失效

string 在 insert、扩容、erase 等操作后，迭代器同样会失效，原理与 vector 一致。

---

五、memcpy 拷贝问题（模拟实现必考）

5.1 核心结论

如果对象涉及资源管理（如动态内存），千万不能用 memcpy 进行拷贝，因为 memcpy 是浅拷贝，会导致内存泄漏甚至程序崩溃。

5.2 问题场景

vector<string> v;
v.push_back("1111");
v.push_back("2222");
v.push_back("3333");

当 vector<string> 扩容时，如果用 memcpy 拷贝 string 对象：

1. memcpy 按二进制原封不动拷贝
2. string 内部有指向堆内存的指针
3. 新旧两个 string 对象指向同一块堆内存
4. 旧对象析构释放内存 → 新对象的指针变成野指针
5. 新对象析构时再次释放 → double free，程序崩溃

5.3 正确做法

• 对内置类型（如 int）：memcpy 高效且安全
• 对自定义类型（如 string）：必须用逐个赋值或 std::copy，触发深拷贝

---

六、动态二维数组

vector<vector<int>> vv(n);   // n 行，每行是空的 vector<int>
for (int i = 0; i < n; ++i)
    vv[i].resize(i + 1, 1);  // 每行 resize 为 i+1 个元素，值为 1

• vv[i] 的类型是 vector<int>
• vv[i][j] 等价于先取行，再取列
• 与标准二维数组存储结构不同：二维 vector 的每一行是独立分配的连续内存，不是一整块连续内存

杨辉三角核心代码

vector<vector<int>> generate(int numRows) {
    vector<vector<int>> vv(numRows);
    for (int i = 0; i < numRows; ++i)
        vv[i].resize(i + 1, 1);            // 每行初始化为 1
    for (int i = 2; i < numRows; ++i)
        for (int j = 1; j < i; ++j)
            vv[i][j] = vv[i-1][j] + vv[i-1][j-1];  // 杨辉三角递推
    return vv;
}

---

七、常见 OJ 题型与解法

题目	核心思路
只出现一次的数字 I	异或：a ^ a = 0，遍历异或，剩下的就是唯一出现一次的数
杨辉三角	vv[i].resize(i+1, 1) + 递推 [i][j] = [i-1][j] + [i-1][j-1]
删除排序数组重复项	双指针，operator[] 遍历
只出现一次的数字 II/III	位运算统计每一位 1 的个数取模
数组中出现次数超过一半	摩尔投票法 / 排序取中间
电话号码字母组合	回溯 DFS，vector<string> 存结果

---

八、复习自测问答

Q1：reserve 和 resize 的区别？

答： reserve 只改变 capacity，不改变 size，不会初始化新元素。resize 改变 size，如果新 size 大于原 size，用指定值填充新增元素，可能触发扩容。

Q2：VS 下 vector 扩容倍数是多少？g++ 呢？

答： VS（PJ 版 STL）是 1.5 倍，g++（SGI 版 STL）是 2 倍。

Q3：为什么不建议在循环中使用 push_back 而不提前 reserve？

答： 每次 push_back 可能触发扩容，扩容涉及开辟新空间、拷贝元素、释放旧空间，频繁扩容效率低。提前 reserve 一次性分配足够空间，避免反复扩容。

Q4：erase 删除元素后，迭代器怎么了？怎么写才安全？

答： erase(pos) 后，pos 及之后的所有迭代器都失效。安全写法：it = v.erase(it);，用返回值更新迭代器。

Q5：为什么 vector<string> 扩容时不能用 memcpy？

答： memcpy 是浅拷贝，string 内部有指向堆内存的指针。浅拷贝导致两个 string 对象指向同一块内存，析构时 double free，程序崩溃。必须逐个赋值触发深拷贝。

Q6：迭代器失效的本质原因是什么？

答： vector 迭代器底层是原生指针 T*。扩容后旧空间被释放，指针变成野指针，继续访问导致未定义行为。

Q7：哪些操作会导致 vector 迭代器失效？

答： push_back、insert、erase、resize、reserve、assign 等可能改变底层空间的操作。解决办法是操作后重新获取迭代器。

Q8：vector<vector<int>> 的二维数组在内存中是连续的吗？

答： 不是。每行（每个 vector<int>）是独立分配的连续内存，但行与行之间不一定连续。这与 int arr[M][N] 栈上二维数组不同。

Q9：find 是 vector 的成员函数吗？

答： 不是。find 是 <algorithm> 头文件中的泛型算法。

Q10：vector 的 end() 指向哪里？

答： 指向最后一个元素的下一个位置，不是最后一个元素。end() 位置没有有效元素，不能解引用。

复习建议：重点掌握第 3-5 章（扩容机制、迭代器失效、memcpy 问题），这是面试和笔试最高频的考点。