将指向列表中元素的指针插入地图会导致垃圾值

html5 • • 问答

我试图实现 Prim 的算法（急切），它需要跟踪到顶点的最佳输入边（最低成本）。为此，我将 stl map 用作：

std::map<int, Edge*> bestEdgeFor;

但是，当我尝试为某个键分配边时，实际存储的是带有数据成员垃圾值的边。因此，我得到一些随机边缘作为输出。但是，当我使用相同的数据分配 Edge 类的新实例时，它可以正常工作。

bestEdgeFor[destNode] = &e; //Doesn't work
bestEdgeFor[destNode] = new Edge(e.from,e.to,e.cost); // Works

这是 Edge 类定义：

class Edge {
public:
    int from;
    int to;
    int cost;
};

我无法弄清楚到底是什么问题。是不是我们不能直接分配一个类的对象？请原谅我的天真。

这是Graph类，我在这个类的一个成员函数中进行赋值操作。e来自adjList. 范围有效吗？

class Graph {
    int V;
    std::map<int, std::list<Edge>> adjList;
    map<int, Edge*> bestEdgeFor;
public:
    void relaxEdgesAtNode(int currentNode, MinIndexedPQ&  ipq, int* visited){
        visited[currentNode] = 1;
        for(Edge e : adjList[currentNode]) {
            int destNode = e.to;

            if(visited[destNode]){
                continue;
            }

            if(!ipq.contains(destNode)) {
                ipq.insert(destNode,e.cost);

                // bestEdgeFor[destNode] = &e // Don't work
                bestEdgeFor[destNode] = new Edge(e.from,e.to,e.cost); // Works
            } else {
                if(e.cost < ipq.keyOf(destNode)) {
                    ipq.decreaseKey(destNode,e.cost);
                    // bestEdgeFor[destNode] = &e // Don't work
                    bestEdgeFor[destNode] = new Edge(e.from,e.to,e.cost);
                }
            }
        }
    }

    std::vector<Edge*> primsMST() {
        int s = 0; //choosing the starting node
        int* visited = new int[V]{0};
        MinIndexedPQ ipq(V);
        visited[s] = 1; // marking the starting node visited

        int m = V - 1;
        int edgeCount = 0, mstCost = 0;
        std::vector<Edge*> mstEdges; // This is the return value in case the mst exists

        // Call the problematic function
        relaxEdgesAtNode(s, ipq, visited);

        // Here, the values are garbage, and the printing code prints garbarge
    }
};

回答

这是Graph类，我在这个类的一个成员函数中进行赋值操作。e来自adjList. 范围有效吗？

通常，是的。这是因为链表中的对象具有稳定的地址。只要它们在列表中，您就可以获取它们的地址并将指针放入映射中而不会出现问题。

现在让我们看看你的任务：

范围有效吗？

bestEdgeFor[destNode] = &e; //Doesn't work

但什么是e？你如何初始化它？让我们来看看：

for (Edge e : adjList) {
     // ... much code ...
     bestEdgeFor[destNode] = &e;
}

在此代码中，e是循环范围内的局部变量，您从列表中的值复制初始化。

e 来自 adjList

这不是真的。e不要来自adjList. 正如您的代码中所见，e是循环内的一个局部变量，它具有从其他地方复制的值，在您的情况下是列表。您获取将在循环迭代后消亡的局部变量的地址。

你想要做的很可能是这样的：

// something similar to this
for (Edge& e : adjList) {
     // ... much code ...
     bestEdgeFor[destNode] = &e;
}

现在e是对列表中变量的引用。当你获取 的地址时e，你获取了一个指向列表元素的指针。

但是，请注意从列表中的元素获取指针需要特别注意。一旦从中删除元素，就必须更新映射并删除所有指向该删除元素的指针。

以上是将指向列表中元素的指针插入地图会导致垃圾值的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>