我应该使用什么C++ STL类来减少由大量小分配引起的碎片？

Question

我的C++类随着时间的推移构建了一个树结构.树中的每个节点当前都在构造上分配(使用new).节点类仅使用几个字节的内存.随着树的增长,可能有10万个节点; 除了理论上的最大值2 ^ 33之外,在构造树时不知道最大节点数.我通过指针引用树结构中的节点.所有节点在销毁树时都会被释放,然后才会被解除分配.

我正在使用标准库容器或内存分配器/池,我可以使用它来分配和存储我的树类中的节点,以减少内存碎片和内存分配开销.我想避免编写自定义分配器.容器应具有以下两个属性:

1. 分配的对象不会在内存中移动,因此可以安全地通过指针引用.
2. 该类为大块对象分配内存,从而减少内存碎片.请注意,我不要求整个容器在内存中是连续的.

我不需要容器的迭代器或查找功能,因为我的树结构存储指针.什么标准库类将为我提供此功能,并给我最低的内存开销？

Answer 1

由于您要求专门提供标准容器,std::deque因此根据您的要求,这是最有前途的选择.只要您只添加元素,就不会重新定位现有元素,并且引用/指针(但不是迭代器)仍然有效.删除元素时,您可能需要留下空白或交换元素以使用最后一个元素删除.

std::vector是不是稳定的,并且std::list,std::forward_list以及所有的关联容器是支离破碎的.

看看Boost.Container,您还有其他选择,但需要进行其他权衡:

• boost::flat_map提供连续的存储(如std::vector),但有稳定性问题
• boost::stable_vector 以连续性为代价提供元件稳定性.

或者,您可以查看池分配器(如Boost.Pool).它们提供低碎片和快速分配,并且它前面的容器仍然可以像普通容器一样使用.

Answer 2

当您通过指针引用树结构中的节点（因此，不应重新分配它们）并希望减少内存碎片时，我建议对Node对象使用内存池。

Boost.Pool库可能适合您的需求。

例子：

class Tree
{
    Tree() : nodesPool_(new boost::object_pool<Node>()) {}

    void CreateNode(nodeArg1, nodeArg2, ...)
    {
        Node * node = nodesPool_->construct(nodeArg1, nodeArg2, ...);
        ...
    }

    std::unique_ptr<boost::object_pool<Node>> nodesPool_;
};