vector 容器优化编程笔记

发表于 分类于 ， 阅读次数：

vector 容器优化编程笔记

时间：2025/11/22
课程地址：Bilibili - BV1qF411T7sd
课件仓库：parallel101/course

1. 先建立正确认知

std::vector<T> 本质上是一个连续内存上的动态数组：

  • 支持 O(1) 随机访问
  • 尾部追加通常是摊还 O(1)
  • 中间插入、删除通常是 O(n)
  • 元素存储连续，因此缓存友好，这也是它在高性能 C++ 里极其常见的原因

可以把一个 vector 理解成 3 个核心状态：

  • data：底层连续内存首地址
  • size：当前已构造的元素个数
  • capacity：当前已分配、但不一定都已使用的容量

示意：

1
2
3
4
5
6
7
8
栈上（若 vec 是局部变量）
    vec 对象本身
    ├── data -----> 堆上连续内存
    ├── size
    └── capacity

堆上
    [elem0][elem1][elem2]...[elemN-1]

注意：

  • vector 对象本身未必一定在栈上，它也可以位于堆上、全局区或作为成员存在
  • 但它管理的元素存储区通常在动态分配的连续内存中

2. 底层发生了什么

2.1 分配器 allocator

vector 并不是直接手写 malloc/free，而是通过分配器管理内存。标准库实现里更准确地说，通常是通过 std::allocator_traits<Alloc> 来调用：

操作 作用
allocate(n) 分配可容纳 n 个 T 的原始内存
deallocate(p, n) 释放之前分配的内存
construct(p, args...) 在指定地址构造对象
destroy(p) 调用对象析构

2.2 扩容时的流程

当 size == capacity 且继续插入时，vector 通常会：

  1. 申请一块更大的新内存
  2. 将旧元素搬迁到新内存
  3. 销毁旧内存中的对象
  4. 释放旧内存
  5. 更新 data/capacity

这里的关键代价不是“申请内存”本身，而是元素搬迁。

如果 T：

  • 支持廉价移动，并且移动构造 noexcept，扩容代价通常较小
  • 只能复制，或者复制/移动代价大，扩容成本就会明显上升

对平凡类型（如 int/float/POD）来说，搬迁通常更便宜。

2.3 为什么 vector 性能常常很好

核心不是“接口简单”，而是它的存储模型很适合现代 CPU：

  • 连续内存，缓存命中率高
  • 顺序遍历容易被硬件预取
  • 适合 SIMD / 批量处理
  • 与 C 接口天然兼容，可直接用 data()

所以很多场景中，哪怕算法复杂度一样，vector 也会比 list/map 这类节点式容器更快。

3. 迭代器、指针与连续内存

vector 的迭代器是随机访问迭代器，很多实现中本质上接近普通指针。

常见容器对比：

容器 迭代器类型 连续内存
vector 随机访问 是
array 随机访问 是
deque 随机访问 否
list 双向迭代器 否
set/map 双向迭代器 否

这意味着：

  • vector 支持 it + n、it[n]
  • 可高效配合排序、二分、批量算法
  • 可用 data() 直接获得底层首地址

4. 常用接口整理

4.1 创建

1
2
3
std::vector<int> a;          // 空 vector
std::vector<int> b(4);       // 4 个元素，值初始化为 0
std::vector<int> c(4, 7);    // 4 个元素，均为 7

4.2 读写与访问

接口 说明
a[i] O(1) 访问，不做边界检查
a.at(i) 带边界检查，越界会抛异常
a.front() 首元素，空容器上调用是未定义行为
a.back() 尾元素，空容器上调用是未定义行为
a.data() 返回底层连续内存首地址；空容器时不可解引用
a.size() 当前元素个数
a.capacity() 当前容量
a.empty() 是否为空

4.3 修改

接口 说明
push_back(x) 尾部追加一个元素
emplace_back(args...) 尾部原位构造对象
pop_back() 删除尾元素，不返回值
clear() 清空元素，通常不释放 capacity
resize(n) 改变 size；变大时会构造新元素
resize(n, val) 扩大时用 val 填充
reserve(n) 预留至少 n 个容量，不改变 size
shrink_to_fit() 请求回收多余容量，但不保证一定执行
insert(pos, x) 在任意位置插入，通常需要搬移后续元素
erase(pos) 删除一个元素，后续元素前移
erase(first, last) 删除一个区间
assign(...) 覆盖原有内容
swap(other) 常数级交换内部资源

4.4 reserve 和 resize 的区别

这是最容易混淆，也最影响性能的一组接口。

接口 改 size 改 capacity 是否构造元素
reserve(n) 否 是，至少到 n 否
resize(n) 是 可能会变大 是

例子：

