Re: [問題] 煩請高手建議一個結構

看板C_and_CPP (C/C++)作者ledia (下班後才下棋)時間16年前 (2009/07/02 12:07)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串3/4 (看更多)

※ 引述《DRLai (蘇打)》之銘言： : ※ 引述《DRLai (蘇打)》之銘言： : 我目前宣告一個結構如下 : multimap<int,string> : 因為map可以自動排序 : 讓我可以快速的找到最小值 : 但是現在有個問題 : 我需要去erase一些資料，而資料是以string為主 : 除了linear搜尋以外有什麼比較好得方式可以達到需求 : 同時又可以保持自動sorting的好處呢不好意思我對 STL containers 能怎麼修改不太熟所以我就用基本的 data structure 解釋一下我猜測 heap + map 所做的事情像是這樣 hash min heap <string, HeapNode> pair<int,string> 王小華 ──────→ 92,"王小華" 王小明 ┐ / \ 王小毛 ┼───→ 95,"王小毛" 99,"王小明" │ ↑ └───────────────┘ * heap 的排序是以第一個 int 為準 * 如果取最小值只需要分數, 那 heap 只要存 int 就好 1. function AddName (name, score) a. 把 <score,name> 加入 heap 並回傳 heap node pointer b. 把 <name,HeapNode> 加入 hash 裡面 1. function GetMin (): a. 從 heap 拿出最小值 2. function EraseByName (name): a. 從 hash 得到 heap node b. 從 hash 中除去 name c. 從 heap 中出去 a. 中得到的 heap node (註, 2.c 可從 heap 的基本操作 decrease key + extract min 完成) 其中 heap 實作可能要注意一點小細節比如說資料存的位置不能更動, 以免 hash 內指向錯誤的 node 如果能用已存在的 container 來實作會更好以上供你參考 -- 有時候，遺忘，是令人快樂的。什麼時候？當然是有人傷了你的心的時候。　存心傷你的那個人，固然是故意和你過不去，但是被傷了心而耿耿於懷的你　，卻是和自己過不去了。所以，記性不好的人，通常會是比較快樂的人，也　是比較不容易被擊倒的人。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.49 ※ 編輯: ledia 來自: 140.112.30.49 (07/02 12:10)