※ 引述《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)