1
2
3
std::vector<int> v;
v.reserve(100); // 只预留空间，还没有元素
v.resize(100);  // 现在真的有 100 个元素了

如果你只是“后面准备持续 push_back 数据”，通常应该优先考虑 reserve，而不是 resize。

5. 复杂度与性能直觉

操作 复杂度 说明
随机访问 a[i] O(1) 动态数组优势
push_back 摊还 O(1) 扩容那次会更贵
pop_back O(1) 尾删很便宜
insert 到尾部 摊还 O(1) 本质接近 push_back
insert/erase 中间位置 O(n) 后续元素要搬移
顺序遍历 O(n) 且通常缓存友好

一句话总结：

  • 尾部加删很适合 vector
  • 头部/中间频繁插删不适合 vector

6. 迭代器、引用、指针何时失效

这是 vector 最重要的易错点之一。

6.1 会导致整体失效的典型情况

一旦发生扩容，原来的：

  • 迭代器
  • 指针
  • 引用

都可能全部失效，因为底层内存地址变了。

1
2
3
4
5
6
7
std::vector<int> v;
v.reserve(1);
v.push_back(10);

int* p = &v[0];
v.push_back(20); // 可能扩容
// p 此时可能已经悬空，不能继续使用

6.2 局部失效的情况

即使没有扩容，insert/erase 也会让插入点/删除点及其之后的迭代器、引用、指针失效，因为元素位置被搬动了。

6.3 记忆方式

可以直接记成一句：

只要 vector 的元素位置可能发生变化，相关迭代器/引用/指针就要重新获取。

7. 高性能写法与优化要点

7.1 已知大概元素个数时，先 reserve

这是最实用、收益也最稳定的优化。

1
2
3
4
5
std::vector<int> v;
v.reserve(n);
for (int i = 0; i < n; ++i) {
    v.push_back(i);
}

好处：

  • 避免多次扩容
  • 减少元素重复搬迁
  • 降低 allocator 调用次数

7.2 “稍后赋值”时，不要误用 resize

如果你只是想“预留空间，后面再逐个写入”，错误写法往往是：

1
2
3
4
5
std::vector<int> v;
v.resize(n); // 先构造 n 个元素
for (int i = 0; i < n; ++i) {
    v.push_back(i); // 最终 size 变成 2n，逻辑也错了
}

正确思路通常是：

1
2
3
4
5
std::vector<int> v;
v.reserve(n);
for (int i = 0; i < n; ++i) {
    v.push_back(i);
}

如果你确实要“先开好 n 个元素，再按下标写”，那才用 resize(n)：

1
2
3
4
5
std::vector<int> v;
v.resize(n);
for (int i = 0; i < n; ++i) {
    v[i] = i;
}

7.3 对复杂对象，优先考虑 emplace_back

1
2
3
4
5
6
7
8
struct Person {
    std::string name;
    int age;
    Person(std::string n, int a) : name(std::move(n)), age(a) {}
};

std::vector<Person> v;
v.emplace_back("alice", 18);

emplace_back 的主要收益是：

  • 直接在尾部构造对象
  • 减少临时对象

但对 int/double 这类简单类型，emplace_back 和 push_back 通常差别不大。

7.4 批量删除时使用 erase-remove 惯用法

1
2
3
4
std::vector<int> v = {1, 2, 3, 4, 5, 6};
v.erase(std::remove_if(v.begin(), v.end(),
                       [](int x) { return x % 2 == 0; }),
        v.end());

remove_if 不是真的删元素，它只是把“保留元素”搬到前面，真正缩短容器还要靠 erase。

7.5 尽量顺序访问

相比随机跳跃式访问，顺序遍历更容易利用：

  • cache line
  • CPU 预取
  • 向量化优化

这就是为什么很多数值计算、图像处理、游戏 ECS、批量数据处理都偏好 vector。

7.6 减少中间插入和删除

如果你的操作模式是：

  • 频繁在头部插入
  • 频繁在中间删除
  • 大量元素反复搬移

那么 vector 往往不是好选择。
可以重新审视算法，或者考虑：

  • deque
  • 分块数组
  • 索引表 + 延迟删除
  • SoA 数据布局

8. 容量增长与摊还复杂度

为什么 push_back 明明偶尔会很贵，却仍然说是摊还 O(1)？

因为 vector 不会每次只多分配 1 个元素。实现通常会按一定倍率增长容量，例如：

  • 1.5 倍
  • 2 倍

具体倍率由标准库实现决定，标准没有强制规定。

正因为每次扩容都“多留一些余量”，所以虽然少数插入很贵，但均摊到大量 push_back 上，单次成本仍可视为常数级。

9. 并发场景下的注意点

这部分在“并行编程”里很重要。

9.1 vector 本身不是线程安全容器

