原始需求：求某電車到D公里范圍內(nèi)的地圖顯示

轉(zhuǎn)換需求：

　　第一步：由某個點P到距離恰好大于等于D公里的所有的路的集合求出來

      第二步：所有的路外的點組成polygon 然后渲染

第一步的詳細算法A*：

        1.我們有一個空的集合C用來放符合條件的R，和某個點P（簡單起見，假設(shè)P在路上，用R表示路）

        1.1 R有屬性id，權(quán)重weight（也就是路到A點的當前路徑的距離）

        2. R根據(jù)graph模塊找到和他直接相連的幾條路Rx1…Rxn ，Rx1…Rxn權(quán)重weight小于D公里時放入集合C。在放入集合之前

           查看C中和Rx1…Rxn id是否有相同的Rx，如果有并且新的權(quán)重大的話就更新權(quán)重，否則放棄更新。 

        3. 在集合C中找到一個權(quán)重weight最小的Rmin

        4. 如果Rmin 的權(quán)重weight 小于D 重復(fù)2，3步。

           否則退出循環(huán)，表示目前的集合C已經(jīng)滿足情況。

本文重點-集合C需要的特性：

　　1.根據(jù)id 快速查找id相同的Rx1…Rxn 

　　2.插入新的Rx1…Rxn 

　　3.根據(jù)權(quán)重weight找到Rmin

　　4.刪除Rmin

　　也就是說集合C需要快速查找，插入，刪除，有序。看到這個需求同事用了2版數(shù)據(jù)結(jié)構(gòu)

　　第一版：二叉堆版的優(yōu)先級隊列priority_queue， 性能7s，方案錯誤

      優(yōu)點O(logN)的插入和刪除Rmin，缺點O(N)的id查找，無法刪除飛最小值

　　第二版：有序鏈表版的優(yōu)先級隊列，性能5s

　　優(yōu)點O(1)的刪除Rmin，缺點O(N)的id查找，O(N)的插入

　　由LRU cache的list+map啟發(fā)：

　　第三版：list無序存放R，map1存放{id, node指針}, multimap存放{weight, node指針}，性能1s

　　　　　　優(yōu)點：O(logN)的map1查找，更新，multimap的刪除Rmin，插入

　　　　　　缺點：這里的 weight是一個浮點型數(shù)，所以weight不能通過計算后查找比如（1.0+2.0）去find3.0。

  　　　　　　　　 這里還得明白map的find函數(shù)是通過(key >= lower_bound)&&(lower_bound >= key)實現(xiàn)的。