C++ 有两种主要的内存类型:堆和栈。使用堆栈，一切对我来说都很清楚，但关于堆，仍然存在一个问题:
堆内存是如何组织的？我读到了 heap data structure ，但这似乎不适用于堆，因为在 C++ 中我可以访问堆中的任何数据，而不仅仅是最小值或最大值。
所以我的问题是:堆内存在 C++ 中是如何组织的？当我们读到“在堆上分配”时，我们想到的是什么内存组织？
最佳答案
空闲存储的一个常见(当然不是唯一)实现是空闲内存块(即当前未使用的 block )的链表。堆管理器通常会从操作系统分配大块内存(例如，一次 1 兆字节)，然后将这些 block 分成几 block ，供您在使用 new 等时使用。当您使用 delete 时，您退出使用的内存块将作为一个节点添加到该链表上。
对于如何使用这些空闲 block ，有多种策略。最常见的三种是最佳拟合、最差拟合和首次拟合。
在最佳匹配中，您尝试找到大小最接近所需分配的空闲 block 。如果它大于要求(通常在四舍五入分配大小之后)，则将其分成两部分:一个返回分配，一个新的(较小的)空闲 block 放回列表中以满足其他分配请求。尽管这看起来是一个不错的策略，但它通常会出现问题。问题是，当您找到最接近的拟合时，剩下的 block 通常太小而无用。短时间后，您最终会得到大量微小的可用空间 block ，其中没有一个对任何事情都有好处。
最差匹配通过在空闲 block 中找到最差匹配来解决这个问题——IOW，最大的空闲空间 block 。当它拆分该 block 时，剩下的将尽可能大，从而最大限度地提高它对其他分配有用的机会。
第一个拳头只是遍历空闲 block 列表，并且(正如您从名称中猜到的那样)使用第一个足够大以满足要求的 block 。
不少人也从搜索精确匹配开始，并优先使用它来分割 block 。
相当多的人还保留(例如)许多用于不同分配大小的单独链表，以最大限度地减少对正确大小的 block 的搜索。
在很多情况下，管理器也有一些代码来遍历空闲 block 列表，以找到彼此相邻的任何 block 。如果找到它们，它将把两个小块合并为一个更大的 block 。有时这会在您释放/删除 block 时正确完成。更多时候，它是懒惰地完成的，以避免在/如果您使用大量相同大小的 block (这很常见)时加入然后重新拆分块。
在处理大量相同大小的项目(尤其是小项目)时，另一种常见的可能性是 block 数组，其中有一个位集来指定哪些是空闲的或正在使用的。在这种情况下，您通常会跟踪找到最后一个空闲 block 的位集中的索引。当需要一个 block 时，只需从最后一个索引向前搜索，直到找到位集表示该 block 空闲的下一个索引。
关于C++堆组织——哪种数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15314475/