如果多个线程同时：

  • 读同一个 vector，且没有线程写，一般没问题
  • 只要有线程写，就必须同步

尤其是以下操作风险极高：

  • push_back
  • emplace_back
  • insert
  • erase
  • resize
  • reserve

因为它们可能改变底层内存布局。

9.2 并行读通常友好，并行写要分区

比较典型的安全模式是：

  • 先 resize(n)
  • 再让不同线程写入互不重叠的下标区间

例如每个线程只负责 [L, R) 一段：

1
2
3
4
std::vector<float> v;
v.resize(n); // 先把元素都构造好

// 不同线程各自写不同区间 v[L..R)

这种模式比多个线程同时 push_back 更容易获得正确性和性能。

9.3 并行场景下的一个常见优化思路

不要让所有线程争抢同一个全局 vector：

  • 每个线程先写自己的局部 vector
  • 局部阶段用 reserve
  • 最后统一汇总到总容器

这样通常比共享一个 vector + 加锁 push_back 更高效。

10. 容易忽略但很重要的点

10.1 data() 在空容器上可取，但不可解引用

1
2
3
std::vector<int> v;
auto p = v.data(); // 可以拿到
// *p; // 错，空容器上不能解引用

所以和 C 接口交互时，要同时传 data() 和 size()，不能只传裸指针。

10.2 clear() 不等于释放内存

1
v.clear();

这通常只会把 size 变成 0，capacity 往往还在。
如果后面还会继续填充数据，这反而是好事，因为可以复用之前申请过的内存。

10.3 shrink_to_fit() 只是“请求”

它不是强制命令，标准并不保证一定回收成功。

10.4 vector<bool> 是特化版，行为不像普通 vector<T>

vector<bool> 为了节省空间，会按位压缩存储，它返回的很多东西不是普通 bool&。
所以在泛型代码、并发位操作、取地址等场景里常常带来意外问题。

如果你需要稳定、直观的布尔数组语义，常见替代方案是：

  • std::vector<char>
  • std::vector<uint8_t>
  • std::bitset
  • 专用 bitset/bitmap 容器

10.5 不要长期持有元素地址并假设它永远稳定

这类代码很危险：

1
2
3
auto* p = &v[0];
// ... 中间若发生扩容/插入/删除
use(*p); // 可能悬空

更稳妥的做法通常是：

  • 只在短时间内使用指针/引用
  • 改动容器后重新获取
  • 或保存索引，而不是保存地址

11. 什么时候优先选 vector

优先考虑 vector 的典型场景：

  • 元素个数大，且以遍历为主
  • 需要频繁随机访问
  • 主要在尾部追加
  • 希望更好的缓存局部性
  • 需要和 C API / GPU / 数值库交互

不太适合的场景：

  • 频繁头插头删
  • 中间位置大量插删
  • 强依赖“节点地址永不变化”

12. 高频面试 / 复习题

Q1：reserve 和 resize 的区别？

  • reserve 调整容量，不创建元素
  • resize 调整元素个数，必要时构造或销毁元素

Q2：为什么 push_back 是摊还 O(1)？

  • 因为容量按倍率增长
  • 少数扩容代价被大量普通插入均摊

Q3：什么时候迭代器会失效？

  • 扩容后，通常全部失效
  • insert/erase 后，受影响位置及其之后通常失效

Q4：为什么高性能代码偏爱 vector？

  • 连续内存
  • 缓存友好
  • 顺序遍历快
  • 接近底层数组，抽象成本低

Q5：为什么很多并行写入场景不建议多个线程同时 push_back？

  • 存在数据竞争
  • 扩容会改写底层地址
  • 即便加锁，争用也会明显拖慢性能

13. 一页总结

vector 最重要的不是“会用 API”，而是要掌握它的性能模型：

  • 它是连续内存动态数组
  • 尾插强，中间插删弱
  • reserve 是最常用的性能优化手段
  • 扩容会导致迭代器/引用/指针失效
  • 在并发环境里，推荐“先分配、再分区写入”

如果只记一条实战原则，那就是：

能预估元素个数时，优先 reserve；能顺序访问时，尽量顺序访问。

14. 可继续补充的相关主题

和本节关系最紧密、值得继续整理的内容：

  1. AoS 与 SoA 的访存差异
  2. std::span 与 data()/size() 的无拷贝视图
  3. std::pmr::vector 与内存池优化
  4. 平凡类型、移动语义、noexcept move 对扩容成本的影响
  5. 并行归约、分块写入、避免伪共享的 vector 用法

15. 参考资料

  1. cppreference: std::vector
    https://en.cppreference.com/w/cpp/container/vector

  2. cppreference: iterator invalidation
    https://en.cppreference.com/w/cpp/container#Iterator_invalidation

  3. parallel101/course
    https://github.com/parallel101/course