前阵子一个刚转C的同事问我说程序跑着跑着就崩了定位了半天发现是往vector里塞数据越界访问。聊完之后我发现很多人虽然天天写std::vector但对它的底层机制、扩容规则、迭代器失效、还有那一堆容易踩的坑其实并没有真正吃透。我干脆把这几年来在项目里用 vector 的经验、踩过的坑以及那些面试里高频出现的问题一次性整理出来这篇就当是给自己团队写的一份内部手册也希望对你有用。vector 说白了就是标准库里提供的动态数组它在内存里是一段连续的存储空间所以支持随机访问任何位置的访问都是常数时间。相比裸数组它能自动扩容帮你管理内存相比 list、deque 这些容器它缓存局部性好在大多数场景下性能更优。从刚学 C 的新手到写大型项目的老兵vector 都是躲不开的基础设施。这篇文章不讲虚的全部围绕实际开发中的使用场景来展开包含常用操作、排序去重、迭代器失效、性能优化和避坑经验你能直接照着用。1. 先搞清楚 vector 的本质一个会自动扩容的动态数组1.1 它和普通数组到底差在哪普通数组在栈上或者堆上定义之后大小就定死了比如int arr[100]你想塞第 101 个元素进去要么改代码要么就得手动去堆上分配、重新拷贝、释放旧内存。这个流程写一两次还好写多了就容易出错漏了释放就是内存泄漏多释放一次就是崩溃。vector 把这一整套流程封装好了。你只需要push_back它内部会帮你检查容量不够就重新分配一块更大的内存、把旧数据搬过去、释放旧内存。这个搬过去的过程对使用者是透明的你感知不到但它的存在恰恰决定了 vector 的性能特征和使用方式。如果你把普通数组想成停车场里固定划线的车位vector 就是一个自带扩容机制的停车场。车多了它自己会去旁边再租一块更大的场地把所有车一辆一辆挪过去然后把老场地退掉。整个过程你只管把车开进来。vector 在内存里的布局其实不复杂它本质上维护了三个指针不同标准库实现细节略有区别但思想一致一个指向已用空间的起始位置一个指向已用空间的末尾一个指向整个已分配空间的末尾。已分配空间减去已用空间就是咱们常说的 capacity 刨去 size 的部分。1.2 扩容机制到底是几倍为什么要这样设计这里引入两个关键概念size()是当前容器里有多少元素capacity()是当前容器在不需要重新分配内存的情况下最多能装多少元素。两者不是一回事很多初学者搞混后面会专门讲。当size() capacity()时再往里面 push_back 一个元素vector 就会触发扩容。经典实现里GCC 的 libstdc 大约是 2 倍扩容MSVC 大约是 1.5 倍。比如初始 capacity 是 1往里头 push_back容量会变成 2、4、8、16……这是 2 倍的序列换成 MSVC 则是 1、2、3、4、6、9、13……大概是 1.5 倍。为什么不是每次 push_back 只多分配一个位置因为每次扩容都要经历分配新内存 → 拷贝或移动旧元素 → 释放旧内存这一整套流程如果元素是复杂的类对象这个代价会非常昂贵。均摊下来用倍数扩容可以让每次 push_back 的均摊时间复杂度接近 O(1)。为什么不是扩容 100 倍因为内存利用率太低了。你只存了 10 个元素却占着 1000 个元素的内存空间这在服务器端动辄上亿数据的场景下是不可接受的。2 倍是一个时间与空间的平衡点MSVC 用 1.5 倍是出于内存碎片和利用率上的进一步考量。了解这个机制之后你就明白如果你预先能猜到数据量最好用reserve把容量提前分配好这一条后面会展开讲。2. 从初始化到常用操作这些写法你真不一定全会2.1 各种构造和初始化方式vector 的初始化方式非常多每一种适用场景都不同。我列一下平时用得最多的几种#include vector #include string using namespace std; // 1. 空 vector最常用 vectorint v1; // 2. 指定大小元素默认构造int 就是 0 vectorint v2(10); // 3. 指定大小 统一初始值 vectorint v3(10, -1); // 4. 用初始化列表C11 起 vectorint v4{1, 2, 3, 4, 5}; // 5. 用另一个 vector 的某段区间拷贝 vectorint v5(v4.begin() 1, v4.begin() 4); // 6. 从普通数组拷贝 int arr[] {9, 8, 7}; vectorint v6(arr, arr 3); // 7. 直接拷贝整个 vector vectorint v7 v4;这里有一个高频坑vectorint v2(10);和vectorint v4{1, 2, 3, 4, 5};中圆括号和花括号的意义完全不同。圆括号是创建 n 个元素花括号是以这些值初始化。如果你写vectorint v{10};得到的是一个包含单个元素 10 的 vector而不是 10 个元素。再说到字符串数组初始化群里总有人问。vectorstring vs {hello, world};是最直观的写法。如果你要创建一个固定大小的字符串数组可以vectorstring vs(3);然后逐个赋值也可以vectorstring vs(3, string());。更灵活的做法是先vs.resize(5);再通过下标去填充。还有一个非常实用的场景二维 vector。很多人一开始处理二维数据都卡在这里。标准写法是// 3 行 4 列的二维 vector初始值为 0 vectorvectorint matrix(3, vectorint(4, 0));内层那个vectorint(4, 0)是每一行的初始状态。如果你漏了内层初始化只写了vectorvectorint matrix(3);那 matrix 里只有 3 个空的一维 vector你直接访问matrix[0][0]就是未定义行为大概率崩给你看。必须先确保内层 vector 也有足够的大小比如再写matrix[i].resize(4);。vector 也支持每一行长度不同这种叫不规则二维数组。典型场景是杨辉三角vectorvectorint triangle(5); for (int i 0; i 5; i) { triangle[i].resize(i 1); triangle[i][0] triangle[i][i] 1; for (int j 1; j i; j) { triangle[i][j] triangle[i - 1][j - 1] triangle[i - 1][j]; } }这种写法灵活但要注意vectorvectorint的性能并不像看起来那么好。因为每一行是独立的动态数组整块内存并不连续访问时会存在额外的指针跳转和多次内存分配。后面性能部分再细说。2.2 增删改查与 capacity 相关操作vector 最常用的增删改查操作一张表就能说清楚操作写法说明尾部插入v.push_back(x)均摊 O(1)可能引发扩容尾部删除v.pop_back()O(1)只析构末尾元素指定位置插入v.insert(it, x)it 之后元素整体后移O(n)删除指定位置v.erase(it)it 之后元素整体前移O(n)删除区间v.erase(first, last)区间 [first, last) 被删除O(n)清空元素v.clear()size 归零capacity 不变首元素/末尾元素v.front()/v.back()空容器上调用是未定义行为按下标访问v[i]不做越界检查检查越界访问v.at(i)越界抛std::out_of_range直接取内存地址v.data()返回指向底层数组的指针关于emplace_back和push_back这是个很经典的性能话题。push_back(x)会把 x 拷贝或移动到容器里而emplace_back(args...)直接在容器内存上就地构造对象省掉了一次移动或拷贝。对于像std::string、自定义类这种构造开销不小的类型emplace_back在多数情况下更优。struct Point { int x, y; Point(int a, int b) : x(a), y(b) {} }; vectorPoint points; // push_back 需要临时对象先构造再移动 points.push_back(Point(1, 2)); // emplace_back 直接传构造参数 points.emplace_back(1, 2);两者在 basic 类型上差别几乎可以忽略但容器装的是复杂对象时建议优先 emplace_back。还有一对必须掰开揉碎讲的概念resize和reserve。resize(n)改变的是 size。如果当前 size 小于 n会用默认值填充新增元素如果大于 n会直接截断末尾的元素。容器里实际元素个数变了遍历、size()的返回值都会受影响。reserve(n)改变的是 capacity它只预留内存空间但不会创建任何元素size 不变。如果你知道大概要存多少数据reserve可以一次性分配足够的容量避免多次扩容。很多新手的误区是以为reserve(1000)之后就能直接v[i] xxx这是错的。没有元素你访问下标就是越界正确做法是resize(1000)之后再按下标写或者reserve(1000)之后继续用 push_back 往里塞。shrink_to_fit()的作用是把多余的 capacity 释放掉让 capacity 对齐到 size。但它只是请求标准库实现可以忽略这个请求实际用下来多数主流实现都会真正做一次缩容。注意缩容是要把所有元素拷贝/移动到新内存的代价不小别频繁调用。3. 排序、去重、查找一套带走vector 实战三板斧3.1 sort 排序的几种用法日常开发里 vector 排个序太常见了。基础类型直接排vectorint nums {5, 2, 8, 1, 9}; sort(nums.begin(), nums.end()); // 升序 sort(nums.rbegin(), nums.rend()); // 降序利用反向迭代器 sort(nums.begin(), nums.end(), greaterint()); // 降序用预置仿函数 sort(nums.begin(), nums.end(), [](int a, int b) { return a b; }); // 降序用 lambda倒序最简单实用的是sort(nums.rbegin(), nums.rend());连比较规则都不用写反向迭代器一轮回顺序正好倒过来。如果容器里存的是pairint, int默认排序规则是先按 first 排first 相同再按 second 排。比如vectorpairint, int intervals; // 按 first 升序first 相同按 second 升序 sort(intervals.begin(), intervals.end());但如果你需要按 second 排就得自定义比较器sort(intervals.begin(), intervals.end(), [](const auto a, const auto b) { return a.second b.second; });C14 之后 lambda 参数可以用auto写起来干净很多。C11 就把具体的 pair 类型写全也一样能用。如果是自定义结构体我习惯的做法是如果能修改结构体就重载operator这样直接 sort 就行如果不能改或者排序规则多变用 lambda规则写在使用处直观规则复杂、多处复用的写个仿函数或者函数传函数名进去。struct Task { int priority; int deadline; string name; }; // 按优先级升序优先级相同按截止时间升序 sort(tasks.begin(), tasks.end(), [](const Task a, const Task b) { if (a.priority ! b.priority) return a.priority b.priority; return a.deadline b.deadline; });sort是不稳定排序如果有相同关键字的元素你希望保持原有相对顺序就用stable_sort。大多数情况下 sort 够用但对象里带关联信息、逻辑上要求稳定时stable_sort 别忘。3.2 unique 去重千万别忘了 erase这是一道经典面试题也是实际开发里特别容易写错的地方。std::unique的作用是把相邻的重复元素挪到容器末尾返回新逻辑末尾的迭代器。它只做搬移不负责删除。搬过去之后vector 的 size 并没有变小那些被挪到末尾的重复值还占着位置。所以去重的完整套路是三步先 sort再 unique最后 erase。vectorint v {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); // 结果: 1 2 3 4 5 6 9这三步一步都不能省。unique 之所以要求先排序是因为它只比较相邻元素。如果原数组是{1, 2, 1}没有排序直接 unique逻辑末尾会变成{1, 2, 1}1 并没有被正确去重因为两个 1 不相邻。我第一次用 unique 的时候就犯过这个错只调了unique没有erase结果调试了半天怎么 size 没变打印出来发现末尾多了几个怪值。后来才明白unique 返回的迭代器指向的才是新的逻辑结尾真正让 size 变化的是 erase 那一刀。顺带一提如果你需要的是去掉所有与给定值相同的元素就用erase加remove的惯用法v.erase(remove(v.begin(), v.end(), target), v.end());remove和unique类似也是把不需要的元素移到末尾然后返回新的逻辑末尾。这才是真正的物理删除。这两组手法本质是一个套路标准算法操作迭代器区间真正调整容器大小要靠容器自己的 erase 方法。3.3 查找与条件删除查找某个元素是否存在可以用findauto it find(v.begin(), v.end(), 42); if (it ! v.end()) { // 找到了it 指向第一个 42 }统计某个值出现次数用countint cnt count(v.begin(), v.end(), 42);按条件删除用remove_if和 erase 搭配// 删除所有偶数 v.erase(remove_if(v.begin(), v.end(), [](int x) { return x % 2 0; }), v.end());这几个惯用法一定要滚瓜烂熟。在动态数组里打游击式的逐个删除效率极差每次 erase 都会引发元素搬移。用先搬运、再统一 erase的方式一趟就能搞定而且代码还更简洁。4. 迭代器失效vector 最大的坑面试也爱考4.1 哪些操作会让迭代器失效面试 C 岗位vector 迭代器失效几乎是必问题。这个问题的背后是 vector 的存储特性它把元素放在一段连续内存上任何引起元素位置改变的操作都会让已有迭代器指向错误位置。归纳下来有两类风险操作一是引发扩容的操作比如 push_back、insert、emplace_back、reserve传入的容量大于当前 capacity。扩容意味着整个底层数组被搬走以前保存的迭代器、指针、引用统统失效。注意只要没触发扩容push_back 不会让已有迭代器失效这是很多人没说透的细节。二是会引起该位置之后元素整体移动的操作。vector 的 insert 和 erase 都会让插入/删除位置之后的元素整体搬移位置所以这些位置的迭代器也会失效。具体来说insert 会让插入点之后的所有迭代器失效erase 会让被删除点及之后的所有迭代器失效。底层原因一句话就能解释清楚迭代器本质上是封装了的指针指向底层数组的某个位置数组元素一动这个指针指向的就不再是你原来那个元素了。4.2 实战项目和代码怎么写才能避开失效问题最常见的反面教材是这样一段循环删除代码// 错误示范 for (auto it v.begin(); it ! v.end(); it) { if (*it % 2 0) { v.erase(it); // erase 之后 it 已经失效it 是未定义行为 } }这段代码在删除第一个偶数元素后it就失效了循环继续it就是典型未定义行为。看起来可能能跑可能崩溃可能在某个平台正常、换个编译器就出问题都是你排查起来最头疼的那种 bug。正确写法是利用 erase 的返回值它会返回被删除元素的下一个有效迭代器for (auto it v.begin(); it ! v.end(); ) { if (*it % 2 0) { it v.erase(it); } else { it; } }或者更推荐的做法直接用前面说的remove_if加 erase不用手动管迭代器函数式风格更不容易出错v.erase(remove_if(v.begin(), v.end(), [](int x) { return x % 2 0; }), v.end());这里需要说清楚C11 之后erase(it)的返回值是被删除元素之后那个迭代器这是标准里规定的C98 时代 erase 返回 void老代码如果是从那个时代带过来的循环写法完全不同。如果你在维护老项目要格外注意编译器标准版本。迭代器失效还有一个衍生问题引用失效。auto ref v[0];记录了一个元素的引用之后再 push_back 触发扩容ref 指向的内存就被释放了继续使用就会踩到悬空引用。这个问题比迭代器失效隐藏得更深。我的习惯是只要后续要往容器里插数据就不要长期保存容器内元素的指针、引用、迭代器要用的时候现场取。5. 性能优化与内存管理把 vector 用到飞起5.1 reserve 到底要不要用什么时候用直接说结论如果你能预估数据规模强烈建议先用reserve把容量分配好。这个操作能让大量 push_back 的性能提升一个量级。举个我实际测试过的例子往一个空 vector 里 push_back 100 万个 int不 reserve过程中要发生约 19 次扩容按 2 倍算1、2、4……524288、1048576大约 20 次。每次扩容要把已有元素全部搬到新内存算下来会有大量拷贝。如果提前reserve(1000000)就只需要一次内存分配后面全部是纯写入。实测时间差距大约有七八倍数据越多差距越明显。vectorint v; v.reserve(1000000); // 预分配 for (int i 0; i 1000000; i) { v.push_back(i); }注意reserve 之后不要用v[i] i这种方式去赋值因为 size 还是 0下标访问直接越界。可以先resize(1000000)再按下标写或者 reserve 之后继续 push_back。两个方案都常见区别是 resize 会把元素全部默认构造一遍int 无所谓但如果是复杂对象会有构造开销reserve 不会。5.2 clear 和 swap 的区别怎么才能真正释放内存很多人误以为v.clear()之后vector 占用的内存就释放了。这是错的。clear 只是把 size 置 0逐个析构元素capacity 保持原样不动。如果你在 for 循环里反复 clear push_back内存会一直保持高位占用程序峰值内存不好看。如果你就是想把这部分内存还给系统有一个经典手法vectorint().swap(v);或者 C11 之后写作vectorint().swap(v); // 用空临时 vector 和 v 交换swap 之后v 拿到临时对象的空 capacity临时对象拿着 v 原来那堆内存离开这一行就被析构内存随之释放。这是真正把 capacity 清空的写法。如果只想缩小容量而不全部清空用shrink_to_fit()。注意它不一定执行且执行时有全部元素搬移的成本所以只在你确实需要立刻释放多余内存时才用。大多数程序根本不需要频繁缩容频繁缩容反而会破坏 vector 的性能优势。5.3 vector 作为参数和返回值时的性能习惯把 vector 当函数参数时传值会触发一次完整拷贝。大容器传值一次拷贝的开销可能比函数内部逻辑还大。正确的姿势是只读void func(const vectorint v);要改void func(vectorint v);要移动void func(vectorint v);返回 vector 也别太担心现代编译器基本都有 NRVO具名返回值优化和移动语义对于vectorint func() { vectorint v; ... return v; }这种写法绝大多数情况下不会产生真正的拷贝。还有个小技巧如果函数要往传入的容器尾部添加数据接收一个引用参数通常比返回一个新容器更高效void loadData(vectorint out) { out.clear(); out.reserve(expectedSize); // 填充数据 out.push_back(...); }这样还能复用调用方的容量省一次分配。6. 避坑合集这些 vector 使用细节踩过一遍就忘不掉6.1 vectorbool 是个特例vectorbool在标准库设计中是个出了名的特殊公民。它做了位压缩一个 bool 只占 1 bit内存省了但代价是operator[]返回的并不是bool而是一个代理对象。你以为自己在操作 bool实际操作的是一个行为像 bool 的临时对象。因此以下代码是编译不过的vectorbool vb; bool ref vb[0]; // 编译错误不能把代理对象绑定到 boolauto 推导也会出问题auto b vb[0]; // b 是代理类型不是 bool如果不需要位压缩或者想避免这些奇奇怪怪的问题有两个常用替代vectorchar或dequebool。vector 每个元素占 1 字节空间不是最省但行为完全符合直觉。6.2 at() 和 operator[] 的取舍v[i]不做越界检查越界访问的结果是未定义行为可能拿到脏数据可能直接 segfault。v.at(i)会先做边界检查越界就抛std::out_of_range异常。性能上v[i]当然更快但前提是你能保证索引不越界。在算法题和性能敏感的地方用v[i]在业务逻辑里、或者索引来自外部输入的时候用at()更安全。代码里全是裸v[i]的项目越界崩起来定位成本很高。另外v.front()和v.back()在空容器上也是未定义行为用之前检查一下!v.empty()是好习惯。6.3 v.data() 和 C 接口交互vector 的元素是连续存放的这意味着它可以直接和 C 风格接口对接。C11 提供了data()方法返回指向底层数组的指针可以传给需要指针和长度的函数std::vectorint v(100); some_c_function(v.data(), v.size());注意data()返回的指针在 vector 后续插入元素触发扩容后会失效不要长期保存。如果 C 接口要求写入数据可以分配好空间再传v.resize(100); some_c_function(v.data(), v.size()); // 之后 v.size() 是 100可以正常访问还有一点如果 vector 为空data()的返回值可能是 nullptr也可能是非空指针标准库实现规定 C11 之后 data() 可能返回非空传给 C 接口时记得判断 size 为 0 的情况。6.4 二维 vector 的初始化与访问陷阱前面提到过vectorvectorint的内存是分行分配的行与行之间不连续。这个特性带来两个问题第一如果内层 vector 没初始化就直接访问会崩。vectorvectorint mat;这样创建出来mat 大小为 0连行都没有。你需要先mat.resize(rows);或者用vectorvectorint mat(rows, vectorint(cols, 0));再访问mat[i][j]。第二频繁往vectorvectorint里 push_back 小 vector 会产生大量小内存分配性能较差。如果性能敏感且矩阵是规则的推荐用一维 vector 模拟int rows 100, cols 100; vectorint flat(rows * cols, 0); // 访问 (i, j) 元素 flat[i * cols j] 42;这个写法内存连续、访问快唯一的代价是需要手动算索引。处理图像像素、矩阵运算这类高性能场景时这招非常实用。6.5 警惕循环中反复 erase 导致的 O(n²)遇到边遍历边删除的需求如果数据量很大像我前面说的在循环里逐个 erase 最坏情况下是 O(n²) 的因为每次删除后后面所有元素都要前移。更高效的做法是标记 一次性删除或者直接上remove_iferase的惯用法一趟 O(n) 搞定。数据几万以内你可能察觉不到差距到几百万元素时O(n²) 会慢到无法接受。写代码的时候养成分清单次操作代价和多次操作总代价的习惯很多性能问题都能提前规避。7. 项目实战里我的一些固定习惯前阵子在做数据重组模块时要解析几十万行文本每行拆出若干字段存进 vector。第一次跑的时候程序内存稳定增长我一度以为有泄漏。排查下来发现是每次 append 前都没 reservevector 反复扩容旧内存虽然被释放了但分配器没及时把大块内存还给操作系统导致内存峰值虚高。后来我在开头加了一句v.reserve(estimated_size);内存曲线立刻平稳耗时也明显下降。从此我养成了一个习惯凡是能预估数据规模的 vector一律先 reserve。另外一个小技巧提醒一下vector 里存的是对象指针比如vectorunique_ptrT或原始指针时顺序访问的缓存局部性依然很好但对象本身散落在堆上性能没有直接存对象好。能用对象就用对象除非对象体积大、需要的动态多态否则别过度用指针。最后再分享一个判断标准。面试或者实际开发中遇到需要随机访问、需要动态增长、对缓存友好的场景vector 是无脑首选。如果频繁在头部插入删除那是 deque 或 list 的领域如果大量元素而无所谓顺序也可以考虑 unordered_map。选容器的本质是选数据结构vector 是默认答案但不总是最优解。我用 vector 这些年最大的体会就是它之所以是 C 里最常用的容器不是说它没有缺点而是它的缺点只要被理解清楚几乎都能用正确用法避开。把 capacity 和 size 分清楚、记住迭代器失效的时机、惯用 erase remove 这套组合拳就已经超越了很多工作多年的开发者。 C++ vector深度解析：从动态数组原理到性能优化与避坑指南
前阵子一个刚转C的同事问我说程序跑着跑着就崩了定位了半天发现是往vector里塞数据越界访问。聊完之后我发现很多人虽然天天写std::vector但对它的底层机制、扩容规则、迭代器失效、还有那一堆容易踩的坑其实并没有真正吃透。我干脆把这几年来在项目里用 vector 的经验、踩过的坑以及那些面试里高频出现的问题一次性整理出来这篇就当是给自己团队写的一份内部手册也希望对你有用。vector 说白了就是标准库里提供的动态数组它在内存里是一段连续的存储空间所以支持随机访问任何位置的访问都是常数时间。相比裸数组它能自动扩容帮你管理内存相比 list、deque 这些容器它缓存局部性好在大多数场景下性能更优。从刚学 C 的新手到写大型项目的老兵vector 都是躲不开的基础设施。这篇文章不讲虚的全部围绕实际开发中的使用场景来展开包含常用操作、排序去重、迭代器失效、性能优化和避坑经验你能直接照着用。1. 先搞清楚 vector 的本质一个会自动扩容的动态数组1.1 它和普通数组到底差在哪普通数组在栈上或者堆上定义之后大小就定死了比如int arr[100]你想塞第 101 个元素进去要么改代码要么就得手动去堆上分配、重新拷贝、释放旧内存。这个流程写一两次还好写多了就容易出错漏了释放就是内存泄漏多释放一次就是崩溃。vector 把这一整套流程封装好了。你只需要push_back它内部会帮你检查容量不够就重新分配一块更大的内存、把旧数据搬过去、释放旧内存。这个搬过去的过程对使用者是透明的你感知不到但它的存在恰恰决定了 vector 的性能特征和使用方式。如果你把普通数组想成停车场里固定划线的车位vector 就是一个自带扩容机制的停车场。车多了它自己会去旁边再租一块更大的场地把所有车一辆一辆挪过去然后把老场地退掉。整个过程你只管把车开进来。vector 在内存里的布局其实不复杂它本质上维护了三个指针不同标准库实现细节略有区别但思想一致一个指向已用空间的起始位置一个指向已用空间的末尾一个指向整个已分配空间的末尾。已分配空间减去已用空间就是咱们常说的 capacity 刨去 size 的部分。1.2 扩容机制到底是几倍为什么要这样设计这里引入两个关键概念size()是当前容器里有多少元素capacity()是当前容器在不需要重新分配内存的情况下最多能装多少元素。两者不是一回事很多初学者搞混后面会专门讲。当size() capacity()时再往里面 push_back 一个元素vector 就会触发扩容。经典实现里GCC 的 libstdc 大约是 2 倍扩容MSVC 大约是 1.5 倍。比如初始 capacity 是 1往里头 push_back容量会变成 2、4、8、16……这是 2 倍的序列换成 MSVC 则是 1、2、3、4、6、9、13……大概是 1.5 倍。为什么不是每次 push_back 只多分配一个位置因为每次扩容都要经历分配新内存 → 拷贝或移动旧元素 → 释放旧内存这一整套流程如果元素是复杂的类对象这个代价会非常昂贵。均摊下来用倍数扩容可以让每次 push_back 的均摊时间复杂度接近 O(1)。为什么不是扩容 100 倍因为内存利用率太低了。你只存了 10 个元素却占着 1000 个元素的内存空间这在服务器端动辄上亿数据的场景下是不可接受的。2 倍是一个时间与空间的平衡点MSVC 用 1.5 倍是出于内存碎片和利用率上的进一步考量。了解这个机制之后你就明白如果你预先能猜到数据量最好用reserve把容量提前分配好这一条后面会展开讲。2. 从初始化到常用操作这些写法你真不一定全会2.1 各种构造和初始化方式vector 的初始化方式非常多每一种适用场景都不同。我列一下平时用得最多的几种#include vector #include string using namespace std; // 1. 空 vector最常用 vectorint v1; // 2. 指定大小元素默认构造int 就是 0 vectorint v2(10); // 3. 指定大小 统一初始值 vectorint v3(10, -1); // 4. 用初始化列表C11 起 vectorint v4{1, 2, 3, 4, 5}; // 5. 用另一个 vector 的某段区间拷贝 vectorint v5(v4.begin() 1, v4.begin() 4); // 6. 从普通数组拷贝 int arr[] {9, 8, 7}; vectorint v6(arr, arr 3); // 7. 直接拷贝整个 vector vectorint v7 v4;这里有一个高频坑vectorint v2(10);和vectorint v4{1, 2, 3, 4, 5};中圆括号和花括号的意义完全不同。圆括号是创建 n 个元素花括号是以这些值初始化。如果你写vectorint v{10};得到的是一个包含单个元素 10 的 vector而不是 10 个元素。再说到字符串数组初始化群里总有人问。vectorstring vs {hello, world};是最直观的写法。如果你要创建一个固定大小的字符串数组可以vectorstring vs(3);然后逐个赋值也可以vectorstring vs(3, string());。更灵活的做法是先vs.resize(5);再通过下标去填充。还有一个非常实用的场景二维 vector。很多人一开始处理二维数据都卡在这里。标准写法是// 3 行 4 列的二维 vector初始值为 0 vectorvectorint matrix(3, vectorint(4, 0));内层那个vectorint(4, 0)是每一行的初始状态。如果你漏了内层初始化只写了vectorvectorint matrix(3);那 matrix 里只有 3 个空的一维 vector你直接访问matrix[0][0]就是未定义行为大概率崩给你看。必须先确保内层 vector 也有足够的大小比如再写matrix[i].resize(4);。vector 也支持每一行长度不同这种叫不规则二维数组。典型场景是杨辉三角vectorvectorint triangle(5); for (int i 0; i 5; i) { triangle[i].resize(i 1); triangle[i][0] triangle[i][i] 1; for (int j 1; j i; j) { triangle[i][j] triangle[i - 1][j - 1] triangle[i - 1][j]; } }这种写法灵活但要注意vectorvectorint的性能并不像看起来那么好。因为每一行是独立的动态数组整块内存并不连续访问时会存在额外的指针跳转和多次内存分配。后面性能部分再细说。2.2 增删改查与 capacity 相关操作vector 最常用的增删改查操作一张表就能说清楚操作写法说明尾部插入v.push_back(x)均摊 O(1)可能引发扩容尾部删除v.pop_back()O(1)只析构末尾元素指定位置插入v.insert(it, x)it 之后元素整体后移O(n)删除指定位置v.erase(it)it 之后元素整体前移O(n)删除区间v.erase(first, last)区间 [first, last) 被删除O(n)清空元素v.clear()size 归零capacity 不变首元素/末尾元素v.front()/v.back()空容器上调用是未定义行为按下标访问v[i]不做越界检查检查越界访问v.at(i)越界抛std::out_of_range直接取内存地址v.data()返回指向底层数组的指针关于emplace_back和push_back这是个很经典的性能话题。push_back(x)会把 x 拷贝或移动到容器里而emplace_back(args...)直接在容器内存上就地构造对象省掉了一次移动或拷贝。对于像std::string、自定义类这种构造开销不小的类型emplace_back在多数情况下更优。struct Point { int x, y; Point(int a, int b) : x(a), y(b) {} }; vectorPoint points; // push_back 需要临时对象先构造再移动 points.push_back(Point(1, 2)); // emplace_back 直接传构造参数 points.emplace_back(1, 2);两者在 basic 类型上差别几乎可以忽略但容器装的是复杂对象时建议优先 emplace_back。还有一对必须掰开揉碎讲的概念resize和reserve。resize(n)改变的是 size。如果当前 size 小于 n会用默认值填充新增元素如果大于 n会直接截断末尾的元素。容器里实际元素个数变了遍历、size()的返回值都会受影响。reserve(n)改变的是 capacity它只预留内存空间但不会创建任何元素size 不变。如果你知道大概要存多少数据reserve可以一次性分配足够的容量避免多次扩容。很多新手的误区是以为reserve(1000)之后就能直接v[i] xxx这是错的。没有元素你访问下标就是越界正确做法是resize(1000)之后再按下标写或者reserve(1000)之后继续用 push_back 往里塞。shrink_to_fit()的作用是把多余的 capacity 释放掉让 capacity 对齐到 size。但它只是请求标准库实现可以忽略这个请求实际用下来多数主流实现都会真正做一次缩容。注意缩容是要把所有元素拷贝/移动到新内存的代价不小别频繁调用。3. 排序、去重、查找一套带走vector 实战三板斧3.1 sort 排序的几种用法日常开发里 vector 排个序太常见了。基础类型直接排vectorint nums {5, 2, 8, 1, 9}; sort(nums.begin(), nums.end()); // 升序 sort(nums.rbegin(), nums.rend()); // 降序利用反向迭代器 sort(nums.begin(), nums.end(), greaterint()); // 降序用预置仿函数 sort(nums.begin(), nums.end(), [](int a, int b) { return a b; }); // 降序用 lambda倒序最简单实用的是sort(nums.rbegin(), nums.rend());连比较规则都不用写反向迭代器一轮回顺序正好倒过来。如果容器里存的是pairint, int默认排序规则是先按 first 排first 相同再按 second 排。比如vectorpairint, int intervals; // 按 first 升序first 相同按 second 升序 sort(intervals.begin(), intervals.end());但如果你需要按 second 排就得自定义比较器sort(intervals.begin(), intervals.end(), [](const auto a, const auto b) { return a.second b.second; });C14 之后 lambda 参数可以用auto写起来干净很多。C11 就把具体的 pair 类型写全也一样能用。如果是自定义结构体我习惯的做法是如果能修改结构体就重载operator这样直接 sort 就行如果不能改或者排序规则多变用 lambda规则写在使用处直观规则复杂、多处复用的写个仿函数或者函数传函数名进去。struct Task { int priority; int deadline; string name; }; // 按优先级升序优先级相同按截止时间升序 sort(tasks.begin(), tasks.end(), [](const Task a, const Task b) { if (a.priority ! b.priority) return a.priority b.priority; return a.deadline b.deadline; });sort是不稳定排序如果有相同关键字的元素你希望保持原有相对顺序就用stable_sort。大多数情况下 sort 够用但对象里带关联信息、逻辑上要求稳定时stable_sort 别忘。3.2 unique 去重千万别忘了 erase这是一道经典面试题也是实际开发里特别容易写错的地方。std::unique的作用是把相邻的重复元素挪到容器末尾返回新逻辑末尾的迭代器。它只做搬移不负责删除。搬过去之后vector 的 size 并没有变小那些被挪到末尾的重复值还占着位置。所以去重的完整套路是三步先 sort再 unique最后 erase。vectorint v {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); // 结果: 1 2 3 4 5 6 9这三步一步都不能省。unique 之所以要求先排序是因为它只比较相邻元素。如果原数组是{1, 2, 1}没有排序直接 unique逻辑末尾会变成{1, 2, 1}1 并没有被正确去重因为两个 1 不相邻。我第一次用 unique 的时候就犯过这个错只调了unique没有erase结果调试了半天怎么 size 没变打印出来发现末尾多了几个怪值。后来才明白unique 返回的迭代器指向的才是新的逻辑结尾真正让 size 变化的是 erase 那一刀。顺带一提如果你需要的是去掉所有与给定值相同的元素就用erase加remove的惯用法v.erase(remove(v.begin(), v.end(), target), v.end());remove和unique类似也是把不需要的元素移到末尾然后返回新的逻辑末尾。这才是真正的物理删除。这两组手法本质是一个套路标准算法操作迭代器区间真正调整容器大小要靠容器自己的 erase 方法。3.3 查找与条件删除查找某个元素是否存在可以用findauto it find(v.begin(), v.end(), 42); if (it ! v.end()) { // 找到了it 指向第一个 42 }统计某个值出现次数用countint cnt count(v.begin(), v.end(), 42);按条件删除用remove_if和 erase 搭配// 删除所有偶数 v.erase(remove_if(v.begin(), v.end(), [](int x) { return x % 2 0; }), v.end());这几个惯用法一定要滚瓜烂熟。在动态数组里打游击式的逐个删除效率极差每次 erase 都会引发元素搬移。用先搬运、再统一 erase的方式一趟就能搞定而且代码还更简洁。4. 迭代器失效vector 最大的坑面试也爱考4.1 哪些操作会让迭代器失效面试 C 岗位vector 迭代器失效几乎是必问题。这个问题的背后是 vector 的存储特性它把元素放在一段连续内存上任何引起元素位置改变的操作都会让已有迭代器指向错误位置。归纳下来有两类风险操作一是引发扩容的操作比如 push_back、insert、emplace_back、reserve传入的容量大于当前 capacity。扩容意味着整个底层数组被搬走以前保存的迭代器、指针、引用统统失效。注意只要没触发扩容push_back 不会让已有迭代器失效这是很多人没说透的细节。二是会引起该位置之后元素整体移动的操作。vector 的 insert 和 erase 都会让插入/删除位置之后的元素整体搬移位置所以这些位置的迭代器也会失效。具体来说insert 会让插入点之后的所有迭代器失效erase 会让被删除点及之后的所有迭代器失效。底层原因一句话就能解释清楚迭代器本质上是封装了的指针指向底层数组的某个位置数组元素一动这个指针指向的就不再是你原来那个元素了。4.2 实战项目和代码怎么写才能避开失效问题最常见的反面教材是这样一段循环删除代码// 错误示范 for (auto it v.begin(); it ! v.end(); it) { if (*it % 2 0) { v.erase(it); // erase 之后 it 已经失效it 是未定义行为 } }这段代码在删除第一个偶数元素后it就失效了循环继续it就是典型未定义行为。看起来可能能跑可能崩溃可能在某个平台正常、换个编译器就出问题都是你排查起来最头疼的那种 bug。正确写法是利用 erase 的返回值它会返回被删除元素的下一个有效迭代器for (auto it v.begin(); it ! v.end(); ) { if (*it % 2 0) { it v.erase(it); } else { it; } }或者更推荐的做法直接用前面说的remove_if加 erase不用手动管迭代器函数式风格更不容易出错v.erase(remove_if(v.begin(), v.end(), [](int x) { return x % 2 0; }), v.end());这里需要说清楚C11 之后erase(it)的返回值是被删除元素之后那个迭代器这是标准里规定的C98 时代 erase 返回 void老代码如果是从那个时代带过来的循环写法完全不同。如果你在维护老项目要格外注意编译器标准版本。迭代器失效还有一个衍生问题引用失效。auto ref v[0];记录了一个元素的引用之后再 push_back 触发扩容ref 指向的内存就被释放了继续使用就会踩到悬空引用。这个问题比迭代器失效隐藏得更深。我的习惯是只要后续要往容器里插数据就不要长期保存容器内元素的指针、引用、迭代器要用的时候现场取。5. 性能优化与内存管理把 vector 用到飞起5.1 reserve 到底要不要用什么时候用直接说结论如果你能预估数据规模强烈建议先用reserve把容量分配好。这个操作能让大量 push_back 的性能提升一个量级。举个我实际测试过的例子往一个空 vector 里 push_back 100 万个 int不 reserve过程中要发生约 19 次扩容按 2 倍算1、2、4……524288、1048576大约 20 次。每次扩容要把已有元素全部搬到新内存算下来会有大量拷贝。如果提前reserve(1000000)就只需要一次内存分配后面全部是纯写入。实测时间差距大约有七八倍数据越多差距越明显。vectorint v; v.reserve(1000000); // 预分配 for (int i 0; i 1000000; i) { v.push_back(i); }注意reserve 之后不要用v[i] i这种方式去赋值因为 size 还是 0下标访问直接越界。可以先resize(1000000)再按下标写或者 reserve 之后继续 push_back。两个方案都常见区别是 resize 会把元素全部默认构造一遍int 无所谓但如果是复杂对象会有构造开销reserve 不会。5.2 clear 和 swap 的区别怎么才能真正释放内存很多人误以为v.clear()之后vector 占用的内存就释放了。这是错的。clear 只是把 size 置 0逐个析构元素capacity 保持原样不动。如果你在 for 循环里反复 clear push_back内存会一直保持高位占用程序峰值内存不好看。如果你就是想把这部分内存还给系统有一个经典手法vectorint().swap(v);或者 C11 之后写作vectorint().swap(v); // 用空临时 vector 和 v 交换swap 之后v 拿到临时对象的空 capacity临时对象拿着 v 原来那堆内存离开这一行就被析构内存随之释放。这是真正把 capacity 清空的写法。如果只想缩小容量而不全部清空用shrink_to_fit()。注意它不一定执行且执行时有全部元素搬移的成本所以只在你确实需要立刻释放多余内存时才用。大多数程序根本不需要频繁缩容频繁缩容反而会破坏 vector 的性能优势。5.3 vector 作为参数和返回值时的性能习惯把 vector 当函数参数时传值会触发一次完整拷贝。大容器传值一次拷贝的开销可能比函数内部逻辑还大。正确的姿势是只读void func(const vectorint v);要改void func(vectorint v);要移动void func(vectorint v);返回 vector 也别太担心现代编译器基本都有 NRVO具名返回值优化和移动语义对于vectorint func() { vectorint v; ... return v; }这种写法绝大多数情况下不会产生真正的拷贝。还有个小技巧如果函数要往传入的容器尾部添加数据接收一个引用参数通常比返回一个新容器更高效void loadData(vectorint out) { out.clear(); out.reserve(expectedSize); // 填充数据 out.push_back(...); }这样还能复用调用方的容量省一次分配。6. 避坑合集这些 vector 使用细节踩过一遍就忘不掉6.1 vectorbool 是个特例vectorbool在标准库设计中是个出了名的特殊公民。它做了位压缩一个 bool 只占 1 bit内存省了但代价是operator[]返回的并不是bool而是一个代理对象。你以为自己在操作 bool实际操作的是一个行为像 bool 的临时对象。因此以下代码是编译不过的vectorbool vb; bool ref vb[0]; // 编译错误不能把代理对象绑定到 boolauto 推导也会出问题auto b vb[0]; // b 是代理类型不是 bool如果不需要位压缩或者想避免这些奇奇怪怪的问题有两个常用替代vectorchar或dequebool。vector 每个元素占 1 字节空间不是最省但行为完全符合直觉。6.2 at() 和 operator[] 的取舍v[i]不做越界检查越界访问的结果是未定义行为可能拿到脏数据可能直接 segfault。v.at(i)会先做边界检查越界就抛std::out_of_range异常。性能上v[i]当然更快但前提是你能保证索引不越界。在算法题和性能敏感的地方用v[i]在业务逻辑里、或者索引来自外部输入的时候用at()更安全。代码里全是裸v[i]的项目越界崩起来定位成本很高。另外v.front()和v.back()在空容器上也是未定义行为用之前检查一下!v.empty()是好习惯。6.3 v.data() 和 C 接口交互vector 的元素是连续存放的这意味着它可以直接和 C 风格接口对接。C11 提供了data()方法返回指向底层数组的指针可以传给需要指针和长度的函数std::vectorint v(100); some_c_function(v.data(), v.size());注意data()返回的指针在 vector 后续插入元素触发扩容后会失效不要长期保存。如果 C 接口要求写入数据可以分配好空间再传v.resize(100); some_c_function(v.data(), v.size()); // 之后 v.size() 是 100可以正常访问还有一点如果 vector 为空data()的返回值可能是 nullptr也可能是非空指针标准库实现规定 C11 之后 data() 可能返回非空传给 C 接口时记得判断 size 为 0 的情况。6.4 二维 vector 的初始化与访问陷阱前面提到过vectorvectorint的内存是分行分配的行与行之间不连续。这个特性带来两个问题第一如果内层 vector 没初始化就直接访问会崩。vectorvectorint mat;这样创建出来mat 大小为 0连行都没有。你需要先mat.resize(rows);或者用vectorvectorint mat(rows, vectorint(cols, 0));再访问mat[i][j]。第二频繁往vectorvectorint里 push_back 小 vector 会产生大量小内存分配性能较差。如果性能敏感且矩阵是规则的推荐用一维 vector 模拟int rows 100, cols 100; vectorint flat(rows * cols, 0); // 访问 (i, j) 元素 flat[i * cols j] 42;这个写法内存连续、访问快唯一的代价是需要手动算索引。处理图像像素、矩阵运算这类高性能场景时这招非常实用。6.5 警惕循环中反复 erase 导致的 O(n²)遇到边遍历边删除的需求如果数据量很大像我前面说的在循环里逐个 erase 最坏情况下是 O(n²) 的因为每次删除后后面所有元素都要前移。更高效的做法是标记 一次性删除或者直接上remove_iferase的惯用法一趟 O(n) 搞定。数据几万以内你可能察觉不到差距到几百万元素时O(n²) 会慢到无法接受。写代码的时候养成分清单次操作代价和多次操作总代价的习惯很多性能问题都能提前规避。7. 项目实战里我的一些固定习惯前阵子在做数据重组模块时要解析几十万行文本每行拆出若干字段存进 vector。第一次跑的时候程序内存稳定增长我一度以为有泄漏。排查下来发现是每次 append 前都没 reservevector 反复扩容旧内存虽然被释放了但分配器没及时把大块内存还给操作系统导致内存峰值虚高。后来我在开头加了一句v.reserve(estimated_size);内存曲线立刻平稳耗时也明显下降。从此我养成了一个习惯凡是能预估数据规模的 vector一律先 reserve。另外一个小技巧提醒一下vector 里存的是对象指针比如vectorunique_ptrT或原始指针时顺序访问的缓存局部性依然很好但对象本身散落在堆上性能没有直接存对象好。能用对象就用对象除非对象体积大、需要的动态多态否则别过度用指针。最后再分享一个判断标准。面试或者实际开发中遇到需要随机访问、需要动态增长、对缓存友好的场景vector 是无脑首选。如果频繁在头部插入删除那是 deque 或 list 的领域如果大量元素而无所谓顺序也可以考虑 unordered_map。选容器的本质是选数据结构vector 是默认答案但不总是最优解。我用 vector 这些年最大的体会就是它之所以是 C 里最常用的容器不是说它没有缺点而是它的缺点只要被理解清楚几乎都能用正确用法避开。把 capacity 和 size 分清楚、记住迭代器失效的时机、惯用 erase remove 这套组合拳就已经超越了很多工作多年的开发者。