前言刷 LeetCode118 杨辉三角时发现很多同学只会调用vector接口完成题目却完全不懂vector底层内存模型、push_back扩容逻辑、二维vector存储结构。本文结合手写源码 杨辉三角实战彻底吃透vector底层原理。一、vector 基础用法与初始化1. 列表初始化initializer_list#include vector #include string using namespace std; // 1. 列表初始化底层依赖initializer_list vectorint v1({10, 20, 30}); vectorint v2{10, 20, 30, 1,1,1}; // 2. push_back插入临时对象 vectorstring str_v; str_v.push_back(张三); // 底层构造string临时对象拷贝/移动到vector内存底层逻辑vector接收initializer_list参数的构造函数会遍历列表循环调用push_back完成元素拷贝。2. vector 核心修改接口 Modifiers接口作用底层行为push_back(val)尾部插入元素容量充足直接构造容量不足触发扩容emplace_back(args)尾部原位构造直接在内存构造对象无临时对象效率更高insert指定位置插入后续元素全部后移时间复杂度 O (n)erase删除指定元素后续元素前移O (n)clear清空元素析构所有对象不释放底层内存pop_back删除尾部元素析构最后一个元素容量不变二、vector 底层内存模型手写简化源码1. vector 类核心成员templateclass T, class Alloc allocatorT 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计算新容量原容量为 0 则扩为 1否则扩容为原来 2 倍分配一块更大的连续内存将旧内存中所有元素拷贝到新内存在新内存尾部插入待新增元素析构释放旧内存整块空间更新_start/_finish/_end_of_storage指向新内存3. emplace_back 与 push_back 区别push_back(const T val)先构造临时对象再拷贝 / 移动到 vector 内存存在临时对象开销emplace_back(参数1, 参数2...)直接在 vector 底层内存原位构造对象无临时对象性能更优4. 二维 vector 存储结构vectorvectorintvectorvectorint vv; vv.resize(numRows, vectorint());内存模型拆解外层vectorvectorint底层存一堆vectorint对象指针数组每个内层vectorint独立拥有自己的三块指针_start/_finish/_end_of_storage各自管理一维 int 数组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: vectorvectorint generate(int numRows) { vectorvectorint vv; // 1. 先开辟numRows行空间每行初始为空vector vv.resize(numRows, vectorint()); for (size_t i 0; i numRows; i) { // 第i行有 i1 个元素提前resize分配空间 vv[i].resize(i 1); // 每行首尾固定为1 vv[i][0] 1; vv[i][i] 1; } // 从第3行(i2)开始填充中间数值 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; } };代码思路解析外层 vector 开辟行vv.resize(numRows, vectorint())创建 numRows 个空一维 vector每行预分配列空间第i行共i1个元素vv[i].resize(i1)提前分配连续 int 内存避免多次扩容首尾赋值 1杨辉三角每行第一个、最后一个数字恒为 1递推填充中间值从第三行i2开始中间元素等于上一行相邻两数之和拓展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 核心区别C 二级指针二维数组每行 int 数组内存不连续仅外层指针连续手动 malloc 分配、free 释放容易内存泄漏Cvectorvectorint每个内层 vector 内部 int 连续vector 自动管理内存出作用域自动析构释放无需手动管理堆内存四、vector 核心知识点总结三指针模型_start/_finish/_end_of_storage区分 size 和 capacity底层是连续堆内存扩容机制空间不足默认 2 倍扩容旧内存数据拷贝后释放扩容存在性能开销大量数据建议提前reserve()预分配容量emplace_back 优于 push_back原位构造消除临时对象拷贝开销二维 vector 本质存储多个独立一维 vector 对象各行内存互不连续使用场景需要动态长度、随机访问的数组场景底层连续内存缓存友好随机访问 O (1)