Понимание ошибки сегментации в ссылках, когда выскакивает из очереди

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(); бит, но почему? Это потому, что векторы по своей сути ссылаются? При необходимости я могу добавить больше своего кода, просто пытаясь инкапсулировать проблему под рукой.

EDIT: вот главный() водитель:

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, который представляет собой карту с структурами узлов в качестве ключей и векторов структур узла как значения для представления списка смежности графа. Конструктор выводит «график». yup 'бит, пожалуйста, дайте мне знать, если вам нужна дополнительная информация

EDIT 2: Я собираюсь включить остальную часть для полноты, извините за многословие, но я пытаюсь понять, почему это происходит.

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; 

Однако нет возврата не будет сделано, если cur_node.data никогда не равен target.data во время выполнения внешней while петли, таким образом, вызывая неопределенное поведение (в вашем случае ошибка сегментации).

Выполнение вашей программы here, using the triggering output statement, "I'm in trouble!!" показывает, что вы вызываете неопределенное поведение. Обратите внимание, что используемым компилятором является Visual Studio 2015.

Но для того, чтобы показать последствия неопределенного поведения, обратите внимание, что gccas shown here просто потерпит крах, не распечатывая сообщение. Чтобы распечатать это сообщение, буфер необходимо сбросить с помощью std::endl, чтобы увидеть «проблему!». строка as seen here.

Учитывая все это, так как вам нужно что-то вернуть, вы должны решить, что вернуть в случае, если узел не найден. Вы можете вернуть 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 уничтожает каждый узел

• Может быть, деструктор узла делает что-то незаконное?