如何根据STL列表中元素的数量来分配内存？

Question

可以选择为STL容器提供自定义分配器。但是，我找不到一种实现，可以在内存池空间耗尽时增加内存池的块大小。STL分配器如何读取列表容器的大小并自增长块大小？

例如，块大小从1、2、4开始，依此类推，然后当容器中有1、3、7个节点时，块大小在下一次插入后立即增长。

Answer 1

标准容器使用提供的分配器(调用其成员函数)来分配它们所需的内存。相反的情况不会发生-根据标准的规定，在分配器接口中没有任何东西允许它获得关于哪个容器正在使用它的信息。这意味着没有自定义分配器-只要它具有标准中所要求的相同接口-就有办法查询容器大小。

要做你想做的事情，你需要一个特殊用途的分配器，它具有不同于标准分配器的接口，以及一个知道如何与特殊用途分配器通信的自定义容器(例如std::list的替代品)。试图让您的自定义分配器与标准容器一起工作，或者让您的自定义容器与标准分配器一起工作，将不会很好地工作-接口将是不兼容的。

此外，您描述的行为(每次分配加倍)是特定于您的标准库实现的。尽管这种分配策略比较常见，但标准并不要求这样做。允许其他实现使用不同的分配策略。

最后，计算/估计容器大小的上限可能会更容易，用它来计算程序需要运行多少内存，并至少安装这个内存量。

Answer 2

分配器通常不依赖于它的客户端容器类型--这将是一个循环依赖。这个循环需要通过某种不完整的类接口或类型擦除来解决。

例如，使用不完整的类指针：

struct my_pool;

template< typename t >
struct my_allocator {
    my_pool * pool;
    // allocate, deallocate, etc.
};

struct my_pool {
    std::list< foo, my_allocator< foo > > const * client;
};

std::list< foo, my_allocator< foo > > things;
my_pool.client = & things;

在这种情况下，my_pool依赖于std::list<…, my_allocator>依赖于my_allocator<std::__list_node>依赖于my_pool，但是这个周期是可以的，因为有几个依赖项仅仅是指针。

例如，使用std::function类型擦除：

struct my_pool {
    std::function< std::size_t() > client_size;
};

std::list< foo, my_allocator< foo > > things;
my_pool.client_size = [&]{ return things.size(); };

这个池甚至不需要知道容器类型。

但是，无论是哪种情况，这似乎都不是特别好的设计。池不能被其他容器共享，至少不能平等地共享。