STLマップ（セット/マルチセット）をトラバースする最善の方法ですが、ループ中にエレメントを削除して戻すことができますか？

Question

この関数はDFS検索アルゴリズムを実装するのに非常に便利だと思います。

たとえば、{A-> B}、{B-> C}、{A-> C}、{C-> A}}のグラフを横切るエッジを知っていて、 A-> C-> A-> B

このような問題を解決するには、どのノード/エッジが存在するかを示すデータ構造を持つことでDSPで解決しますvistied/used。

私は通常ちょうどノードをシミュレートするためにそれを保存して、値を変更（および背面変更）するために、ベクターを使用し

が例について

を使用している：

string now = "A"; 
vector<string> nexts = get_all_edges_starting_from(now); 
for (int i=0; i<nexts.size(); i++) { 
    string next = nexts[i]; 
    nexts[i] == "visited"; // assume no node named "visited" 
    if (go_recursive_and_find_path_cover_all_edges()) 
    { 
     results.push_back(now); // some global or whatever variable to store the result 
     return true; 
    } 
    nexts[i] = next; // abandon the "visit" so the recursion can use node/edge next time 
} 
return false; 

それは見つける動作しますが、efficentではありません使用マップまたはセット/マルチセットと比較されます。しかし、ループ中に要素が読み込まれて戻されている間は、map/set/multisetをどのようにトラバースするかわかりません。

例えば、失敗した例は次のようになります。私は削除し、ループ内の要素を追加することにより、要素のメモリ構造を台無しにするので

string now = "A"; 
multiset<string> nexts = get_all_edges_starting_from(now); 
multiset<string>::iterator it = nexts.begin(); 
for (it != nexts.end()) { 
    string next = *(it); 
    nexts.erase(next); // visited 
    if (go_recursive_and_find_path_cover_all_edges()) 
    { 
     results.push_back(now); // some global or whatever variable to store the result 
     return true; 
    } 
    nexts.insert(next); // abandon the "visit" 
    it++; 
} 
return false; 

この例は失敗します。

一般的に、現在のトラバース位置の前に「新しい」要素を追加する場合を考えると、動作が定義されていない可能性があることを知っています。しかし、DFSの例では、通常は単に要素を削除し、「前に削除される」要素を追加します。

簡単な方法はありますか？

Answer 1

まず、マルチマップがベクトルよりも優れていることは明らかではありません。なぜなら、メモリの局所性が非常に悪いためです。両方の実装方法を試して比較してみてください。関心の

for (auto it = nexts.begin(); it != nexts.end();) 
{ 
    string next = *it; 
    auto it = nexts.erase(it); 
    if (...) { ... } 
    nexts.insert(it, std::move(next)); 
} 

ポイント：

• 値で削除してはいけませんが、反復子によって

  次に、あなたのループは、私たちが解決することができ、いくつかの基礎の非効率性が含まれています。

• 要素がどこにあるかを既に知っているので、ヒントを挿入します。
• コピーを必要としないため、文字列を移動挿入します。
• C++では、extractを使用しての文字列をに移動することもできます。