c++ - 保留存储在 STL 容器中的指针指向的值 (unordered_map)

Question

我的数据结构如下

struct routing
{
    int color;       //white = -1, gray = 0, black = 1
    unsigned int d;      //distance
    unsigned int pi;     //previous node id

    routing() : color (-1), d (UINT_MAX), pi (UINT_MAX ) {}
};

struct attraction //each node in graph is called an attraction
{
    unsigned int id;                           //id of node
    std::string name;                          //name
    unsigned int priority;                     //priority
    std::unordered_map<int, int> nodeMap;      //destination node id, distance
    routing r;                                 //routing information

    attraction() : id (0) , name(""), priority(0) {}
};

现在，我必须运行 Dijkstra 算法来找到不同节点(称为景点)之间的最短距离。我已经实现了它并且工作正常。除了它很慢(比我需要的要慢)。
我有一个存储节点信息的 STL 容器。我用它来执行路由。如下所示:

//I use unordered_map for fast access of elements.
typedef std::unordered_map<unsigned int, attraction*> attractionList;
attractionList attrList;  

我想做的是一旦我计算了某个节点的所有顶点的所有路径/成本并将其存储在 attractionList 容器中，我想重用这些信息，所以来自该特定源节点的后续路由调用将更快。为此，我想保存我的 attrList 容器的状态，这样我就可以快速重用存储的信息。我正在尝试的是这样的:

//make another container whose first element is a unique source id, second element is the attractionList 
std::unordered_map<unsigned int, attractionList> stateMap; (containig routing information)

attractionList* newList = new attractionList(); //make a new object to store old state
newList = &attrList;     //copy values from old state

//insert in another container so that each unique source id has all routing information stored
stateMap.insert(std::pair<unsigned int, attractionList> (from, *newList)); 

嗯，这个问题很明显。当存储在 attrList 中的指针发生变化时，所有从它制作的拷贝都是无效的。我如何永久保存它们？在此容器中如何进行复制？如有必要，我该如何重载赋值运算符？这可能吗？我可以对我的数据结构和容器进行细微的更改，但更改幅度不大。

抱歉发了这么长的帖子。提前谢谢你。

Answer 1

attractionList* newList = new attractionList(); //make a new object to store old state
newList = &attrList;     //copy values from old state

Well, the problem with this is obvious. When the pointers stored in the attrList change all the copies made from it are invalid.

您没有制作拷贝。您在堆上分配了一个新的空列表，然后丢弃了指向它的指针并存储了一个指向现有列表的指针。

我想你的意思是:

attractionList newList = attrList;

但我还没有检查您的其余代码，因此这可能不是一个完整的修复。

关于您的评论:

如果您还需要复制景点，那么您将需要一个地方来存储它们。由于您没有说明如何存储原件，因此我无法告诉您将拷贝存储在何处，但其余代码将如下所示:

attractionList newList;
for (attractionList::iterator it = attrList.begin(); it != attrList.end(); ++it) {
    attraction *newNode = /* copy of *(it->second) */;
    newList.insert(make_pair(it->first, newNode));
}