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

Question

我的C++类会随着时间的推移构建一个树形结构。目前，树中的每个节点都是在构造时分配的（使用new）。该节点类仅使用了几个字节的内存。随着树的增长，可能会有数十万个节点;除了理论最大值2^33之外，在构建树时不知道节点的最大数量。我通过它们的指针引用树结构中的节点。所有节点都在销毁树时释放，此时才被销毁。

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

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

我不需要容器的迭代器或查找功能，因为我的树结构存储了指针。哪个标准库类将为我提供此功能，并给出最低的内存开销？

- user664303

---

节点数100,000是固定的吗？ - 101010

不，这是未知的。理论上的上限是2^33。 - user664303

@user664303 在构建树之前，这个数字会被知道吗？ - skyking

@skyking：不，它不会。 - user664303

你可能想考虑一个有些相关的优化，就是在树内部使用索引来引用节点而不是指针。如果子节点和父节点指针改为uint32_t类型，你可能可以节省很多空间。当然，你必须将理论最大节点数降低到2^32。 - Arvid

Answer 1

考虑到你特别要求标准容器，根据你的需求，std::deque 是最有前途的选择。只要添加元素，现有元素不会被重新定位，并且引用/指针（但不包括迭代器）仍然有效。但是在删除元素时，您可能需要留下间隙或将要删除的元素与最后一个元素交换。

std::vector 不稳定，std::list、std::forward_list 以及所有关联容器都是分散的。

观察 Boost.Container，您可以有其他选项，但也带来其他权衡：

• boost::flat_map 提供连续存储（类似于 std::vector），但是会有稳定性问题
• boost::stable_vector 提供元素稳定性，但造成不连续。

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

- TheOperator

---

我不介意一些内存碎片，也不需要连续的容器。但是，我确实希望为分配在比单个节点的几个字节大得多的块中的对象保留内存。 - user664303

谢谢。这是一个有用而全面的概述。 - user664303

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_;
};

- Stas

---

嗯，理想情况下是使用标准库的解决方案。 - user664303

从Boost.Pool文档中，我不清楚如何使用它来替换调用具有输入参数的非默认构造函数的new。除非我错过了什么。 - user664303

@user664303 请查看 boost::object_pool 的 construct() 方法。它应该类似于 boost::object_pool<Node> pool; pool.construct(nodeArg1, nodeArg2, ...)。 - Stas

尽管这不是一个STL解决方案，但我使用了它。但我使用的是这个池，而不是Boost的：http://www.codeproject.com/Articles/746630/O-Object-Pool-in-Cplusplus - user664303

@Paul 我说他需要使用内存池。Boost.Pool只是可以使用的库的一个例子。我并没有坚持使用Boost，他最终选择了另一个第三方库。 - Stas

Answer 3

您所描述的内容与 std::deque 非常相似。此外，请查看这篇文章，其比较了 vector 和 deque。

- smac89

---

std::deque 的块大小似乎是由实现决定的，而不是用户可定义的：https://dev59.com/FYHba4cB1Zd3GeqPMhQi - user664303

std::deque 可能会像 std::vector 一样移动对象（并使指针失效）。在这种情况下使用它是不安全的。 - Stas

@Stas：只有在使用类的破坏性成员时才会出现问题，而我不会这样做。因此，我相信对于这种特定情况来说是安全的。但这是需要注意的事情。 - user664303

@user664303 我同意，但是在这个解决方案中有很多前提条件。如果不能使用boost（或其他第三方库），我会实现一些自定义的内存池。 - Stas

这里列出了Deque块的大小：http://info.prelert.com/blog/stl-container-memory-usage - user664303

Answer 4

我怕你对要实现的东西设定了太多限制。

你可以试试使用 vector。它（除了 array，还有可能我没提及的其他容器）是唯一一个标准容器，能够将对象分配在一块连续的内存中。

然而，这里有个小问题，当 vector 增长时，并不能保证对象仍然驻留在同一地址上。如果你不调整 vector 的大小（或者使用无法增长的 array），很有可能是安全的。

否则，通常的做法是编写一个自定义的分配器，使用对象池来满足分配需求。此外，你还需确保你的树结构不会为每个节点都分配数据块。

- skyking

---

只有两个限制条件。许多容器符合第一个条件，但向量不符合。真正的问题是哪些容器（例如双端队列、映射、列表、前向列表）可以满足第一个条件，并且可以可靠地分配内存块或块来添加对象到容器中。 - user664303

@user664303，它并不是计数会使它变得复杂。而是因为您希望将其放置在标准容器中，并且希望避免使用自定义分配器。如果您想对分配进行控制，则需要控制它 - 标准容器提供了很少的保证来执行哪些分配。 - skyking

Answer 5

你可能想考虑的另一个选项是使用 std::vector，但在节点上保留索引而不是指针。

这样，您甚至可以节省一些内存，因为您可以存储32位索引而不是64位指针，具体取决于您的架构和需求。

当然，这需要节点可以被复制或移动。

- Adrien Hamelin