1

開始ノードへのイテレータを指定して、グラフをトラバースするために単一の深さ優先探索アルゴリズムを実装しています。

ドキュメントの概要：

  • GraphIterのtypedefですGraph::iterator
  • Graphクラス拡張 map<string, Node>
  • start->second.edges()戻り値set<string>

のサイズが0の場合、このコードはセグメンテーション違反を引き起こしstart->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);
    }
}

したがって、違いは、適切なコードでは、 （メソッドからの）文字列のセットのサイズが0の場合、2番目のケースではループに入ることがないということです。ただし、最初のケースでは、変数を逆参照できないことがわかるまで、ループは少なくとも1回は実行されます。edges()forforit

なぜこれらは違うのですか？彼らは記憶の同じ部分にアクセスしませんか？

4

2 に答える 2

6

は値でaを返しedges()、を呼び出すたびに新しいものが返されるため、イテレータを別のコンテナに返します。setstart->second.edges().begin()start->second.edges().end()edges()set

名前付き変数を使用して単一のコピーを作成することにより、イテレーターがすべて同じコンテナーからのものであり、からbegin()へのイテレーターを有効に実行できるようになりますend()。

于 2012-07-28T18:02:18.120 に答える
3

by値を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 に答える