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

看板C_and_CPP (C/C++)作者時間2年前 (2021/05/20 21:25), 編輯推噓1(1017)
留言18則, 3人參與, 2年前最新討論串1/1
版本: 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

05/20 22:23, 2年前 , 1F
要直接看程式碼的話 GCC、Clang跟MSVC網路上都有
05/20 22:23, 1F

05/20 22:23, 2年前 , 2F
得看
05/20 22:23, 2F

05/21 02:39, 2年前 , 3F
第一題是在問 Amortized 的概念, 它並不單看單一存取的時間
05/21 02:39, 3F

05/21 02:39, 2年前 , 4F
而是將許多次同樣操作所需要的時間進行平均
05/21 02:39, 4F

05/21 02:40, 2年前 , 5F
Amortized (均攤) 常數時間代表, 雖然有可能單一操作會花
05/21 02:40, 5F

05/21 02:41, 2年前 , 6F
稍微多一點, 但其他時候的狀況的時間都很短
05/21 02:41, 6F

05/21 02:41, 2年前 , 7F
當考慮進各種狀況的比例及所需操作平攤之後
05/21 02:41, 7F

05/21 02:42, 2年前 , 8F
平均每個操作的時間仍然是常數, 那就說這是個均攤常數時間
05/21 02:42, 8F

05/21 02:44, 2年前 , 9F
2 的話只要平常多維護一個 linked list 就可以做到了吧?
05/21 02:44, 9F

05/21 02:45, 2年前 , 10F
第二題, 最簡單的做法是右→左→左→左→…到底
05/21 02:45, 10F

05/21 02:46, 2年前 , 11F
但這個方法在往上時要知道從哪裡來的, 所以也有另外維護
05/21 02:46, 11F

05/21 02:46, 2年前 , 12F
下一個元素所在指標的方式 (這可以在樹有調整時一起調整)
05/21 02:46, 12F

05/21 02:48, 2年前 , 13F
補充一點均攤分析的東西, 這種分析一般其實並不會真的去求
05/21 02:48, 13F

05/21 02:48, 2年前 , 14F
各種狀況的比例, 而是實際去看全部跑下來會有哪些操作
05/21 02:48, 14F

05/21 02:49, 2年前 , 15F
常用技巧是利用某個虛擬 token 擺在結構中表示未來可能操作
05/21 02:49, 15F

05/21 02:50, 2年前 , 16F
接著去證明每個地方只要某個數量的 token 的數目
05/21 02:50, 16F

05/21 02:50, 2年前 , 17F
這樣就代表不管狀況怎樣, 總操作數目不會超過一個已知數量
05/21 02:50, 17F

05/21 02:51, 2年前 , 18F
從這個已知數量即可推得均攤的時間複雜度
05/21 02:51, 18F
文章代碼(AID): #1WfcDECy (C_and_CPP)
文章代碼(AID): #1WfcDECy (C_and_CPP)