[分享] C++實作無序容器的方法

看板C_and_CPP (C/C++)作者GameHeven (Mark Williams)時間10年前 (2015/08/04 16:07)推噓2(2推 0噓 4→)

留言6則, 3人參與討論串1/1

此文是翻譯文章網頁版 http://gamehevenhome.blogspot.tw/2015/08/c.html C++不叫Hash Table，而是取了一個華麗名字叫無序容器(unordered associative container)。從2011開始c++提供了四種無序容器。 unordered_set , unordered_map (不可接受重複的元素) unordered_multiset , unordered_multimap (可接受重複的元素) 一個常用的方法是採用單向連結。在這種狀況下，每個桶子內部都是一個指標，指向一個單向序列。如果Hash演算法設計的好，每個鏈結都很短，插入跟刪除效率會接近O(1)。如圖所示， b1,b3只有一個元素，b2 有兩個元素。簡單方便，但是在C++不合用，因為規範要求容器必須可以遍歷，必須提供一個iterator，可以讓 iterator從頭到尾掃過一遍。那要如何從b1跳到b2？最明顯的方法是繼續掃描陣列，直到下一個有裝東西的桶子。但這不可用，因為陣列愈大，掃描愈慢。偏偏規範明定++i;效率要保持O(1)。為了符合規範，只好把所有元素都串在一起。我們來看一些Hash Table常用的結構。加上一個模仿Boost.MutiIndex的設計。先假設所有元素都不一樣。 (unordered_multiset , unordered_multimap以後再討論) 假設有N筆資料，陣列有B個桶子。 Dinkumware函式庫這是微軟Visual C++的實現方法。請看圖。 (請注意，桶子的順序不一定要跟元素順序一樣。圖片只是為了繪圖方便) 就跟你想的一樣，所有元素都串在一起。使用雙向連結。現在可以用iterator雙向訪問，代價是要多一個指標。好處是刪除元素非常容易。陣列裡面每個桶子都有兩個指標，指向鏈結的頭跟尾。插入元素的方法： 1.使用Hash先找到桶子。(常數時間) 2.元素如果重複要放棄插入，所以要掃描桶子裡面所有元素。(桶子大小線性時間) 3.新元素插入在鏈結的頭。(常數時間) 4.調整桶子裡面的兩個指標。(常數時間) 刪除元素的方法： 1.使用Hash先找到桶子。(常數時間) 2.刪除鏈結一個元素，調整前後指標。(常數時間) 3.調整桶子裡面的兩個指標。(常數時間) 4.操作效率是O(1)，記憶體消耗，每個元素要兩個指標，每個桶子也要兩個指標。 2N+2B 看起來很好，但其實Dinkumware的方法對於刪除元素，有一個嚴重的瑕疵。使用Hash先找到桶子。(常數時間) 如果Hash函式會丟出例外，今天刪除動作就失敗了。偏偏規範又講明刪除保證要成功，而且不可以丟出任何例外。所以Dinkumware方法其實不符合規範。 Boost.Unordered, libc++ , libstdec++ -V3函式庫 Boost.Unordered, libc++函式庫使用類似的資料結構。但設計成單向鏈結。所有元素用單向鏈結串在一起。因為刪除動作不可以拋出異常。刪除的時候不可以呼叫Hash函式，所以只好把Hash後的數字也存起來。因為是單向鏈結，為了刪除方便。桶子裡面的指標不是指向第一筆元素，而是第一筆的前一個。所以圖片中的b2指標指向前一個的b1。刪除元素的方法： 1.因為節點裡面已經有Hash值，可直接定位到桶子。(常數時間，不會丟出異常) 2.鏈結掃過一遍。(桶子大小線性時間) 3.刪除鏈結一個元素，調整前後指標。(常數時間) 4.調整桶子裡面的指標。(常數時間) 插入刪除都是O(1)。滿足規範。記憶消耗如下 2N+1B (我們假設Hash的數字，占用大小跟一個指標一樣) libstdec++ -V3提供了一個最佳化設計。如果Hash函式確定不會丟出異常。(有使用 nonexcpt)。函式庫會標記成fast模式。節點裡面不會儲存Hash數字。我覺得這設計有點危險。代碼裡面使用__is_fast_hash type來標記，基本型態通通設定為true。使用者自訂Hash函式預設是false，除非函式有用nonexcept，才會變成true。不考慮最佳化的特殊機制，2N+1B似乎已經是好的設計了。但事實上還有更好的方法，不需要再增加任何記憶體。簿記式的資料結構 Boost 1.56 Boost.MutiIndex裡面使用了一種全新的方式。雙向鏈結改用環狀的方式。定一個節點叫做X，下一個節點叫做Xn，前一個節點叫做Xp。環形鏈結代表 X = Xnp = Xpn 這個條件永遠成立。連結往前再往後一定會回到自己。連結往後再往前一定會回到自己。我們現在看一下完整的示意圖把陣列桶子也加進來，做一個小改動。如果元素是桶子的第一個元素，Xp改成指向桶子自己。可以導出一些規則。如果Xpn != X，代表X是這個桶子的第一個元素如果Xnp != X，代表X是這個桶子的最後一個元素下一個元素一定可以用Xn取得。前一個元素比較麻煩，如果是桶子的第一個元素，前一個元素就是Xpn，其他元素直接用 Xp存取即可。所有動作都是常數時間，我們可以把它還是當作環形鏈結。只是往前移動需要特殊處理。刪除元素的方法： 1.從雙向連結刪除元素，調整前後指標。(常數時間) 2.調整桶子裡面的指標。(常數時間) 刪除元素不需要把一個桶子都翻遍，就算遇到差勁的Hash演算法也沒差。記憶體不用增加。還是2N+1B。 -- 下列哪個最好笑？ http://gamehevenhome.blogspot.tw/ 1.馬英九維護台灣主權 6.徐旭東宣佈投資全面離開台灣 2.江宜樺愛護學生 7.連勝文表示我的一生充滿挫折 3.戴盛益建議沒錢跟父母借 8.慈濟善款全面救助窮人，絕無貪污 4.趙籐雄呼籲大家不要炒房 9.劉黎兒宣稱太陽能比核電便宜 5.施振榮談創新 10.台灣富人呼籲，證所稅/證交稅打趴經濟，應全面廢除 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.25.0.164 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1438675646.A.DD7.html