Usage of objects in multiple containers in C++

Question

In cases where there is a desire for objects to be "shared" between multiple containers, I would like to know what is the best practice in C++. For example, when implementing some path algorithms (such as A*), I have implemented a 2-dimensional array of Nodes (user-defined class), and I also want to have a Set, where specific Nodes will be added and removed during the execution of the algorithm. However, when adding a Node in the Set, I want to store this specific Node (and not a copy), so that modifications in the objects of the Set are also visible in the 2-dimensional array. I guess there are 2 approaches :

• hold different copies of the Nodes in Set and 2-d array, and also create a mechanism that would synchronize the copies, so that modifications are passed from one to the other. However, this would be hard to implement and it would also consume a lot of memory, due to a lot of redundant copies of the nodes.
• the 2 containers (the 2-dimensional array and the set) just hold pointers to Nodes. So, when I want to add a specific Node in the set, I retrieve the pointer to this node from the 2-d array and insert the pointer to the Set.

Since, I have concluded that the second solution must be the right one, I would like to ask the following questions :

1. During learning C++, I have found books recommending to avoid creating containers with pointers. So, should I just accept this case as an exception to the rule ?
2. How should I optimally design the initialization of the Nodes and the destruction (freeing of resources), since both the 2-d array and the Set will hold pointers ?

Answer 1

During learning C++, I have found books recommending to avoid creating containers with pointers. So, should I just accept this case as an exception to the rule ?

No, burn the books instead. There's nothing special about T* that makes it unsuitable in a container.

How should I optimally design the initialization of the Nodes and the destruction (freeing of resources), since both the 2-d array and the Set will hold pointers ?

Use std::shared_ptr, which uses refcounting to handle multiple owners.

Judging by the content of your post, I'm going to posit that you're in a pre-smart-pointer state, so let me give you a core piece of advice. Don't ever use new and delete, because it's almost impossible to write correct programs with them and this is just the tip of the iceberg in the ways in which that completely does not scale from trivial programs at all- for example, exceptions.

Always use a dedicated resource-holding object to handle resources. Never free them yourself.

Answer 2

First off, containers that hold raw pointers are only problematic because those pointers could become invalid/out of date at any time (from the point of view of the pointer container). Same goes for containers of iterators.

Possible solutions I can think of:

1) The slightly-less-dangerous option: Store the objects in a stable, node-based container such as std::list, std::map or std::set so that a pointer/iterator to a single object is guaranteed to remain valid as long as that particular item has not been removed from the container. This still requires a significant amount of synchronization on your part, so it's rarely the best move, but it's almost always an option.

2) One safe option: Use shared pointers in both containers, so that all the resources are guaranteed by the language to get cleaned up correctly in a deterministic fashion.

3) Another safe option: Don't use pointers/iterators at all, and come up with some other way of referencing the 2D array from the set. For instance, the set could contain std::pairs of ints that represent indexes into the 2D array.

4) The ideal option: Refactor your code so you don't need two data structures in the first place. Needing to store a container of pointers/iterators would be a code smell, even if it was

Which of these options is the best depends heavily on your code. For example, if the Set you're talking about exists solely within a doAStar() function that takes a reference to a 2D array, and no concurrency is involved, then I would personally go for #3. In this case the array is guaranteed not to change during the function call so smart pointers are overkill, and the Set is strictly temporary so the "code smell" isn't really there.