C ++ - Ошибка сегментации при вставке значений в std :: map - PullRequest
Новая
       48

C ++ - Ошибка сегментации при вставке значений в std :: map

0 голосов
/ 15 марта 2019

Я пытаюсь создать синтаксический анализатор экземпляров графа в C ++, который принимает узлы графа в качестве входных данных и вставляет их в класс SmartGraph, определенный библиотекой LEMON.

Библиотека не позволяет мневставьте узлы с определенным идентификатором (насколько я видел в документации), поэтому я создал параллельную структуру для хранения отношений между идентификаторами узлов входного файла и идентификаторами узлов реального графа в моем коде (мог бы быть умный способ обойти это, но я не особо задумывался над этим, и это звучит нормально для меня, пока экземпляры не настолько массивны, что у меня заканчивается память, что почти невозможно).Для этого я использую std :: map, который содержит идентификатор входного файла в качестве ключа и идентификатор узла графа в качестве значения.

Эта ошибка std :: map в итерации № 239 циклаон читает строки из входного файла, если я просто запускаю программу, и до 2252, если я проверяю его с помощью Valgrind, что заставляет меня думать, что я, должно быть, делаю действительно большой надзор и теряю память где-то, но я не могу понять этоиз.Код выглядит следующим образом: 

#include <lemon/smart_graph.h>
#include <lemon/concepts/graph.h>
#include <iostream>
#include <fstream>
#include <map>
#include <string>

using std::cout;
using std::cin;
using std::getline;
using std::vector;
using std::string;
using std::stringstream;
using std::exception;
using std::ifstream;
using std::ios;
using std::map;

using lemon::SmartGraph;

map<int, int> instance_graph_ids;
map<int, int>::iterator it;
SmartGraph graph;
ifstream input_instance("instance.txt", ios::in);
string current_line;
while (getline (input_instance, current_line))
    {
        stringstream stream(current_line);
        string buffer;
        vector <int> separated_nodes;
        while(getline(stream, buffer, '\t')){
            separated_nodes.push_back(stoi(buffer));
        };
        for (int node : separated_nodes){
            it = instance_graph_ids.find(node);
            if (it == instance_graph_ids.end())
                {
                    int new_node_id;
                    SmartGraph::Node new_node = graph.addNode();
                    new_node_id = graph.id(new_node);
                    instance_graph_ids.insert({ node, new_node_id });
                };
        };
        auto first_node_iterator = instance_graph_ids.find(separated_nodes[0]);
        auto second_node_iterator = instance_graph_ids.find(separated_nodes[1]);
        graph.addEdge( graph.nodeFromId(first_node_iterator -> first),graph.nodeFromId(second_node_iterator -> second));
    }

Я знаю, что это довольно уродливо, но я пытаюсь заставить его работать до того, как начну ловить рыбу, так что терпите меня здесь.узел - это идентификатор узла во входном файле, представленный в виде целого числа.Сбой при попытке .insert () значения в instance_graph_ids, который является структурой карты, о которой я писал ранее.Я проверил это с помощью gdb, и node, и new_node_id являются обычными целыми числами, и существующие значения для instance_graph_ids тоже выглядят нормально.Попытка вызова find () или insert () в instance_graph_ids в gdb возвращает ошибку «Попытка получить адрес значения, не находящегося в памяти».Что мне здесь не хватает?

Отредактировано с полным примером.Пример экземпляра можно загрузить с https://snap.stanford.edu/data/oregon1_010331.txt.gz

1 Ответ

0 голосов
/ 15 марта 2019

Вы должны изменить first_node_iterator->first на first_node_iterator->second

graph.addEdge(graph.nodeFromId(first_node_iterator->second),
              graph.nodeFromId(second_node_iterator->second));

Например, при обработке первой строки «10000 4725»
используйте std :: vector для хранения узлов в SmartGraph,
в std :: vector есть только два элемента, когда graph.addEdge,
вы используете first_node_iterator-> first (значение 10000) в качестве нижнего индекса, который находится за пределами диапазона.

Модифицированный код: 

#include <lemon/smart_graph.h>
#include <lemon/concepts/graph.h>
#include <iostream>
#include <fstream>
#include <map>
#include <string>
#include <assert.h>

using std::cout;
using std::cin;
using std::getline;
using std::vector;
using std::string;
using std::stringstream;
using std::exception;
using std::ifstream;
using std::ios;
using std::map;

using lemon::SmartGraph;

int main()
{
    map<int, int> instance_graph_ids;
    map<int, int>::iterator it;
    SmartGraph graph;
    ifstream input_instance("instance.txt", ios::in);
    string current_line;

    while (getline (input_instance, current_line)) {
        stringstream stream(current_line);
        string buffer;
        vector <int> separated_nodes;

        while (getline(stream, buffer, '\t')) {
            separated_nodes.push_back(stoi(buffer));
        };

        for (int node : separated_nodes) {
            it = instance_graph_ids.find(node);

            if (it == instance_graph_ids.end()) {
                int new_node_id;
                SmartGraph::Node new_node = graph.addNode();
                new_node_id = graph.id(new_node);
                instance_graph_ids.insert({ node, new_node_id });
            };
        };

        auto first_node_iterator = instance_graph_ids.find(separated_nodes[0]);
        auto second_node_iterator = instance_graph_ids.find(separated_nodes[1]);

        assert(first_node_iterator->second < graph.nodeNum());
        graph.addEdge(graph.nodeFromId(first_node_iterator->second),
                      graph.nodeFromId(second_node_iterator->second));
    }

    return 0;
}
...