刪除元素，而迭代同一矢量

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 
*/ 

我不明白「add v to 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 = uc.erase(it2); 

通過迭代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() can invalidate iterators指向向量。

這會使所有迭代器和對位置（或第一個）及其後續元素的引用無效。

您需要添加的erase結果迭代器（它只是一個被擦除後指向元素），並使用該結果。請注意，在

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

迭代器it無效uc.erase，因此後續++和使用後可能導致運行錯誤。

同樣，即使您將擦除結果分配給it2，該調用也可以使it無效，但不會更改。

最好的辦法是在每個erase()之後從頭開始重新開始算法，或者如果您可以修改它以便它可以從erase返回的迭代器繼續，那麼可以獲得一些效率。

Answer 3

而是與iterator類型的工作，存儲索引到vector。當你需要一個迭代器 - 也許是傳入erase - 你可以說begin() + myIndex來生成一個迭代器。

這也使得循環看起來更熟悉的，例如

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

Answer 4

你已經有了運行時錯誤，因爲it2 = uc.erase(it2);返回最後刪除的元素之後的迭代器，所以在for(it2=uc.begin();it2<uc.end();it2++)的it2++超越了最後一個元素。

試着改變你如果：

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