unordered_mapをツリーデータ構造で効率的に実装する方法は？

Question

は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からKeyWrapperへの変換を定義したoperator<()は、ツリーを使った実装では避けられないようです。

Answer 1

unordered_map内のツリーをバケット内で使用することはできません。 unordered_mapのインターフェイスは単にそれを許可しません。鍵のタイプは、同等以上のものでなければならない。それが「順序付けられていない」マップと呼ばれる理由です。要素の特定の順序付けがないためです。ある種のバイナリツリーを使用するには厳密な弱い順序が必要ですが、これは必須ではありません。

unordered_mapのバリエーションを使用することができます。しかし、それは標準によって定義されたunordered_mapではありません。