vector.push_back()执行过慢排查：O(N³)复杂度代码耗时异常分析

我参与了一个时间复杂度为O(N³)（N约为300）的项目，使用tuple的vector存储数据，运行耗时超5秒，速度极慢。为排查问题，编写了以下基础耗时测试代码，平均运行耗时3.5秒，但按理论计算（总操作约300³=27000000次，vector.push_back()均摊O(1)，加上tuple的常数因子）应该在1秒内完成。

测试代码如下：

#include <bits/stdc++.h>
using namespace std;

vector<tuple<int, int, int>> pos[305];

int main() {
    auto start = clock();
    for (int i = 1; i <= 300; i ++) {
        for (int j = 1; j <= 300*300; j ++) {
            pos[i].push_back({0, 0, 0});
        }
    }
    cout << (double)(clock() - start)/CLOCKS_PER_SEC;
}

核心原因拆解 #

1. 频繁扩容带来的拷贝开销 #

vector.push_back()的均摊O(1)复杂度是基于扩容策略（通常每次扩容为当前容量的1.5~2倍），但初始容量极小。你的代码中每个pos[i]需要插入90000个元素，会触发多次扩容，每次扩容都要将现有元素完整拷贝到新的内存块中。300个vector的累计扩容拷贝操作，是耗时的主要来源之一。

2. 内存碎片化导致分配效率下降 #

你创建了305个独立的vector，每个存储的tuple<int,int,int>是小对象（约12字节）。频繁的小内存块分配会造成内存碎片化，操作系统的内存分配器在处理大量分散的小对象请求时，分配和回收的效率会显著降低，进一步拉长了执行时间。

3. CPU缓存命中率极低 #

300个vector的内存地址是分散的，当循环切换i值时，CPU缓存无法利用空间局部性，每次都要从主存加载新的内存页，缓存失效的开销会大幅拖慢执行速度。

关于vector.push_back()的速度 #

push_back()本身的均摊复杂度没有问题，但实际性能严重依赖内存分配效率和缓存利用。你的场景中，push_back()的开销被扩容拷贝、内存碎片化和缓存失效放大了，并非push_back()本身执行慢，而是配套的内存操作和缓存问题导致整体耗时飙升。

优化方向 #

• 提前预留容量：在插入元素前调用pos[i].reserve(300*300)，彻底避免扩容拷贝。
• 改用连续内存存储：比如用单个vector存储所有元素，或使用二维数组，提升CPU缓存命中率。
• 替换tuple为array<int,3>：固定大小的数组构造开销略低于tuple，能减少常数因子。

内容的提问来源于stack exchange，提问作者Lithanium