出乎意料的堆损坏在功能中发生在异常处理中

Question

我正在编程C 中的有向图。如果我使用使用异常处理的某个函数初始化了我的图节点的邻接节点列表中的图节点指针会损坏，但是如果我使用类似的功能使用不使用异常处理的函数来初始化列表。p>我的图形类具有此标题：

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);
    }
}

我意识到，这两个功能都在调用其他功能的 lot ，因此，如果您想查看更多的实现详细信息，您可以发表评论，我应该尽快与您联系

我使用了一些基本数据进行了三个测试。在第一个测试中，我手动添加节点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 -> 

另外，要彻底，我进行了A 第三测试，我在其中手动添加了所有节点，然后称为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

如果您能够使用诸如Valgrind或GCC/Clang地址 - 销售器之类的代码运行代码，则通常是识别此类问题的好方法。

Answer 2

您的假设是，问题是add_directed_edge中的例外处理方法是充分猜测，但不正确。实际问题是，添加图节点是导致图中的图形节点进行调整大小，从而使图形节点指针无效。

图形类具有成员变量vector<graph_node<Key>> nodes，每个图节点具有成员变量vector<graph_node<Key>*> adjacencyList。每当您在两个节点之间建立针对的边缘时，您都会执行类似：nodes[i].adjacencyList.push_back(&nodes[j])。这将使节点i指向节点j

这是一个问题。在矢量nodes需要调整大小时，参考&nodes[j]将无效，因为在调整大小期间，将nodes[j]的数据复制到内存中完全不同的位置。

此网页有有关容器的更多信息 - 您应该仔细阅读标题"迭代器无效"部分。看看我看到了什么？对于矢量，如果调整了内部数组的大小，则所有迭代器(即所有指针(无效。

如果您坚持使用 pointers 的邻接列表，则应使用具有更稳定迭代器的STL容器，例如列表或地图