STL性能优化：容器选择策略、内存管理技巧、算法复杂度分析、避免不必要的拷贝
说实话，STL用得好不好，性能差距能到十倍以上。我见过太多人把vector当万能容器，结果程序跑起来慢得像蜗牛。今天咱们就聊聊怎么把STL的性能榨干。
一、容器选择：选对了就赢了一半
容器选型这事儿，说白了就是「数据怎么用」决定了「容器怎么选」。我个人习惯先问自己三个问题：
- 需要频繁在中间插入/删除吗？
- 数据量有多大？
- 查找操作多不多？
1.1 序列容器：vector vs list vs deque
| 操作 | vector | list | deque |
|---|---|---|---|
| 尾部插入 | O(1) 均摊 | O(1) | O(1) |
| 头部插入 | O(n) | O(1) | O(1) |
| 中间插入 | O(n) | O(1)（已知位置） | O(n) |
| 随机访问 | O(1) | O(n) | O(1) |
| 内存占用 | 低（连续） | 高（每个节点额外开销） | 中（分块连续） |
我在项目中遇到过这样一个坑：用list存了10万个整数，每个节点光指针开销就16字节（64位系统），加上数据本身4字节，内存浪费了4倍！后来换成vector，内存占用直接降到40%。
核心原则：能用vector就别用list。除非你需要在中间频繁插入删除，而且数据量很大。
1.2 关联容器：map vs unordered_map
很多人觉得unordered_map一定比map快，其实不一定。我做过测试：
- 数据量小于1000时，map（红黑树）反而更快，因为哈希计算有开销
- 数据量大于10000时，unordered_map优势明显
- 需要有序遍历时，只能用map
我的经验：如果键是整数且范围密集，直接用vector做索引查找，O(1)且没有哈希冲突，这才是最快的。
二、内存管理技巧：别让STL偷偷浪费内存
2.1 reserve() 和 shrink_to_fit() 的正确用法
vector的动态扩容是性能杀手。每次扩容都要重新分配内存、拷贝所有元素。我见过一段代码：
// 糟糕的做法
std::vector<int> v;
for (int i = 0; i < 100000; ++i) {
v.push_back(i); // 可能触发多次扩容
}
// 好的做法
std::vector<int> v;
v.reserve(100000); // 提前分配足够内存
for (int i = 0; i < 100000; ++i) {
v.push_back(i); // 不会触发扩容
}我曾经在一个数据处理模块里，没加reserve，结果vector扩容了18次，每次都要拷贝几十万个元素。加上reserve后，性能提升了3倍。
注意：shrink_to_fit() 只是请求，不保证一定释放内存。C++标准说这是「非绑定请求」，具体看实现。
2.2 自定义分配器：什么时候用？
说实话，90%的场景不需要自定义分配器。但如果你在做高频交易或游戏引擎，那就另当别论了。
我建议在以下情况考虑自定义分配器：
- 大量小对象频繁分配释放（比如每秒几万次）
- 需要内存池来避免碎片
- 特定内存对齐要求（比如SIMD指令需要16字节对齐）
三、算法复杂度分析：别被O(1)骗了
很多人看到O(1)就觉得快，其实不然。常数因子可能很大。举个例子：
// 看似O(1)，实际很慢
std::unordered_map<int, std::string> m;
m[42] = "hello"; // 哈希计算 + 冲突处理
// 看似O(log n)，实际更快
std::map<int, std::string> m;
m[42] = "hello"; // 红黑树插入，但常数小为什么会这样？因为哈希函数本身有开销，而且unordered_map的内存不连续，缓存命中率低。map虽然O(log n)，但数据量小时，log n也就几次比较操作。
避坑指南：我曾经用unordered_map存了500个键值对，结果比map慢了30%。后来一分析，哈希函数太复杂，而且冲突严重。换成map后，性能反而提升了。
四、避免不必要的拷贝：STL性能优化的核心
4.1 传引用，别传值
这是最基础但也最容易犯的错误。我见过有人这样写：
// 糟糕：每次调用都拷贝整个vector
void process(std::vector<int> v) {
// ...
}
// 好的：传常量引用
void process(const std::vector<int>& v) {
// ...
}如果vector里有10万个元素，传值意味着每次调用都要拷贝40万字节（假设int是4字节）。传引用只是拷贝一个指针（8字节）。
4.2 移动语义：C++11带来的礼物
移动语义能避免深拷贝。我习惯这样用：
std::vector<int> createData() {
std::vector<int> v;
v.reserve(100000);
// 填充数据...
return v; // 移动语义，不会拷贝
}
// 调用方
std::vector<int> data = createData(); // 零拷贝注意：要确保你的类型支持移动语义。自定义类型记得实现移动构造函数和移动赋值运算符。
4.3 emplace_back vs push_back
emplace_back直接在容器内构造对象，避免了临时对象的创建和拷贝。看个例子：
struct BigObject {
BigObject(int a, int b, int c) : x(a), y(b), z(c) {}
int x, y, z;
};
std::vector<BigObject> v;
// push_back：先构造临时对象，再拷贝到容器
v.push_back(BigObject(1, 2, 3));
// emplace_back：直接在容器内构造
v.emplace_back(1, 2, 3); // 少一次拷贝对于简单类型（如int），两者没区别。但对于复杂对象，emplace_back能省掉一次构造和一次析构。
我的习惯：所有插入操作都用emplace_back/emplace，除非你需要显式控制临时对象的生命周期。
五、知识体系总览
下面这张图总结了STL性能优化的核心要点，我建议你收藏起来，写代码前看一眼：
六、实战建议
最后，我总结几条实战经验：
- 先测量，再优化。别凭感觉优化。用perf或Valgrind看看热点在哪。
- 默认用vector。除非你有明确理由用其他容器。
- reserve是免费的午餐。只要你知道大概数据量，就加上。
- emplace_back代替push_back。养成习惯就好。
- 传引用，别传值。这条能解决80%的性能问题。
嗯，STL性能优化就聊到这儿。记住，没有银弹，只有理解原理才能做出正确选择。