为什么我们使用堆来存储内存？
如果这听起来像是一个幼儿园问题，那么请原谅我）;但是，在C ++中，堆被用于内存分配，因为......至少在80年代以前。 它是这个工作的最佳算法，还是我们刚刚陷入困境（就像javascript所发生的那样）？ 是否所有（非嵌入式）操作系统都使用堆来存储内存？
编辑：那么，什么结构/ 使用的算法。 它如何（如果）与堆算法有关？
没有必要与“堆栈”分配（它遍布整个网络）进行比较，或者讨论C ++语义 - 当前内存堆的一个tl; dr？
这听起来像是你把一堆堆与“堆”混淆了。 堆数据结构很少用于动态内存分配。
现在，重新：为什么动态内存分配？ 有时你不知道你需要多少内存，也不想仅仅分配一个巨大的缓冲区以防万一。 在堆上分配允许您在运行时必须更改的存储空间量。
在内存分配的情况下，堆不是数据结构或算法。 它更符合英语定义，它在某些地方本质上是一个非结构化的东西。
从历史上看，早期的计算机系统只有很少的内存，而早期的操作系统只能管理少量的内存。 像64K（即千字节，不是兆字节或千兆字节）的数量在早期实际上是大量的内存，而早期的操作系统的设计能够支持不超过640K的程序运行。 这是全部内存。
当一些计算机拥有两个或更多独立的物理内存芯片库时，这实际上是一个创新。 其中之一用于在内存中运行程序，其他程序用于存储程序所需的数据，其方式可以比从磁盘读取数据更快地进行访问。 这两个内存区域分别被称为栈和堆。 需要使用特殊设备驱动程序访问堆。 可用的堆内存量通常（并非总是）比堆栈内存大得多。
实际上，在C和C ++的早期实现中，静态和自动变量通常使用堆栈内存，动态分配内存（ malloc()等）使用堆。 即使这个区别现在在很大程度上是学术性的（例如，堆和堆栈限制被设置为逻辑配额，而不是反映物理上可用的存储区），名称仍然存在。
因此，在现代C和C ++中，“堆”的正确术语是“动态分配内存”。 动态内存分配（例如像malloc()这样的malloc()不一定会使用被称为“堆”的任何内存区域（尽管显然主机系统必须使用某些数据结构来跟踪内存分配和释放）。
在这种情况下，所讨论的“堆”与被称为堆的数据结构并不相同。
通常“堆”是指由malloc / realloc / free管理的malloc 。 这些通常在合理编写的C ++中很少使用（如果有的话）。
对于C ++中的动态分配，更经常使用new和delete （至少是间接的，比如通过容器使用的std::allocator<T> ）。 有些人有时也将此称为“堆”，但试图更加合适的人往往将其称为“自由存储”（这是标准中使用的措词）。
然而，不管怎样，尽管涉及实际的堆很少（如果有的话）。 既没有规定（或意图指代）用于管理存储器的数据结构。
对于它的价值来说，与我看到用于管理内存的实际堆栈最接近的是使用“伙伴系统”分配器（但我在实际使用中看到的这些内存相对较少，尽管Knuth进入了相当长的一段时间关于他们的细节。
至于使用什么结构，一个非常常见的结构就是块的链表。 每个块至少会记录自己的大小。
常用的基本算法是最佳拟合，最差拟合和首次拟合。
在所有情况下，您通常都会制定分组分块政策。 也就是说，如果一个分配要求的大小小于所选择的块的大小，你可以选择如何将块保留原样，并给用户一点额外的内存，否则将该块分成两块：一块用于以满足分配，另一个可以回到免费清单。 在大多数情况下，您尽量避免创建小块，因此除非“遗留”部分大于特定大小，否则您只需保留原始块。
如果他们对事物没有多少关注，大多数人的第一本能就是使用最合适的。 最合适的问题是，当你分割一个块时，它会产生最小的剩余块，所以你往往会得到很多不能满足任何分配的小块。 如果你确实使用它，你通常会设置一个相当高的阈值，在那里你将保持一个块完整无损，而不是分割它。
最糟糕的情况是试图抵消这一点。 尽管可能会分割最大的块，但它往往留下最大的剩余块，因此它最有可能被使用。
还有混合，如精确适应，最合适。 也就是说，不是总是使用最大的块，而是首先寻找一个恰好符合（或足够接近以至于不会分割该块）的块，并且只有在失败时才会分割最大的块。
如果您按照某种顺序保留空闲块，还可以使用某种或某些树的存储块进行明显修改，以便可以在大致对数时间内而非线性时间内找到块。
链接地址: http://www.djcxy.com/p/82503.html