[問題] C++ iter = map.earse(iter)的實作

[worcdlo ()]

版本: 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是透過什麼方式找到的？

想請問是否有比較詳細的解釋，
或是不知道去哪看這段程式碼？

謝謝大家

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.176.57.68 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1621517134.A.33C.html
→ nh60211as: 要直接看程式碼的話 GCC、Clang跟MSVC網路上都有
→ nh60211as: 得看
推 LPH66: 第一題是在問 Amortized 的概念, 它並不單看單一存取的時間
→ LPH66: 而是將許多次同樣操作所需要的時間進行平均
→ LPH66: Amortized (均攤) 常數時間代表, 雖然有可能單一操作會花
→ LPH66: 稍微多一點, 但其他時候的狀況的時間都很短
→ LPH66: 當考慮進各種狀況的比例及所需操作平攤之後
→ LPH66: 平均每個操作的時間仍然是常數, 那就說這是個均攤常數時間
→ oToToT: 2 的話只要平常多維護一個  linked list 就可以做到了吧?
→ LPH66: 第二題, 最簡單的做法是右→左→左→左→…到底
→ LPH66: 但這個方法在往上時要知道從哪裡來的, 所以也有另外維護
→ LPH66: 下一個元素所在指標的方式 (這可以在樹有調整時一起調整)
→ LPH66: 補充一點均攤分析的東西, 這種分析一般其實並不會真的去求
→ LPH66: 各種狀況的比例, 而是實際去看全部跑下來會有哪些操作
→ LPH66: 常用技巧是利用某個虛擬 token 擺在結構中表示未來可能操作
→ LPH66: 接著去證明每個地方只要某個數量的 token 的數目
→ LPH66: 這樣就代表不管狀況怎樣, 總操作數目不會超過一個已知數量
→ LPH66: 從這個已知數量即可推得均攤的時間複雜度