Неожиданное повреждение кучи происходит в функции с обработкой исключений

Question

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

Мой класс графа имеет функцию с таким заголовком:

bool directed_edge(const Key& parent, const Key& child) throw(std::invalid_argument);

... и другая функция с этим заголовком:

std::tuple<bool, bool, bool> add_directed_edge(const Key& parent, const Key& child);

directed_edge выдает исключение, если либо parent, либо child отсутствует на текущем графике. add_directed_edge работает, вызывая directed_edge и обрабатывает исключение, фактически добавляя узлы в список и затем , соединяя их с ребром.

Если я использую directed_edge для создания своих ребер, то никакого искажения данных нет вообще - списки смежности узлов графа содержат ожидаемые данные. Однако, если я использую add_directed_edge, данные будут повреждены. Это странно, поскольку add_directed_edge на самом деле мало что делает, кроме вызова directed_edge и обработки любых потенциальных ошибок, которые он может выдать. Это наводит меня на мысль, что это как-то связано с обработкой исключений внутри функции, но я не совсем уверен.

Вот реализация для обеих функций:

template<typename Key>
bool graph<Key>::directed_edge(const Key& parent, const Key& child) throw(std::invalid_argument)
{
    node* parentItor = find_node(parent);
    node* childItor = find_node(child);

    // Return true if the edge was added
    return parentItor->directed_edge(childItor);
}

template<typename Key>
std::tuple<bool, bool, bool>
graph<Key>::add_directed_edge(const Key& parent, const Key& child)
{
    bool parentAdded;
    bool childAdded;
    bool edgeAdded;

    // Try to add the directed edge.  Exception thrown if either doesn't exist
    try {
        edgeAdded = directed_edge(parent, child);
        return std::make_tuple(false, false, edgeAdded);
    }
    catch(std::invalid_argument& invArg) {
        // Add parent and child, and assign to see if they needed to be added
        parentAdded = add(parent);
        childAdded = add(child);

        // Add the directed edge
        edgeAdded = directed_edge(parent, child);
        return std::make_tuple(parentAdded, childAdded, edgeAdded);
    }
}

Я понимаю, что обе эти функции вызывают много других функций, поэтому, если вы хотите увидеть больше деталей реализации, вы можете оставить комментарий, и я должен скоро вернуться к вам

Я провел три теста с некоторыми основными данными. В первом тесте я вручную добавил узлы 0-9, затем использовал directed_edge, чтобы установить несколько соединений. Результат таков:

0 -> 1, 3
1 -> 2, 4, 6, 7
2 -> 3, 8, 9
3 -> 
4 -> 6, 7, 5
5 -> 
6 -> 7
7 -> 
8 -> 
9 -> 

Во втором тесте я не добавлял вручную узлы на график. Я неоднократно вызывал add_directed_edge, поскольку эта функция предназначена для добавления узлов каждый раз, когда ей дается ключ к несуществующему узлу. Результат таков:

0 -> 284985109, 976560249
1 -> 1752440936, 116, 17504392, 7
3 -> 
2 -> 1768366181, 8, 9
4 -> 6, 7, 5
6 -> 7
7 -> 
8 -> 
9 -> 
5 -> 

Кроме того, чтобы быть точным, я провел третий тест, в котором я вручную добавил все узлы и затем вызвал add_directed_edge, чтобы установить соединения на уже существующих узлах. Интересно, что это дало ожидаемые результаты:

0 -> 1, 3
1 -> 2, 4, 6, 7
2 -> 3, 8, 9
3 -> 
4 -> 6, 7, 5
5 -> 
6 -> 7
7 -> 
8 -> 
9 -> 

Answer 1

Ваша гипотеза о том, что проблема связана с обработкой исключений в add_directed_edge, правильна, но неверна.Фактическая проблема заключается в том, что добавление узлов графа приводит к изменению размера вектора узлов графа, что делает недействительными указатели узлов графа в списках смежности каждого графа

В классе графа есть переменная-член vector<graph_node<Key>> nodesи каждый узел графа имеет переменную-член vector<graph_node<Key>*> adjacencyList.Всякий раз, когда вы делаете направленное ребро между двумя узлами, вы делаете что-то вроде: nodes[i].adjacencyList.push_back(&nodes[j]).Это заставит узел i указывать на узел j

Это проблема.Ссылка &nodes[j] будет считаться недействительной в любое время, когда вектор nodes необходимо изменить размер, поскольку во время изменения размера данные nodes[j] копируются в совершенно другое место в памяти.

На этой веб-странице есть больше информации о контейнерах - вы должны внимательно прочитать раздел с заголовком "Недопустимость итераторов".Видишь, что я вижу?Для вектора все итераторы (т.е. все указатели) становятся недействительными, если размер внутреннего массива изменяется.

Если вы настаиваете на списках смежности, имеющих указатели на узлы, выследует использовать контейнер STL с более стабильными итераторами, такими как список или карта

Answer 2

Если вы можете запустить свой код с чем-то вроде Valgrind или gcc / clang address-sanitizer , они, как правило, являются хорошими способами выявления причины подобных проблем.