CODEWITHSUNDEEP
c++pointers
František Němec
František Němec

Reputation: 352

Graph structure - are pointers bad?

I am implementing a graph structure for a path finding algorithm in C++.

When a new edge or node is created, it is stored in a separate vector for later deletion by the graph class' destructor. I use pointers because they provide easy graph navigation; I can easily test nodes' identity by simply comparing their addresses or I can create paths by creating vector of pointers and later directly use these pointers to navigate through the graph.

struct Edge
{
    Node* from;
    Node* to;
}

struct Node
{
    Data data;

    std::vector<Edge*> outEdges;
    std::vector<Edge*> inEdges;
}

I have read articles about how pointers are bad and should be avoided or replaced with smart pointers (but even they should be avoided). Or that good programmers don't use them at all (with exceptions). I understand that they are sources of memory leaks, security risks and overall are hard to manage correctly (especially in multithreaded applications).

My question: is pointer approach in this case bad?

Edit 1: There are questions where did i read about pointers (smart) should be avoided. https://softwareengineering.stackexchange.com/questions/56935/why-are-pointers-not-recommended-when-coding-with-c/163279#163279

In a second part of his answer:

Upvotes: 0

Views: 2653

Answers (5)

Crashworks
Crashworks

Reputation: 41374

The meme about pointers being bad is simply false. Pointers are an important part of the language, and often the best (or only) way to reference one data structure from another. Even the NASA JPL uses pointers freely in their performance- and safety-critical code on spacecraft. See their programming standard: http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf

Using pointers carelessly can get you into trouble, but that is true of everything in life.

Upvotes: -1

user4581301
user4581301

Reputation: 33931

Pointers should be avoided until they are needed.

Here, Nodes either contain other Nodes or references to them. In containment, maintaining coherency among N-to-the-N copies of Nodes would be a nightmare. A reference of some sort is vastly less complex and less likely to result in problems.

But now managing ownership becomes a problem. Who owns the Node and is responsible for deletion when it's no longer used?

With an undirected graph, a Node can own itself and self destruct (delete or remove itself from a Node pool) when it has no further connections.

In a directed graph, a Node can't self-determine because it has no knowledge of who may still be pointing to it. Its fellow Nodes must be collectively responsible and free the Node when no Nodes touch the node. Tracking this is a fun management task, but also kind-of the point of a graph.

Upvotes: 1

Surt
Surt

Reputation: 16089

Why are pointers to be avoid if possible for performance reasons?
Because you have to follow them around in memory, they suffer from very bad cache locality.

How many owners can there be of an object?
There can be only one!
unless its a shared_ptr (which then is the real single owner). Hence you can use none-owning pointers as long as you only follow them and don't delete or transfer owner ship with them.

Will pointers magically update if what I point to move?
No! if you use a vector for storage and you exceed its capacity it will relocate rendering all pointers to it invalid. If your sure that you have enough capacity you can use pointers.

So in this case I would consider the following structure, a pointer into a memory is just just an index into memory so why not use the indexes themselves?

struct Edge {
    // index into allNodes
    uint32_t from;
    uint32_t to;
}

std::vector<Edge> allEdges;

struct Node {
    Data data;

    // index into allEdges
    std::vector<uint32_t> outEdges;  // sort on to
    std::vector<uint32_t> inEdges;   // sort on from
}

std::vector<Node> allNodes; // contains all nodes

or more radically if you don't need to traverse all edges

struct Node {
    Data data;

    // index into allNodes
    std::vector<uint32_t> outEdges; // sort
    std::vector<uint32_t> inEdges;  // sort
}

std::vector<Node> allNodes; // contains all nodes

What you can't do with this is:
a) delete any Node/Edge and move the rest up. b) move any of them including c) sort them

remember to erase the Edge in both Nodes if you remove it.

If you got a lot of edges in each vector it might be relevant to sort them so you can use a binary search to find a specific one.

If you want to use pointer just be sure to have one owner for each node and edge. Placing them in a vector secures this, but beware of resizing as it invalidates all vectors.

Upvotes: 1

kamikaze
kamikaze

Reputation: 1579

Using plain pointers for the Edge class is all right, as long as a node that has been added does not get removed again. You can still delete the whole graph in its entirety. If your graph mutates frequently I'd suggest to use std::weak_ptr for the edges.

However the class Edge is completely obsolete.

struct Node
{
    Data data;
    std::vector<Node*> edges;
}

This is sufficient for directed and undirected graphs. In both cases you only need to record outgoing edges. In an undirected graph you have to record the edge in both nodes (with a pointer in the other direction).

Upvotes: 0

SergeyA
SergeyA

Reputation: 62563

I am going to repeat myself. POINTERS ARE NOT BAD. Print it in friendly yellow letters (C) and pin on the wall. They are extremely useful. I have never seen a professional C++ program which managed to avoid pointers completely.

Managing your own pointers is usually bad, unless you are working on pointers manager.

Unconstrained standard memory allocation can be a bottleneck in high performance applications - but pointers are NOT sinonyms with standard memory allocations.

Pointers ARE not source of memory leaks, or security risks. Pointers are NOT hard to manage (no harder than write good programms in general).

If you do not want to use pointer, you've choosen wrong language.

Upvotes: 5

Related Questions