C++多圖迭代器失效

Question

我想弄清楚如何std::multimap迭代器的工作，因此我創建了一個簡單的例子，顯示我的問題的實質。如果取消註釋情況1，我希望迭代器指向第一個具有鍵1的元素，但實際上它會打印與鍵0相關的所有值（如沒有被擦除），並且有時會崩潰，可能是因爲迭代器無效。但是，如果取消註釋情況2，則鍵1的所有值都將被正確刪除。

是否有任何方法可以在擦除後知道multimap的下一個有效迭代器？ （例如std::vector.erase(...)回報之一）

std::multimap<int, int> m; 

for(int j=0; j<3; ++j) { 
    for(int i=0; i<5; ++i) { 
     m.insert(std::make_pair(j, i)); 
    } 
} 

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    ++it; 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
} 

Answer 1

問題

的原因。當你在一個元素調用m.erase(0)在您例如，it點與關鍵0 - 所以it無效。 m.erase(1)的作品，因爲當它第一次被調用時，it沒有指向具有密鑰1的元素，因此它不受影響。在以後的迭代中，沒有保留關鍵字1的元素，所以不會刪除任何元素，也不會影響迭代器。

解決方案

multimap沒有一個erase - 方法返回下一個有效的迭代器。一種替代方法是在刪除後調用it = m.upper_bound(deleted_key);。這是對數，但是，對於您的方案而言可能太慢（erase(x)和upper_bound會是兩次對數運算）。

假設你想刪除你的迭代器當前指向鍵，你可以做這樣的事情（否則，erase是好的，當然，未測試）：

std::multimap<int, int>::iterator interval_start = m.begin(); 
for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end(); ++it) { 
    if(interval_start->first < it->first) // new interval starts here 
     interval_start == it; 
    if((*it).second == 3) { 
     std::multimap<int, int>::iterator interval_end = it; 
     while((interval_end != m.end()) && (interval_end->first == it->first)) { 
      ++interval_end; // search for end of interval - O(n) 
     } 
     m.erase(interval_start, interval_end); // erase interval - amortized O(1) 
     it = interval_end; // set it to first iterator that was not erased 
     interval_start = interval_end; // remember start of new interval 
    } 
} 

它使用一個線性操作，其餘的都是不變的時間。如果你的地圖非常大，並且你只有少數項目的密鑰相同，這可能會更快。但是，如果你有同鍵許多項目，尋求區間的結束，可能是使用upper_bound（O(log n)，而不是O(n)搜索間隔結束時）做得更好。

Answer 2

先回答

std::multimap<int, int> m; 
// ^^^^^^^^ 
std::map<int, int>::iterator it=m.begin(); 
// ^^^ 

嗚嗚....

第二個答案，再：編輯問題

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    .... stuff .... 
     m.erase(1); // container mutation 
    .... stuff .... 
} 

要特別小心當你在迭代它時改變一個容器（任何容器），就像你一樣可能會使您依賴的迭代器失效。

所謂「基於節點的容器」（list，set，map ...）是最強大的容器WRT迭代器失效：他們只迭代器失效到刪除的元素（有沒有辦法讓這些迭代器不無效）。

在這種情況下，您應該檢查您即將刪除的元素實際上不是*it。

我不太清楚你正在嘗試怎樣處理你的循環。

Answer 3

當你擦除迭代器變得無效。而不是記住下一個元素，然後刪除：

std::map<int,int>::iterator next = m + 1; 
m.erase 
m = next; 

Answer 4

從看你的代碼，我認爲你++是造成問題的原因。您正在將其分配給可能已被刪除的地方。在if語句和測試之後將其移動到最後。像這樣：

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
    ++it; 
} 

Answer 5

（編輯）

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    ++it; 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
} 

除了it迭代器失效由於m.erase取決於multimap內容（已經覆蓋在另一個答案）可能會始終存在取消引用問題m.end()迭代器在您每次運行程序時執行if((*it).second == 3)循環的for循環的最後一次循環中。

我建議運行和調試調試版本。我幾乎可以肯定，每個理智的標準庫實現應該包含斷言來檢測end()解引用。

Answer 6

上面已經有一些人已經回答了你是一個玩火。

另外，我想你忘記了，多重映射是有序的地圖，讓您從最小的鍵從最大的迭代。因此，在第一種情況下，您在打印其中的一些文件後將其移除，但在第二種情況下，您在去之前將其移除。