作者worcdlo ()
看板C_and_CPP
標題[問題] C++ iter = map.earse(iter)的實作
時間Thu May 20 21:25:31 2021
版本: 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://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1621517134.A.33C.html
1F：→ nh60211as: 要直接看程式碼的話 GCC、Clang跟MSVC網路上都有 05/20 22:23
2F：→ nh60211as: 得看 05/20 22:23
3F：推 LPH66: 第一題是在問 Amortized 的概念, 它並不單看單一存取的時間 05/21 02:39
4F：→ LPH66: 而是將許多次同樣操作所需要的時間進行平均 05/21 02:39
5F：→ LPH66: Amortized (均攤) 常數時間代表, 雖然有可能單一操作會花 05/21 02:40
6F：→ LPH66: 稍微多一點, 但其他時候的狀況的時間都很短 05/21 02:41
7F：→ LPH66: 當考慮進各種狀況的比例及所需操作平攤之後 05/21 02:41
8F：→ LPH66: 平均每個操作的時間仍然是常數, 那就說這是個均攤常數時間 05/21 02:42
9F：→ oToToT: 2 的話只要平常多維護一個 linked list 就可以做到了吧? 05/21 02:44
10F：→ LPH66: 第二題, 最簡單的做法是右→左→左→左→…到底 05/21 02:45
11F：→ LPH66: 但這個方法在往上時要知道從哪裡來的, 所以也有另外維護 05/21 02:46
12F：→ LPH66: 下一個元素所在指標的方式 (這可以在樹有調整時一起調整) 05/21 02:46
13F：→ LPH66: 補充一點均攤分析的東西, 這種分析一般其實並不會真的去求 05/21 02:48
14F：→ LPH66: 各種狀況的比例, 而是實際去看全部跑下來會有哪些操作 05/21 02:48
15F：→ LPH66: 常用技巧是利用某個虛擬 token 擺在結構中表示未來可能操作 05/21 02:49
16F：→ LPH66: 接著去證明每個地方只要某個數量的 token 的數目 05/21 02:50
17F：→ LPH66: 這樣就代表不管狀況怎樣, 總操作數目不會超過一個已知數量 05/21 02:50
18F：→ LPH66: 從這個已知數量即可推得均攤的時間複雜度 05/21 02:51