将指向列表元素的指针插入到映射中会得到垃圾值

Question

我试图实现Prim的算法(eager)，该算法需要跟踪顶点的最佳传入边(最小成本)。为此，我使用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;
};

我不明白的问题到底是什么。是我们不能直接赋值类的对象吗?请原谅我的天真。

这是一个图类，我在这个类的成员函数中做赋值操作。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
}
};

Answer 1

这是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的地址时，你取了一个指向列表元素的指针。

---

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

Answer 2

默认情况下，c++不管理对象的生存期。如果你这样做

bestEdgeFor[destNode] = &e;

你必须确保e不被破坏。在这种情况下，当函数返回时，e被销毁，映射包含一个无效指针，产生未定义的行为。

可以在映射中存储对象，而不是指针:

map<int,Edge>

或者存储shared_ptrs，或者自己管理生命周期。你可以用new，但你需要一个delete的地方。