c++ - 在 O(1) 上运行的内存池

Question

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

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

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

编辑:图片明白我的意思

Answer 1

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

预分配足够的内存。将它分成 block ，每个对象一个。保留一个空闲 block 列表。当您分配一个新对象时，从空闲 block 列表的顶部选择一个 block 。当你释放一个对象时，将它的 block 追加到空闲 block 列表中。这两个操作都是 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;
}

获取新 block 进行分配:

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

释放后返回 block :

free_chunks.push_back(c);