1

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 ?
1
  • Are you going to modify the 2D array during the algorithm's execution? If not, you can make the set hold pointers to the array elements. Jun 8, 2015 at 1:00

2 Answers 2

3

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.

3
  • Thank for both your answers! I have already read about smart pointers (and shared pointers). However, I was thinking that if someone uses those type of pointers in large-scale systems, then the benefit of C++ (versus garbage-collected languages) is somewhat lost. But from your post, I see that most large-scale systems are constructed using smart pointers (and customized new-delete is used only in special occasions), right ?
    – Dimos
    Jun 7, 2015 at 21:41
  • @RaptisDimos: Effectively. The problem with new/delete is that it only works when the programmer puts in a huge amount of effort, which does not scale at all. It's much more effective to use smart pointers- pretty much exclusively. The advantages of C++ over GC are not lost at all by using smart pointers- they are fully deterministic and resource-generic.
    – DeadMG
    Jun 7, 2015 at 21:43
  • 3
    @RaptisDimos: You only use std::shared_ptr when needed. Contrast this with GC languages where GC is always on, for all objects.
    – Siyuan Ren
    Jun 8, 2015 at 4:52
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.