請問C++的std ::地圖和std ::設置擦除複製值，從而迭代器失效

Question

我考慮去除的二叉搜索樹的實現。我知道std :: map和std :: set通常是作爲一個RBTree實現的。但無論如何，如果它是一些BST，那麼當擦除/移除具有2個孩子的節點時，我們通常將其與其後繼者（或前驅者）交換。許多教科書顯示這只是複製繼任者的關鍵和價值。但是這個副本不透明。例如，如果值是另一個容器，我有未完成的迭代器，然後刪除一些OTHER鍵，現在可以使迭代器無效，我必須對我沒有明確更改的容器進行迭代。我們可以將後繼節點重新鏈接到應該刪除節點的樹中，而不是複製鍵值。這將維護節點的狀態。

假設我有地圖矢量的：

std::map<int, vector<int> > mymap; 
// Add root 
mymap.insert(make_pair(2, vector<int>())); 
// Add left child 
mymap.insert(make_pair(1, vector<int>())); 
// Add right child 
mymap.insert(make_pair(3, vector<int>())); 
mymap[3].push_back(10); 
// I get an iterator to the vector stored in the node with key=3 
vector<int>::iterator it = mymap[3].begin(); 

// I now remove element 2 from the map. 
mymap.erase(2); 

// If the successor's (i.e. 3's) key,value were *copied* to 2's node 
// and then 3's node was deleted this would invalid iterators 
vector<int>::iterator it2 = mymap[3].begin(); 

// These could/should be different if remove copied the successor 
cout << &*it << " " << &*it2 << endl; 

當然包含到位2的節點和2的節點中刪除的3可能只是「重新連接」樹內的節點。這將保持關鍵值的正確狀態。

我編寫了這個測試的情況下，它似乎重新鏈接，而不是複製。這種行爲是在哪裏定義的？同樣，如果我有一個矢量向量（即vector>，並且我在其中一個「內部」向量中持有一個迭代器，但由於插入另一個向量而導致外部向量調整大小，那麼我的迭代器甚至是無效的雖然我沒有在技術上修改那個內部向量，那麼無效化的「傳遞性」屬性在某處是拼寫出來還是「顯而易見」/「隱含」，而我只是對遊戲速度很慢？

Answer 1

擦除操作基於節點的容器（地圖，集合，列表）僅無效迭代器和引用到已刪除的元素，但沒有任何其他的迭代器。

在按值刪除，這通常是直接的，但是當你用迭代器擦除時，這在循環遍歷整個容器的常見情況下需要謹慎。即：

for (auto it = my_set.begin(); it != my_set.end();) 
{ 
    if (should_we_erase(it)) { my_set.erase(it++); } 
    else      { ++it;    } 
} 

密切關注我們如何確保不使用迭代器之後，我們刪除了！在擦除分支，我們首先設置it到一個新的有效的迭代一個進一步經由後遞增，然後在原來的迭代器擦除（這是後增量表達的值）。或者，我們可以這樣寫爲it = my_set.erase(it);，因爲erase操作返回下一個（有效）迭代器。一個非常常見的新手錯誤是把++it int循環頭，然後結束對無效迭代器執行算術。

相比之下，向量和雙端隊列中有更多的操作無效了很多迭代器和引用。

迭代器和引用的失效是有據可查的標準庫規範的一部分，任何自我尊重的文檔或教程將非常清楚，當有什麼東西是如何失效。