C++ Vector 容器详解：基本用法与迭代器失效

注意：不同编译器下 vector 的扩容策略不同：

• VS 下按 1.5 倍增长
• g++ 下按 2 倍增长

三、Vector 的增删查改

3.1 基本操作

vector<int> v;
// 增
v.push_back(10); // 尾插
v.insert(v.begin(), 5); // 在指定位置插入
// 删
v.pop_back(); // 尾删
v.erase(v.begin()); // 删除指定位置
v.clear(); // 清空
// 查
auto it = find(v.begin(), v.end(), 10); // 查找元素
if (it != v.end()) {
    cout << "找到了";
}
// 改
v[0] = 100; // 像数组一样访问

四、迭代器失效问题（重点！）

迭代器失效是使用 vector 时最容易出错的问题之一。简单说，就是当 vector 发生某些操作后，之前获取的迭代器指向的内存可能已经无效。

4.1 导致迭代器失效的操作

1. 扩容操作：push_back、resize、reserve、insert 等可能导致扩容
2. 删除操作：erase 删除元素
3. 赋值操作：assign

4.2 错误示例

vector<int> v = {1, 2, 3, 4};
auto it = v.begin();
v.push_back(5); // 可能导致扩容，it 失效！
// 错误！it 可能指向已释放的内存
while (it != v.end()) {
    cout << *it << " ";
    ++it;
}

4.3 正确做法

// 删除所有偶数 - 正确写法
vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin();
while (it != v.end()) {
    if (*it % 2 == 0) {
        it = v.erase(it); // erase 返回下一个有效迭代器
    } else {
        ++it;
    }
}

五、Vector 在算法题中的应用

5.1 只出现一次的数字（异或技巧）

int singleNumber(vector<int>& nums) {
    int value = 0;
    for (auto e : nums) {
        value ^= e; // 利用 a^a=0 的特性
    }
    return value;
}

5.2 杨辉三角

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 j = 1; j < i; ++j) {
            vv[i][j] = vv[i-1][j] + vv[i-1][j-1];
        }
    }
    return vv;
}

六、Vector 的模拟实现注意事项

6.1 深拷贝问题

在模拟实现 vector 时，reserve 中不能使用 memcpy 来拷贝元素，尤其是元素类型涉及资源管理（如 string）时：

// 错误！浅拷贝会导致问题
void reserve(size_t n) {
    // ...
    memcpy(_newStart, _start, sizeof(T) * size()); // 危险！
}
// 正确做法：使用循环赋值，调用元素的拷贝构造
for (size_t i = 0; i < size(); ++i) {
    _newStart[i] = _start[i]; // 调用 T 的 operator= 或拷贝构造
}

6.2 动态二维数组

// 创建 n 行的二维数组
vector<vector<int>> vv(n);
// 每行设置不同大小
for (int i = 0; i < n; ++i) {
    vv[i].resize(i + 1, 1);
}

七、实战练习建议

1. 基础操作：熟练掌握 push_back、pop_back、operator[]、size 等常用接口
2. 迭代器理解：理解迭代器失效的原因及解决方案
3. OJ 练习：
   • 删除排序数组中的重复项
   • 只出现一次的数字 II/III
   • 数组中出现次数超过一半的数字
   • 电话号码字母组合

八、总结

vector 是 C++ 中最实用、最高效的容器之一，掌握它需要：

• 理解其底层是动态数组
• 熟悉常用接口的使用场景
• 特别注意迭代器失效问题
• 了解不同编译器下的扩容策略差异