了解从队列弹出时引用中的分段错误

Question

我有以下函数：

std::vector<Node> BFS(Graph g, Node source, Node target) {
std::queue<std::vector<Node> > q;
std::vector<Node> path = {source};
q.push(path);
while (!q.empty()) {
std::vector<Node> cur_path = q.front();
q.pop();
Node cur_node = cur_path[cur_path.size() - 1];
if (cur_node.data == target.data) {
return cur_path;
}
// for (int i = 0; i < g.edge_map[cur_path].size(); i++) {
//     std::vector<Node> new_path = cur_path;
//     new_path.push_back(g.edge_map[cur_path][i]);
//     q.push(new_path);
// }
}
}

现在，我并不是说这可以实现搜索，我只是想知道为什么它会导致分割错误。我知道这是因为我有一个q。pop()；但是为什么？这是因为矢量本身就是参考吗？如果需要，我可以包含更多的代码，只是试图封装手头的问题。

编辑：这是main()驱动程序：

int main(int argc, char **argv) {
// double normals[][3] = {
//    #include "normals.txt"
// };
Graph g;
Node n0 {0, "red"};
Node n1 {1, "yellow"};
Node n2 {2, "black"};
Node n3 {3, "black"};
Node n4 {4, "red"};
Node n5 {5, "yellow"};
Node n6 {6, "black"};
Node n7 {7, "black"};
Node n8 {8, "red"};
Node n9 {9, "yellow"};
Node n10 {10, "black"};
Node n11 {11, "black"};
g.add_neighbor(n0, n1, true);
g.add_neighbor(n0, n2, true);
g.add_neighbor(n0, n3, true);
g.add_neighbor(n2, n4, true);
g.add_neighbor(n4, n5, true);
g.add_neighbor(n4, n6, true);
g.add_neighbor(n4, n7, true);
g.add_neighbor(n6, n8, true);
g.add_neighbor(n8, n9, true);
g.add_neighbor(n8, n10, true);
g.add_neighbor(n8, n11, true);
BFS(g, n0, n11);
return 0;
}

它给出：

graph. yup
Segmentation fault (core dumped)

FWIW，我的图有一个edge_map成员，它是一个以节点结构为键，以节点结构的向量为值的映射，以表示图的邻接列表。构造函数输出"graph"。是的，如果你需要更多信息，请告诉我

第二版：为了完整起见，我将把它的其余部分包括在内，很抱歉过于冗长，但我正在努力理解为什么会发生这种情况。

图形.h:

#include <iostream>
#include <map>
#include <vector>
struct Node {
int data;
std::string color;
};
inline bool operator<(const Node & left, const Node & right) {
return left.data < right.data;
}
class Graph {
public:
std::map< Node, std::vector<Node> > edge_map;
Graph();
void add_neighbor(Node cur_node, Node new_node, bool both_ways=false);
void remove_neighbor(Node cur_node, Node del_node, bool both_ways=false);
void print_neighbors(Node cur_node);
virtual ~Graph();
};

graph.cpp:

#include <iostream>
#include <vector>
#include <algorithm>
#include "graph.h"
#include <map>
Graph::Graph() {
std::cout << "graph. yup" << std::endl;
}

void Graph::add_neighbor(Node cur_node, Node new_node, bool both_ways) {
edge_map[cur_node].push_back(new_node);
if (both_ways) {
edge_map[new_node].push_back(cur_node);
}
}
void Graph::remove_neighbor(Node cur_node, Node del_node, bool both_ways) {
// TODO: convert vector values in map of <Node, vector<Node> > into maps, so this function can be easy and have sensible complexity
std::cout << "Not implemented yet." << std::endl;
// if (both_ways) {
//     edge_map[del_node].remove(cur_node);
// }
//this->edge_map[cur_node].erase(std::remove(this->edge_map[cur_node].begin(), this->edge_map[cur_node].end(), del_node), this->edge_map[cur_node].end());
}
void Graph::print_neighbors(Node cur_node) {
for (int i = 0; i < edge_map[cur_node].size(); i++) {
std::cout << edge_map[cur_node][i].data << " " << edge_map[cur_node][i].color << std::endl;
}
}
Graph::~Graph() {
std::cout << "ded graph :(" << std::endl;
}

任何一般的提示也很感激，我是绿色的地狱。

Answer 1

一个明显的大错误：

BFS函数不会为所有控制路径返回值，即使它应该返回std::vector<Node>。因此，您的程序具有未定义的行为。BFS返回的唯一路径是在while循环中的条件语句中：

if (cur_node.data == target.data) {
return cur_path;

但是，如果在运行外部while循环期间cur_node.data永远不等于target.data，从而触发未定义的行为(在您的情况下，是分段故障)，则不会返回。

在这里运行程序，使用触发输出语句"我有麻烦了！！"表明您正在导致未定义的行为。请注意，使用的编译器是Visual Studio 2015。

但是，为了显示未定义行为的后果，请注意，这里显示的gcc将在不打印消息的情况下崩溃。要让它打印消息，必须使用std::endl刷新缓冲区，才能看到此处显示的"麻烦！！"字符串。

考虑到所有这些，由于您必须返回一些东西，因此您必须决定在找不到节点的情况下返回什么。您可以返回一个std::vector<Node>()，但是BFS的调用者如何确定这个节点是否存在？我认为您需要理顺BFS的基本规则，即该函数的输出应该表示什么。

还有：

Node cur_node = cur_path[cur_path.size() - 1];

可以简单地为：

Node cur_node = cur_path.back();

Answer 2

(我没有足够的信誉添加评论)

据我所知可能会发生什么：

• q.pop调用std:：vector 的析构函数

• ~std:：vector摧毁每个节点

• 也许Node析构函数做了违法的事情？