如何在不使指针无效的情况下生长缓冲液？

题

_{^{术语“池”和“缓冲区”可以在这里互换使用。}}
假设我有一个我想在程序开始时分配的池，以至于不总是打电话 new 每时每刻。
现在，我不想人工限制自己的泳池大小，但是如果我重新分配一个更大的游泳池，那么所有的指针都会被无效，这当然不是很酷。

我想到的一种方式是“分页”，又名

const int NUM_PAGES = 5;
char* pool[NUM_PAGES];

并分配一个新页面，而不是仅重新分配一个页面。这将使所有指针保持有效，但使分类池的管理更加困难。另外，我将自己限制在页面数量上，因此再次限于池的大小。

另一种方法是将我的分配函数从指针中进行映射，返回到指针到真实的内存空间。这将使所有旧的指针保持有效，但会采用更多的内存，我需要编写一个明智的指针，以从我的分配功能中返回，该函数可以完成映射。

哪些其他可能的方法可以实现我想要的东西？我在上述示例实现中错过了什么（DIS）？

解决方案

您在说的是让我想起的事情 std::deque. 。我不确定您是否可以使用 std::deque 如下，或者您只需要使用其基本设计即可实现某种分配器。

其他提示

扩展您的“池”概念，如果将页面存储为链接列表，该怎么办？

要从池中分配新数据，您只需要访问顶部的“页面”，该数据将位于列表的头脑中，因此是O（1）。如果您需要增加游泳池的总尺寸，请分配一个新页面，然后将其推入列表的头部，也将其推入O（1）。

我基本上将同样的想法用于合并的分配器，但也有一个最近交易的项目的“免费列表” ...

编辑：根据您的评论，如果您还想使用已交易的数据，则还可以存储一个免费列表，也可能是链接列表。因此，当您处理数据时，将指针和大小标记将其推入免费列表。当您从池中分配数据时，您首先检查是否可以使用免费列表上的任何项目，如果不是从池中分配。

标准内存漫画通常已经做过这样的事情，因此这种方法不会总是会更好。具体来说，当分配的项目大小相同时，我通常只使用这种类型的自定义分配器（因此，免费列表的遍历为O（1）！）。 STD ::列表的自定义分配器将是一个示例。

希望这可以帮助。

考虑使用提升池

当然，一个问题是为什么要这么困扰自己？

你说你希望避免 new 开销，但是为什么不选择更好的实施 new ? tcmalloc 和 jemalloc 通常是多线程应用程序的非常好的竞争者。

实际上，您试图创建的内容与编写自定义化非常相似 malloc / new 执行。因此，如果您真的不想从那些人的见解中使用可靠的实施，您将受益。

我的个人兴趣倾向于Bibop策略（大书页）来抵抗分裂。这个想法是每个分配尺寸的专用池，因此简单的自由列表（与分配交错）足够（不需要合并）。通常，只要要求的大小小于页面大小（我已经看到4KB），并且单独分配更大的内容（在几页中）。丢弃的页面被回收。

我的主要兴趣是，Bibop可以容易地维护间隔树地址范围 - >页面标头，从而从（可能是）内部元素（例如属性）的地址确定对象的全尺寸，这很有用用于垃圾收集（参考下一步）。

对于多线程分配， tcmalloc 和 jemalloc 使用两种不同的方法：

jemalloc 使用每线程池：良好，固定数量的线程 /线程池，但使创建线程的过程更加昂贵
tcmalloc 使用一个带有无锁技术的全局多线程池，并尝试通过将线程查找新池来限制可用的池上的线程，如果它使用的是“锁定”（而不是而不是等待）并让每个线程在线程局部变量中放置最后一个使用的池。因此，线程是轻量级的，但是如果池的数量太低WRT，则可能存在一些争议。

一些想法：

当你有一个 std::vector<T*>, ，添加元素并触发调整大小无效的引用/指针/迭代器中的容器，而不是直接解决尖头对象的引用/指针。因此，根据您真正尝试使用这些参考/指针/迭代器来解决问题，间接方向可能会解决您的问题。
在具有虚拟内存和较大地址空间的系统中，您可以进行大量分配，而无需实际从物理内存资源分配的页面，直到将其写入为止。最后， 在这样的系统上 您可以为有史以来设置超过有史以来的能力 vector 最初没有感觉到您浪费了任何有价值的东西。
其他容器 - std::map<> 和 std::list<> - 不要在添加新元素时移动其现有元素，因此迭代器/指针/引用仍然有效。

许可以下： CC-BY-SA 和归因