Why std::list is consuming all memory in insertion

Question

I have this struct:

struct Node {
    list<int> path;
    int cost;

    Node(int cost = 0) {
        this->cost = cost;
    }

    Node(const Node &other, int newNode, int cost) {
        path = other.path;
        path.push_back(newNode);
        this->cost = other.cost + cost;
    }

    bool operator>(const Node &rsh) const {
        return cost > rsh.cost;
    }
};

and this line of code

Node newNode(node, *i, cost);

where node is other Node object with cost = 0 and path contains one element: 0. *i = 1 and cost = 1 The problem is that when this code is running the program starts consuming more and more memory until all memory in my pc is consumed and my computer freezes. Using the debugger I discover the problem is in this line

path.push_back(newNode);

When the program reaches this line it consumes all RAM and if I replace the path type from list to vector, the problem does not occur.

Any ideas of why is this happening?

This is all the code:

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <functional>

using namespace std;

struct Node {
    list<int> path;
    int cost;

    Node(int cost = 0) {
        this->cost = cost;
    }

    Node(const Node &other, int newNode, int cost) {
        path = other.path;
        path.push_back(newNode);
        this->cost = other.cost + cost;
    }

    bool operator>(const Node &rsh) const {
        return cost > rsh.cost;
    }
};

Node result;

class Graph {
    uint size;
    vector<int> *adjacents;
    vector<int> *weights;

public:
    Graph(uint size);
    ~Graph();

    void addEdge(int v1, int v2, int weight);
    bool UCF(int start, int target);
    void displayPath(const Node &node);
};

Graph::Graph(uint size) {
    this->size = size;
    adjacents = new vector<int>[size];
    weights = new vector<int>[size];
}

Graph::~Graph() {
    delete[] adjacents;
    delete[] weights;
}

void Graph::addEdge(int v1, int v2, int weight) {
    adjacents[v1].push_back(v2);
    weights[v1].push_back(weight);

//    non-directed graph
//    adj[v2].push_back(v1);
//    weights[v2].push_back(weight);
}

bool Graph::UCF(int start, int target) {

    priority_queue<Node, vector<Node>, greater<Node>> queue;
    Node startNode(0);
    startNode.path.push_back(start);
    queue.push(startNode);

    while (!queue.empty()) {
        const Node &node = queue.top();
        queue.pop();

        int current = node.path.back();

        if (current == target) {
            result = node;
            return true;
        } else {
            const vector<int> &adj = adjacents[current];
            uint pos = 0;

            for (auto i = adj.begin(); i != adj.end(); ++i) {
                int cost = weights[current][pos];
                Node newNode(node, *i, cost);
                queue.push(newNode);

                ++pos;
            }
        }
    }

    return false;
}

void Graph::displayPath(const Node &node) {
    cout << "Path: ";
    for (auto i = node.path.begin(); i != node.path.end(); ++i) {
        cout << "->" << *i;
    }

    cout << endl;
    cout << "Path lenght: " << node.cost;
}

int main() {

    uint vertices = 6;

    Graph graph(vertices);

    graph.addEdge(0, 1, 1);
    graph.addEdge(0, 5, 12);
    graph.addEdge(1, 2, 3);
    graph.addEdge(1, 3, 1);
    graph.addEdge(2, 4, 3);
    graph.addEdge(3, 4, 1);
    graph.addEdge(3, 5, 2);
    graph.addEdge(4, 5, 3);

    int start = 0, end = 5;

    if (graph.UCF(start, end)) {
        cout << "Found!" << endl;
        graph.displayPath(result);
    } else {
        cout << "Not found!" << endl;
    }

    return 0;
}

Answer 1

These lines of code:

    const Node &node = queue.top();
    queue.pop();

Consider what node is referring to after you have called pop