C++链表反向遍历内存损坏

Question

我正在学习C++。作为映射项目的一部分，我试图通过节点类中的父地址指针属性(反向(遍历从特定节点到起始节点的链表。我试图弄清楚为什么父级的地址值总是被破坏，这会导致错误并阻止遍历。

我在下面提取了该项目的基本组件，以及一些帮助代码，这些代码可以轻松地重新创建错误。

#include <iostream>
#include <stdio.h>
#include <vector>
using std::vector;
using std::cout;
using std::endl;
class Node
{
public:
int idx;
Node * addr = nullptr;
Node * parent_addr = nullptr;

Node (int init_idx, Node * init_parent) {
idx = init_idx;
parent_addr = init_parent;
}
};
void PrintNode(Node & n) {
cout << "idx: " << n.idx << " addr: " << n.addr << " parent_addr: " << n.parent_addr << endl;
}
void PrintNodeList (vector<Node> & path) {
for (Node n : path) {PrintNode(n);}
}
void CreateNodeList (const int node_count, vector<Node> & node_list) {
for (int i=0; i<=(node_count - 1); i++) {
if (i==0) {
//  first node parent is null
node_list.push_back(Node(i, nullptr));
} else {
// subsequent nodes parent is previous node
node_list.push_back(Node(i, &node_list[i-1]));
}
// store address of node to clearly follow forward and reverse traversals
node_list[i].addr = &node_list[i];
}
cout << "Node List..." << endl;
PrintNodeList(node_list);
}
void TraverseNodeList(Node * current_node) {
cout << endl << "Traversing node list in reverse..." << endl;
while (current_node != nullptr) {
PrintNode(*current_node);
current_node = current_node->parent_addr;
}
cout << endl << "Completed reverse traversal." << endl;
}
int main() {
// generate list of nodes
const int node_count = 5;
vector<Node> node_list;
CreateNodeList (node_count, node_list);

// reverse traverse the list of nodes
const int last_node = node_count - 1;
TraverseNodeList(&node_list[last_node]);

return 0;
}

以下是一个示例节点列表(节点索引、节点地址、节点父节点地址(：

这是一个在起始节点损坏的遍历：

以下是在开始节点之前损坏的遍历：

实际CreateNodeList函数：

此代码是从A*搜索项目中提取的。当遍历映射时，正在检查的节点(current_node(的邻居会被更新(设置父属性并将其标记为已访问(，并通过以下方式推送到std::vector<node *>node_list上：

for (auto neighbor : current_node->neighbors) {
neighbor->parent = current_node; 
node_list.push_back(neighbor); 
neighbor->visited = true;
}

Answer 1

node_list.push_back(Node(i, &node_list[i-1]));

指向向量中上一个元素的指针将传递给新Node元素的构造函数。

这会立即变成未定义的行为。std::vector的一个基本特性是，当std::vector重新分配时，将使指向向量的所有现有指针和迭代器无效。

在构造这个新的Node之后，它被作为参数传递给push_back，这可能导致向量内容的重新分配，从而使这个和所有以前指向向量的指针无效。

如果需要处理指向向量中元素的指针，则必须做额外的工作来确保向量永远不会重新分配。这超出了这个问题的范围，而且会很麻烦，所以这里最好的办法可能是重新思考链表的整体设计，使其不使用std::vector，也许std::list将是一个替代方案(然而，由于std::list本身就是一个链表，这会有点可疑(。在任何情况下，崩溃的原因都是未定义的行为，因为引用了指向被重新分配的向量中的值的指针，从而使指向该向量中值的所有指针无效。