c++ - 可遍历内存池的数据结构

Question

我正在用 C++ 实现一个内存池，具有以下限制:

• 分配的元素应该可以在线性时间内按照它们的内存地址遍历，以促进缓存重用。
• 需要能够释放元素(内存块)并将它们返回到内存池。

分配和释放在实时程序运行期间会频繁发生，因此需要尽快发生。

到目前为止，我已经使用两个链表作为 stub 实现了这个内存池，一个用于空闲，一个用于分配的元素。这行得通，但当然非常慢，因为每次释放或分配一个元素时，都需要将该元素从一个列表中删除并添加到另一个列表中，这是线性的。我希望速度更快。

我可以使用什么数据结构来使(取消)分配尽可能高效？我正在考虑使用红黑树(或类似的平衡 BST)来存储分配的元素，并且空闲元素的优先级队列。这将使分配和释放都是 O(log n)。

关于如何改进此设计的任何建议？我可以使用的其他数据结构？是否有可能通过恒定时间操作创建一个内存池(具有上述约束)？

编辑:我应该澄清一下，这些数据结构仅用于存储和访问内存地址，内存块本身已经分配并且是连续的。

Answer 1

由于我们正在处理具有固定大小内存块的内存池，因此可以按如下方式实现恒定时间操作，例如。 :

• 通过其在池中的索引来识别每个内存块(内存块的地址可以很容易地从该索引中导出 block_address = base_address + index * block_size，反之亦然)。
• 拥有元数据 的数据结构(以跟踪已分配和空闲的 block )。一个符合要求的是一个固定大小的数组，其中一个项目对应于每个内存块(由相同的索引标识)。该数组中嵌入了两个(双向)链表(一个用于分配的 block ，一个用于空闲 block )。由于这些链表不重叠，它们可以使用相同的 prev 和 next 指针。

这如何符合要求:

• 线性时间遍历:内存块可以通过它们的索引(在这种情况下作为元数据的一部分的空闲/分配标志可能很有用)或通过两个链接中的任何一个来遍历列表，取决于要求。迭代数组和链表是在线性时间内完成的。
• constant time allocation :分配内存块意味着从空闲列表中获取第一项，并将其移动到已分配列表中(例如末尾)。删除链表的第一项，并将一项附加到链表的末尾都是常量时间操作(假设保留指向链表开头和/或结尾的指针 - 使列表循环可以帮助) .然后返回 block 的索引/地址。
• constant time deallocation :释放内存块意味着通过其索引识别相应的元数据项，并将其从分配列表移动到空闲列表(例如末尾)。通过索引从数组中获取项目、从(双向)链表中删除给定项目以及将项目追加到链表末尾，这些都是常量时间操作。