containers - C++ pointer ownership in path finding

Question

I am writing a path finding algorithm, so I have TreeNode that represents the nodes but in my algorithm, I have an open container that is a priority_queue, which allows fast retrieval of the highest priority node. I also need to check quickly if I already explored a given node, so I have a closed container that is a set.

Now the problem is: who owns what? where are my TreeNodes stored? The open and closed containers don't need to store the nodes themselves, they can just have a pointer to them, but where do I store the nodes then?

My idea is to store in these containers weak_ptr<TreeNode> and when I want to create a new TreeNode I use make_shared<TreeNode>? Or can I have a vector<TreeNode> that stores all the nodes and the other containers just store indices, so I avoid costly shared_ptr?

question from:https://stackoverflow.com/questions/65897837/c-pointer-ownership-in-path-finding

Answer 1

I would indeed separate the ownership of the objects from the algorithm itself.

In case you know for sure you will have a fixed number of nodes during the algorithm's execution, you can use vector<TreeNode> which is created once, fully, beforehand. Then you can either use pointers to the elements or their indices and operate on those. Pointers are slightly more flexible as then you can change the underlying storage container to something non-contiguous (e.g. std::set, or even store them in a map or something else entirely). Then no extra visual and code overhead "pollutes" the algorithm code unnecessarily, and the ownership question is trivial, which is always a good thing.