C++第九讲：vector

C++第九讲：vector

vector 是STL 中最常用的序列式容器，本质是一个动态数组，彻底解决了 C 语言静态数组大小固定、手动管理内存的痛点。它支持随机访问、自动扩容，是所有 C++ 开发者日常开发的首选容器，也是面试第一高频考点。

一、vector 简介

1. 什么是 vector

vector 是 C++ 标准库提供的动态数组容器，可以存储任意类型的元素，底层是一段连续的内存空间。

• 自动管理内存：不需要手动申请 / 释放空间

• 支持随机访问：通过[]像数组一样访问元素，时间复杂度 O (1)

• 自动扩容：当空间不足时，自动申请更大的空间并拷贝元素

• 丰富的接口：提供了增删查改等常用操作

2. 为什么不用 C 语言数组

二、vector 常用接口（重点）

使用 vector 需要包含头文件：#include <vector>，所有接口都在std命名空间中。

1. 构造函数（4 个最常用）

代码示例

#include <iostream> #include <vector> using namespace std; ​ int main() { vector<int> v1; // 空vector vector<int> v2(5, 10); // 5个10 vector<int> v3(v2); // 拷贝v2 vector<int> v4(v2.begin(), v2.begin()+3); // 前3个元素：10,10,10 ​ // 用数组构造 int arr[] = {1,2,3,4,5}; vector<int> v5(arr, arr+sizeof(arr)/sizeof(int)); ​ return 0; }

2. 容量操作（面试高频）

核心考点：vector 的扩容机制

当 vector 的 size 达到 capacity 时，再插入元素会触发自动扩容：

1. 申请一块更大的新空间（VS 按1.5 倍扩容，G++ 按2 倍扩容）

2. 将旧空间的元素拷贝到新空间

3. 释放旧空间

4. 更新指针指向新空间

代码验证扩容倍数

void TestExpand() { vector<int> v; size_t sz = v.capacity(); cout << "初始容量：" << sz << endl; for (int i=0; i<100; ++i) { v.push_back(i); if (sz != v.capacity()) { sz = v.capacity(); cout << "扩容到：" << sz << endl; } } }

• VS 输出：1→2→3→4→6→9→13→19→28→42→63→94→141（1.5 倍）

• G++ 输出：1→2→4→8→16→32→64→128（2 倍）

优化技巧：提前 reserve 预留空间

如果知道大概要存储多少元素，提前用reserve预留空间，避免频繁扩容（扩容会拷贝元素，效率低）：

vector<int> v; v.reserve(100); // 提前预留100个元素空间 for (int i=0; i<100; ++i) { v.push_back(i); // 不会触发扩容 }

3. 增删查改操作

注意：find 不是 vector 的成员函数

查找元素需要使用<algorithm>头文件中的find算法：

#include <algorithm> vector<int> v = {1,2,3,4,5}; // 查找3，返回迭代器，找不到返回v.end() auto it = find(v.begin(), v.end(), 3); if (it != v.end()) { cout << "找到了：" << *it << endl; }

4. 迭代器

vector 的迭代器本质是原生指针，支持 ++、--、*、-> 等操作。

代码示例：三种遍历方式

