消去要素

Question

可能性の重複同じベクトルを反復しながら：
Erasing from a std::vector while doing a for each?

を私は、このアルゴリズムに従って着色頂点を実装しようとしています。

/* 
Given G=(V,E): 
Compute Degree(v) for all v in V. 
Set uncolored = V sorted in decreasing order of Degree(v). 
set currentColor = 0. 
while there are uncolored nodes: 
    set A=first element of uncolored 
    remove A from uncolored 
    set Color(A) = currentColor 
    set coloredWithCurrent = {A} 
    for each v in uncolored: 
     if v is not adjacent to anything in coloredWithCurrent: 
     set Color(v)=currentColor. 
     add v to currentColor. 
     remove v from uncolored. 
     end if 
    end for 
    currentColor = currentColor + 1. 
end while 
*/ 

「vをcurrentColorに追加する」とは分かりません。しかし、私は、それはcurrentColorをvにしようとしていることを意味します。したがって、 "set"は何ですか？とにかく問題は、反復処理中にベクトルの要素を消去することです。これがコードです。

vector<struct Uncolored> uc; 
    vector<struct Colored> c; 

    int currentColor = 0; 
    struct Colored A; 
    struct Colored B; 

    vector<struct Uncolored>::iterator it; 
    vector<struct Uncolored>::iterator it2; 
    vector<struct Colored>::iterator it3; 

    for(it=uc.begin();it<uc.end();it++){ 

     A.id = (*it).id;   
     uc.erase(uc.begin()); 
     A.color = currentColor; 
     c.push_back(A); 

     for(it2=uc.begin();it2<uc.end();it2++) { 
      it3=c.begin(); 
      while(it3 != c.end()) { 
       if(adjacencyMatris[(*it2).id][(*it3).id] == 0) { 
        B.id = (*it2).id;  
        it2 = uc.erase(it2); 
        B.color = currentColor; 
        c.push_back(B); 
       } 
       it3++; 
      } 
     } 
     currentColor = currentColor + 1; 
    } 

私はit2 = uc.erase(it2);行はすでに一般的に使用されていますが、実行時エラーが発生すると考えています。

Answer 1

：イテレータit2が指し示す要素をベクターから除去さ

it2 = uc.erase(it2); 

、要素はit2を無効にそのギャップを埋めるために、メモリ内にシフトされます。 it2は新しい値を取得し、削除された要素またはベクトルの末尾の後の最初の要素（削除された要素が最後の要素だった場合）をポイントするようになりました。つまり、要素を消去した後には、it2を先送りしないでください。提案remove-erase idiomに代わるものは、単純なトリックです：

for(it2 = uc.begin(); it2 != uc.end();) 
{ 
    ... 
    if(...) 
    { 
     it2 = uc.erase(it2); 
    } 
    else 
    { 
     ++it2; 
    } 
    ... 
} 

あなたはこのhereについての詳細を読むことができます。

編集： あなたのコメントについて、あなたは要素が消去されているか否かの情報を渡すためにフラグを使用することができ、あなたは内側のループから抜け出すとき、あなたはそれをチェックすることができます。

for(it2=uc.begin(); it2 != uc.end();) 
{ 
    bool bErased = false; 

    for(it3 = c.begin(); it3 != c.end(); ++it3) 
    { 
     if(adjacencyMatris[(*it2).id][(*it3).id] == 0) 
     { 
     B.id = (*it2).id; 
     it2 = uc.erase(it2); 
     bErased = true; 
     B.color = currentColor; 
     c.push_back(B); 
     break; 
     } 
    } 

    if(!bErased) 
     ++it2; 
} 

ucから要素を消去した後、内側のループを解除する必要があります。外部ループの次の反復では、有効なイテレータを介してucの次の要素にアクセスできます。

Answer 2

vector::erase()invalidate iteratorsを指す。

これは、すべてのイテレータと、位置（または最初の）とその後続の要素への参照を無効にします。

eraseの結果をイテレータに追加する必要があります（削除された直後の要素を指します）。 uc.erase、これ以降の++および使用はランタイムエラーになる場合があります後

for(it=uc.begin();it<uc.end();++it){ 
    A.id = (*it).id;   
    uc.erase(uc.begin()); 
    ... 
} 

にイテレータitが有効でないことに注意してください。

同様に、消去結果をit2に割り当てても、変更されていないitが無効になります。

各erase()の後にアルゴリズムを最初から再起動するか、またはeraseによって返されたイテレータから継続できるように変更することができます。これを実行して効率を上げてください。ラインで

Answer 3

iteratorタイプを使用する代わりに、vectorにインデックスを格納します。イテレータを必要とするとき - おそらくeraseに渡す - あなたはイテレータを生成するためにbegin() + myIndexと言うことができます。

これにより、ループの外観もわかりやすくなります。

for(ind=0; ind < uc.size(); ind++) { 

Answer 4

for(it2=uc.begin();it2<uc.end();it2++)でit2++は最後の要素を超えてit2 = uc.erase(it2);は、最後の削除の要素以下のイテレータを返すので、あなたは、ランタイムエラーを持っています。

はであれば、あなたを変更してみてください：

if(adjacencyMatris[(*it2).id][(*it3).id] == 0) { 
    B.id = (*it2).id;  
    uc.erase(it2); 
    B.color = currentColor; 
    c.push_back(B); 
    break; 
}