3

有没有办法设计一个可以在 O(1) 中分配和释放内存的 C++ 内存池（仅适用于特定类）？

假设我有 T 类，我想在需要时只分配 100*sizeof(T) 的块。但是，我该如何处理在块中删除特定对象时发生的碎片？我可以为每个插槽设置一个布尔值来判断插槽是否被占用，但是我需要一个算法来给我下一个空闲插槽。

是否有任何标准方法可以在 O(1) 中实现这一点？我想这是一个相当普遍的事情

编辑：图片看看我的意思 图片

4

3 回答 3

4

此解决方案正在使用额外的内存（这可能是您想要的也可能不是您想要的），如果您尝试连续两次释放一个块，您也会遇到问题。

预分配足够的内存。将其分成块，每个对象一个。保留一个空闲块的列表。当你分配一个新对象时，从空闲块列表的顶部选择一个块。当您释放一个对象时，将其块附加到空闲块列表中。这两个操作都是 O(1)。

它看起来像这样：

在里面：

char* mem = new char[CHUNK_SIZE * OBJ_COUNT];
std::list<char*> free_chunks;
for (char* c = mem, int i = 0; i < OBJ_COUNT; ++i)
{
   free_chunks.push_back(c);
   c += CHUNK_SIZE;
}

获取一个新的块进行分配：

   if(free_chunks.size() > 0)
   {
    char* c = free_chunks.back();
    free_chunks.pop_back();
    return c;
   }
   else{ // Error, not enough memory... }

释放后返回一个块：

free_chunks.push_back(c);
于 2012-11-09T20:11:54.523 回答
1

您只有针对一般内存分配问题的碎片，其中请求任意长度的块。这里的问题是给定这个内存布局：

@@@@@@---@--@-@@@@

（其中@表示正在使用和-表示免费）

尽管总共有 6 个空闲块，但您不能分配 4 个连续块。所以你必须增加治理空间的总量（如果可能的话）。同样在这种一般情况下，决定选择哪个地址并非易事，并且有几种影响碎片程度的策略（第一次拟合、最差拟合等）。

在您的情况下，问题要容易得多，因为您知道要分配的区域将始终与某个整数的大小完全相同k（例如k = sizeof(T)）。这意味着您将始终拥有完美贴合的块，您可以随意组织这些块。只需像处理链表一样处理可用空间，并始终使用链表中的第一项来响应内存分配请求。

@@@---@@@------@@@@@@@@@---@@@ (k=3)

现在，如果您想在大块中分配以摊销分配，您可以保留一个额外的计数器来记录一个特定块中使用了多少个插槽，以便在该块为空时释放该块（如果您想缩小插槽库！ ）。

如果您坚持总是从最常用的块中分配新的内存块，您可以通过使用指示哪个块最满的附加列表来做到这一点。由于您始终只能将已使用插槽的数量更改为 1，因此您可以将该列表排序为O(1)，只需交换相邻节点即可。

于 2012-11-09T20:38:29.813 回答
1

您可以使用 O(1) 对象检索来实现简单的对象池。但是您的对象需要具有指向下一个对象的内部指针。在池的构造函数内部进行了一些预先计算：

pool.reserve(capacity); //std::vector<Object*>
for (int i = 0; i < capacity; ++i) {
    pool.push_back(new Object());
}
for (int i = 0; i < capacity-1; ++i) {
    pool[i]->setNext(pool[i+1].get());
}
first_available = pool[0].get(); //variable where you store first free object 
pool[capacity-1]->setNext(NULL);

那么getObject方法是：

getObject* getObject()
{
    getObject* obj = first_available;
    first_available = first_available->getNext();
    return obj;
}

void returnObject(Object* obj)
{
    obj->setNext(first_available);
    first_available = obj;
}

希望能帮助到你。

于 2012-11-09T20:13:21.360 回答