c++ creating cyclically dependent objects with raw pointers

Question

I'm trying to create a connected graph and to perform certain computations on it. To do that, from each node in this graph, I need to access its neighbors and to access its neighbor's neighbors from its neighbor and so forth. This inevitably creates many (useful) cyclic dependencies.

Below is a simplified example with 3 mutually connected nodes (like the 3 vertices of a triangle), and I'm not sure if this method is a good way to do it, particularly if the clean-up leaves any memory leaks :

#include <iostream>
#include <vector>

class A {
public:
    int id;
    std::vector<A*> partners;
 
    A(const int &i) : id(i) {
        std::cout << id << " created\n";
    }
    ~A() {
        std::cout << id << " destroyed\n";
    }
};

bool partnerUp(A *a1, A *a2) {
    if (!a1 || !a2)
        return false;

    a1->partners.push_back(a2);
    a2->partners.push_back(a1);

    std::cout << a1->id << " is now partnered with " << a2->id << "\n";

    return true;
}

int main() {
    std::vector<A*> vecA;
    vecA.push_back(new A(10));
    vecA.push_back(new A(20));
    vecA.push_back(new A(30));
 
    partnerUp(vecA[0], vecA[1]);
    partnerUp(vecA[0], vecA[2]);
    partnerUp(vecA[1], vecA[2]);

    for (auto& a : vecA) {
        delete a;
        a = nullptr;
    }
    vecA.clear();
 
    return 0;
}

