1

我有一个单一的深度优先搜索算法来遍历我的图，给定一个起始节点的迭代器。

文档摘要：

  • GraphIter是一个typedefGraph::iterator
  • Graph类扩展 map<string, Node>
  • start->second.edges()返回set<string>

如果 的大小为0start->second.edges() ，则此代码会导致分段错误：

（为简洁起见，我已经截断了不相关的部分，包括递归调用。）

错误代码

void Graph::dfs(GraphIter start)
{
    cout << "EDGES SIZE: " << start->second.edges().size() << endl;

    for (set<string>::iterator it = start->second.edges().begin();
          it != start->second.edges().end(); ++it)
    {
        GraphIter iter = this->find(*it);     // <--- SEGMENTATION FAULT
    }
}

现在看看当我拉start->second.edges()入一个局部变量时会发生什么：不再有段错误！

这是不生成段错误的代码：

好代码

void Graph::dfs(GraphIter start)
{
    set<string> edges = start->second.edges();       // <--- MAGIC TRICK
    cout << "EDGES SIZE: " << edges.size() << endl;

    for (set<string>::iterator it = edges.begin();
          it != edges.end(); ++it)
    {
        GraphIter iter = this->find(*it);
    }
}

所以区别在于，在好的代码中，当字符串集的大小（来自edges()方法）为0时，for在第二种情况下永远不会进入循环。但是在第一种情况下，for循环仍然至少执行一次，直到它意识到它不能取消引用it变量。

为什么这些不同？他们不访问相同的内存部分吗？

4

2 回答 2

6

因为按值edges()返回一个，并且将迭代器返回到不同的容器，因为每次调用都会返回一个新的。setstart->second.edges().begin()start->second.edges().end()edges()set

通过使用命名变量创建单个副本，您可以确保迭代器都来自同一个容器，并且您可以有效地迭代 from begin()to end()。

于 2012-07-28T18:02:18.120 回答
3

可能是按值start->second.edges()返回std::set<std::string>。这将使循环中的迭代器不兼容并导致未定义的行为。

你的“魔术”

set<string> edges = start->second.edges();

确保您在同一个容器“边缘”上进行迭代。

Node::edges()您可以通过引用返回来修复它：

const std::set<std::string>& edges() const { .... }
于 2012-07-28T18:01:52.353 回答