为什么 std::list 在插入时消耗了所有内存

Question

我有这个结构：

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 newNode(node, *i, cost);

其中节点是成本 = 0 的另一个节点对象，路径包含一个元素：0。 *i = 1 和成本 = 1 问题是，当此代码为运行时，程序开始消耗越来越多的内存，直到消耗完我电脑中的所有内存并且我的计算机死机。使用调试器我发现问题出在这一行

path.push_back(newNode);

当程序到达这一行时，它会消耗所有 RAM，如果我将路径类型从列表替换为矢量，问题就不会发生。

知道为什么会这样吗？

这是全部代码：

#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

这些代码行：

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

在调用 pop

后考虑 node 指的是什么

为什么 std::list 在插入时消耗了所有内存

Why std::list is consuming all memory in insertion

c++

stdlist