0

Let's say I have a graph and each node may contain a value for other nodes. Let's also say that the complexity to calculate that value is rather high ( ~O(n^4) ). Consequently, I would like to store the values that have been calculated for each relation. I'm rather new at C++, so this is what I got (constructors, etc. not included and using struct for simplicity):

struct Node{
    long id_;
    const std::shared_ptr<Node> left_;
    const std::shared_ptr<Node> right_;
    const std::shared_ptr<Node> up_;
    const std::shared_ptr<Node> down_;
    std::unordered_map<std::shared_ptr<Node>, double> otherValues;
    
    double calculate(Node other);   // do math based on neighboring nodes
};

So assuming that nodes very rarely get removed but are added frequently, I wonder if this is the right approach? Initially, I was going for weak_ptr since all the nodes are stored somewhere else as well, but then I'd have to cast to shared_ptr anytime I look up the next nodes (which is all the time). The book, as well as most articles, that I have read state that one should use smart pointers if possible, but I wonder if raw pointers are the more efficient approach here. But then I'd have no idea how to implement these here while still being safe.

Any advice would be greatly appreciated!

Edit: I've changed otherValues to reflect the rest of the example.

Markstar
  • 639
  • 9
  • 24
  • 2
    You will have problems with cyclical references. And having your members as `const` will also make it hard to actually construct your graph. – François Andrieux Jan 06 '21 at 21:01
  • 2
    The container should own the nodes. The nodes should not own each other. – Mooing Duck Jan 06 '21 at 21:13
  • 2
    Raw pointers are safe as long as you don't delete any nodes until after you are finished with the network. These are _structural_ pointers, they don't need to be owning. – Galik Jan 06 '21 at 21:14
  • What does the container that contains the nodes look like? – Mooing Duck Jan 06 '21 at 21:16
  • One should always use smart pointers _for owning pointers_. These aren't owning, so they _should_ use raw pointers. – Mooing Duck Jan 06 '21 at 21:17
  • @MooingDuck: [Regarding owning each other] Yes, that's why I originally had `weak_ptr`. Is that what you are saying as well? – Markstar Jan 06 '21 at 21:20
  • @Markstar: No. They should be `Node*`, since Nodes don't own each other. – Mooing Duck Jan 06 '21 at 21:20
  • @MooingDuck: [Regarding container] To be honest I'm not sure yet, but I think something like a `std::vector`. While the calculations will be initiated from there, the rest should be done through the objects themselves. Also, I changed *otherValues*. – Markstar Jan 06 '21 at 21:23
  • The big problem with `vector` and raw pointers to the `Node`s will be [invalidation](https://stackoverflow.com/questions/6438086/iterator-invalidation-rules) if you change the size or ordering of the `vector`. – user4581301 Jan 06 '21 at 21:52

1 Answers1

3

Very often, you want to access nodes by coordinate rather than only relative, in which case you get something like this:

class Coordinate {
   int x, y;
};
enum Direction4 {
   Left, Up, Right, Down
};
Coordinate operator+(Coordinate, Direction4);

class Node {
    Graph* graph;
    Coordinate coordinate;
    Node* getAdjacent(Direction4 dir);
    double calculate(Node other);
};

class Graph {
    std::unordered_set<Coordinate, Node> nodes;
};

Node* Node::getAdjacent(Direction4 dir) {
    Coordinate coord = coordinate + dir;
    auto it = graph->nodes.find(coord);
    if (it == graph->nodes.end()) return nullptr;
    return &(it->second);
}

You can access any node immediately via coordinates. The graph owns the Nodes, the Nodes do not own each other. In fact, the nodes don't even refer to each other. This means I do not have to worry about memory leaks, or reallocations, or dead pointers, at all. All those issues have gone away entirely.

Mooing Duck
  • 64,318
  • 19
  • 100
  • 158
  • Thank you for your reply! I'm sorry if my example was misleading - there are no coordinates or actual directions for what I need, that was just for the example. But I *think* I see what you are getting at. After having skipped reading about raw pointers, thinking they were obsolete, I guess I will have to double down on it now. :/ My algorithm will create millions of nodes, so I am quite afraid of memory leaks and efficiency. – Markstar Jan 06 '21 at 21:40
  • @Markstar: "Avoid raw pointers" is common advice and it's misleading and I hate it. Instead, avoid `new`. Instead use `std::make_unique` and standard containers, and all memory leaks become a thing of the past. – Mooing Duck Jan 06 '21 at 21:44
  • The problem is that nodes will get removed, as it is not a fixed structure. I will have to find a way to verify that an object still exists, which is not possible with raw pointers afaik. – Markstar Jan 06 '21 at 22:04
  • @Markstar: My code does not have that issue. If a node is removed, it simply ceases to exist. `getAdjacent` will simply start returning `null` if the node is erased. This is possible _because_ the nodes do not have any direct references to each other. – Mooing Duck Jan 06 '21 at 22:07