C++ STL vector 详解：基础用法、核心接口与实战算法
一、vector 容器简介
在学习 vector 之前，不妨回顾一下 string 类的实现。你会发现 vector 的接口比 string 少了很多。string 类诞生较早，STL 中很多容器都借鉴了它的特性，但 string 的部分接口在实际使用中显得比较鸡肋。
vector 本质上是一个动态顺序表，对应 C 语言初阶数据结构中的顺序表概念，只是用 C++ 封装得更优雅。
1. vector 的定义
vector 提供了多种构造函数来初始化对象：
| 构造函数声明 | 接口说明 |
|---|---|
vector() | 无参构造 |
vector(size_type n, const value_type& val) | 构造并初始化 n 个 val |
vector(const vector& x) | 拷贝构造 |
vector(InputIterator first, InputIterator last) | 使用迭代器范围初始化 |
二、vector 的使用实践
1. 输出与迭代器
vector 本身不支持直接通过 cin/cout 输出，我们需要封装一个打印函数。既可以用下标遍历，也可以用范围 for 循环。
void Print(const vector<int>& v) {
for (auto e : v) {
cout << e << " ";
}
cout << endl;
}
迭代器基础
迭代器是访问容器元素的指针抽象。常用接口如下：
| 接口 | 说明 |
|---|---|
begin() / end() | 获取首元素迭代器 / 尾后迭代器 |
rbegin() / rend() | 获取反向迭代器（从尾到头） |
实践示例：
void test_vector1() {
vector<int> v1; // 空 vector
vector<int> v2(10, 1); // 10 个 1
vector<int> v3(v2); // 拷贝构造
vector<int> v4(v3.begin(), v3.end()); // 范围构造
vector<int> v6 = { 1, 2, 3, 4, 5 }; // 列表初始化
Print(v2);
Print(v6);
}
2. 空间增长机制
vector 底层是连续内存，扩容时涉及内存分配和拷贝，开销较大。理解其增长策略对性能优化至关重要。
| 接口 | 说明 |
|---|---|
size() | 当前元素个数 |
capacity() | 当前容量大小 |
empty() | 判断是否为空 |
resize() | 改变 size，可能触发扩容或缩容 |
reserve() | 预分配 capacity，不改变 size |
扩容倍数差异
不同编译器实现的 STL 版本，扩容策略不同：
- VS (PJ 版本): 通常按 1.5 倍增长。
- g++ (SGI 版本): 通常按 2 倍增长。
不要固化认为都是 2 倍，具体取决于实现。测试代码可验证这一现象：
void TestVectorExpand() {
size_t sz = 0;
vector<int> v;
cout << "making v grow:\n";
for (int i = 0; i < 100; ++i) {
v.push_back(i);
if (sz != v.capacity()) {
sz = v.capacity();
cout << "capacity changed: " << sz << '\n';
}
}
}
Reserve 优化
如果已知需要存储的元素数量，提前调用 reserve 可以避免多次扩容带来的性能损耗。
void TestVectorExpandOP() {
vector<int> v;
v.reserve(100); // 提前预留空间
for (int i = 0; i < 100; ++i) {
v.push_back(i);
}
}
3. 增删查改操作
vector 只支持尾部插入和删除（push_back, pop_back），因为头部操作需要移动大量数据，效率低。若需头插/头删，可使用 insert 和 erase。
| 接口 | 说明 |
|---|---|
push_back | 尾插 |
pop_back | 尾删 |
insert | 指定位置前插入 |
erase | 删除指定位置元素 |
operator[] | 下标访问 |
实践示例：
void test_vector3() {
vector<int> v1 = { 1, 2, 3 };
v1.push_back(4);
// 头插
v1.insert(v1.begin(), 0);
// 中间插入
v1.insert(v1.begin() + 3, 0);
// 头删
v1.erase(v1.begin());
// 中间删除
v1.erase(v1.begin() + 3);
}
4. Emplace 机制
emplace 系列函数（如 emplace_back）在 C++11 引入，相比 push_back 能直接在容器内构建对象，避免临时对象的拷贝构造，效率更高。
struct AA {
int _a1 = 1, _a2 = 1;
AA(int a1 = 1, int a2 = 1) :_a1(a1), _a2(a2) {}
};
void test_vector4() {
vector<AA> v1;
AA aa1 = { 0, 0 };
v1.push_back(aa1); // 先构造再拷贝
v1.emplace_back(aa1); // 转发参数构造
v1.emplace_back(2, 2); // 直接传参构造，无需临时对象
}
三、经典算法题实战
1. 只出现一次的数字
题目描述： 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
思路： 利用异或运算性质，相同为 0，不同为 1。所有数异或一遍，成对的抵消，剩下的即为答案。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int val = 0;
for (auto e : nums) {
val ^= e;
}
return val;
}
};
- 时间复杂度： O(n)
- 空间复杂度： O(1)
2. 杨辉三角
题目描述： 给定行数 numRows，生成杨辉三角的前 numRows 行。
思路： 二维 vector 模拟。每行第一个和最后一个元素为 1，中间元素等于上一行同列与前一列之和。
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv;
vv.resize(numRows);
for (size_t i = 0; i < numRows; ++i) {
vv[i].resize(i + 1, 1);
for (size_t j = 1; j < vv[i].size() - 1; ++j) {
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
return vv;
}
};
- 时间复杂度： O(n²)
- 空间复杂度： O(n²)（用于存储结果）
四、完整代码展示
#include <iostream>
#include <vector>
using namespace std;
void Print(const vector<int>& v) {
for (auto e : v) {
cout << e << " ";
}
cout << endl;
}
void test_vector1() {
vector<int> v1;
vector<int> v2(10, 1);
vector<int> v3(v2);
vector<int> v4(v3.begin(), v3.end());
vector<int> v6 = { 1, 2, 3, 4, 5 };
Print(v2);
Print(v6);
}
void test_vector2() {
vector<int> v1;
const int n = 100;
v1.reserve(n);
size_t begin = clock();
for (size_t i = 0; i < n; i++) {
v1.push_back(i);
}
size_t end = clock();
cout << end - begin << endl;
}
void test_vector3() {
vector<int> v1 = { 1, 2, 3 };
v1.push_back(4);
v1.insert(v1.begin(), 0);
v1.erase(v1.begin());
Print(v1);
}
struct AA {
int _a1 = 1, _a2 = 1;
AA(int a1 = 1, int a2 = 1) :_a1(a1), _a2(a2) {}
};
void test_vector4() {
vector<AA> v1;
AA aa1 = { 0, 0 };
v1.push_back(aa1);
v1.emplace_back(aa1);
v1.emplace_back(2, 2);
}
int main() {
test_vector4();
return 0;
}