I'm also aware that I can use shared_ptr + weak_ptr to complete the task, but smart pointers come with an overhead and I'd love to avoid that whenever possible (I also hate to use .lock() all the time to access the data, but that doesn't really matter). I rewrote the code using smart pointers as follows, and I'd like to know what are the differences between the 2 pieces of code (outputs of the two codes are identical).

#include <iostream>
#include <vector>
#include <memory>

using namespace std;

class A {
public:
    int id;
    vector<weak_ptr<A>> partners;
 
    A(const int &i) : id(i) {
        cout << id << " created\n";
    }
    ~A() {
        cout << id << " destroyed\n";
    }
};

bool partnerUp(shared_ptr<A> a1, shared_ptr<A> a2) {
    if (!a1 || !a2)
        return false;

    a1->partners.push_back(a2);
    a2->partners.push_back(a1);

    cout << a1->id << " is now partnered with " << a2->id << "\n";

    return true;
}

int main() {
    vector<shared_ptr<A>> vecA;
    vecA.push_back(make_shared<A>(10));
    vecA.push_back(make_shared<A>(20));
    vecA.push_back(make_shared<A>(30));
 
    partnerUp(vecA[0], vecA[1]);
    partnerUp(vecA[0], vecA[2]);
    partnerUp(vecA[1], vecA[2]);

    return 0;
}

*"I'd like to know what are the differences between the 2 pieces of code"* Hmm, I don't quite understand what kind of answer you're looking for. — dyp, Sep 04 '20 at 16:41
Using `vector>` or `deque` would be perfectly fine as well (in `main`). Usually, one wants to avoid this container and only store pointers inside the graph. Then, deletion becomes an issue. — dyp, Sep 04 '20 at 16:44
The second code with smart pointers is suppose to have no leak, I'd like to know if the same is true for the first one. If both codes have no leak, I prefer to use the first one. — Xiasu Yang, Sep 04 '20 at 16:46
But by using vector> in main() I wouldn't be able to do partnerUp and all connections are lost — Xiasu Yang, Sep 04 '20 at 16:54
`But by using vector> in main() I wouldn't be able to do partnerUp and all connections are lost ` that is not true. The combination of smart pointers and raw pointers is a valid approach. If you have a tree structure, a node uniquely holds its children and refers to its parent, using `unique_ptr` for the children and raw pointer for the parent is perfectly fine. For complex graphs, the graph itself would own the nodes and manages their connections, and the nodes have connected, also here you could use `unqiue_ptr` and raw pointers. — t.niese, Sep 04 '20 at 19:58

dyp · Accepted Answer · 2020-09-04T17:30:41.873

You can prevent memory leaks by using a principle of ownership: At every point, there needs to be an owner who is responsible for freeing the memory.

In the first example, the owner is the main function: It undoes all the allocations.

In the second example, each graph node has shared ownership. Both vecA and the linked nodes share ownership. They are all responsible in the sense that they all call free if necessary.

So in this sense, both versions have a relatively clear ownership. The first version is even using a simpler model. However: The first version has some issues with exception safety. Those are not relevant in this small program, but they will become relevant once this code is embedded into a larger application.

The issues come from transfer of ownership: You perform an allocation via new A. This does not clearly state who the owner is. We then store this into the vector. But the vector itself won't call delete on its elements; it merely call destructors (no-op for a pointer) and deletes its own allocation (the dynamic array/buffer). The main function is the owner, and it frees the allocations only at some point, in the loop at the end. If the main function exits early, for example due to exception, it won't perform its duties as the owner of the allocations - it won't free the memory.

This is where the smart pointers come into play: They clearly state who the owner is, and use RAII to prevent issues with exceptions:

class A {
public:
    int id;
    vector<A*> partners;
 
    // ...
};

bool partnerUp(A* a1, A* a2) {
    // ...
}

int main() {
    vector<unique_ptr<A>> vecA;
    vecA.push_back(make_unique<A>(10));
    vecA.push_back(make_unique<A>(20));
    vecA.push_back(make_unique<A>(30));
 
    partnerUp(vecA[0].get(), vecA[1].get());
    partnerUp(vecA[0].get(), vecA[2].get());
    partnerUp(vecA[1].get(), vecA[2].get());

    return 0;
}

The graph can still use raw pointers, since the ownership is now solely the responsibility of the unique_ptr, and those are owned by vecA, and that is owned by main. Main exits, destroys vecA, and this destroys each of its elements, and those destroy the graph nodes.

This is still not ideal, though, because we use one indirection more than necessary. We need to keep the address of the graph nodes stable, since they're being pointed to from the other graph nodes. Hence we should not use vector<A> in main: if we resize that via push_back, this changes the addresses of its elements - the graph nodes - but we might have stored those addresses as graph relations. That is, we can use vector but only as long as we haven't created any links.

We can use deque even after creating links. A deque keeps the addresses of the elements stable during a push_back.

class A {
public:
    int id;
    vector<A*> partners;

    // ...

    A(A const&) = delete; // never change the address, since it's important!

    // ...
};

bool partnerUp(A* a1, A* a2) {
    // ...
}

int main() {
    std::deque<A> vecA;
    vecA.emplace_back(10);
    vecA.emplace_back(20);
    vecA.emplace_back(30);
 
    partnerUp(&vecA[0], &vecA[1]);
    partnerUp(&vecA[0], &vecA[2]);
    partnerUp(&vecA[1], &vecA[2]);
 
    return 0;
}

The actual problem of deletion in a graph is when you don't have a data structure like your vector in main: It is possible to just keep pointers to one or several nodes from which you can reach all other nodes in main. In that case, you need graph traversal algorithms to delete all nodes. This is where it gets more complicated and hence more error prone.

In terms of ownership, here the graph itself would have ownership of its nodes, and main has ownership of just the graph.

int main() {
    A* root = new A(10);
 
    partnerUp(root, new A(20));
    partnerUp(root, new A(30));
    partnerUp(root.partners[0], root.partners[1]);

    // now, how to delete all nodes?
 
    return 0;
}

Why would the second approach be recommended?

Because it follows a widespread, simple pattern that reduces the likelyhood of a memory leak. If you always use smart pointers, there'll always be an owner. There's just no opportunity for a bug that drops ownership.

However, with shared pointers, you can form cycles where multiple elements are kept alive because they own each other in a cycle. E.g. A owns B and B owns A.

Therefore, the typical rule-of-thumb recommendations are:

Use a stack object, or if not possible, use a unique_ptr or if not possible, use a shared_ptr.
For multiple elements, use a container<T>, or container<unique_ptr<T>> or container<shared_ptr<T>> in that order.

These are rules of thumb. If you have time to think about it, or some requirements like performance or memory consumption, it can make sense to define a custom ownership model. But then you also need to invest the time to make that safe and test it. So it should really give you a great benefit to be worth all the effort needed to make it safe. I would recommend against assuming that shared_ptr is too slow. This needs to be seen in the context of the application and usually measured. It's just too tricky to get custom ownership concepts right. In one of my examples above, you need to be very careful with resizing the vector, for example.

In class A - `vector> partners;` - Is there any benefit in the use of `weak_ptr` for the partners, as opposed to using `shared_ptr`? — Den-Jason, Sep 04 '20 at 17:03
Also - where you state `Hence we cannot use vector in main (if we resize that, it changes the addresses).` - surely the original pointers are still valid even though the location of where those pointers are stored changes? A deque would provide better performance though. — Den-Jason, Sep 04 '20 at 17:07
@Den-Jason Yes, cycles of shared pointers won't be deleted. If A points to B and B points to A using a shared pointer, the reference count for either will never reach 0. — dyp, Sep 04 '20 at 17:07
@Den-Jason If you use `vector vecA;` and push back, and the vector resizes, then the addresses of the elements in the vector change. The values of the pointers in `A::partners` remain, but they point into memory that has been free'd. — dyp, Sep 04 '20 at 17:08
That would be the case if he's calling `partnerUp(&vecA[0], &vecA[1])`, but he's not. Am I missing something here? — Den-Jason, Sep 04 '20 at 17:10
@Den-Jason That's what I was implying. We can store the graph nodes directly in the vector, but then we must not resize the vector after forming the links. Sorry if that was unclear. — dyp, Sep 04 '20 at 17:15
This answer offers more than I expected ! I find the second solution is a good idea, since I do have a superclass called Graph in my real code which encloses all Node pointers in a vector (replaced by main in the example code). I chose to put all nodes on heap and store only pointers in Graph as a habit, but now that you mentioned it, it does make more sense to put all Nodes on stack in a container from a leak-free point of view, and it also makes it more natural to use raw pointer.But I suppose this solution can run into trouble when graph size grow too big? — Xiasu Yang, Sep 04 '20 at 20:09
@XiasuYang containers with dynamic size (like `list`, `deque`, `vector`, …) don't store their elements on the stack, but on the heap. Besides that, you should not think in terms of stack and heap if it comes to a leak-free point of view, but about storage duration and ownership. If you have a class called `graph`, you would have a e.g. a member `container<…> nodes`, `graph` has unique ownership over `nodes` and the storage duration of `nodes` is defined by the lifetime of `graph`. `nodes` has unique ownership over its elements and their storage duration is given by the lifetime of `nodes`. — t.niese, Sep 04 '20 at 22:20
@XiasuYang if `container<…> nodes` is e.g. `container nodes`, the ownership of nodes is - from c++ runtimes point of view - over the pointers and not the nodes those pointers point to and only the pointers (not the elements) will be deleted. If it is `container nodes` then the ownership is on the `node` elements. If it is `container> nodes` the ownership is over the `unique_ptr` instance, and those `unique_ptr` have the ownership over `node`. — t.niese, Sep 04 '20 at 22:24
Another thought on this - if you're doing something like a route calculation with the node graph, allowing it to grow and then deleting everything when the route is found, then you can simply add each node to a deque as it is discovered and delete everything in the deque when you're done; there would be no point reference counting in the nodes, and you *could* even use naked pointers for the "partners" in the nodes. If you intend to both add and delete nodes during the lifetime of the graph, then the whole thing becomes a lot more involved. — Den-Jason, Sep 05 '20 at 08:51
@Den-Jason The graph is actually a polygonal grid for fluid dynamics computation, so there’s no “discovery” of polygons, all polygons must be available during the grid’s lifetime and deleted once a converged solution is obtained. I realised it’s totally unnecessary to use shared_ptr and unique_ptr does the job without refCount, but by using deque, I can indeed get rid of smart pointers completely, which is my original intention (first code in my question). — Xiasu Yang, Sep 05 '20 at 12:17

c++ creating cyclically dependent objects with raw pointers

1 Answers1