一、vector 的基础遍历与迭代器这个函数只做一件事把同一个 vector 用五种方式读出来/改出来借此展示 C 容器的各种访问接口。void test01() { vectorint v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); // ① 下标访问 for (size_t i 0; i v1.size(); i) cout v1[i] ; cout endl; // ② 正向迭代器 vectorint::iterator it1 v1.begin(); while (it1 ! v1.end()) { cout *it1 ; it1; } cout endl; // ③ 范围 for引用可改值 for (auto a : v1) { a; } cout endl; // ④ 反向迭代器 vectorint::reverse_iterator it2 v1.rbegin(); while (it2 ! v1.rend()) { cout *it2 ; it2; } cout endl; // ⑤ 只读 const_iterator vectorint::const_iterator it3 v1.begin(); while (it3 ! v1.end()) { //--(*it3); cout *it3 ; it3; } cout endl; }准备构造一个 vectorvectorint v1;是默认构造得到一个空的动态数组size 0、capacity 0底层还没分配任何元素空间。v1.push_back(1..4)连续在尾部追加 4 个元素此时v1内是{1,2,3,4}。push_back是 vector 最常用的写操作专门在末尾追加——因为 vector 是一个连续内存的数组尾部追加最快。① 下标访问v1[i]v1[i]调用的是operator[]按下标直接定位到第 i 个元素时间复杂度 O(1)。关键陷阱operator[]不做越界检查。i 超出size不会报错而是未定义行为可能读到垃圾值或崩溃。想安全访问应该用v1.at(i)越界会抛std::out_of_range。返回的是引用所以既能读也能写v1[i] 99是合法的。v1.size()返回类型是size_t无符号整数所以循环下标也用size_t i避免符号/无符号比较的告警。② 正向迭代器begin() / end()迭代器是 STL 的核心概念能指向容器中的某个元素并支持*解引用取值、前进到下一个、!比较是否相等。begin()指向第一个元素end()指向最后一个元素的下一个位置叫哨兵/尾后迭代器。这是一个半开区间[begin, end)。循环条件it1 ! v1.end()判断还没走到末尾it1让迭代器前进一位。*it1解引用得到元素本身。这里只读输出1 2 3 4。为什么要用迭代器而不是下标因为迭代器对所有容器通用list、map、set 都能用而下标只对支持随机访问的容器可用。学 STL 就要习惯用迭代器而不是下标去遍历。③ 范围 for范围 for 是 C11 引入的语法糖本质就是把迭代器遍历包装成更简洁的写法等价于上面的while循环。这里的auto a是引用a是容器里每个元素的别名所以a会直接修改容器里的值。执行后 v1 变成{2,3,4,5}。如果写成for (auto a : v1)没有那a只是每个元素的拷贝a改的是副本容器不变。这是想改值必须用的最典型场景。只想读、不想改时写成for (const auto a : v1)更安全、也更省拷贝。注意此处cout endl只是打一个换行没有输出内容。④ 反向迭代器rbegin() / rend()反向迭代器让从尾部往前遍历变得和正向一样自然。rbegin()指向最后一个元素反向意义上的 beginrend()指向第一个元素之前反向哨兵。区间仍是[rbegin, rend)只是方向反了。it2在反向迭代器上意味着向容器头部移动。在 v1 已被改成{2,3,4,5}后反向输出是5 4 3 2。反向迭代器用起来和普通迭代器几乎一样唯一的心理落差是居然在倒退。这是它最重要的记忆点。⑤ 只读const_iteratorconst_iterator解引用后得到const 引用只能读、不能写。被注释的--(*it3)如果放开会编译报错——因为*it3是 const 的不允许自减。编译器在编译期就拦住了这类误写。有意思的是即使v1本身不是 const 对象你也可以显式用const_iterator强制只读遍历作为纪律性的手段。此时 v1 是{2,3,4,5}只读输出仍是2 3 4 5。同一个 vector五种视角示意2345begin()end()→rbegin()←rend()v1[2] → 4下标[]、正向迭代器、范围for、反向迭代器、const_iterator 五种方式都在这条连续内存上工作示意非精确布局vector 的元素存放在一段连续内存里五种访问方式只是视角不同小结遍历方式本身不难真正要记住的是三个区别——下标无越界检查、范围 for 想改值必须用引用、const_iterator 只读。二、构造、扩容、insert 与 erase这个函数在演示三件事用个数值构造 vector、观察 capacity 是怎么翻倍增长的、以及insert/erase怎么在中间增删元素。void test02() { vectorint v1(10, 2); for (size_t i 0; i v1.size(); i) cout v1[i] ; cout endl; vectorsize_t v2; size_t old v2.capacity(); cout old endl; // 0 for (size_t i 0; i 100; i) { v2.push_back(i); if (old ! v2.capacity()) { old v2.capacity(); cout old endl; } } v2.insert(v2.begin(), 1000); // 头插 v2.insert(v2.begin(), 10); for (auto a : v2) cout a ; cout endl; v2.insert(v2.begin() 8, 10); // 任意位置插 for (auto a : v2) cout a ; cout endl; size_t x; cin x; auto it find(v2.begin(), v2.end(), x); if (it ! v2.end()) v2.insert(it, 10000); for (auto a : v2) cout a ; cout endl; size_t t; cin t; it find(v2.begin(), v2.end(), t); if (it ! v2.end()) v2.erase(it); for (auto a : v2) cout a ; cout endl; }①vectorint v1(10, 2)fill 构造这是 vector 的填充构造函数第一个参数是元素个数第二个是每个元素的初值。这里得到 10 个值全部为 2 的元素。如果只写vectorint v1(10)那就是 10 个元素初值为该类型的默认值int 为 0。注意它和vectorint v1{10, 2}的区别大括号是列表初始化会解释成两个元素10 和 2。小括号才是个数 值。这是新手最容易踩的坑。② capacity 与扩容机制核心中的核心先厘清两个概念size()是当前实际元素个数capacity()是当前已分配的内存能容纳的元素个数。后者是预留容量两者常常不相等。空 vector 的 capacity 为 0所以第一次打印 old 是0。循环里连续push_back100 次每次检查 capacity 是否变化在vs里面第一次是二倍扩容后面都是1.5倍扩容。这个翻倍增长就是 vector 高效的原因之一push_back的均摊时间复杂度是 O(1)——虽然扩容一次要搬动所有元素O(n)但扩容次数少log n 次均摊下来每次追加几乎都是常数时间。扩容的内部步骤① 申请一块更大的新数组 → ② 把旧元素逐个拷贝/移动过去 → ③ 释放旧数组 → ④ 更新_ptr、_size、_capacity。每次扩容都会让所有迭代器/引用/指针失效。扩容四步示意以 capacity 2 → 4 为例旧数组(cap2)AB① 申请更大的新数组(cap4)????②③④ 拷贝旧元素 释放旧数组 更新指针ABCD示意扩容 申请新内存 搬运旧元素 释放旧内存A/B 是原有元素C/D 是刚 push 进去的新元素vs下的扩容:Linux下的扩容③ 头插insertinsert(pos, val)把val插到迭代器pos指向的位置之前。v2.begin()是头部所以两次insert(begin(), …)都是头插先插 1000 再插 10最终 10 在最前面、1000 在第二位。代价头部插入会让后面所有元素整体后移复杂度 O(n)。在 vector 里频繁头插是非常低效的——这种场景应该用deque或list。插入前 vector 已有 100 个元素0..99。④ 任意位置插入insertv2.begin() 8用到了迭代器的随机访问能力vector 的迭代器是随机访问迭代器支持n。对 list/set 就不能这么写。把 10 插到当前第 8 个元素之前同样是 O(n) 的搬移代价。扩容的连带作用如果插入导致size撞上capacity会先触发一次扩容之前拿到的begin()等迭代器会失效。⑤findinsert按值定位再插入std::find(begin, end, x)来自algorithm在[begin,end)里线性查找第一个等于x的元素返回指向它的迭代器找不到就返回end()。所以if (it ! v2.end())是在判断找到了。v2.insert(it, 10000)把 10000 插到找到的那个元素之前。注意find是线性扫描 O(n)insert也是 O(n)。⑥erase删除指定位置的元素v2.erase(it)把迭代器指向的那个元素删掉后面的元素整体前移size减 1。capacity不会因 erase 而缩小——删除只是逻辑上减少元素底层内存还留着。迭代器失效erase之后被删位置及其之后的迭代器/引用/指针都失效了不要继续用它们。想一次删多个可用erase(it1, it2)区间版本。同样的if (it ! v2.end())保护找不到就不删。⚠ 重要提醒insert/erase以及触发扩容后旧迭代器会失效。这是 C 里最常见的悬空引用事故源头——用完旧的it前千万别先 insert/erase。另外find只做线性查找别在大数据量下期望它很快。三、emplace_back 与 push_back 的差异这个函数通过一个会打印构造痕迹的结构体 A直观展示push_back和emplace_back在拷贝次数上的差别。先看结构体 Astruct A { A(int a 0, int b 0) : _a(a), _b(b) { cout A(int,int) endl; } A(const A a) { _a a._a; _b a._b; cout A(const A) endl; } int _a, _b; };构造函数带默认参数(int a0, int b0)并用成员初始化列表:_a(a), _b(b)初始化两个成员。初始化列表比在函数体里赋值更高效、更规范。拷贝构造函数A(const A)手动逐个成员拷贝并在里面打印一行标记。这行打印就是为了让我们肉眼看见拷贝发生了几次——是这段代码的观察工具。因为是struct成员_a/_b默认公有外面能直接访问。注意这个 A 没有定义移动构造函数所以后面出现的移动都会退化成调用拷贝构造。主体void test03() { // 对 int 而言 push_back / emplace_back 完全等价 vectorint v1; v1.push_back(1); vectorint v2; v2.emplace_back(1); vectorA v3; A aa1(3, 3); v3.push_back(aa1); // ① 左值 → 拷贝构造 1 次 v3.push_back(A(3, 3)); // ② 临时对象 → 构造1次 拷贝1次 v3.push_back({ 3,3 }); // ③ 列表初始化临时 → 构造1次 拷贝1次 vectorA v4; A aa2(3, 3); v4.emplace_back(aa2); // ④ 传左值 → 仍是拷贝 1 次 v4.emplace_back(A(3, 3)); // ⑤ 传临时 → 构造拷贝 v4.emplace_back(3, 3); // ⑥ 直接传构造参数 → 就地构造0 拷贝 ✔ // 迭代器解引用用 - 访问成员 vectorA::iterator it1 v3.begin(); while (it1 ! v3.end()) { cout it1-_a : it1-_b endl; it1; } // C11 范围 for用 . 访问成员 for (auto e1 : v3) cout e1._a : e1._b endl; // C17 结构化绑定 for (auto [x, y] : v4) cout x : y endl; }核心对比push_back vs emplace_back两者都是尾部插入唯一的区别是怎么把元素放进容器push_back接受一个已经构造好的对象左值或临时对象把它拷贝/移动进容器。也就是说它需要先构造、再拷贝两步。emplace_back接受的是构造函数的参数在容器已分配的内存里就地构造对象——少了一次拷贝/移动。所以代码里的⑥v4.emplace_back(3,3)是最高效的直接把 3、3 传给 A 的构造函数只构造一次、零拷贝就是注释里写的效率更高传构造 A 的参数。但是①④ 传的是左值对象aa1/aa2无论 push 还是 emplace 都免不了拷贝——因为对象已经存在必须复制一份进容器。②③⑤ 传临时对象也类似。一句话总结emplace 只有在直接传构造参数时才真正省一次拷贝如果你手里已经有一个对象要放进去两者区别不大。构造流程对比示意push_back(3,3) 做不到——必须给对象临时 A(3,3)→ 拷贝容器里的 A先构造、再拷贝 2 次动作emplace_back(3,3) 直接给参数就地构造 A(3,3)→ 直接放进容器里的 A只构造 1 次0 拷贝关键emplace 的优势只在你直接传构造参数时才体现emplace_back 在容器内就地构造省掉一次拷贝/移动三种读对象的方式迭代器 -it1-_a。因为迭代器解引用后得到对象-等价于(*it1)._a这是迭代器习惯的写法。范围 for .for (auto e1 : v3)里e1直接就是对象引用所以用点号e1._a。C17 结构化绑定for (auto [x, y] : v4)把每个 A 的_a、_b直接解构到x、y两个变量上。它是 C17 的新语法要求类型所有非静态成员都是公有的、且无基类并按声明顺序绑定。A恰好满足所以能编译。被注释的auto [x,y] aa1;同理。三种写法都能用日常最推荐范围 for要同时拿多个字段就上结构化绑定。小结emplace_back 的省拷贝只在直接传构造参数时成立读取对象的三种方式-、.、结构化绑定只是语法差异本质都是访问同一个对象。④ 杨辉三角C 版vectorvectorint用二维动态数组实现杨辉三角展示vectorvectorint怎么充当二维数组。class Solution { public: vectorvectorint generate(int numRows) { vectorvectorint vv; vv.resize(numRows, vectorint()); // 外层先开 numRows 行空 vector for (size_t i 0; i numRows; i) vv[i].resize(i 1, 1); // 第 i 行 resize 成 i1 个元素全置 1 for (size_t i 2; i numRows; i) { for (size_t j 1; j i; j) // ⚠ 边界细节见下文 vv[i][j] vv[i - 1][j] vv[i - 1][j - 1]; } return vv; } };① 理解vectorvectorint是什么外层 vector 的每个元素又是一个vectorint。也就是说vv是一个装了很多个一维数组的数组。vv[i]得到第 i 行的那个一维 vectorvv[i][j]再取这行的第 j 个元素——语法上和二维数组一模一样。但它是动态的每行长度可以不同。普通二维数组int a[n][n]必须每行等长而杨辉三角每行长度是i1天然适合vectorvector。② 两遍 resize先建骨架再填值vv.resize(numRows, vectorint())把外层扩容到 numRows 行每行暂时是一个空的vector。vv[i].resize(i 1, 1)把第 i 行扩成i1个元素全部初始化为 1。因为杨辉三角每行两端本来就是 1所以先把整行铺满 1边界就不需要再单独处理。于是现在vv已经是一张边缘全是 1 的三角形骨架只剩中间的数字要填。③ 递推填数杨辉三角的核心递推式vv[i][j] vv[i-1][j] vv[i-1][j-1]即当前数 左上 正上。从i 2开始前两行全 1不用算对第 i 行内部j 1 … i逐个覆盖。复杂度 O(n²)因为要填满整个三角形共n(n1)/2个元素空间也是 O(n²)。⑤ 杨辉三角C 风格int** malloc同一个问题换到 C 语言没有容器得自己用二级指针 动态内存分配手工搭一个二维数组。int** generate(int numRows, int* returnSize, int** returnColumnSizes) { // ① 建空间先开行指针数组再给每行开数组 int** aa (int**)malloc(sizeof(int*) * numRows); for (size_t i 0; i numRows; i) aa[i] (int*)malloc(sizeof(int) * (i 1)); // ② 设置返回参数 *returnSize numRows; *returnColumnSizes (int*)malloc(sizeof(int) * numRows); for (int i 0; i numRows; i) (*returnColumnSizes)[i] i 1; // ③ 填数两端置 1中间递推 for (int i 0; i numRows; i) for (int j 0; j i; j) { if (i j || j 0) aa[i][j] 1; else aa[i][j] aa[i - 1][j] aa[i - 1][j - 1]; } return aa; }① 用int**模拟二维数组C 里没有 vector最接近的二维数组就是二级指针int**aa是一个指针的指针。结构是aa指向一块存放 int* 指针的数组其中aa[i]又指向第 i 行的int 数组头。所以aa[i][j]等价于*(*(aai)j)。malloc分配原始内存第一句给行指针数组开numRows个int*循环里给每一行开i1个int。这正好对应 C 版的两遍 resize。(int**)malloc(...)是 C 风格强制转换。严格说malloc返回void*C 里可以不转但int**的写法在混编/可读性上更清晰。② 用指针带出多个返回值C 函数只能返回一个值但这里调用方需要三样信息行数、每行长度、数据本身。于是用输出参数解决returnSize行数指针、returnColumnSizes每行长度的数组。*returnSize numRows;把行数写进调用者提供的 int 变量。*returnColumnSizes (int*)malloc(...)先分配一个记录每行长度的 int 数组然后(*returnColumnSizes)[i] i1逐行记录。注意括号优先级(*returnColumnSizes)[i]是先解引用、再下标如果漏掉括号写成*returnColumnSizes[i]含义就完全不同了先下标再解引用。这是 C 里很经典的一个坑。③ 边界处理与 C 版的对照C 版显式用if (ij || j0) aa[i][j] 1;处理两端中间才递推——边界完全正确不会像 C 版那样越界。对比价值C 版靠resize(i1, 1)把边界预置成 1更省心但容易在循环边界上出问题C 版全手动繁琐但每一步都显式。C 版的代价所有内存都要自己管理——用完要逐行free(aa[i])再free(aa)、free(*returnColumnSizes)漏一个就内存泄漏。C 版vector析构时自动全部释放。这也是为什么现代 C 更推荐vector而不是裸指针 malloc的最好例子同样的逻辑C 更安全、更不易错。aa 指向一组行指针每个 aa[i] 指向一行的 int 数组——这就是 C 版二维数组⑥ 总结一份知识点清单话题要点一句话记忆遍历下标 []、迭代器 begin/end、范围 for、反向迭代器、const_iterator想改值用想只读用const auto下标越界operator[] 不检查越界是未定义行为安全用 at()[] 快但野at() 慢但稳扩容capacity 约 2 倍增长扩容新内存搬运释放更新push_back 均摊 O(1)insert/erase中间插入删除都是 O(n)会搬移元素会失效迭代器别再碰旧迭代器emplace vs pushemplace 直接传构造参数就地构造省一次拷贝手里有对象用 push有参数用 emplace二维容器vectorvectorint 每行可变长注意内层循环的边界j 别越到 iC 风格二维int** malloc用输出参数带返回值手动 free括号优先级 ( *p )[i]记得逐行 freevector 本质封装 _ptr/_size/_capacity 的动态数组三个量看懂容器就懂了练习建议把test01里auto改成auto观察值变不变体会引用的作用。打印扩容前后的begin()地址亲眼看看扩容后旧迭代器指向的内存是否已被释放。