如何使用樹狀數據結構高效地實現unordered_map？

考慮unordered_map：如何使用樹狀數據結構高效地實現unordered_map？

template< 
    class Key, 
    class T, 
    class Hash = std::hash<Key>, 
    class KeyEqual = std::equal_to<Key>, 
    class Allocator = std::allocator< std::pair<const Key, T> > 
> class unordered_map;

我知道(a==b)比!(a<b) && !(b>a)快，但由於unordered_map不使用std::less<Key>在地圖上比較/存儲密鑰，我不知道如何才能在實現利潤按樹的數據結構最有效的方式來讀取/存儲在同一個桶中的不同密鑰。看起來，通過樹的任何實現都無法避免從Key轉換爲operator<()定義的KeyWrapper。

來源

2012-02-04 Martin

我不完全確定你在問什麼。你在談論在桶裏使用樹嗎？或者使用樹而不是哈希表？（後一種情況是std :: map是什麼）。但是你的一般問題：對於任何一種高效的樹，你需要一個比較運算符來適當地平衡樹。 – Joe 2012-02-04 15:04:53

是的，我正在談論一個桶內的樹（即張大樹） – Martin 2012-02-04 15:44:49

你不能在unordered_map內部使用樹，即使只是在一個桶內。 unordered_map的界面根本不允許。關鍵類型只需要平等可比，僅此而已。這就是爲什麼它被稱爲「無序」的地圖;因爲沒有特定的元素排序。要使用某種二叉樹，需要嚴格的弱排序，這不是必需的。

如果你想使用unordered_map的變體，你可以。但它不會是標準定義的unordered_map。

來源

2012-02-04 16:24:47

我在談論存儲/讀取元素的樹在同一個桶中崩潰 – Martin 2012-02-05 00:35:38

@Martin：夠公平的。看我的編輯。 – 2012-02-05 00:50:58

如何使用樹狀數據結構高效地實現unordered_map？

回答

相關問題