int main() { vector<int> v = {1,2,3,4,5}; ​ // 1. []访问（推荐，最简洁） for (int i=0; i<v.size(); ++i) { cout << v[i] << " "; } cout << endl; ​ // 2. 迭代器 vector<int>::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; ​ // 3. 范围for（C++11推荐） for (auto e : v) { cout << e << " "; } cout << endl; ​ return 0; }

三、核心难点：迭代器失效（面试必考）

1. 什么是迭代器失效

vector 的迭代器本质是指向底层数组的指针，当底层空间被释放或元素位置发生改变时，原来的迭代器就会变成野指针，继续使用会导致程序崩溃或结果错误。

2. 两种导致迭代器失效的场景

场景 1：底层空间改变（扩容）

所有会导致扩容的操作都会使迭代器失效：reserve、resize、insert、push_back、assign等。

错误示例

int main() { vector<int> v = {1,2,3,4,5}; auto it = v.begin(); cout << "扩容前容量：" << v.capacity() << endl; // 5 ​ // 触发扩容，旧空间被释放，it变成野指针 v.reserve(100); cout << "扩容后容量：" << v.capacity() << endl; // 100 ​ // 错误：使用失效的迭代器，VS下直接崩溃，G++下结果错误 while (it != v.end()) { cout << *it << " "; ++it; } return 0; }

场景 2：指定位置删除元素（erase）

删除 pos 位置的元素后，pos 后面的元素会往前搬移，导致pos 及之后的迭代器失效（VS 下严格检测，G++ 下部分情况可能运行但结果错误）。

错误示例：删除所有偶数

// 错误写法 int main() { vector<int> v = {1,2,3,4}; auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { v.erase(it); // 删除后it失效 } ++it; // 访问失效的迭代器，崩溃 } return 0; }

正确写法

erase会返回删除元素的下一个位置的迭代器，用这个返回值更新 it：

// 正确写法 int main() { vector<int> v = {1,2,3,4}; auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { it = v.erase(it); // 用返回值更新it } else { ++it; } } return 0; }

3. 迭代器失效的解决方法

所有可能导致迭代器失效的操作后，重新获取迭代器。

• 扩容后：重新调用begin()获取新的迭代器

• erase 后：使用erase返回的迭代器

四、vector 底层原理与模拟实现

1. 底层结构

vector 的底层非常简单，只有三个指针：

• _start：指向数组的起始位置

• _finish：指向最后一个有效元素的下一个位置

• _endofstorage：指向数组容量的末尾位置

template<class T> class vector { private: T* _start; T* _finish; T* _endofstorage; };

核心关系

• size() = _finish - _start

• capacity() = _endofstorage - _start

2. 模拟实现核心函数

2.1 构造与析构

template<class T> class vector { public: // 无参构造 vector() : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) {} // 构造n个val vector(size_t n, const T& val = T()) : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { reserve(n); for (size_t i=0; i<n; ++i) { push_back(val); } } // 拷贝构造（深拷贝） vector(const vector<T>& v) : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { reserve(v.capacity()); for (const auto& e : v) { push_back(e); } } // 赋值运算符重载（现代版） vector<T>& operator=(vector<T> v) { swap(v); return *this; } // 析构函数 ~vector() { if (_start) { delete[] _start; _start = _finish = _endofstorage = nullptr; } } // 交换两个vector void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); } // ... 其他成员函数 private: T* _start; T* _finish; T* _endofstorage; };

2.2 容量操作：reserve

void reserve(size_t n) { if (n > capacity()) { size_t oldSize = size(); // 1. 申请新空间 T* tmp = new T[n]; // 2. 拷贝元素（不能用memcpy！自定义类型会浅拷贝） for (size_t i=0; i<oldSize; ++i) { tmp[i] = _start[i]; } // 3. 释放旧空间 delete[] _start; // 4. 更新指针 _start = tmp; _finish = _start + oldSize; _endofstorage = _start + n; } }

易错点：不能用 memcpy 拷贝自定义类型

memcpy 是浅拷贝，如果 vector 存储的是 string、vector 等自定义类型，memcpy 会导致多个对象共享同一块内存，析构时重复释放崩溃。必须用赋值运算符进行深拷贝。

2.3 尾插：push_back

void push_back(const T& val) { // 空间满了就扩容 if (_finish == _endofstorage) { size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newCapacity); } // 尾插元素 *_finish = val; ++_finish; }

2.4 访问与迭代器

T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; } iterator begin() { return _start; } iterator end() { return _finish; }

五、动态二维数组：vector<vector<T>>

vector 可以嵌套使用，实现动态二维数组，比 C 语言的二维数组更灵活。

1. 原理

vector<vector<int>> vv(n)表示一个包含 n 个vector<int>的 vector，每个元素都是一个独立的 vector。

2. 示例：杨辉三角

class Solution { public: vector<vector<int>> generate(int numRows) { // 创建numRows行的二维数组 vector<vector<int>> vv(numRows); // 每行的元素个数等于行号+1，初始化为1 for (int i=0; i<numRows; ++i) { vv[i].resize(i+1, 1); } // 填充中间元素：第i行第j列 = 第i-1行第j列 + 第i-1行第j-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 实战

1. 只出现一次的数字

// 要求：线性时间复杂度，不使用额外空间 class Solution { public: int singleNumber(vector<int>& nums) { int res = 0; for (int e : nums) { res ^= e; // 异或：相同为0，不同为1 } return res; } };

2. 删除排序数组中的重复项

// 要求：原地修改，空间复杂度O(1) class Solution { public: int removeDuplicates(vector<int>& nums) { if (nums.empty()) return 0; int slow = 0; for (int fast=1; fast<nums.size(); ++fast) { if (nums[fast] != nums[slow]) { nums[++slow] = nums[fast]; } } return slow + 1; } };

七、本章核心总结

1. vector 是动态数组，底层是连续内存，支持随机访问，自动扩容

2. 扩容机制：VS1.5 倍，G++2 倍，提前 reserve 可优化性能

3. 迭代器失效：扩容和 erase 会导致失效，解决方法是操作后重新获取迭代器

4. 模拟实现：核心是三个指针，深拷贝避免浅拷贝问题，不能用 memcpy 拷贝自定义类型

5. 常用接口：push_back、pop_back、operator []、reserve、resize、迭代器