c++ - C ++堆组织 - 哪种数据结构？

Question

C++ 有两种主要的内存类型：堆和栈。有了堆栈，我什么都清楚了，但是关于堆还有一个问题：

堆内存是如何组织的？我阅读了堆数据结构，但这似乎不适用于堆，因为在 C++ 中我可以访问堆中的任何数据，而不仅仅是最小值或最大值。

所以我的问题是：堆内存在 C++ 中是如何组织的？当我们阅读“在堆上分配”时，我们想到了什么内存组织？

Answer 1

一个常见的（虽然肯定不是唯一的）空闲存储实现是空闲内存块的链接列表（即，当前未使用的块）。堆管理器通常会从操作系统分配大块内存（例如，一次 1 兆字节），然后将这些块分成几块以供您的代码在使用时使用new等。当您使用delete时，您退出使用的内存块将作为一个节点添加到该链表上。

关于如何使用这些空闲块有多种策略。三种常见的方法是最佳拟合、最差拟合和首次拟合。

在最合适的情况下，您尝试找到一个大小最接近所需分配的空闲块。如果它大于要求（通常在四舍五入分配大小之后），则将其分成两部分：一个返回分配，一个新的（较小的）空闲块放回列表中以满足其他分配请求。尽管这似乎是一个不错的策略，但它通常会出现问题。问题是，当您找到最接近的匹配时，剩余的块通常太小而没有多大用处。不久之后，你会得到大量的小块可用空间，这些都对任何事情都没有好处。

最差匹配通过在空闲块中找到最差的匹配来对抗这种情况——IOW，最大的可用空间块。当它拆分该块时，剩下的将尽可能大，从而最大限度地提高它对其他分配有用的机会。

第一个拳头只是遍历空闲块列表，并且（正如您从名称中猜到的）使用第一个足够大以满足要求的块。

不少人还从搜索精确匹配开始，并优先使用它而不是拆分块。

相当多的人还保留（例如）许多用于不同分配大小的单独链表，以尽量减少对正确大小块的搜索。

在相当多的情况下，管理器也有一些代码来遍历空闲块列表，以找到彼此相邻的任何块。如果找到它们，它将把两个小块连接成一个更大的块。free有时，当您/delete一个块时，这是正确的。更常见的是，它是懒惰地完成的，以避免在/如果您使用很多相同大小的块时加入然后重新分割块（这很常见）。

在处理大量相同大小的项目（尤其是小项目）时，另一种常见的可能性是块数组，其中有一个位集来指定哪些是空闲的或正在使用的。在这种情况下，您通常会跟踪找到最后一个空闲块的位集中的索引。当需要一个块时，只需从最后一个索引向前搜索，直到找到位集表示该块空闲的下一个索引。

Answer 2

堆有两个主要含义，有两个不同的概念：

1. 用于排列数据的数据结构，树。
2. 可用内存池。它通过分配/释放可用内存块来管理内存。

内存管理中堆的介绍：

堆是另一个动态内存区域，由 malloc/free 及其变体分配/释放....

Answer 3

这里的堆并不是堆数据结构的意思。该内存被称为堆内存，其中存储了全局静态变量。此外，当我们动态分配内存时，它是在堆内存中分配的。

Answer 4

当您阅读“在堆上分配”时，这通常是 C++ 的“动态存储持续时间”的特定于实现的实现。这意味着您曾经new分配过内存，并且有一个指向它的指针，您现在必须跟踪它直到您delete（或delete[]）它。

至于它是如何组织的，没有固定的方法。在某一时刻，如果内存服务，“堆”实际上是一个最小堆（按块大小组织）。不过，这是特定于实现的，不一定要那样。任何数据结构都可以，在给定的情况下，有些数据结构比其他数据结构更好。