26、性能优化与benchmark：容器选择策略、算法复杂度分析、缓存友好性、避免不必要的拷贝
性能优化这件事，说白了就是「用最少的资源，干最多的活」。我在项目里见过太多人一上来就写 std::vector，也不管数据怎么用、怎么删、怎么查。结果上线后 CPU 飙高，一查火焰图，全是容器的锅。
这一章，我会把容器选择、算法复杂度、缓存友好性、避免拷贝这几个点串起来讲。最后再带你用 Google Benchmark 做一次正经的性能测试。嗯，都是实战经验。
26.1 容器选择策略：别让习惯替你做决定
我习惯先问自己三个问题：
- 数据是频繁插入删除，还是只读遍历？
- 需要随机访问吗？
- 数据量有多大？
举个例子。如果你只需要在末尾追加数据，偶尔按索引访问，std::vector 是首选。但如果你需要在中间频繁插入，std::list 或 std::deque 可能更合适。我在项目中遇到过有人用 std::vector 做高频中间插入，结果每次插入都触发大量元素移动，性能直接崩了。
| 场景 | 推荐容器 | 原因 |
|---|---|---|
| 随机访问 + 尾部插入 | vector | 连续内存，缓存友好 |
| 中间插入/删除频繁 | list / forward_list | 节点式，不移动元素 |
| 双端操作 | deque | 两端插入删除 O(1) |
| 查找频繁 | unordered_set / map | 哈希表，平均 O(1) |
| 有序查找 | set / map | 红黑树，O(log n) |
26.2 算法复杂度分析：别被大O骗了
大O表示法是个好东西，但它只告诉你「趋势」，不告诉你「常数」。我见过有人因为 std::map 是 O(log n) 就无脑用，结果数据量只有几百个，哈希表的 O(1) 反而因为哈希计算开销更大。
为什么会这样？因为大O忽略了常数因子。当 n 很小时，常数因子可能主导性能。你想想看，一个简单的线性查找在 100 个元素里可能比红黑树还快。
我曾经在项目中优化一个查找热点，把 std::map 换成了 std::vector + 线性查找，结果快了 30%。原因很简单：数据量小，vector 的缓存局部性完胜。
26.3 缓存友好性：CPU 比你想象的更挑剔
现代 CPU 的 L1 缓存只有几十 KB。如果你的数据不连续，CPU 就得频繁去内存取数据，这叫「缓存未命中」。一次缓存未命中的代价，可能是几百个 CPU 周期。
我习惯用 std::vector 而不是 std::list，就是因为 vector 的元素在内存里是挨着的。遍历 vector 时，CPU 可以预取下一批数据。而 list 的节点散落在内存各处，遍历一次就是一次「内存跳跃」。
看个例子：
// 缓存友好：连续内存
std::vector<int> vec(1000000);
for (auto& v : vec) { v = v * 2; }
// 缓存不友好：节点分散
std::list<int> lst(1000000);
for (auto& v : lst) { v = v * 2; }在我的测试中，vector 版本比 list 版本快了 5 倍以上。这就是缓存的威力。
std::vector 模拟「逻辑链表」——用索引代替指针，数据还是连续的。我曾经在游戏服务器里这么干过，效果拔群。
26.4 避免不必要的拷贝：拷贝是性能杀手
拷贝操作是 C++ 性能优化的头号敌人。我见过有人写这样的代码：
std::vector<std::string> getNames() {
std::vector<std::string> names;
// ... 填充数据
return names; // 这里可能触发拷贝
}在 C++11 之后，返回值优化（RVO）和移动语义已经能解决大部分问题。但如果你不小心，还是会踩坑。
我习惯的做法：
- 传参用 const 引用，避免值传递
- 返回时直接返回局部变量，依赖 RVO
- 需要「保留原数据 + 修改副本」时，用移动语义
- 对于大对象，用
std::move显式转移所有权
// 好的做法
void process(const std::vector<int>& data) {
// 只读访问，不拷贝
}
// 坏的做法
void process(std::vector<int> data) {
// 这里会拷贝整个 vector
}26.5 实战：使用 Google Benchmark 进行性能测试
理论说再多，不如跑一次 benchmark。Google Benchmark 是我最常用的性能测试工具，简单、准确、可重复。
先安装：
git clone https://github.com/google/benchmark.git
cd benchmark
cmake -E make_directory "build"
cmake -E chdir "build" cmake -DCMAKE_BUILD_TYPE=Release ..
cmake --build "build" --config Release写一个简单的 benchmark：
#include <benchmark/benchmark.h>
#include <vector>
#include <list>
static void BM_VectorTraversal(benchmark::State& state) {
std::vector<int> vec(state.range(0));
for (auto& v : vec) v = 1;
for (auto _ : state) {
for (auto& v : vec) {
benchmark::DoNotOptimize(v);
}
}
}
static void BM_ListTraversal(benchmark::State& state) {
std::list<int> lst(state.range(0));
for (auto& v : lst) v = 1;
for (auto _ : state) {
for (auto& v : lst) {
benchmark::DoNotOptimize(v);
}
}
}
BENCHMARK(BM_VectorTraversal)->Range(8, 8<<10);
BENCHMARK(BM_ListTraversal)->Range(8, 8<<10);
BENCHMARK_MAIN();运行结果会告诉你每个操作的耗时。我习惯关注「每轮迭代的时间」和「CPU 周期数」。如果两个容器的大O一样，但实际耗时差很多，那多半是缓存的问题。
mean 和 cpu_time。
26.6 知识体系总览
下面这张图总结了我对性能优化的理解。从容器选择到算法分析，再到缓存和拷贝，最后用 benchmark 验证。每一步都环环相扣。
这张图把整个流程串起来了。你从「容器选择」出发，结合「算法复杂度」和「缓存友好性」，再注意「避免拷贝」，最后用 benchmark 验证。每一步都有据可依。