HashTable実装を使用したHashMapの実装

Question

私はinsert, remove, find, existsのような関数を含むハッシュテーブルの実装を持っています。

ハッシュテーブルを使用して、私はハッシュマップを実装したいと思っていました。

私は、キーと値だけを含む単純なペアクラスを作成することを念頭に置いていました。 キーが等価であることを考慮すると、operator=がオーバーロードされます。 また、ハッシュ関数は入力としてペアオブジェクトを取得し、キー部分だけを考慮してハッシュを返します。

したがって、私はhashtable<key>のようなものになるハッシュマップの内部にhashtable<pair>を持つでしょう。なぜなら、それはキー部分だけを考慮に入れ、値のメンバーに沿って運ぶだけだからです。

しかし、問題が発生しました。

たとえば、指定されたキーを持つペアがハッシュマップに存在するかどうかをチェックするexists関数を実装したかったのです。それはキーを取り込み、そのキーがマップ内にあるかどうかをチェックします。これは、ハッシュテーブルの存在を使用して実装されます。 しかし、hashtable::existsは入力としてペアのタイプを取ります。

だから私は、私はちょっと好きではないこれらの選択肢を持っていました。

• ハッシュテーブルの機能のみを使用するように

• 初期化されていない部分（reinterpret_castは（&キー）等）対オブジェクトにキーオブジェクトをキャスト鍵とペアのオブジェクトを作成し、その値のままこの状況では、ペアの重要な部分です。

最初のものは不必要なコピーを作成します。 2番目のキーのアドレスがペアのオブジェクトアドレスと等しくない場合があります。私は、キーのアドレスは、私が

(&pair.key) - (&pair) 

を計算して、私はペアとしてのキーを渡すために適切なキャストを行うことができることを使用してすることができます考慮して確実に知ることができると信じていますが。

代替案の候補はありますか？

Answer 1

あなたはgoogle::dense_hash_maphere（私はstd::unordered_mapのようなSTLのコードよりも読みやすいと考えているので、私は例としてこれを取る）のようなハッシュマップの既存の実装を見れば、あなたはハッシュマップは、単にテンプレートハッシュではないことがわかります表。言い換えれば

、それはのように実装されていません。

template <class T> 
struct hash_table { ... }; 

template <class Key, class Value> 
using hash_map = hash_table<std::pair<Key, Value>>; 

...しかし、のような：

template <class Value, class Key> 
struct hash_table { ... }; 

template <class Key, class Value> 
struct hash_map 
{ 
    using ht = hash_table<std::pair<Key, Value>, Key>; 
    ht _ht; 
}; 

次に、このクラスがあるようhash_table<Value, Key>であなたは、insert(const Value&)もfind(const Key&)を持つことができますすべてのタイプを認識しています。

非常に簡単に実装することができますhash_set。ロジック全体がhash_tableクラスにあり、hash_mapとhash_setは、呼び出しを転送するだけで、APIのクライアントにはいくつかの美容的な処理を行います。