pointers - C++ avoid dynamic memory allocation

Question

Imagine I have some Node struct that contains pointers to the left and right children and some data:

struct Node {
  int data;
  Node *left;
  Node *right;
};

Now I want to do some state space search, and naturally I want to construct the graph as I go. So I will have a kind of loop that will have to create Nodes and keep them around. Something like:

Node *curNode = ... ; // starting node

while (!done) {
  // ...
  curNode->left = new Node();
  curNode->right = new Node();
  // ..
  // Go left (for example)

  curNode = curNode->left;
}

The problem is that I have to dynamically allocate node on each iteration, which is slow. So the question is: how can I have pointers to some memory but not by allocating it one by one?

The first solution I thought of is to have a std::vector<Node> that will contain all the allocated nodes. The problem is that when we push_back elements, all references might be invalidated, so all my left/right pointers will be garbage.

The second solution is to allocate a big chunk of memory upfront, and then we just grab the next available pointer when we want to create a Node. To avoid references invalidation, we just have to create a linked list of big chunks of memory when we exceed the capacity of the current chunk so every given pointer stays valid. I think that std::deque behaves like this, but it's not explicitly created for this.

Another solution would be to store vector indices instead of pointers but this is not a solution because a Node doesn't want to be associated with any container, it wants the pointer directly.

So what is the good solution here, that would avoid having to allocated new nodes on each iteration?

Answer 1

You can use std::deque<Node> and it will do memory management for you creating elements by groups and no invalidating pointers if you do not delete elements in middle. Though if you want to have more precise control on how many elements in a group you can quite simply create something like that:

class NodePool {
    constexpr size_t blockSize = 512;
    using Block = std::array<Node,blockSize>;
    using Pool  = std::list<Block>;

    size_t allocated = blockSize;
    Pool   pool;
public:
    Node *allocate() 
    {
       if( allocated == blockSize ) {
           pool.emplace_back();
           allocated = 0;
       }
       return &( pool.back()[ allocated++ ] );
    }
};

I did not try to compile it, but it should be enough to exress the idea. Here changing blockSize you can fine tune performance of your program. Though you should be aware than Node objects will be fully constructed by groups (unlike hoiw std::deque would do it). As much as I am aware there is no way to create raw memory for Node objects which is standard comformant.