11

Sometimes I'm really sure that I want to have circular dependence of pointers, and every object on cycle should be able to use his pointer (so it can't be weak_ptr).

My question is: Does this mean that I have bad design?

What if I want to implement graph? Can I use smart pointers? In graphs there are cycles, but with weak_ptr I can't use "->". What can I do?

I read some articles, reference and topics on StackOverflow, but it looks like I still don't get smart pointers. Really, why doesn't exists some variant of weak_ptr with "->"?

7
  • 1
    General graphs implementations avoid the issue by using either a matrix or list format to represent relationships, rather than actual pointers. en.wikipedia.org/wiki/… May 1, 2014 at 13:37
  • @StoryTeller matrix takes a lot of space, much more than needed and in general case it is not good idea. Having a list is what the OP is talking about - having pointers to adjacent nodes.
    – Andrey
    May 1, 2014 at 13:40
  • @Andrey, no that is not what the OP is talking about. He was talking about having edges represented by actual pointers. If he had an adjacency or incidence list in mind, he would not feel he can't use a weak pointer, since those are just condensed forms of the matrix. May 1, 2014 at 13:43
  • 2
    @Andrey, That is the naive implementation which is prone to the problem the OP is asking about. Having struct Node { whatever data; vector<Node_ID> nodes; } and using a table to retrieve actual nodes is what I was talking about. May 1, 2014 at 14:30
  • 2
    Just an aside but do you actually want to implement your own graph library? If so, I would just just use boost graph. I say this because I went down this road myself (I used shared_ptr's with raw pointers to break cycles) and while I learned a lot about c++, smart pointers, graph theory, etc, I ultimately learned how hard it is to write a good graph theory library and just went with boost graph.
    – Sean Lynch
    May 2, 2014 at 18:00

3 Answers 3

30

Approach this from the conceptual side, not the implementation one. Smart pointers represent ownership. And existence of smart pointers does not invalidate the role of raw pointers as non-owning observers.

Does each object have a single, clearly defined owner (e.g. a graph owns all of its vertices and edges)? If so, use std::unique_ptr to hold the vertices and edges in the graph, and use raw pointers inside vertices and edges to refer to each other.

Is shared ownership applicable (e.g. a vertex only exists as long as at least one edge is connected to it)? If so, use std::shared_ptr to represent that ownership, again with raw pointers for non-owning observers. If you need mutual ownership (i.e. ownership cycles) where "a vertex only exists as long as an edge refers to it, and an edge only exists as long as a vertex refers to it," then 1. double-check that such design is correct and maintainable, and 2. if so, use a std::weak_ptr somewhere in the cycle to break the ownership loop. You can always lock() a weak_ptr to obtain a shared_ptr.

For your particular graph scenario, I believe "everything's owned by the graph" would be the most logical ownership scheme; but that depends on the idiosyncracies of your task.

11
  • 2
    @KrzysztofStanisławek Yes, exactly. Herb sutter has :several: :articles: on this. There's also a question here on SO. May 1, 2014 at 14:21
  • 1
    @KrzysztofStanisławek A weak_ptr can't be directly dereferences precisely because it's non-owning; it can become "dangling" if all shared_ptrs to its object are destroyed. Use a weak_ptr if you can outlive the thing it points to, or a raw pointer if you cannot. May 1, 2014 at 14:23
  • 1
    @Angew I can understand your point about having the graph contain a std::unique_ptr, but in practice, it shouldn't be necessary, and it adds a lot of extra overhead and complexity. A graph is a somewhat special case where the object (the graph) owing the dynamically allocated pointer (the nodes in the graph) may not even have a pointer to them. But it does know how to get to them, and in the destructor, it will walk the graph to delete whatever. (Although graphs are a case where a garbage collector does a lot better job.) May 1, 2014 at 14:43
  • 2
    I like this answer, but I want to note that weak_ptr can only break cycles statically, i.e. cycles known at compile-time. May 1, 2014 at 15:33
  • 1
    @KrzysztofStanislawek Following a non-owning reference to an unknown lifetime object has to be a two step process. First, you have to check that the object still exists, then you have to use the object. You could have a throwing operator-> like interface, but weak_ptr instead makes you generate the shared_ptr, ensure it is valid, use it, then discard the shared_ptr. Writing a throw based interface around this is not hard... May 1, 2014 at 18:12
4

You can use weak_ptr somewhere in the cycle; you just need to promote the weak_ptrs to shared_ptrs before you can dereference them. You can do this by calling weak_ptr::lock() or simply by passing a weak_ptr to shared_ptr's constructor (but beware; this will throw a bad_weak_ptr exception if the object the weak_ptr points to has been destroyed.

If you really can't do this (for example, if all objects involved in the cycle are of the same type, which is probably the case in your graph example), another option is to put a release function somewhere in the chain that causes the object in question to set all its shared_ptrs to null.

2
  • Sounds like a great recipe for making the code for walking the graph unreadable. All of the pointers in the graph would have to be weak pointers, and they are probably all of the pointers which exist for most of the nodes. May 1, 2014 at 14:44
  • @JamesKanze Right; the idea in the first paragraph is a good solution when the cycle is composed of different kinds of objects, but it becomes more difficult when they're all the same (that's what I try to address with the second paragraph). Without seeing his actual code, it's hard to make a concrete suggestion for what OP should do. And it sounded like he was interested in general solutions, rather than just a solution for a graph.
    – dlf
    May 1, 2014 at 14:59
1

Does this mean that I have bad design?

Yes, but it is a starting point.

Let's consider some of the smart pointers availabe to use.

unique_ptr - a single owner exists that is responsible for disposing of the object.

shared_ptr - many (or potentially many) owners exist and the last one must dispose of the object

weak_ptr - many owners may exist but this is not one of them, the weak pointer may out live the object pointed to, if the object pointed to is disposed of the weak pointer will be null (that is the lock method will return a null shared_ptr)

observer_ptr(n3840)- Not yet part of the standard so C-style pointers (T*) can be used instead if needed. These work very much like a weak_ptr, but it is the programmer’s responsibility to make sure that all observers are not dereferenced after the object pointed to is disposed of.

A solution is to split the design into an object that will own all the pieces and the pieces (the cycle nodes). The owning object can use shared_ptr or unique_ptr to automatically manage the life time of the nodes. The nodes themselves can refer to each other with weak_ptr, observer_ptr, or a Reference (Node&)

Your Answer

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

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