Correct way to add a pointer to an empty std::list using push_back

Question

I have two simple classes representing nodes and edges in a connected graph structure.

//node.h

#include "edge.h"
#include <string>
#include <list>
#include <utility> 

using namespace std; 

class Edge;

class Node {
private:
    list<Edge> edgeList;
    string nodeName; 
    pair <int, int> coordinates;
public:
    Node();
    void setXY(int x, int y);
    void insertEdge(Edge& edgeToAdd);
    void removeEdge(Edge& edgeToAdd);
    list<Edge> getEdgeList();
};

With insertEdge method implemented in node.cpp as:

void Node::insertEdge(Edge& edgeToAdd) {
    this->edgeList.push_back(edgeToAdd);
}

The Edge class is another simple class declared in edge.h:

#pragma once
#include "node.h"

class Node; 

class Edge {
private:
    Node* destinationNode;
    int edgeWeight;
public:
    //constructor
    Edge(Node* destNode, int w);

    //Setters and Getters 
    void setDestinationNode(Node* destNode);
    void setEdgeWeight(int weight);
    Node* getDestinationNode();
    int getEdgeWeight();
};

In another file in which I am writing unit tests I try to insert a pointer to an edge object using the insertEdge method detailed above:

SECTION("an edge gets inserted to the adjacency list") 
{
        Node* b = &Node();
        Edge* e = new Edge(b,1);
        b->insertEdge(*e);
        list<Edge> edgelist = b->getEdgeList();
}

I have determined that edgeList.push_back(edgeToAdd) results in a segmentation fault due to illegal memory access. Stepping through the code I can see that the variables which are being illegally accessed are _Prev and _Next which are members of the allocator of the std::list. I suspect that my problem has something to do with how I have declared std::list<Edge*> edgeList

My question is, what is a correct way to add a pointer to a std::list which has only being declared?

`Node* b = &Node();` should not compile, it is taking the address of a temporary object that goes out of scope as soon as that full expression ends. — NathanOliver, Mar 07 '23 at 18:45
@NathanOliver am I correct in saying that only Node* b = new Node() would be a correct usage? In that case the memory would be allocated on the heap and not get released as soon as the full expression ends. — Blargian, Mar 07 '23 at 18:48
Yes, that would keep the pointer pointing to a valid object. — NathanOliver, Mar 07 '23 at 18:49
Side note: The linked-list (or linked list-like) `std::list` is really slow unless you are performing inserts or removals at an already known location. As soon as you have to iterate or find stuff, you lose and lose hard compared to an array-like `std::vector`. `list` does have wonderfully forgiving [iterator invalidation](https://stackoverflow.com/q/6438086/4581301), though. — user4581301, Mar 07 '23 at 18:51
@Blargian `In that case the memory would be allocated on the heap and not get released as soon as the full expression ends` you should stop thinking about heap and stack when you are talking about the lifetime of objects, instead use [storage duration](https://en.cppreference.com/w/cpp/language/storage_duration#Storage_duration). It might be true that storage duration and stack/heap are often related but that's not always the case. stack/heap: where the data is stored based on the implementation, storage duration: describes the lifetime of objects. — t.niese, Mar 07 '23 at 18:59
`Edge* e = new Edge(b, 1); b->insertEdge(*e);` There's no reason to dynamically-allocate your `Edge` here. You're inserting a copy of it into the `Node`'s `edgeList`, so you may as well just use a local with automatic storage duration. — Miles Budnek, Mar 07 '23 at 19:07

score 1 · Accepted Answer · answered Mar 07 '23 at 18:49

1

The correct way is the way you did it.

However, this line:

Node* b = &Node();

creates a new Node, gets its address, then destroys that node because it was only a temporary object. Then you access the list inside that destroyed Node.

You probably wanted to write Node b; and then use b. instead of b-> - this creates a Node in a local variable that stays alive until the end of the function.

answered Mar 07 '23 at 18:49

user253751

57,427
7
48
90

Thanks, that fixed the issue. I'm trying to do an adjacency list implementation of a graph here, so I originally had in mind storing pointers to nodes in the edge list. I have in my mind for some reason that not making copies but rather using pointers or references is more efficient. However If the Node object will only stay alive until the function end I'm thinking it would be better to rather store copies of Nodes in the edge list? – Blargian Mar 07 '23 at 19:13
@Blargian do you *want* to store copies of nodes in the edge list? (does that include copies of their edge lists including copies of the edge lists including copies of the copies of the other nodes? going on forever? creating infinite copies?) If not, what do you actually want to do? – user253751 Mar 07 '23 at 19:15

Correct way to add a pointer to an empty std::list using push_back

1 Answers1