C++ 缓存友好的数据结构：让你的代码像猎豹一样奔跑
嘿，各位码农朋友们！今天咱们不聊高深莫测的算法，也不谈花里胡哨的设计模式，咱们来聊点实在的——如何让你的 C++ 代码跑得更快，就像一头猎豹追逐羚羊一样迅猛！秘诀就在于：缓存友好的数据结构。
等等，缓存？那不是浏览器用来存网页图片的东西吗？
没错，但这里的缓存指的是 CPU 缓存，它就像 CPU 的贴身小棉袄，能以极快的速度提供数据。CPU 访问内存的速度可比访问缓存慢多了，简直就像蜗牛爬树和火箭发射的区别。所以，我们要做的就是尽量让 CPU 从缓存里拿到数据，而不是慢吞吞地去内存里翻箱倒柜。
想象一下，你是一位图书管理员，要帮读者找书。
- 情况一：书架上的书按照主题分类，同一主题的书都放在一起。读者要借同一主题的书，你只需要在一个区域找，效率杠杠的！
- 情况二：书架上的书乱七八糟，东一本西一本。读者要借同一主题的书，你得满屋子跑，累得半死！
这两种情况的区别，就类似于缓存友好和缓存不友好的数据结构的区别。
什么是缓存友好？
简单来说，就是你的数据在内存里排列得比较紧凑，而且访问模式也比较有规律，这样 CPU 就能更容易地把数据加载到缓存里，提高访问速度。
为什么缓存友好这么重要？
因为 CPU 实在是太快了！CPU 的速度远超内存的访问速度。如果 CPU 大部分时间都在等待内存提供数据，那它的性能就大打折扣了，简直就是英雄无用武之地。
接下来，咱们就来聊聊如何在 C++ 中打造缓存友好的数据结构：
1. 数组：最简单的缓存友好结构
数组是 C++ 中最基本的数据结构，也是最容易实现缓存友好的。为什么呢？因为数组的元素在内存中是连续存储的，就像一排整齐排列的士兵。
int arr[1000]; // 声明一个包含 1000 个整数的数组当你访问 arr[0] 后，CPU 很可能会把 arr[1], arr[2] 等等也一起加载到缓存里。如果你接下来要访问这些相邻的元素，CPU 就能直接从缓存里拿到，速度飞快！
使用数组的技巧：
- 避免跳跃式访问： 尽量按照顺序访问数组元素，比如用循环遍历。避免像
arr[0],arr[500],arr[999]这样跳跃式访问，这样会导致缓存失效，降低性能。 -
考虑多维数组的存储顺序： C++ 中多维数组是按行存储的。这意味着
arr[0][0],arr[0][1],arr[0][2]是连续存储的，而arr[0][0],arr[1][0],arr[2][0]则是跳跃存储的。因此，在访问多维数组时，尽量按照行优先的顺序访问，例如：int arr[100][100]; for (int i = 0; i < 100; ++i) { for (int j = 0; j < 100; ++j) { arr[i][j] = i + j; // 行优先访问 } }
2. 结构体：小心“内存空洞”！
结构体可以将不同类型的数据组合在一起，方便我们组织复杂的数据。但是，结构体也可能存在“内存空洞”，导致缓存效率降低。
什么是“内存空洞”？这是因为编译器为了保证数据对齐，可能会在结构体中插入一些额外的空间。
struct MyStruct {
char a; // 1 字节
int b; // 4 字节
char c; // 1 字节
};你可能觉得 MyStruct 应该占用 1 + 4 + 1 = 6 个字节，但实际上它可能占用 8 个字节。这是因为编译器为了让 int b 能够按照 4 字节对齐，可能会在 char a 后面插入 3 个字节的空洞。同样，char c 后面也可能插入空洞，最终导致结构体占用更多的内存空间。
如何避免“内存空洞”？
-
调整成员变量的顺序： 将相同类型的成员变量放在一起，并将占用空间大的成员变量放在前面，可以减少内存空洞。
struct MyStruct { int b; // 4 字节 char a; // 1 字节 char c; // 1 字节 };这样调整后，
MyStruct占用的空间可能会减少到 6 个字节。 - 使用
#pragma pack指令： 可以使用#pragma pack指令来控制结构体的对齐方式。但是，这种方式可能会影响程序的兼容性，需要谨慎使用。
3. 向量（std::vector）：动态数组的优化选择
std::vector 是 C++ 标准库提供的动态数组，它可以在运行时动态调整大小。std::vector 也是一种缓存友好的数据结构，因为它在内存中也是连续存储的。
std::vector<int> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);使用 std::vector 的技巧：
-
提前预留空间： 如果你知道
std::vector大概需要存储多少个元素，可以使用reserve()函数提前预留空间。这样可以避免在插入元素时频繁地重新分配内存，提高性能。std::vector<int> vec; vec.reserve(1000); // 预留 1000 个元素的空间 for (int i = 0; i < 1000; ++i) { vec.push_back(i); } - 使用
emplace_back()替代push_back()：emplace_back()可以直接在std::vector的末尾构造元素，避免了先构造临时对象再拷贝的开销，提高性能。尤其是在存储复杂对象时，emplace_back()的优势更加明显。
4. 链表（std::list, std::forward_list）：缓存的噩梦？
链表是一种动态的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的优点是可以方便地插入和删除元素，但是它的缺点是：缓存不友好！
为什么链表缓存不友好？因为链表的节点在内存中是随机分布的，而不是连续存储的。当你访问一个节点后，CPU 无法预测你接下来要访问哪个节点，因此无法有效地利用缓存。
所以，如果你的程序对性能要求很高，而且需要频繁地访问链表中的元素，那么最好避免使用链表，选择其他缓存友好的数据结构，比如 std::vector。
5. 树（Tree）：一种复杂的平衡
树结构，例如二叉树、平衡树（如红黑树、AVL树）等，在查找、插入和删除操作上具有一定的优势。然而，它们的缓存友好性取决于具体的实现和访问模式。
- 二叉树： 普通的二叉树节点通常在堆上动态分配，导致节点在内存中分散，缓存效率较低。
- 平衡树： 平衡树通过保持树的平衡来保证查找效率，但这并不一定能提高缓存友好性。虽然节点间的逻辑关系明确，但物理存储位置可能仍然分散。
提升树结构缓存友好性的方法：
- 数据局部性优先： 在构建树时，尽量将相关的节点存储在相邻的内存区域。例如，在插入节点时，优先选择靠近父节点的空闲内存块。
- 使用节点池： 预先分配一块连续的内存区域作为节点池，所有节点都从这个池中分配。这样可以提高节点在内存中的局部性。
- 尝试数组实现： 对于某些特殊的树结构（如完全二叉树），可以使用数组来存储节点，从而获得更好的缓存友好性。
总结：缓存友好的黄金法则
- 连续存储： 尽量让数据在内存中连续存储，这样 CPU 才能更好地利用缓存。
- 顺序访问： 尽量按照顺序访问数据，避免跳跃式访问，减少缓存失效。
- 减少内存空洞： 合理地组织结构体成员，避免出现过多的内存空洞，提高内存利用率。
- 选择合适的数据结构： 根据实际需求选择合适的数据结构，不要盲目追求算法复杂度，而忽略了缓存的影响。
最后，一些额外的建议：
- 使用性能分析工具： 使用性能分析工具（如 gprof, valgrind）来分析程序的性能瓶颈，找到需要优化的地方。
- 进行基准测试： 在优化代码后，进行基准测试，验证优化效果。
- 不断学习和实践： 缓存优化是一个持续学习和实践的过程，只有不断地学习和尝试，才能掌握其中的奥秘。
希望这篇文章能帮助你更好地理解缓存友好的数据结构，并应用到你的 C++ 代码中，让你的代码像猎豹一样奔跑！记住，好的代码不仅要能完成任务，还要跑得飞快！加油，各位码农朋友们！让我们一起写出更高效、更优雅的 C++ 代码！