夜雨聆风学习资料网

ARTICLE · 1383395

我把 vector 的源码翻了一遍,push_back 没那么简单

我把 vector 的源码翻了一遍,push_back 没那么简单

朋友线上服务 CPU 周期性飙高,用了线程池也没压住。VS 诊断工具一跑,50% 的 CPU 落在一个叫 init_vector 的函数上。

循环只有 4800 次 push_back,代码里连个分支都没有。问题不在算法,在内存分配。

▍4800 次 push_back 吃掉一半 CPU

那段代码简化后是这样:

void init_vector() {

  std::vector<float> v;

  for (int i = 0; i < 4800; i++) {

    v.push_back(float(i) / 4800);

  }

}

每次 push_back 发现 capacity 不够,vector 就要重新开一块内存,把旧元素全部搬过去,再释放旧块。4800 个 float 最终容量约 6144,扩容约 13 次,累计搬移元素数接近 1.2 万次。

最近整理了一套比较完整的学习资料(如下图所示),主要包括:

  • AI专栏:图解 Transformer、图解深度学习、AI infra 工程必知必会等

  • C++专栏:C++地基、C++入门、C++进阶、内存序与原子操作等

需要的同学可以添加小助手 vx(cppmiao24),免费领取👇👇

搬移本身不慢,慢的是每次搬移都伴随一次 new 加一次 delete。13 次分配在 4800 次循环里不算多,但每次分配都可能触发系统调用和内存碎片整理。

你以为在 pushback 一个元素,其实在 pushback 整个数组。

图 1 · 4800 次 push_back 中扩容次数与搬移元素量的关系

▍扩容三步:开新内存、搬旧元素、释放旧内存

MSVC STL 里扩容走三步。第一步 _Calculate_growth 算新容量:旧容量加旧容量的一半,即 1.5 倍扩张。网上常说的 2 倍是 GCC 的做法,MSVC 不是。

第二步 _Umove_if_noexcept 搬旧元素。元素有 noexcept 移动构造就移动,否则退化成拷贝。拷贝成本可能是移动的几倍,取决于元素里有没有堆内存。

第三步 _Change_array 释放旧内存:先销毁旧元素再 deallocate。旧迭代器全部失效,扩容期间任何持有引用的代码都会踩空。

size_type _Calculate_growth(size_type _Newsize) {

  const size_type _Old = capacity();

  const size_type _Geo = _Old + _Old / 2;

  if (_Geo < _Newsize) return _Newsize;

  return _Geo;

}

这段源码说明扩容倍率是 1.5,不是 2。倍率越小,扩容越频繁。

▍1.5 倍扩容为什么比 2 倍更坑

1.5 倍增长在容量较小时扩容更频繁。4800 个元素要扩约 13 次,2 倍增长只需约 9 次,搬移总量差近一倍。

1.5 倍的好处是内存复用率高,释放的旧块更容易被后续分配复用。2 倍容易留下大量无法利用的碎片,尤其在长时间运行的服务里。

判断条件很简单:元素数量可预估且构造代价高时,提前 reserve;数量不可预估且元素很轻时,1.5 倍反而更省内存。

图 2 · 1.5 倍与 2 倍扩容的累计搬移量对比

▍改一行 reserve,CPU 从 50% 降下来

在循环前调用 v.reserve(4800),一次性分配足够内存,后续 push_back 不再触发扩容,搬移次数归零。

reserve 只改 capacity 不改 size,push_back 仍然安全。resize 会真正构造元素,适合需要下标直接赋值的场景。两者别混用。

如果元素类型没有 noexcept 移动构造,扩容时走拷贝构造,代价更高。给移动构造加 noexcept 能省掉这笔拷贝。

· 在所有已知规模的 push_back 循环前加 reserve。

· 给自定义类型的移动构造补上 noexcept。

· 用 resize 替代「先 reserve 再逐个 push_back」的写法。

▍用构造/析构计数验证扩容次数

写一个 Person 类,在构造、拷贝、移动、析构里各打印一个标记。push_back 时观察输出就能数出扩容次数。

不 reserve 时 10 个元素会看到多次 copy/move 和 destruct;reserve(10) 后只剩 10 次构造和 10 次析构。

struct Person {

  Person() { puts("ctor"); }

  Person(const Person&) { puts("copy"); }

  Person(Person&&) noexcept { puts("move"); }

  ~Person() { puts("dtor"); }

};

这个验证方法比看源码快,适合在 code review 时当场演示给同事看。

今天就能做两件事:在所有已知规模的 push_back 循环前加 reserve;给自定义类型的移动构造补上 noexcept。本周挑一个高频路径,用构造计数跑一遍,确认扩容次数是否为零。

C++ 校招 / 社招跳槽逆袭!从0到1打造高含金量项目,导师1v1辅导,助你斩获大厂offer!

很多同学准备校招时最焦虑的问题就是:“简历没项目,怎么打动面试官?”

为了解决这个痛点,我们推出了C++项目实战训练营

在这里,你可以:

  • 系统学习 C++ 进阶知识
  • 自选项目,从 0 到 1 实战造轮子
  • 导师一对一指导,代码逐行 Review
  • 拿到能写进简历的项目成果,秋招直接加分!

我们不只是教你写代码,更带你走一遍完整的项目流程: 从需求分析、架构设计、编译调试,到版本管理、测试发布,全流程掌握!

项目配套资料齐全,遇到问题还有导师帮你答疑,不怕卡壳!

📌 想了解具体项目可以看这篇:成果喜人,新一轮成长机会来了!或直接添加vx(cppmiao24)了解详情~

项目准备好了,你只差一次出发。

相信我,这些项目绝对能够让你进步巨大!下面是其中某三个项目的说明文档

训练营适用人群:

  • 备战春招和秋招的应届生,科班非科班均可,
  • 工作 3 年以内,想跳槽的社招同学
  • 如果你有以下困扰,欢迎联系我们,我们愿意为你提供帮助和支持
  • 不知道该复习哪些内容,如何开始复习。
  • 对面试考察重点不清楚,复习效率低下。
  • 缺乏有含金量的实战项目经验。
  • 想要提升自己的实战能力,提升做项目及解决问题的能力
  • 对算法题无从下手,缺乏解题思路和常见解题模板。
  • 自控力不足,难以专注于系统复习。
  • 希望获得大厂的内推机会。
  • 独自备战校招社招感到孤单,想要找到学习伙伴。

不适合人群:

  • 缺乏耐心和毅力,急于求成的人
  • 对编程逻辑思维基础薄弱,且不愿努力提升的人
  • 只想快速获得成果而不注重基础学习的人
推荐阅读:
模板报错三百行?concept 让它变成三行
C++性能优化:移动语义到底省了多少拷贝?
一个 shared_ptr 循环引用,让服务内存每天涨 200M

回首页,搜索你想要的文档

在首页搜索框输入关键词,快速定位资料

文库首页搜索指引 立即搜索

相关学习资料