如何使用树状数据结构高效地实现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？

回答

相关问题