Which C ++ STL class should be used to reduce fragmentation caused by many small distributions?

Question

My C ++ class creates a tree structure over time. Each node in the tree is currently allocated during construction (using a new one). The node class uses only a few bytes of memory. As the tree grows, there may be 100,000 nodes; the maximum number of nodes is unknown when constructing the tree, except for the theoretical maximum of 2 ^ 33. I refer to the nodes in the tree structure with my pointer. All nodes are exempt from the destruction of the tree, and only then.

I am after a standard library container or memory allocator / pool that I can use to allocate and store nodes in my tree class, to reduce memory fragmentation and memory retrieval. I would like not to write a custom allocator. A container must have the following two properties:

• Selected objects do not move in memory, so pointers can be safely referenced.
• The class allocates memory for large blocks of objects, thereby reducing memory fragmentation. Note that I do not require the entire container to be contiguous in memory.

I don't need iterators or container search functions, as my tree structure stores pointers. What class of standard library will provide me this function and give me the least memory overhead?

Answer 1

When you refer to nodes in a tree structure with pointers (so you should not reallocate them) and want to reduce memory fragmentation, I would recommend using a memory pool for objects Node.

The Boost.Pool library can 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_;
};

Answer 2

, std::deque . , , / ( ) . .

std::vector , std::list, std::forward_list, .

Boost.Container, , :

• boost::flat_map (, std::vector),
• boost::stable_vector .

, (, Boost.Pool). , .

Answer 3

, , , std:: deque. , vs deque

Answer 4

, , .

, , - vector. ( array , , - , ) , , , .

, vector, , . vector ( array, ), , .

, . , , .

Answer 5

Another option you might want to consider is to use std::vector, but keep an index instead of a pointer on your nodes. That way, you can even get some memory, since you can save a 32-bit index instead of a 64-bit pointer depending on your architecture and needs.

It is required that the nodes can be copied or moved, of course.