關於使迭代器無效

Question

STL容器存在迭代器在容器更改時可能失效的問題。容器是否可以通過添加一個調用has_changed（）來通知它已經改變了？

在某些操作之前查詢empty（）很常見。如果容器對會影響迭代器的操作（例如insert（）或erase（））設置布爾值，那麼在重用迭代器之前可以查詢has_changed（）。

瘋了嗎？

編輯感謝您的一堆好回覆和思考。我希望我能授予不止一個獲勝者。

Answer 1

在Java中工作的（近似的）快速失敗迭代器的工作原理是容器在每次更改時都增加一個計數器。迭代器在創建時複製此計數器，並在每次通過容器更改容器時增加它。如果迭代器檢測到不匹配，則會拋出異常。

C++有令人興奮的屬性，一些操作使容器上的迭代器無效，但其他操作無效。例如，假設已經保留足夠的空間vector::insert使迭代器在插入點之後失效，但不在之前。

另一個難題是list::remove。這將使所有迭代器都有效，除了被刪除的迭代器，和它的所有副本。

正如你可以想象的那樣，要精確跟蹤這一點非常困難。實踐中發生的事情是，您的實現可能會提供調試選項，其中迭代器將盡最大努力檢測它們是否有效。但是，這可能取決於他們目前是否「有效」的實施細節，而不是標準是否保證他們仍然有效。

在C++中執行類似於Java中的「版本號」的操作是可能的，但它會給出錯誤的迭代器錯誤，它們看起來無效但實際上是有效的。

Answer 2

有點瘋了，如果有意的話。

我認爲這個問題的主要原因是容器如何知道它何時「不變」？換句話說，一些東西被抹去，並且「已更改」標誌被設置。由於重新恢復正常或穩定狀態，重置旗子的事件是什麼？它實際上是迭代器而不是處於無效狀態的容器。

我認爲爲了在所有迭代器中工作，需要比現在更多，更智能，並且更像操作容器的觀察者。容器可以發送一個事件給它已經改變的註冊迭代器，並且他們可以在嘗試操作之前檢查它們自己的狀態。但即使有這麼多漏洞，它可能會導致比你想要解決的更大的混亂。

Answer 3

這將是低效的，因爲容器需要A）提供另一個數據字段並且B）相應地更新它。然而，STL被認爲是爲了做不可能的事情，並將效率與抽象結合起來。 （它成功了，我要補充。）

如果你需要保持引用到不斷變化的容器，要麼使用一個不壞的迭代器（std::list，std::set）或保留指數爲std::vector。

Answer 4

迭代器失效的規則已經足夠清晰，如果您按規則付費，則不應要求詢問容器何時失效。

此外，迭代器並不總是同時失效。從矢量中移除一個元素只會使該元素和後一個元素無效。但是指向矢量開始的迭代器仍然有效。

在列表中，迭代器通常只在它們指向的特定節點被銷燬時纔會失效。

所以你不能問容器你的迭代器是否有效。

通用標準庫實現可以選擇啓用與請求類似的附加運行時檢查，儘管實現更復雜（它必須是爲了正確）並且會損害性能。

Answer 5

這在技術上是可行的，並且MSVC實現了提供類似功能的'checked iterators'（http://msdn.microsoft.com/en-us/library/aa985965.aspx）。儘管當迭代器失效時你沒有得到通知，並且你不能直接查詢狀態（我知道的），但是拋出異常並且/或者調用invalid_parameter，這取決於構建的配置。

但是，它絕對是非標準的，並且顯着提高了性能。這對調試很有用。

Answer 6

容器是否可以通過添加一個調用has_changed（）來宣告它已經改變了？

我想，是的，它可以實施。這是一個非常簡單的嘗試（不那麼優雅，但仍然）：

bool has_changed(std::vector<int> &v) 
{ 
    static std::map<void*, size_t> has_changed_info; 
    void *ptr = &v; 
    std::map<void*, size_t>::iterator it = has_changed_info.find(ptr); 
    if (it == has_changed_info.end()) 
    { 
     has_changed_info[ptr] = v.capacity(); 
     return false; 
    } 
    if (it->second != v.capacity()) 
    { 
     it->second = v.capacity(); 
     return true; 
    } 
    return false; 
} 

測試代碼：

int main() { 
     std::vector<int> v; 
     has_changed(v); 
     for (int i = 0 ; i < 100 ; ++i) 
     { 
      v.push_back(i); 
      if (has_changed(v)) 
        cout << "changed at " << i << endl; 
     }  
     return 0; 
} 

輸出（GCC-4.3.4）：

changed when inserting i = 0 
changed when inserting i = 1 
changed when inserting i = 2 
changed when inserting i = 4 
changed when inserting i = 8 
changed when inserting i = 16 
changed when inserting i = 32 
changed when inserting i = 64 

在線演示：http://www.ideone.com/QmO5q