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

Question

我的 C++ class 随着时间的推移构建树结构。树中的每个节点当前都是在构造时分配的（使用 new）。节点 class 仅使用几个字节的内存。随着树的增长，可能会有 100,000 个节点；除了理论最大值 2^33 之外，树的构造时不知道最大节点数。我通过指针引用树结构中的节点。所有节点都在树被破坏时被释放，并且只有在那时。

我正在寻找一个标准库容器或内存 allocator/pool，我可以使用它来分配和存储我的树 class 中的节点，以减少内存碎片和内存分配开销。我想避免编写自定义分配器。容器应具有以下两个属性：

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

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

Answer 1

恐怕您对想要实现的目标施加了很多限制。

您可能尝试使用的是vector。它是（除了 array 和我可能遗漏的其他人之外）唯一可能在一个块中分配对象的标准容器。

但是这里有一个问题，当 vector 增长时，不能保证对象将继续保留在同一地址上。如果您不调整 vector 的大小（或使用无法增长的 array），那么您很可能是安全的。

否则，正常程序是编写一个使用对象池来完成分配的自定义分配器。此外，您必须注意您的树不会为每个节点分配数据块。

Answer 2

由于您专门要求标准容器，因此 std::deque 是根据您的要求最有希望的选择。只要你只添加元素，现有的元素不会被重新定位，references/pointers（但 not 迭代器）仍然有效。删除元素时，您可能需要留空或交换要删除的元素与最后一个元素。

std::vector不稳定，std::list、std::forward_list以及所有的关联容器都是碎片化的

查看 Boost.Container，您还有其他选择，但需要权衡取舍：

boost::flat_map 提供连续存储（如std::vector），但稳定性问题
boost::stable_vector 以牺牲连续性为代价提供元素稳定性。

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

Answer 3

当您通过指针引用树结构中的节点（因此，不应重新分配它们）并希望减少内存碎片时，我建议为 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_;
};

Answer 4

您描述的内容听起来与 std::deque does. Also check out this article 比较 vector 与 deque

Answer 5

您可能要考虑的另一个选择是使用 std::vector，但在您的节点上保留索引而不是指针。这样您甚至可以获得一些内存，因为您可以存储 32 位索引而不是 64 位指针，具体取决于您的体系结构和需要。

当然要求节点可以被复制或移动。

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

What C++ STL class should I use to reduce fragmentation caused by lots of small allocations?

c++

containers

memory-management

stl

c++11