boost :: pool <> :: malloc和boost :: pool <> :: ordered_malloc有什么区别，什么时候应该使用boost :: pool <> :: ordered_malloc？

Question

我正在使用boost.pool，但我不知道何时使用boost::pool<>::malloc和boost::pool<>::ordered_malloc？

所以，

1. 什么的boost::pool<>::malloc和boost::pool<>::ordered_malloc区别？

2. 什么时候应该使用boost::pool<>::ordered_malloc？

Answer 1

首先，我们应该了解Boost池库背后的基本思想是：simple_segregated_storage，它类似于一个单向链表，并负责划分内存块成固定大小的块：

内存池保留一个空闲的内存块列表。所以我们提到了块和块：内存池使用new或malloc来分配一个内存块并将它分成许多具有相同大小的内存块。
假设地址对齐了8,4个字节用于存储下一个块的地址，所以一个内存块（8字节* 32块）如下（内存地址仅用于说明问题，而不是真实的） ：

现在，假设用户分配8个字节存储器的两倍，因此在块：[0xDD00,0xDD08），[0xDD08,0xDD10）被使用。一段时间后，用户释放内存在[0xDD00,0xDD08），所以这个块将回到空闲列表。现在，块是这样的：

此后用户在[0xDD08,0xDD10释放内存），该块放回列表最简单的办法是更新first指向它，一定时间复杂。该simple_segregated_storage<T>::free()是这样做的正是：

void free BOOST_PREVENT_MACRO_SUBSTITUTION(void * const chunk) 
{ //! Free a chunk. 
    //! \pre chunk was previously returned from a malloc() referring to the same free list. 
    //! \post !empty() 
    BOOST_POOL_VALIDATE_INTERNALS 
    nextof(chunk) = first; 
    first = chunk; 
    BOOST_POOL_VALIDATE_INTERNALS 
} 

之后，名单会是这样：

现在我们注意到块的列表中的地址，这些操作后，不会下令！ 如果我们希望在取消分配时保留顺序，请拨pool<>::ordered_free()而不是pool<>::free()将内存按照正确顺序放回列表中。现在我们已经知道什么是在内存池的顺序，让我们深入的boost::pool<>::malloc和boost::pool<>::ordered_malloc源代码：

void * malloc BOOST_PREVENT_MACRO_SUBSTITUTION() 
{ 
    if (!store().empty()) 
    return (store().malloc)(); 
    return malloc_need_resize(); 
} 

void * ordered_malloc() 
{ 
    if (!store().empty()) 
    return (store().malloc)(); 
    return ordered_malloc_need_resize(); 
} 

正如我们所看到的，他们只不同时存在内存列表中没有空闲块块。在这种情况下，它分配一个新的内存块，将其空闲列表合并到池的空闲列表中，这两种方法的区别在于boost::pool<>::ordered_malloc在合并空闲列表时保留了顺序。
以上是问题1。
那么，为什么顺序很重要？！看起来内存池可以和无序的块完美配合！
首先，如果我们想要找到一个连续的n个区块序列，那么有序的自由列表会让它更容易。其次，让我们来看看派生类的boost::pool：boost::object_pool，它提供了对object_pool对象的破坏不释放对象的自动销毁，而你也可以手动销毁对象，例如：

class X { … }; 

    void func() 
    { 
     boost::object_pool<X> alloc; 

     X* obj1 = alloc.construct(); 
     X* obj2 = alloc.construct(); 
     alloc.destroy(obj2); 
    } 

的上面的代码是可以的，没有内存泄漏或双重删除！ boost::object_pool如何做到这一点？让我们找到的boost::object_pool析构函数（我有升压1.48我的机器上）执行：

template <typename T, typename UserAllocator> 
object_pool<T, UserAllocator>::~object_pool() 
{ 
#ifndef BOOST_POOL_VALGRIND 
    // handle trivial case of invalid list. 
    if (!this->list.valid()) 
    return; 

    details::PODptr<size_type> iter = this->list; 
    details::PODptr<size_type> next = iter; 

    // Start 'freed_iter' at beginning of free list 
    void * freed_iter = this->first; 

    const size_type partition_size = this->alloc_size(); 

    do 
    { 
    // increment next 
    next = next.next(); 

    // delete all contained objects that aren't freed. 

    // Iterate 'i' through all chunks in the memory block. 
    for (char * i = iter.begin(); i != iter.end(); i += partition_size) 
    { 
     // If this chunk is free, 
     if (i == freed_iter) 
     { 
     // Increment freed_iter to point to next in free list. 
     freed_iter = nextof(freed_iter); 

     // Continue searching chunks in the memory block. 
     continue; 
     } 

     // This chunk is not free (allocated), so call its destructor, 
     static_cast<T *>(static_cast<void *>(i))->~T(); 
     // and continue searching chunks in the memory block. 
    } 

    // free storage. 
    (UserAllocator::free)(iter.begin()); 

    // increment iter. 
    iter = next; 
    } while (iter.valid()); 

    // Make the block list empty so that the inherited destructor doesn't try to 
    // free it again. 
    this->list.invalidate(); 
#else 
    // destruct all used elements: 
    for(std::set<void*>::iterator pos = this->used_list.begin(); pos != this->used_list.end(); ++pos) 
    { 
     static_cast<T*>(*pos)->~T(); 
    } 
    // base class will actually free the memory... 
#endif 
} 

它通过在内存块列表（list的boost::pool<>数据成员所有块，保存位置和从系统分配的所有内存块的大小）来查找其中的任何块是否也显示在空闲列表中，如果没有，则调用该对象的析构函数，然后释放该内存。所以它有点像两个集合，就像std::set_intersection()一样！如果列表已排序，那么执行该操作会快得多。其实在boost::object_pool<>，订单需要，公众的成员函数：boost::object_pool<>::malloc()和boost::object_pool<>::free()只是调用分别为boost::pool<>::ordered_malloc()和boost::pool<>::ordered_free()：

element_type * malloc BOOST_PREVENT_MACRO_SUBSTITUTION() 
{ //! Allocates memory that can hold one object of type ElementType. 
    //! 
    //! If out of memory, returns 0. 
    //! 
    //! Amortized O(1). 
    return static_cast<element_type *>(store().ordered_malloc()); 
} 
void free BOOST_PREVENT_MACRO_SUBSTITUTION(element_type * const chunk) 
{ //! De-Allocates memory that holds a chunk of type ElementType. 
    //! 
    //! Note that p may not be 0.\n 
    //! 
    //! Note that the destructor for p is not called. O(N). 
    store().ordered_free(chunk); 
} 

所以对于queston 2：你需要在大多数情况下使用boost::pool<>::ordered_malloc。