前言

刷 LeetCode118 杨辉三角时，发现很多同学只会调用vector接口完成题目，却完全不懂vector底层内存模型、push_back扩容逻辑、二维vector存储结构。本文结合手写源码 + 杨辉三角实战，彻底吃透vector底层原理。

一、vector 基础用法与初始化

1. 列表初始化（initializer_list）

#include <vector> #include <string> using namespace std; // 1. 列表初始化底层依赖initializer_list vector<int> v1({10, 20, 30}); vector<int> v2{10, 20, 30, 1,1,1}; // 2. push_back插入临时对象 vector<string> str_v; str_v.push_back("张三"); // 底层：构造string临时对象，拷贝/移动到vector内存

底层逻辑：vector接收initializer_list参数的构造函数，会遍历列表，循环调用push_back完成元素拷贝。

2. vector 核心修改接口 Modifiers

二、vector 底层内存模型（手写简化源码）

1. vector 类核心成员

template<class T, class Alloc = allocator<T>> class vector { public: typedef T value_type; typedef T* iterator; private: iterator _start; // 有效数据起始地址 iterator _finish; // 有效数据末尾下一位 iterator _end_of_storage; // 内存容量末尾 public: // 构造、析构、接口省略 iterator begin() { return _start; } iterator end() { return _finish; } // 有效元素个数 size_t size() const { return _finish - _start; } // 总容量 size_t capacity() const { return _end_of_storage - _start; } };

内存图解：[_start 元素1 元素2 元素3 _finish 空闲内存 _end_of_storage]

• size()：_finish - _start，当前存了多少元素

• capacity()：_end_of_storage - _start，整块内存能容纳多少元素

2. push_back 扩容核心逻辑

void push_back(const T& x) { // 内存还有空闲，直接在_finish处构造对象 if (_finish != _end_of_storage) { construct(_finish, x); ++_finish; } else { // 空间不足，触发扩容 insert_aux(end(), x); } }

扩容流程insert_aux：

1. 计算新容量：原容量为 0 则扩为 1；否则扩容为原来 2 倍

2. 分配一块更大的连续内存

3. 将旧内存中所有元素拷贝到新内存

4. 在新内存尾部插入待新增元素

5. 析构释放旧内存整块空间

6. 更新_start/_finish/_end_of_storage指向新内存

3. emplace_back 与 push_back 区别

• push_back(const T& val)：先构造临时对象，再拷贝 / 移动到 vector 内存，存在临时对象开销

• emplace_back(参数1, 参数2...)：直接在 vector 底层内存原位构造对象，无临时对象，性能更优

4. 二维 vector 存储结构vector<vector<int>>

vector<vector<int>> vv; vv.resize(numRows, vector<int>());

内存模型拆解：

1. 外层vector<vector<int>>底层存一堆vector<int>对象（指针数组）

2. 每个内层vector<int>独立拥有自己的三块指针_start/_finish/_end_of_storage，各自管理一维 int 数组

3. vv[i][j]等价vv.operator[](i).operator[](j)：先取第 i 个内层 vector，再取它的第 j 个 int 元素

三、实战：LeetCode 118 杨辉三角

题目要求

给定非负整数numRows，生成杨辉三角前numRows行，每行首尾都是 1，中间数字 = 上一行左上 + 右上数字。

C++ vector 完整实现

#include <vector> using namespace std; class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>> vv; // 1. 先开辟numRows行空间，每行初始为空vector vv.resize(numRows, vector<int>()); for (size_t i = 0; i < numRows; ++i) { // 第i行有 i+1 个元素，提前resize分配空间 vv[i].resize(i + 1); // 每行首尾固定为1 vv[i][0] = 1; vv[i][i] = 1; } // 从第3行(i=2)开始填充中间数值 for (size_t i = 2; i < vv.size(); ++i) { for (size_t j = 1; j < vv[i].size() - 1; ++j) { // 当前值 = 上一行j-1 + 上一行j vv[i][j] = vv[i-1][j-1] + vv[i-1][j]; } } return vv; } };

代码思路解析

1. 外层 vector 开辟行：vv.resize(numRows, vector<int>())，创建 numRows 个空一维 vector

2. 每行预分配列空间：第i行共i+1个元素，vv[i].resize(i+1)提前分配连续 int 内存，避免多次扩容

3. 首尾赋值 1：杨辉三角每行第一个、最后一个数字恒为 1

4. 递推填充中间值：从第三行（i=2）开始，中间元素等于上一行相邻两数之和

拓展：C 语言动态二维数组实现（对比 vector）

很多同学混淆 C 语言二级指针二维数组和 C++ 二维 vector，附上 C 版本对比：

/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. */ int** generate(int numRows, int* returnSize, int** returnColumnSizes) { // 外层：指针数组，存放每行int数组地址 int** aa = (int**)malloc(sizeof(int*) * numRows); // 记录每行元素个数 *returnColumnSizes = (int*)malloc(sizeof(int) * numRows); for (int i = 0; i < numRows; ++i) { int col = i + 1; aa[i] = (int*)malloc(sizeof(int) * col); (*returnColumnSizes)[i] = col; aa[i][0] = 1; aa[i][i] = 1; } for (int i = 2; i < numRows; ++i) { for (int j = 1; j < i; ++j) { aa[i][j] = aa[i-1][j-1] + aa[i-1][j]; } } *returnSize = numRows; return aa; }

C 与 C++ vector 核心区别

1. C 二级指针二维数组：每行 int 数组内存不连续，仅外层指针连续；手动 malloc 分配、free 释放，容易内存泄漏

2. C++vector<vector<int>>：每个内层 vector 内部 int 连续，vector 自动管理内存，出作用域自动析构释放，无需手动管理堆内存

四、vector 核心知识点总结

1. 三指针模型：_start/_finish/_end_of_storage区分 size 和 capacity，底层是连续堆内存

2. 扩容机制：空间不足默认 2 倍扩容，旧内存数据拷贝后释放，扩容存在性能开销，大量数据建议提前reserve()预分配容量

3. emplace_back 优于 push_back：原位构造，消除临时对象拷贝开销

4. 二维 vector 本质：存储多个独立一维 vector 对象，各行内存互不连续

5. 使用场景：需要动态长度、随机访问的数组场景，底层连续内存缓存友好，随机访问 O (1)