C++中的缓存友好型容器选择策略

很多 C++ 性能问题表面看像算法问题，实际上是容器选择问题。不同容器在大 O 复杂度上也许相近，但它们对 CPU 缓存、分支预测和内存局部性的影响差异极大。

最典型的对比是 vector 和 list。理论上 list 插入删除快，但现实中，大量遍历场景下 vector 往往远快于 list，因为它的内存连续。

示例：

#include
#include
#include

int main() {
std::vector v(100000, 1);
std::list l(100000, 1);

auto sum_v = std::accumulate(v.begin(), v.end(), 0);
auto sum_l = std::accumulate(l.begin(), l.end(), 0);
}

虽然二者时间复杂度一样，但 list 节点分散在堆上，遍历时缓存命中率明显更差。

另一个常被忽略的问题是 unordered_map 的桶分布与 rehash 成本。若元素数量可预估，应主动 reserve：

#include
#include

int main() {
std::unordered_map freq;
freq.reserve(10000);
}

这样可以减少扩容和重新哈希带来的抖动。

对于小规模、频繁查找的集合，有时排序 vector 加二分查找反而比 set 更划算：

#include
#include

int main() {
std::vector ids{1, 3, 5, 7, 9};
bool found = std::binary_search(ids.begin(), ids.end(), 5);
}

因为 vector 不仅节省节点指针开销，还具备更好的顺序访问局部性。

容器选择的实用原则通常是：

- 默认优先考虑 vector
- 需要哈希查找时考虑 unordered_map/unordered_set，并提前 reserve
- 除非确实需要稳定迭代器和频繁中间插删，否则谨慎使用 list
- 小数据集上不要迷信复杂容器

性能工程里，最值钱的优化往往不是更复杂的数据结构，而是更贴近硬件访问模式的容器选择。