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

Question

My C++ class builds a tree structure over time. Each node in the tree is currently allocated on construction (using new). The node class uses only a few bytes of memory. As the tree grows there may be 100,000s of nodes; the maximum number of nodes is not known on construction of the tree, other than the theoretical maximum of 2^33. I reference nodes in the tree structure by their pointer. All nodes are deallocated on destruction of the tree, and only then.

I'm after a Standard Library container or memory allocator/pool that I can use to allocate and store the nodes within my tree class, in order to reduce memory fragmentation and memory allocation overhead. I'd like to avoid having to write a custom allocator. The container should have the following two properties:

1. Allocated objects do not move in memory, therefore can referenced by pointers safely.
2. The class allocates memory for large blocks of objects, thus reducing memory fragmentation. Note that I do not require the entire container to be contiguous in memory.

I do not need the iterator or lookup functionality of the container, as my tree structure stores the pointers. What Standard Library class will provide me with this functionality, and give me the lowest memory overhead?

Answer 1

Since you're asking specifically for a standard container, std::deque is the most promising option given your requirements. As long as you only add elements, the existing ones are not relocated, and references/pointers (but not iterators) remain valid. When removing elements, you may however need to leave gaps or swap the element to remove with the last element.

std::vector is not stable, and std::list, std::forward_list as well as all the associative containers are fragmented.

Looking at Boost.Container, you have additional options, however with other trade-offs:

• boost::flat_map provides contiguous storage (like std::vector), but with it the stability problem
• boost::stable_vector offers element stability at the cost of contiguity.

Alternatively, you can have a look at pool allocators (like Boost.Pool). They provide low fragmentation and fast allocation, and the container in front of it can still be used like a normal container.

Answer 2

As you reference nodes in the tree structure by pointers (so, they shouldn't be reallocated) and wants to reduce memory fragmentation, I would recommend to use memory pool for Node objects.

Boost.Pool library may fit your needs.

Example:

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