版本: C++ 11
參考網站：https://www.cplusplus.com/reference/map/map/erase/
問題(Question)：
我們都知道map是用紅黑樹實踐的，
但關於map.erase()，我這邊有兩個問題想請教各位高手：
1. 假設map.erase的引數是疊代器，代表我已經事先知道特定的node位置，
但紅黑樹已經指到node，經過erase之後，還是要執行「重新平衡」的動作，
這樣是否真的如同網站所寫，erase(iter)是逼近常數時間？
2. 另外 iter2 = map.erase(iter)，iter2應該是指到iter的下一個數字，
但這是一顆紅黑樹，當我們把iter所指到的節點刪掉後，
紅黑樹的節點分布應該會有若干變化，很好奇iter2是透過什麼方式找到的？
想請問是否有比較詳細的解釋，
或是不知道去哪看這段程式碼？
謝謝大家

要直接看程式碼的話 GCC、Clang跟MSVC網路上都有得看

第一題是在問 Amortized 的概念, 它並不單看單一存取的時間而是將許多次同樣操作所需要的時間進行平均Amortized (均攤) 常數時間代表, 雖然有可能單一操作會花稍微多一點, 但其他時候的狀況的時間都很短當考慮進各種狀況的比例及所需操作平攤之後平均每個操作的時間仍然是常數, 那就說這是個均攤常數時間

2 的話只要平常多維護一個 linked list 就可以做到了吧?

第二題, 最簡單的做法是右→左→左→左→…到底但這個方法在往上時要知道從哪裡來的, 所以也有另外維護下一個元素所在指標的方式 (這可以在樹有調整時一起調整)補充一點均攤分析的東西, 這種分析一般其實並不會真的去求各種狀況的比例, 而是實際去看全部跑下來會有哪些操作常用技巧是利用某個虛擬 token 擺在結構中表示未來可能操作接著去證明每個地方只要某個數量的 token 的數目這樣就代表不管狀況怎樣, 總操作數目不會超過一個已知數量從這個已知數量即可推得均攤的時間複雜度