Boost Pool free效率O（n）or O（1）

Question

最近我發現了Boos Pool庫，並開始將它調整爲我的代碼。圖書館提到它缺少的一件事是基類，它將覆蓋任何類的新/刪除操作符，並使用該池進行內存管理。我寫了自己的實現和一些元模板編程，實際上它看起來非常體面（通過簡單地從基類派生，支持大小在1到1024個字節之間的任何類）

我提到那些因爲目前爲止這真的很酷，令人興奮，然後我發現這個post from Boost mailing list。看起來有些人確實錘擊了Pool庫，特別指出他們所說的free（）方法在O（n）時間運行的低效性。我通過代碼加強，並發現這是方法的實現：

void free(void * const chunk) 
{ 
    nextof(chunk) = first; 
    first = chunk; 
} 

對我來說，這看起來像O（1），我真的不明白他們在說什麼的低效率。我注意到的一件事是，如果你使用singleton_pool的多個實例（即不同的標籤和/或分配大小），它們都共享相同的互斥量（關鍵部分更精確），這可以進行一些優化。但是如果你使用常規的堆操作，他們會使用相同的同步形式。

那麼沒有人認爲池庫效率低下和過時？

Answer 1

這自由肯定對我來說看起來不變。也許帖子的作者指的是ordered_free，其中有這樣實現：

void ordered_free(void * const chunk) 
{ 
    // This (slower) implementation of 'free' places the memory 
    // back in the list in its proper order. 

    // Find where "chunk" goes in the free list 
    void * const loc = find_prev(chunk); 

    // Place either at beginning or in middle/end 
    if (loc == 0) 
    (free)(chunk); 
    else 
    { 
    nextof(chunk) = nextof(loc); 
    nextof(loc) = chunk; 
    } 
} 

哪裏find_prev如下

template <typename SizeType> 
void * simple_segregated_storage<SizeType>::find_prev(void * const ptr) 
{ 
    // Handle border case 
    if (first == 0 || std::greater<void *>()(first, ptr)) 
    return 0; 

    void * iter = first; 
    while (true) 
    { 
    // if we're about to hit the end or 
    // if we've found where "ptr" goes 
    if (nextof(iter) == 0 || std::greater<void *>()(nextof(iter), ptr)) 
     return iter; 

    iter = nextof(iter); 
    } 
}